Design a Rate Limiter

A rate limiter caps how many requests a client may make in a window (“100 requests/minute”). It’s a deceptively rich design problem: the single-machine version is a few lines, but doing it correctly across a fleet of servers forces you to confront shared state, latency, and accuracy trade-offs. (For the concept, see Rate Limiting; here we design one.)

1. Requirements

Functional

• Limit requests per client (by user ID, API key, or IP) to N per time window.
• Return 429 Too Many Requests (with a Retry-After header) when exceeded.
• Limits must apply across the whole fleet, not per server.

Non-functional

• Low latency — the limiter is on every request’s hot path, so it must add single-digit milliseconds at most.
• Highly available — if the limiter is down, fail open (allow) or closed (block)? A deliberate choice (see below).
• Memory-efficient at scale (millions of clients).

2. Estimation

Say 1M active clients and 10k requests/second globally. The limiter does at least one read+write of counter state per request → ~10k ops/s against the counter store, and must hold ~1M small counters. That comfortably fits an in-memory store like Redis — which points us at the architecture.

3. Algorithm choice

The heart of the design. Each trades accuracy for simplicity/cost:

Algorithm	Idea	Pro	Con
Fixed window	Count per clock-aligned window	Trivial, 1 counter	Burst at edges: 2× limit across a boundary
Sliding window log	Store timestamp of every request	Exact	Memory-heavy (one entry per request)
Sliding window counter	Weighted blend of current + previous window	Smooth, cheap	Slight approximation
Token bucket	Tokens refill at a steady rate; each request spends one	Allows controlled bursts	Two values to track (tokens, last-refill)
Leaky bucket	Requests queue and drain at a fixed rate	Smooths output	Adds queuing latency

Token bucket is the common default: it permits short bursts (good UX) while enforcing a long-run rate, and needs just (tokens, last_refill_time) per client.

tokens refill at R/sec, capacity = B
request arrives → refill tokens based on elapsed time → if tokens ≥ 1: allow, tokens-- ; else: 429

4. The distributed problem

A per-server counter is wrong: with 10 servers each allowing 100/min, a client gets 1,000/min. The limit must live in shared state.

   request ──► any app server ──► [ Redis: client:123 → {tokens, ts} ] ──► allow / 429
                 (stateless)          single source of truth, fleet-wide

The update must be atomic — read-modify-write across many servers races. Use Redis with an atomic Lua script (or INCR + EXPIRE for window counters) so the check-and-decrement happens in one indivisible operation.

The race that lets clients over-spend

Naïve GET then SET lets two servers both read “1 token left” and both allow the request. The fix is atomicity: do the whole “refill, check, decrement” in a single Redis Lua script (or INCR-based window). Without atomicity your limiter silently leaks capacity under concurrency.

5. Deeper trade-offs

• Where to enforce: an API gateway is the natural home — limit once at the edge before requests fan into the system.
• Latency vs accuracy: a strictly-correct global counter means a network hop to Redis per request. For extreme throughput, allow a small local token cache per server (approximate, occasionally over-permits) and reconcile with the central store — trading perfect accuracy for speed.
• Fail open or closed? If Redis is unreachable, failing open (allow) preserves availability but removes protection; failing closed (block) protects the backend but causes an outage. Most user-facing APIs fail open for availability; abuse-sensitive endpoints fail closed.

By the numbers — the fixed-window edge burst

“Fixed window” resets the counter at a clock boundary, which lets a client legally double its rate by straddling that boundary. Picture a 100-requests/minute limit:

limit = 100 per 60s window
11:00:59  → client fires 100 requests   (window 11:00 counts 100 → all allowed)
11:01:00  → client fires 100 more       (window 11:01 counts 100 → all allowed)
result:   200 requests in ~1 second — 2× the intended rate, zero rejections

Neither window ever exceeded 100, so the limiter is “correct” — yet a downstream service just took a 2× burst. Sliding-window and token-bucket algorithms exist precisely to close this gap; the price they pay is tracking more state per client (a weighted previous window, or tokens + last_refill_time). That is the page’s accuracy vs cost tension in one example.

The thread

What does this buy us, and what does it cost? A rate limiter buys protection (against overload, abuse, runaway clients) and fairness — at the cost of latency on every request and a shared-state dependency. The central design tension is accuracy vs speed: perfectly global counting is a hop away on every call; cheap local approximations are fast but leak a little capacity. Pick the point that matches whether you’re protecting a fragile backend or just shaping traffic.

Check your understanding

1. Why is a per-server counter incorrect, and where must the limit’s state live?
2. Why is token bucket often preferred over fixed window?
3. Describe the race condition in a naïve GET-then-SET limiter and how atomicity fixes it.
4. Explain the accuracy-vs-latency trade-off of a per-server local token cache.
5. When would you fail open vs fail closed if the counter store is unreachable?

Show answers

1. A per-server counter lets each box allow N independently, so with 10 servers each permitting 100/min a client actually gets 1,000/min — the limit must apply across the whole fleet. So the counter state lives in shared state (a single source of truth like Redis) that every stateless app server consults.
2. Token bucket permits short, controlled bursts (good UX) while still enforcing the long-run rate, and needs only (tokens, last_refill_time) per client. Fixed window is simpler but suffers the edge-burst flaw: a client can fire the full limit at the end of one window and again at the start of the next, allowing up to 2× the limit across a boundary.
3. With a naïve GET-then-SET, two servers can both read “1 token left,” both decide there’s capacity, and both allow the request — a read-modify-write race that lets clients over-spend. The fix is atomicity: do the whole “refill, check, decrement” in one indivisible operation, e.g. a Redis Lua script (or an INCR-based window), so no two servers interleave.
4. A local token cache per server avoids a network hop to Redis on every request, cutting latency for extreme throughput. The cost is accuracy: the local view is approximate and can occasionally over-permit before it reconciles with the central store — the page’s central tension, accuracy vs speed.
5. Fail open (allow) when availability matters most — most user-facing APIs prefer to keep serving traffic if the limiter is down, accepting temporarily-removed protection. Fail closed (block) for abuse-sensitive endpoints, where protecting the backend is worth causing an outage rather than letting an unprotected flood through.