The 100 problems, solved / Infrastructure and platform / 059 · Design a distributed rate limiter

Design a distributed rate limiter

Allow N requests per key per second across many servers without a central bottleneck.

Problem 059 of 100Infrastructure and platformL51 Nov 2026
Concepts this design leans on
  • Rate limiting — Token buckets, sliding windows, and enforcing them across many servers.
  • Key-value stores — The simplest database: a hash map spread over machines.
  • Consistent hashing — Assigning keys to machines so adding one machine moves only a few keys.
  • Clocks and ordering — Why machines disagree about time, and how to order events anyway.
  • Caching strategies — Read-through, write-through, write-back, TTLs and invalidation.

01The design, in the six-step framework

1. Requirements

Functional

  • Limit requests per key (API key, user, IP) to a configured rate, for example 1,000 per minute, with rules per endpoint and per tier.
  • Return a clear rejection (HTTP 429) with headers saying how long to wait; never silently drop.
  • Rules change without a deploy; a new key is limited within a second of its first request.
  • Work in front of many services as a shared component, and as a library inside a service.
  • Out of scope: billing and quotas over days (that is the quota limiter), abuse scoring.

Non-functional

  • Scale: 5 million requests a second across 2,000 gateway servers, 50 million distinct keys active in a minute.
  • Latency: the decision adds under 1 ms p99 to a request.
  • Accuracy: within 5 percent of the configured rate under normal operation; never block a key that is under its limit by more than a brief burst.
  • Availability: if the limiter's store is down, requests must still be served (fail open) unless a rule says otherwise.
Back of the envelope

5 × 106 req/s ÷ 2,000 servers = 2,500 req/s per server; a central store hit per request would need 5 × 106 ops/s

50 × 106 keys × 64 bytes of counter state = 3.2 GB: fits in one memory tier, sharded for throughput

The central store cannot take one round trip per request at 1 ms; most decisions must be made locally with periodic synchronisation.

2. Core entities

  • Rule: rule id, match (endpoint pattern, tier, key type), limit (count, window), burst allowance, action on exceed, fail-open flag.
  • Bucket: key, rule id, tokens available, last refill time; the token-bucket state.
  • Decision: key, rule, allowed or denied, retry-after; emitted for metrics.

3. API

  • POST /check with key, endpoint, cost (default 1); returns allowed, remaining, reset time. Called by the gateway or in-process by the library.
  • PUT /rules/{id} and GET /rules for configuration; pushed to limiters, not pulled per request.
  • Response headers on every limited call: RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset, and Retry-After on 429.

4. High-level design

ClientsEdgeServicesDataallowedbatched deltaspush rulesdecisionsAPI clientsGateway serverslocal token bucketsProtected servicesSync agent(on each gateway)Rules serviceCounter storesharded by keyRules DB + pushDecision stream
  1. A request arrives at a gateway server, which identifies the key and the matching rule from an in-memory copy of the rules.
  2. The server consults its local token bucket for that key: if a token is available it decrements and forwards; otherwise it returns 429 with the headers. This is the sub-millisecond path.
  3. A sync agent on each server periodically (every 50 to 100 ms) sends the consumed counts per key to the counter store and receives the global consumption, adjusting local buckets.
  4. Rule changes are pushed to all servers within a second; decisions are streamed for dashboards and alerts.

5. Deep dives

Which algorithm, and how exact is it?

Fixed windows (count per minute) are simple but allow 2× the limit at a boundary: 1,000 at 11:59:59 and 1,000 at 12:00:00. Sliding log (store every timestamp) is exact but costs memory per request. The token bucket is the usual pick: a bucket of capacity b refills at r tokens a second; a request takes one token or is rejected. It allows a burst of b and a steady rate of r, and its state is two numbers (tokens, last refill). A sliding window counter approximates the sliding log with two fixed windows weighted by overlap, also two numbers. Both are O(1) per decision; say the token bucket is what you implement and name the burst parameter, because interviewers ask how bursts are treated (rate-limiting algorithms).

How do 2,000 servers enforce one global limit without a round trip per request?

Pure local buckets would allow 2,000× the limit if a key is spread across all servers. Pure central counters cost a network hop per request. The middle path: each server holds a local bucket for the key with a slice of the global rate, and syncs consumption to the central store every 100 ms. The store returns the global count, and servers adjust. The error is bounded by what can be consumed during one sync interval across all servers, which at 100 ms is 10 percent of a per-second limit in the worst case and far less in practice because a key is usually routed to a few servers. To tighten it, route a key's requests to a consistent subset of servers with consistent hashing at the load balancer, so a key's buckets live on a handful of machines and the sync is nearly exact. For the strictest keys, a rule can require a synchronous check against the store, paying the 1 ms.

What happens when the counter store is slow or down?

The store is a cache tier (Redis-like), sharded by key with replicas. If a sync fails, servers keep enforcing from their local buckets with the last known global state, so limits degrade to roughly per-server limits rather than disappearing. The fail-open flag per rule says what to do if even local state is missing (first request for an unknown key during an outage): allow by default for public APIs, deny for expensive internal endpoints. Timeouts on the sync call are short (5 ms) and never block the request path. This is the availability trade the interviewer wants spoken: a rate limiter that fails closed takes the whole API down with it.

How do clocks and retries interact?

Refill uses each server's monotonic clock, never wall time, so a clock jump cannot grant a flood of tokens; the central store uses its own clock for window boundaries. Retry-After is computed from tokens needed divided by the refill rate and rounded up, and clients that respect it smooth their traffic. Retried requests from a client count again, which is correct: the limit is on attempts. For clients that send a request id, the gateway can refund the token when the upstream returned a retryable 5xx, so a flaky backend does not burn the client's budget (clocks and ordering).

6. What a strong answer sounds like

  • Start with the arithmetic that forbids a central hop per request, then present local buckets plus periodic sync as the consequence.
  • Name the algorithm, its two numbers of state, and the burst parameter; mention the fixed-window boundary flaw.
  • Quantify the inaccuracy of the sync approach and show the routing trick that shrinks it.
  • Say "fail open" out loud, per rule, with the reasoning.
  • Follow-ups to expect: weighted costs per endpoint (a request takes k tokens), limits on multiple dimensions at once (per key and per IP, evaluate all and deny on any), and client-side limiting with the same headers to reduce 429s.
  • A common mistake is to shard the store by server rather than by key, which makes global counts impossible.

02Where this question was reported