Design a Rate Limiter

The most common opener in system design interviews, because it is small enough to finish and still forces you to talk about distributed state, atomicity and trade-offs.

Requirements

Functional

• Limit a client to N requests per time window, keyed by user, API key or IP.
• Different limits per endpoint or tier (free vs paid).
• Reject over-limit requests with 429 Too Many Requests and a Retry-After header.

Non-functional

• Low latency — this sits in the request path, so a few milliseconds at most.
• Highly available. A rate limiter that is down must not take the API down with it.
• Accurate enough. Perfect accuracy is expensive; agree the tolerance early.

Scale to assume: 1M users, 10K requests/second peak, limits like 100 requests/minute.

Where it goes

Say "at the gateway" and move on. The interesting part is the algorithm and the state.

The algorithms

Fixed window counter. A counter per key per window, incremented and compared.

key: user:123:2024-01-15T10:30    value: 47

Trivial and memory-cheap, but it allows a burst of 2N at the boundary: 100 requests at

10:30:59 and 100 more at 10:31:00 is 200 in one second, both within limits. Name that flaw

— it is what the follow-up is about.

Sliding window log. Store a timestamp per request in a sorted set, drop entries older

than the window, count what is left. Exact, and O(N) memory per key — too expensive at high limits.

Sliding window counter. The practical compromise: keep the current and previous fixed

windows and interpolate.

count = current_window_count
      + previous_window_count × (overlap fraction of the previous window)

Approximate, but with fixed-window memory cost and no boundary burst. This is what most production limiters actually do.

Token bucket. A bucket of capacity B refills at R tokens/second; each request takes

one. Empty bucket means reject.

tokens = min(B, tokens + (now - last_refill) × R)
if tokens >= 1: tokens -= 1 → allow
else: reject

Two properties make this the usual recommendation: it allows bursts up to B while holding the long-run average at R, which matches how real clients behave, and it needs only two numbers per key. Leaky bucket is the variant that smooths output to a constant rate instead of allowing bursts — right for protecting a downstream that cannot absorb spikes.

Distributed state

The core problem: with many API servers, a per-process counter lets a client with 10 servers get 10× the limit. State must be shared, and Redis is the standard answer — in-memory, single-threaded, with atomic primitives and TTLs.

The critical detail is atomicity. Read-then-write is a race:

Server A: GET count → 99
Server B: GET count → 99
Server A: SET 100  ✓ allowed
Server B: SET 100  ✓ allowed    ← 101 requests went through

Two correct fixes:

1. INCR + EXPIRE — INCR is atomic and returns the new value.
   Set the TTL only when INCR returns 1, or the window never expires.

2. A Lua script — Redis runs it atomically, so a token-bucket
   read-compute-write is a single operation. This is the general answer.

Cost: one network round trip per request. At scale, that is the thing to optimise, and the optimisation is local pre-allocation — each server leases a slice of the budget from Redis and enforces locally, syncing periodically. Slightly less accurate, dramatically fewer round trips.

Availability

If Redis is unreachable, you choose:

• Fail open — allow everything. Keeps the API up, removes protection exactly when a

traffic spike may have caused the failure.

• Fail closed — reject everything. Protects the backend, turns a limiter outage into a

full outage.

Most systems fail open with a local in-memory fallback limit, and alert loudly. Stating the choice and its consequence is what the question is testing.

Response

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1705315860
Retry-After: 23

Returning the headers on successful responses too lets well-behaved clients slow down before being rejected, which is worth a sentence.

Follow-ups to expect

• Boundary burst — answered by sliding window or token bucket.
• Different limits per tier — the limit is config keyed by plan, not code.
• Distributed accuracy vs latency — the local-lease trade-off.
• Rate limiting by IP behind a proxy or NAT — one IP can be a whole office; prefer

authenticated identity where available, and treat IP as a coarse backstop.

• Hot keys — one abusive tenant hammering a single Redis key; shard the key or use a

local pre-check.

• Retry storms — clients that retry immediately on 429 make it worse; require

exponential backoff with jitter.

Track this problem on the System Design sheet.