Rate Limiter Library

Prompt

"Write a rate limiter as a library that a service can embed. The API is roughly allow(client_id) -> bool. Each client gets N requests per second. Design the classes, then implement the core."

Clarifying questions

• In-process or distributed? In-process, one instance per server. Sharing limits across servers is a follow-up, and the design should make the boundary visible.
• What does "N per second" mean exactly? Ask whether bursts are allowed. Token bucket allows a burst up to the bucket size then a steady rate; a strict sliding window allows at most N in any one-second interval. The interviewer usually says "either, but tell me the difference."
• How many distinct keys? Up to millions of client ids over a day, tens of thousands active at any moment. So per-key state must be bounded.
• Different limits per key? Yes, a default plus overrides. Rules are configured, not hardcoded.
• What happens on rejection? Return false; optionally report how long until the next request would pass, for a Retry-After header.
• Thread safety? Required. Many request threads call allow concurrently.

Requirements

Functional

• allow(key) returns true if the request is within the key's limit and records it; false otherwise.
• Per-key limits with a default and overrides; limits are rate plus burst.
• Optional retry_after(key) in seconds.
• Pluggable algorithm: token bucket and sliding-window counter at minimum.

Non-functional

• O(1) time and O(1) memory per key per call. No per-request log for the sliding window at these volumes.
• Correct under concurrency: two threads calling allow for the same key must not both pass when only one token remains.
• Deterministic in tests: time must be injectable.
• Bounded memory: idle keys must be evicted.

Numbers

• 10^4 active keys x roughly 100 bytes of state = 1 MB. Fine. A sliding-window log storing every timestamp for a key at 1,000 requests per second would be 1,000 floats per key, 10^7 floats across active keys, about 80 MB and growing with the limit. That arithmetic is why the counter approximation exists.
• Per-call cost must stay in the low microseconds; a global lock at 10^5 calls per second across 32 threads becomes the bottleneck, which motivates per-key locking.