Design exercise: API rate limiter

Generated by Claude (Fable 5.1) by hand, Scout learning center M4a on 2026-10-12, reviewed by a second reader (Claude Fable 5.1), Scout learning center M4b on 2026-10-12.

Concept: System design and architecture · also covers API design, Scaling, Reliability · Part C (Design exercises) of the system design module · design exercise · version 1

On this page

A classic design exercise: rate limiting for a public API served from twenty gateway nodes, with a 1 ms decision budget and a limiter that must never become the outage. The reference answer keeps token buckets on each node, corrects them from a shared store every 100 ms, fails open by default, and bounds overshoot in numbers. Converted by hand from the module outline's reference answer and its 45-minute script; every number and source is kept.

Attempt the design from the prompt, the constraints and the questions before reading the reference answer.

The prompt

Design the rate limiting for a public HTTP API served from many gateway nodes. Each API key has a limit; callers over the limit get a 429. The product team wants to add tiers and per-endpoint costs later.

Constraints and numbers

Functional

A per-key limit with a burst; 429 with headers that tell the caller when to retry; policies editable without a deploy.

Scale (assumption)

50,000 requests per second across 20 gateway nodes in one region; 1 million active keys; typical limits of 100 requests per second with a burst of 200; a few keys hold 30 to 40 percent of traffic. All chosen for the exercise; derive the per-node rate, the policy data size and the per-node bucket memory yourself.

Targets (assumption)

The decision adds under 1 ms at p99; the limiter must never make the API unavailable; overshoot of up to 10 percent over a one-second window is acceptable, sustained overshoot is not.

Non-goals

DDoS protection at the network layer, billing.

Clarifying questions worth asking

  • Per key, per user or per IP? Per key; per IP is a separate abuse limiter.
  • Exact or approximate? Approximate within 10 percent per second.
  • What if the shared store is down? The API must stay up; limits may loosen, and that must be visible.
  • Limits per endpoint? Later, via a cost per request.
  • Must Retry-After be exact? A ceiling is fine.
  • Do limits span regions? Per region now; a global view later.

Reference answer

Requirements and estimates

Derived numbers

50,000 decisions per second across 20 nodes is 2,500 per node. An exact shared counter means one atomic read-modify-write per request on a shared store: 50,000 operations per second plus a network round trip inside the 1 ms budget on every request; feasible for one store but a single point of latency and failure, and it doubles under retry storms. Policy data: 1 million keys at 100 bytes is 100 MB, cacheable on every node. State: one token bucket per key per node is two numbers (tokens, last refill) in a map; 1 million keys at 32 bytes is 32 MB per node, fine.

Algorithms

Fixed window: a counter per key per second; cheap, but allows up to twice the limit across a window boundary. Sliding log: exact, but stores every timestamp; too costly at this rate. Sliding window counter: weights the previous window's count by the overlap; the public Cloudflare write-up reports an average difference of 6 percent between the approximated and the real rate, with 0.003 percent of requests wrongly allowed or limited, at a fraction of the cost. Token bucket: a rate and a burst in two numbers, natural for '100 per second, burst 200', and the model Stripe describes for its request rate limiter. The answer uses token buckets locally and sliding window counters in the shared store for the global view.

High-level design

Container view

The limiter is a library inside each gateway node plus a shared store, not a separate network hop, because of the latency budget. Local buckets decide; the shared store corrects them a few times per second; a policy service pushes policies that every node caches.

flowchart LR
  CL[API clients] --> LB[Load balancer]
  LB --> G1[Gateway node 1: local buckets]
  LB --> G2[Gateway node 2..20: local buckets]
  G1 --> S[(Shared counter store, sliding windows)]
  G2 --> S
  G1 --> B[Backend services]
  G2 --> B
  PC[Policy service] -->|policies, pushed and cached| G1
  PC --> G2
  G1 -->|metrics: allowed, rejected, overshoot| M[(Metrics)]
flowchart LR
  CL[API clients] --> LB[Load balancer]
  LB --> G1[Gateway node 1: local buckets]
  LB --> G2[Gateway node 2..20: local buckets]
  G1 --> S[(Shared counter store, sliding windows)]
  G2 --> S
  G1 --> B[Backend services]
  G2 --> B
  PC[Policy service] -->|policies, pushed and cached| G1
  PC --> G2
  G1 -->|metrics: allowed, rejected, overshoot| M[(Metrics)]

Boxes are containers; cylinders are stores. The shared store is off the request path.

