Rate Limiter

System Design series #2. Topic skill: skills/rate-limiter/. Distributed rate limiting at scale, from algorithm to operation.

The problem

Rate limiting looks like a counter with a TTL in Redis. That covers part of it. At scale the hard questions sit outside the algorithm: where the limit is enforced (edge, gateway, service, or all), what the key is (user, token, IP, tenant, endpoint, method, region), whether the limit is hard or soft, whether to fail open or closed when the store fails, how to stop abusive bursts without hurting legitimate throughput, and how to count across many replicas without races or a central bottleneck.

Start by naming what you protect and how much imprecision you accept to protect it without hurting latency and simplicity. That answer drives almost every decision below.

Why rate limiting exists

A limiter serves five goals at once. It protects finite capacity, keeps fairness between clients, tenants, and users, and shrinks the blast radius of a client in a loop or a deploy that generates anomalous traffic. It also enforces commercial plans (free, pro, enterprise) and caps cost for services that call expensive dependencies such as LLMs, search, or third parties.

A good design is a set of overlapping limits (global, tenant, user, endpoint, IP security), never a single counter. Policy first, Redis second.

Where to enforce

Mature architectures layer all three: edge for coarse protection, gateway for generic API limits, service for semantic and cost limits. Each layer catches what the one above cannot see, the same defense-in-depth idea as security layering.

The limit key

Choose the dimensions on purpose, often as a composite. The key sets cardinality, which is how many distinct counters exist and so drives store load and hot-key risk. It also sets the abuse surface: an IP limit is easy to evade behind NAT or proxies, while a token limit ties to identity. Composite keys (tenant plus endpoint) localize limits precisely but multiply the counter count.

Algorithms

Each algorithm is a different answer to how you count.

Fixed window counter counts requests in a fixed clock bucket (for example per minute) and resets at the boundary. It costs one counter per key. Its flaw is the boundary burst: a client sends a full window at 11:59:59 and another at 12:00:00, about 2x the intended rate.

Sliding window log stores a timestamp per request and counts those inside the trailing window. It is exact and fair, but memory and CPU grow with traffic. Fine at low volume, expensive at scale.

Sliding window counter approximates the sliding window with two fixed buckets, current and previous, weighted by the elapsed fraction of the current window. It smooths the boundary burst with one or two counters per key and a single atomic operation. It is the common production compromise between fixed-window cost and sliding-log accuracy.

estimate = current_count + previous_count * (1 - elapsed_fraction)

Leaky bucket queues requests and drains them at a constant rate, rejecting overflow. It produces a smooth, constant output rate, good for shaping traffic into a downstream that wants steady flow.

Token bucket is the industry default. A bucket holds up to capacity tokens that refill at a constant rate; each request takes one token, and an empty bucket rejects or queues. It separates the allowed burst (capacity) from the sustained rate (refill): a client spikes up to capacity at once, then is held to rate. It is the classic traffic-shaping algorithm from networking (Tanenbaum, Computer Networks) and what most API platforms and cloud providers expose.

on request:
  now = clock()
  tokens = min(capacity, tokens + (now - last_refill) * rate)
  last_refill = now
  if tokens >= 1: tokens -= 1; allow
  else: reject (429, Retry-After)

Pick token bucket for a sustained rate with controlled burst, and sliding window counter for a near-exact rolling limit with a sub-ms check. Make the check atomic: a Lua script in Redis runs read, decide, and write as one server-side operation, so concurrent replicas cannot race.

State and storage

Keep each key's bucket or counter in an in-memory store (Redis) with a TTL (for example 2 windows), so cold keys expire and memory stays bounded. One Lua script does refill or weighting, check, and decrement in one round trip. Limit config (key to quota and refill) lives in a config service with a short local cache and reloads without a redeploy.

Hot keys

One tenant with disproportionate traffic concentrates load on one store shard. Four mitigations apply.

Local budgets grant each node a slice of the global budget to decrement locally, reconciling with the central store periodically. You over-admit by up to one slice per node in exchange for a large drop in central-store pressure. This is Helland's data on the outside, reconciled asynchronously, applied to counters.

Composite limits spread a tenant across sub-keys (tenant plus endpoint) so no single counter runs hot. A local pre-check throttles a saturating key at the node before it touches the shared store. Sharding the store by key with consistent hashing keeps one key's operations on one shard.

Fail-open vs fail-closed

Decide on purpose what happens when the store fails. Fail-open (allow) protects legitimate traffic from your own outage but drops protection while it lasts. Fail-closed (deny) keeps protection but turns a limiter outage into an availability incident.

Most platforms fail open on the generic path and fail closed only where the limit guards a hard capacity or cost ceiling. State the posture of each layer and why. Pair it with a circuit breaker (Nygard): once the store is unhealthy, the limiter stops calling it and applies the fallback posture at once, so a slow store does not add latency to every request.

Hard vs soft limits

A hard limit rejects with 429 Too Many Requests and Retry-After. A soft limit warns, degrades, or queues and still serves. Cost and fairness limits are often soft with escalating friction; security and capacity limits are hard.

Multi-region

Strict global accuracy needs a synchronous cross-region hop on every request, which destroys latency. The realistic compromise is regional budgets with reconciliation: each region enforces a local share of the global limit and reconciles asynchronously. A global limit of N may briefly admit a bit more than N, in exchange for low latency. Reserve strict global counting for the few limits that need it. This is the CAP/PACELC trade-off made concrete: in normal operation you trade consistency for latency.

Shadow mode

Before enforcing a hard limit, run it in observation mode. The system computes the block decision, does not apply it, and emits what it would have blocked. You see "this new limit would have 429'd 40% of tenant X's legitimate traffic" on a dashboard instead of in a 3am page. Promote a limit from shadow to enforce only after the shadow metrics look right. Of every practice on this page, it pays back the most.

Observability

Track requests allowed per policy, requests blocked (429) per policy and dimension, decision latency (the limiter must add near zero to the request path), store op latency, fail-open events, top-throttled keys, and shadow-mode would-block counts.

At 3am someone must answer which limit fired, in which dimension, whether the policy was wrong, and whether traffic regressed. A design that cannot answer that is not operationally governable, and that is the bar.

Failure modes

Incremental plan

Trade-offs to state

State each one in the design: accuracy vs latency (exact global count vs local budget), fail-open vs fail-closed, central store vs local budgets, one limit key vs composite, enforce now vs shadow first, and placement per layer (catch early at the edge vs rich context in the service).

Worked example

The repo ships a complete filled SDD for a distributed rate limiter as the agent's good example: sliding window counter, 200k QPS, under 1 ms added latency, fail-open. See good-system-design-example.md. The general method lives in System Design Method.

References

This page mirrors Rate Limiter in the wiki. Edit it there.