Design a Rate Limiter

Step 1: Clarify the requirements

Confirm the limit shape before designing anything: is it N requests per fixed window, or a rolling window? Per user, per IP, or per API key? What happens to a rejected request: hard reject with 429, or queue it? Ask whether this needs to work on a single machine or across a fleet; the answer changes the whole design.

Step 2: Trace an example

Limit = 3 requests per 10-second window, per userId:

1. `allowRequest("u1")` at t=0s -> true (count: 1)
2. `allowRequest("u1")` at t=2s -> true (count: 2)
3. `allowRequest("u1")` at t=4s -> true (count: 3)
4. `allowRequest("u1")` at t=5s -> false (limit hit)
5. `allowRequest("u1")` at t=11s -> true (new window)

Step 3: Brute force

Store every request timestamp per user in a list. On each call, drop timestamps older than `windowSeconds`, then check if the remaining count is under the limit. Correct, but an unbounded list per user is memory-heavy at scale. This is the sliding window log approach, and it is worth naming even though you will optimize past it.

Step 4: Compare the standard algorithms

Interviewers expect you to know the trade-offs, not just one implementation:

• **Fixed window counter**: one counter per `(userId, windowStart)`, reset when the window rolls over. O(1) memory per user, but bursts at window boundaries can let through up to 2x the limit (N requests at the end of one window, N more at the start of the next).
• **Sliding window log**: store exact timestamps (Step 3). Fully accurate, but O(N) memory per user where N is the limit.
• **Sliding window counter**: blend the current and previous fixed windows, weighted by how far into the current window you are. Fixes the boundary-burst problem with O(1) memory and an approximation most systems accept.
• **Token bucket**: a bucket refills at a fixed rate up to a capacity; each request consumes a token. Naturally allows short bursts up to the bucket size while enforcing a long-run average rate. This is the most common answer in practice because it separates "burst allowance" from "sustained rate" as two tunable numbers.
• **Leaking bucket**: same idea inverted; requests queue into a bucket that drains at a fixed rate, smoothing bursts into constant output. Good when you need steady downstream load, not just a cap.

For this problem, lead with **token bucket** for a single-machine implementation, and be ready to name the other four when asked "what else could you use."

Step 5: Design the optimized approach

Per userId, track `{tokens, lastRefillTime}`. On each `allowRequest` call: compute elapsed time since `lastRefillTime`, add `elapsed * refillRate` tokens (capped at bucket capacity), update `lastRefillTime`, then check if at least one token is available. If so, consume it and return true; otherwise return false. A hash map from userId to bucket state gives O(1) average lookup and update.

Step 6: Implement and test

Lazy-refill on read (as above) avoids needing a background timer thread. Test: burst up to capacity succeeds, the next request immediately after fails, and after waiting one refill interval a request succeeds again. Also test a brand-new userId (lazily create its bucket on first call).

Step 7: Scale, complexity, and follow-ups

Time and space are O(1) per request with the token bucket + hash map design (space O(U) across U active users).

**Scaling across multiple servers** (the first follow-up above): an in-process hash map does not work once traffic is load-balanced across machines, because each server only sees its own slice of a user's requests. Move the counter state to a shared store; Redis is the standard choice, using `INCR` + `EXPIRE` for fixed/sliding window counters, or a Lua script for atomic token-bucket updates. At very high throughput, shard by userId (consistent hashing) so each user's counter always lands on the same Redis node.

**Where to place it**: in-process is fast but inaccurate across a fleet; a dedicated rate-limiter microservice is accurate but adds a network hop; enforcing it at the API gateway is the usual production answer, since it gives one choke point and no per-service duplication.

**Token bucket vs. sliding window** (the second follow-up): token bucket is simpler and cheaper, and its burst tolerance is often a feature (real clients are bursty). Sliding window counter is preferred when the SLA promises a hard, precise cap with no boundary leakage. Mention both, then justify your pick based on the stated requirements from Step 1.

**Fail-open vs. fail-closed**: if the Redis-backed limiter itself becomes unavailable, decide up front whether to allow all requests through (fail-open: protects availability, risks overload) or block them (fail-closed: protects downstream systems, risks false rejections). State your choice and why; there is no universally correct answer.

Related reading

• System design interview framework: the same requirements-first approach applied to full systems.
• LRU Cache: another O(1) hash-map-backed design question with the same clarify-then-optimize shape.