Design a Client-Specific Rate Limiter

Problem Design a per-client rate limiter: given a maximum of R requests allowed from a client within a window of T seconds, enforce the limit, and decide what happens when more requests arrive than the system can process.

Functional requirements

• Track and enforce request counts per client, not globally.
• Reject or queue requests beyond R in any T-second window.
• Behave correctly under bursty traffic, including at window boundaries.
• Return a clear rejection (429 + Retry-After) rather than timing out.
• Share limiter state across all gateway instances so a client can't multiply their quota by hitting different nodes.

Non-functional requirements

• ~100k requests/sec across ~10M distinct clients; ~200 gateway instances.
• Limiter decision must add < 2 ms at p99 — it runs before every request.
• Memory: a sliding-window log storing every timestamp costs R entries per active client; at R=1000 and 1M active clients that is ~1B entries, so approximation is required at the top end.
• Overload behaviour: bounded queues only. Unbounded buffering converts a load spike into an OOM and a full outage.
• Fail-open on limiter-store unavailability, with a local fallback limit.

Key components

• Sliding window log: per client, a sorted structure of recent request timestamps. On each request, evict entries older than now-T, count the remainder, and admit if < R. Binary search over the sorted log gives the in-window count in O(log n).
• Memory-efficient alternatives: sliding window counter (blend previous + current bucket) or token bucket (a token count and a last-refill timestamp — two numbers per client instead of R timestamps).
• Shared state: Redis sorted sets keyed by client_id (ZREMRANGEBYSCORE to evict, ZCARD to count, ZADD to record) so all gateway instances share one view per client.
• Sharding limiter state by client_id across Redis nodes.
• Overload path: a bounded queue with backpressure and load shedding past a threshold.

Deep dives / trade-offs

• Log vs counter vs bucket: the sliding window log is exact and handles bursts precisely, but its memory is O(R) per client and eviction work grows with the burst. The token bucket needs O(1) state and naturally permits a burst up to bucket size — usually what you actually want, since real clients are bursty and a strictly smooth limit rejects legitimate traffic. The sliding window counter approximates the log at O(1) memory; quantify the error at the boundary.
• Handling overload — the crux of this problem: buffering excess requests in a queue and processing asynchronously sounds generous, but it trades a fast rejection for unbounded latency and memory. A client waiting 30 s in a queue has already timed out; you did the work and nobody received it. Bounded queues plus early 429s are almost always correct. Discuss when queuing IS right (a fragile downstream you must protect, and requests that stay valuable when delayed) versus when to shed immediately.
• Distributed consistency: 200 gateways each enforcing R locally means an effective limit of 200R. Redis makes it global but adds a network hop to every request and becomes a throughput bottleneck and SPOF. Shard by client_id so one Redis node owns one client's state; consider a local pre-filter for clients nowhere near their limit.
• Atomicity: evict-count-admit-record is a read-modify-write. Concurrent requests from the same client will both pass a naive check — this needs a Lua script or an atomic primitive.
• Fail-open vs fail-closed: if the limiter store dies, do you admit everything (and let a spike kill the backend) or reject everything (and take a full outage from a cache failure)? State the choice; local fallback limits are the usual compromise.