Skip to content

00. Design a Rate Limiter

~20 min read · Level: intermediate · Part 1 of 4 (Overview → HLD → LLD → Q&A)

Problem

A rate limiter sits at the front door of an API and decides, for each incoming request, whether to let it through or reject it with a 429 Too Many Requests. It is the component behind the per-key quotas you see at Stripe, GitHub, Cloudflare, and every API gateway that publishes "X requests per second." Its job is protective: keep one noisy client from starving everyone else, blunt credential-stuffing and scraping, and give the backend a load ceiling it can survive. Conceptually it counts requests per client per unit time and says yes or no. That framing hides the hard part, which is where the count lives.

The difficulty shows up the moment the limiter runs on more than one machine. A single process can keep a counter in memory and be exactly right. A fleet cannot, because no single machine sees all the traffic. The count has to be shared, and sharing it either means a network round-trip on every request or an agreement scheme that tolerates being a little wrong. That tension — between an accurate count and a fast decision — is the whole problem.

To keep the reasoning concrete, thread one scenario through the design: enforce a limit of 100 requests/second for a single API key, across a fleet of 50 stateless gateway servers, without funnelling every request through a central bottleneck. The load balancer spreads that key's traffic across all 50 gateways with no affinity, so on average each server sees only a fraction of the key's requests and none of them sees the whole picture. If each of the 50 servers naively enforced "100/s" locally, the fleet would allow 5,000/s — fifty times the limit. That single number is why a rate limiter is a distributed-systems problem wearing a counting problem's clothes.

Functional requirements

  • Decide fast: for each request, given an API key (or IP, user ID, or route), return allow/deny before the request reaches the backend.
  • Enforce a configured limit: a rate expressed as N requests per window per key, e.g. 100/s, with an optional short burst allowance above the steady rate.
  • Multiple scopes and tiers: different limits per API key, per route, and per plan (free vs paid), evaluated together so the tightest applicable limit wins.
  • Inform the client: on rejection return 429 with a Retry-After and X-RateLimit-* headers so well-behaved clients back off instead of hammering.
  • Configurable policy: limits are data, not code — changeable at runtime without a redeploy.

De-scoped for this round, and worth naming so the interviewer hears it as a choice: full API-key lifecycle and billing, WAF-style attack signatures and bot detection, per-request cost weighting beyond a simple token count, and quota accounting for billing (monthly usage) — that last one is a metering problem with different consistency needs and belongs in its own system. These sit beside the limiter and do not change its core shape.

Non-functional requirements

The dominant constraint is the limiter is on the critical path, so its own latency and availability are pure tax paid by every request — allowed or denied. Everything else bends to that.

  • Latency: the decision must land in well under a millisecond so it is invisible against a typical 50–100 ms backend call. A limiter that adds 5 ms to every request has made the whole API 5–10% slower to stop the 1% that misbehaves.
  • Availability: the limiter must never be a single point of failure for the API. If its counter store is unreachable, it has to degrade gracefully rather than take the API down with it — which forces an explicit fail-open vs fail-closed decision.
  • Accuracy: exactness is not a hard requirement. Overshooting 100/s to 105/s for a moment is usually fine; adding a round-trip to every request to guarantee exactly 100 usually is not. The limiter exists to prevent abuse and overload, not to bill by the request.
  • Throughput / no bottleneck: whatever coordinates the count must scale horizontally with the fleet. A design that routes all 500k req/s through one counter node has moved the bottleneck, not removed it.

Scale estimation

Assume a mid-to-large API platform: 1 million active API keys, a peak aggregate ingress of 500,000 requests/second, served by the fleet of 50 gateway servers. That is 500,000 / 50 = 10,000 req/s per gateway at peak.

If the limiter checks a central counter on every request, that is 500,000 counter operations/second. A single Redis node sustains roughly 100k–150k simple ops/second, so one node cannot hold the whole fleet's checks — routing everything to it recreates the bottleneck the scenario forbids. Sharding the counter by API key across, say, 8 nodes brings each node to 500,000 / 8 ≈ 62,500 ops/s, comfortably inside a single node's envelope with headroom for failover. The shard key is the API key, so each key's counter lives on exactly one node and all 50 gateways consult the same authoritative count for a given key.

Memory is small and its size is a design lever rather than a limit. The choice of algorithm sets the per-key footprint. A sliding-window-counter keeps two integers and a timestamp per key, about 40 bytes; at 1M keys that is 1M × 40 B = 40 MB, spread over the shards it is ~5 MB each — nothing. A sliding-window-log, which stores a timestamp per request in the last window, holds up to 100 timestamps for a key at 100/s — 100 × 8 B = 800 B per active key, so 1M × 800 B = 800 MB. That 40 MB versus 800 MB, a 20× swing, is the memory-versus-precision tradeoff made concrete, and it buys accuracy the platform does not need.

