The Runtime Theory
mediumApplicationDSA#system-design#rate-limiting#distributed-systems

Design a rate limiter

Checks whether you can pick an algorithm for its failure modes rather than its name, and whether you understand where the check lives so it survives the traffic it is supposed to stop.

The Runtime Theory Team2 min readasked at google · stripe · uber · netflix

A rate limiter is a decision made on every request — allow or reject — with a budget of well under a millisecond added latency, because it is a tax on every request, not a feature of one. The interview is about picking an algorithm for its failure modes and placing the check where it can survive the traffic it exists to stop.

Requirements

Limit 100 req/s per API key (plus per-IP caps for anonymous traffic), 1M keys, ~500k req/s total at peak. Latency budget: <1ms added. The limiting must not error — a limiter that falls over during a burst is worse than no limiter.

Algorithms and what they actually cost

  • Fixed window: one Redis key per client per window, INCR + EXPIRE inside one Lua script to close the check-then-act race. Memory: 1M keys ≈ tens of MB. Known failure: the boundary burst — limit requests at 59.999s plus limit more at 0.001s is 2x the limit in two seconds.
  • Sliding log: exact, but memory proportional to traffic, not clients — one client at 1k req/s against a 60s window holds 60k timestamps (~4MB in a sorted set). Use it only when exactness is a product requirement (billing, compliance).
  • Sliding window counter: current + previous window counters, linearly interpolated. Two keys per client, constant memory, no boundary burst. The pragmatic default.
  • Token bucket: burst b, refill r, one integer per client. The gateway default because burst semantics match mobile clients reconnecting.

Where the check lives

Decision 1: gateway vs service. The gateway is the single choke point — everything passes through it, including the traffic that would kill the service. Decision 2: central vs local. Central Redis is exact but adds a round trip (~0.5ms in-region, 1–2ms across AZs); local per-node counters add zero latency but drift by the number of nodes. Real deployments do both: strict central limits for authenticated keys, local approximation for anonymous traffic. If Redis dies: fail open (allow) with degraded local counters, because denying everything is a self-inflicted outage.

Data model and protocol

Key = {client}:{window}; the Lua script returns allow/reject. Reject with 429 plus Retry-After — clients that honor it stop hammering, which is the entire point.

Bottlenecks

Redis single instance does ~100k–1M ops/s; 500k req/s means sharding the keyspace by client hash. The limiter must handle more traffic than the service it protects — that is why it lives at the edge. Clock skew between nodes breaks window boundaries. And the limit's units matter: limiting at the wrong layer (per-node instead of global, or per-IP instead of per-key) makes the math quietly wrong.

This answer walks

Follow-ups they'll push on

  1. 01The limiter must stay fast during a DDoS — where does the check physically live, and what happens to the limiter's own capacity?
  2. 02A user hits your API from three regions. How do you enforce one global limit without a global round trip?
  3. 03What headers do you return on rejection, and why does Retry-After matter to the clients?
  4. 04How do you test that the limiter itself is never the bottleneck?

More interviews in this topic

medium · system designDesign a leaderboard for a million playershard · system designDesign an idempotent payment APIhard · system designDesign a web crawler

One dispatch a week

The trace behind each question, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.