The data model

Entities and the in-process API

Policy {key_pattern or key, rate, burst, cost_rules[], scope: region or global}. In-process: allow(key, cost) returns {allowed, remaining, reset_in}.

Response contract

Headers on every response: a RateLimit field carrying the limit, the remaining quota and the time to reset, and a RateLimit-Policy field describing the policy (the two header fields of the current IETF draft; its first versions defined RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset instead, and the X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset variants that the draft's appendix catalogues are what many APIs still send), and on 429 also Retry-After (RFC 6585 defines 429).

The core flow, step by step

The decision path on one node, and the correction loop behind it.

  1. Each node holds a token bucket per key sized to its share of the limit: with 20 nodes and random balancing, each node gets about 1/20 of a key's traffic, so each bucket refills at rate/20 with burst/20.
  2. A request takes cost tokens from the key's local bucket; if the bucket is empty the node answers 429 with Retry-After and the RateLimit headers, at no backend cost.
  3. Every 100 ms (assumption) a node reports its counts per active key to the shared store and reads the global count for the last second.
  4. If the global count shows a key over its limit while the local buckets allowed it (uneven balancing, a hot key pinned to few nodes), the node tightens that key's local bucket for the next interval. The shared store therefore corrects, it does not decide; its latency is off the request path.
  5. The store's own cost is 20 nodes times 10 reports per second, each a batch of the node's active keys, which is a few hundred batched writes per second, not 50,000 single ones.

Scaling and the bottleneck

The shared store is slow or down

Fail open: nodes keep enforcing local buckets at their share, so each key is still bounded (by at most the number of nodes times its share, in the worst case of all traffic for a key on one node, which balancing makes unlikely). Emit a metric and an alert the moment the store is unreachable. Fail closed (reject when the store is unreachable) would turn a store outage into an API outage, which breaks the first target; fail closed is the right choice only where the limit protects something that must not be exceeded, such as a payment endpoint with a legal cap, and that is a per-policy flag. This follows the overload guidance of the SRE book's handling-overload chapter (reject cheaply, protect the service, never let the protection become the outage) and the Builders' Library article on load shedding.

Hot keys and exactness

A key at 40 percent of all traffic (20,000 requests per second against a limit it may well exceed) is the case where local buckets drift most. Options: pin that key to a dedicated node pair with consistent hashing so one bucket sees all of it (exact, but a hot node); or shorten the correction interval for keys above a traffic threshold; or accept the stated 10 percent overshoot. The answer shortens the interval for the top keys (adaptive, no topology change) and documents the overshoot bound. Per-endpoint cost is a multiplier on the tokens taken; tiers are just different policies; neither changes the architecture.

Failure modes and what degrades

Each row names the failure, its effect on the limit, and the mitigation.

FailureEffectMitigation
Shared store downdrift up to node count times sharefail open per policy, alert, local buckets still bound
Node restartbucket starts fullone burst of overshoot, accepted
Policy service downstale policiespolicies cached on nodes with a long TTL; changes delayed, limits still enforced
Clock skew between nodeswindow misalignmentlocal monotonic clocks for buckets; store windows keyed by store time
Retry storm from a rejected clientmore rejects, cheap429 with Retry-After; rejects cost no backend work
Hot key on few nodesovershootadaptive correction interval; optional pinning

Trade-offs and the alternative not taken

The decisions a reviewer reads first.

DecisionOptionsChosenWhy
Where the decision is madeshared store per request versus local buckets with correctionlocal with correctionthe 1 ms budget and the availability target
Algorithmfixed window, sliding log, sliding window counter, token buckettoken bucket locally, sliding window counters globallyburst semantics locally, cheap approximate global view
Store failurefail open versus fail closedfail open by default, closed per policythe limiter must not become the outage
Exactnessexact versus 10 percent overshootbounded overshootexactness costs a round trip per request and buys nothing at this product's limits

What changes at 10x

A global limit across regions becomes a second, slower correction loop on a replicated store, with the same local-first rule. A concurrency limiter (in-flight requests rather than rate) protects slow endpoints; Stripe describes running both. Adaptive concurrency limits (the Netflix concurrency-limits library) can replace static numbers for internal services. Quotas (per day or month) are a different system: exact, persisted, billed.

Self-check rubric

Read, not scored: find the level your answer reached.

L1, mid-level: applies

  • A token bucket per key and a shared store.
  • 429 with Retry-After and the RateLimit headers, and a clear statement of what happens at the limit.

L2, senior: chooses with numbers and defends

  • The local-first design with a correction loop and the latency arithmetic (2,500 decisions per node per second, a few hundred batched store writes per second).
  • The fail-open argument with its exception (fail closed per policy where a cap is legal or financial).
  • Hot keys, policy caching, the overshoot bound in numbers, and metrics that show drift.

L3, staff: sets the constraint and judges

  • Whether the product wants a rate limiter, a quota, or both; tiers as policy, not architecture.
  • The per-tenant fairness framing (the multi-tenancy lesson) and the cost of exactness as a business decision.
  • How the design behaves during a retry storm from a large customer.

The 45-minute interview frame

  • 0:00 to 0:05 Requirements. Ask: who is limited (API key, user, IP, tenant tier)? What limit shape (requests per second with a burst, or per minute)? What happens on reject (429 with a Retry-After header)? Must limits be exact, or is a small overshoot acceptable? Where does it sit (every edge node, or a central service)? State the numbers you will design for and say them aloud: 50k requests per second at the edge across 20 nodes (chosen for the exercise), 1 million distinct keys, decision latency under 1 ms added at p99, limits of the order of 100 requests per second with a burst of 200. Non-goals: billing, abuse detection, DDoS mitigation.
  • 0:05 to 0:10 API and entities. check(key, cost=1) returns allowed, remaining, reset_at; a policy object (key pattern, rate, burst, window, scope); response headers (RateLimit-*, Retry-After, status 429). Say that the limiter is a library plus a shared store, not a separate network hop, because of the latency budget.
  • 0:10 to 0:20 High-level design and the diagram. Token bucket per key; local in-process buckets on each node for the fast path; a shared store (Redis-class) for the global count; policies loaded from a config service and cached. Explain the two-tier idea: local buckets take the decision, the shared store corrects them a few times per second.
  • 0:20 to 0:40 Two deep dives. (1) Exactness versus cost: a fixed window per node allows up to N times the limit at window edges; a sliding window approximated from two fixed windows (the Cloudflare method) brings the average rate error to about 6 percent at the cost of two counters per key; an exact distributed token bucket needs an atomic read-modify-write on the shared store per request, which is the 1 ms you do not have at 50k per second across 20 nodes. Choose: local token buckets with a global budget split per node, re-split every 100 ms from the shared counts. (2) Failure modes: shared store down (fail open with local limits, alert; say why fail closed is wrong for a public API and right for a payment endpoint); hot key (one tenant at 40 percent of traffic: a dedicated shard or a local-only limit for that key); node restart (buckets start full; acceptable overshoot of one burst); clock skew (windows keyed on monotonic local time, store time only for TTL).
  • 0:40 to 0:45 Evolution. Tiers and per-endpoint costs (cost parameter), limits per region, moving the policy store to the gateway, metrics: allowed, rejected, overshoot ratio per key, shared-store latency. Ask what the interviewer would like to see deeper. The level shows in the deep dives: L1 gives a correct single-store token bucket; L2 gives the two-tier design with the exactness trade-off and the fail-open argument; L3 asks whether the product needs a limiter at all or a cost-based quota, and reframes the hot tenant as a tenancy question.

The design-doc frame

  • Context and scope. The public API, its gateway fleet, the keys and tiers that exist today, and the incidents or abuse that motivate a limiter.
  • Goals and non-goals. Bound every key within 10 percent per second, add under 1 ms, never make the API unavailable; DDoS and billing out of scope.
  • Design. This answer fills it: local token buckets, the correction loop against the shared store, the policy service and the header contract.
  • Alternatives considered. Where the decision is made (shared store per request versus local with correction) and the algorithm choice, with the trade-off table.
  • Cross-cutting concerns. Observability of drift (allowed, rejected, overshoot ratio per key, store latency) and the fail-open policy as a security review item.
  • Review questions the doc must answer. The worst-case overshoot under a store outage, and the behaviour when the policy service is down.

Depth notes

  • L1. A token bucket per key in a shared store with correct headers.
  • L2. Sliding windows, local plus global limits, fail-open versus fail-closed, hot keys.
  • L3. A multi-tenant limiter as a platform (policies, tiers, cost of accuracy, regional limits).

Sources

  • Rate limiting, overload and resilience patterns sd-rate-limiting-overload planned
  • Caching sd-caching planned
  • Consistency models, transactions and consensus in plain words sd-consistency-consensus planned
  • Load balancing and service discovery sd-load-balancing planned