Latency budget: an in-datacenter Redis round-trip is ~0.3–0.5 ms. Against a 50 ms backend call that is under 1% overhead — acceptable for the common path, but it is per request and multiplied by 500k/s, which is exactly why the design also wants a way to avoid the round-trip for the traffic that does not need it.

API sketch

The limiter is a gateway component, so its "API" is a decision contract plus the client-facing response, not a CRUD surface.

# Internal decision call (per request, e.g. Envoy RLS-style)
ShouldRateLimit(
  descriptors: [ {key: "api_key", value: "k_9f3..."},
                 {key: "route",   value: "POST /charges"} ]
) -> { code: OK | OVER_LIMIT,
       limit: 100, remaining: 12, reset_after_s: 0.4 }

# Client-facing response on rejection
HTTP/1.1 429 Too Many Requests
Retry-After: 1
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1751540401

# Runtime policy (data, hot-reloaded — not a redeploy)
PUT /admin/policies/{api_key}
  body: { "limit": 100, "window": "1s", "burst": 50, "on_error": "fail_open" }

Solutioning

Start from the killer number. Fifty servers each enforcing 100/s locally allow 5,000/s, so a purely local limiter is off by the fleet size — 50× here. The count has to be shared. The first fork is how it is shared, and it is the defining tradeoff: accuracy versus latency, expressed as central versus local enforcement. A central counter — every gateway runs an atomic check against a shared store keyed by the API key — is accurate to within one increment because all 50 gateways read and write the same number, but it puts a network round-trip and one store operation on every request. A purely local counter has zero latency and no dependency but is wrong by the fleet factor. Neither pole is the answer; the working design is central-but-sharded with a local fast-path.

The resolution is to make the count central and authoritative but shard it by API key so no single node is the bottleneck, then add a thin local layer that absorbs the traffic the central check does not need to see. Sharding by key means each key's counter lives on one node, all 50 gateways agree on it, and the 500k ops/s spread across 8 nodes at ~62k each — accurate and un-bottlenecked. The local layer is a small in-memory token bucket on each gateway that short-circuits a key already blatantly over its limit: once a gateway has locally seen enough rejections for a key, it can deny without a round-trip, which both saves latency and shields the shard from a hot key hammering it. The memory hook: enforcing 100/s across 50 servers is not a counting problem; it's a coordination problem — the hard part isn't counting the requests, it's agreeing on the count without paying a round-trip on every one.

The second tradeoff is memory versus precision, and it is decided by algorithm choice rather than hardware. A fixed-window counter is one integer per key but permits a 2× boundary burst — 100 requests at t=0.99s and 100 more at t=1.01s is 200 requests in 20 ms while every window individually reads "100, legal." A sliding-window log is exact but stores every timestamp, the 800 MB option above. The sliding-window-counter — one previous-window count, one current-window count, weighted by how far into the current window the clock has moved — costs 40 bytes per key, bounds the error to a fraction of a percent under real traffic, and kills the boundary burst. It is the default here precisely because the accuracy it gives up is accuracy the platform never needed: the fixed window doesn't limit 100/s, it limits 200 across any two adjacent windows, and that is the bug the sliding window fixes for almost no memory.

The third tradeoff is fail-open versus fail-closed, forced by the availability constraint. When a gateway cannot reach the counter shard — network blip, node failover — it must still answer every request in under a millisecond, so it cannot wait. The choice is who to hurt: fail-open lets requests through uncounted, protecting your users at the cost of briefly exposing the backend to overload; fail-closed rejects them, protecting the backend at the cost of a self-inflicted outage for legitimate traffic. The default here is fail-open with a local token bucket as the fallback ceiling — when the shard is unreachable, each gateway falls back to enforcing its per-server share locally, so the fleet still caps traffic at a bounded (if approximate) rate instead of either flooding the backend or blacking out the API. The hook: when the limiter can't reach its counter, you're not choosing whether to be wrong — you're choosing who pays for it.

The result is a system whose hot path is a local check plus, for traffic that needs it, one sharded atomic counter operation; whose accuracy comes from keying the shared count by API key so all 50 gateways agree; and whose failure behavior is a deliberate, bounded fail-open. The following files take these decisions down to components (HLD) and then to schemas, the token-bucket and sliding-window algorithms, and the concurrency corners (LLD).