Hot-Key Rate Limiter with TTL

Problem

You’re on-call for a fintech payments API handling 5M daily active users and bursty traffic during payroll days. A small set of “hot” API keys can suddenly generate huge request spikes, causing CPU thrash and P99 latency regressions. To protect the system, you’re asked to implement an in-memory rate limiter that efficiently rejects requests when a key exceeds its allowed request rate.

Design a function that processes a stream of request events and returns whether each request should be allowed or blocked.

Formal Task

Implement:

• rate_limit(events, limit, window_seconds, ttl_seconds) -> list[bool]

Where:

• events is a list of (timestamp, api_key) pairs sorted by non-decreasing timestamp.
• A request is allowed iff the number of allowed requests for that api_key in the time interval (timestamp - window_seconds, timestamp] is < limit.
• If allowed, the request counts toward the key’s future rate.
• TTL cleanup: If an api_key has had no requests for ttl_seconds, its state must be eligible for removal to prevent memory growth.

Return a boolean list aligned with events indicating allow/block.

Constraints

• 1 <= len(events) <= 2 * 10^5
• 0 <= timestamp <= 10^9
• api_key is a non-empty string, total characters across all keys <= 2 * 10^5
• 1 <= limit <= 10^5
• 1 <= window_seconds <= 10^9
• 1 <= ttl_seconds <= 10^9

Notes / Clarifications

1. events are sorted by time; multiple events may share the same timestamp.
2. Only allowed requests count toward the rate limit.
3. TTL cleanup is about memory safety: you must not keep per-key state forever.