Rate Limiter

Rate Limiter

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

1. The problem and why it is deceptive

From far away, rate limiting looks like "a counter with TTL in Redis". That solves part of it. It does not solve the whole problem. When the system grows, the questions that matter are bigger than the algorithm:

• Where is the limit enforced, edge, gateway, service, or all of them?
• What is the key: user, token, IP, tenant, endpoint, method, region?
• Is the limit hard or soft?
• What happens when the rate-limit storage fails: fail open or fail closed?
• How do you stop abusive bursts without destroying legitimate throughput?
• How do you do this across many replicas without races and without a central bottleneck?

The organizing question, asked first:

What exactly am I protecting, and how much imprecision do I accept to protect it without destroying latency and simplicity?

That one question drives almost every decision here.

2. Why rate limiting exists (five goals at once)

1. Protect finite capacity of a system.
2. Fairness between clients, tenants, users.
3. Reduce blast radius: a client in a loop, a deploy generating anomalous traffic.
4. Sustain commercial models: free / pro / enterprise plans.
5. Control cost: services that call expensive dependencies (LLM, search, third parties).

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

3. Where to enforce (defense in depth)

Layer	Good for	Limit type	Caveat
Edge / CDN	absorb volumetric abuse, L7 DDoS, block early	coarse	lacks rich business context
API Gateway	most common place; per token/user/tenant/endpoint	generic API	if it bottlenecks, the whole platform feels it
Inside the service	limit depends on domain context (expensive report, LLM inference)	semantic / cost	closest to the truth, furthest from the edge

The mature architecture is layered: edge for coarse protection, gateway for generic API limits, service for semantic/cost limits. Each layer catches what the layer above cannot see. This is the same "defense in depth" idea as security layering.

4. The limit key

Choose the dimension(s) consciously: user, token, IP, tenant, endpoint, method, region, often a composite. The key choice sets:

• Cardinality: how many distinct counters exist, which drives store load and hot-key risk.
• Abuse surface: an IP limit is easy to evade behind NAT/proxies; a token limit ties to identity.

Composite keys (tenant + endpoint) localize limits precisely but multiply the counter count.

5. Theory, the algorithms

This is the part everyone names and few explain. Each row is a different answer to "how do we count".

Fixed window counter

Count requests in a fixed clock bucket (e.g. per minute), reset at the boundary. Cheap, one counter per key. Flaw: boundary burst. A client can send a full window at 11:59:59 and another full window at 12:00:00, ~2x the intended rate across the boundary.

Sliding window log

Store a timestamp per request, count those within the trailing window. Exact and fair. Cost: memory and CPU grow with traffic, since you keep every timestamp in the window. Fine at low volume, expensive at scale.

Sliding window counter

Approximate the sliding window with two fixed buckets (current + previous) weighted by the elapsed fraction of the current window:

estimate = current_count + previous_count * (1 - elapsed_fraction)

Smooths the boundary burst, one or two counters per key, a single atomic operation. The common production compromise between fixed-window cheapness and sliding-log accuracy.

Leaky bucket

Requests enter a queue that drains at a constant rate; overflow is rejected. Produces a smooth, constant output rate, good for shaping traffic into a downstream that wants steady flow.

Token bucket ← industry default

A bucket holds up to capacity tokens. Tokens refill at a constant rate. Each request consumes one token; if the bucket is empty, reject (or queue). The key property: it separates the allowed burst (capacity) from the sustained rate (refill). A client can burst up to capacity instantly, then is held to rate thereafter. This matches how platforms want to behave: "you may spike a little, but your steady-state is capped."

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)

Token bucket is the classic traffic-shaping algorithm from networking (see Tanenbaum, Computer Networks); it is what most API platforms and cloud providers expose.

Choosing

Default to token bucket when you want sustained rate + controlled burst; sliding window counter when you want a simple, near-exact rolling limit with a sub-ms check. Make the check atomic: a Lua script in Redis runs read-decide-write in one server-side operation, so concurrent replicas cannot race.

6. State and storage

• Per-key bucket/counter in an in-memory store (Redis), TTL-bounded (e.g. 2 windows) so cold keys expire and memory stays bounded.
• Atomic decision: a single Lua script does refill/weight + check + decrement in one round trip.
• Limit config (key to quota/refill) in a config service with a short local cache, hot-reloadable without redeploy.

7. Theory, hot keys

One tenant with disproportionate traffic concentrates load on one store shard (a hot key). Mitigations:

• Local budgets. Each node is granted a slice of the global budget and decrements it locally, reconciling with the central store periodically. This trades exactness (you may over-admit by up to one budget-slice per node) for a huge 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+endpoint), so no single counter is hot.
• Local pre-check / token pre-filter before the central call: a saturating key is throttled at the node before it touches the shared store.
• Shard the store by key (consistent hashing), so one key's operations stay on one shard.

8. Fail-open vs fail-closed

When the rate-limit store fails, decide deliberately.

• Fail-open (allow): protects legitimate traffic from your own outage, but drops protection during the outage.
• Fail-closed (deny): preserves 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 which posture each layer takes, and why. Pair it with a circuit breaker (Nygard) so a slow store does not add latency to every request, once the store is detected unhealthy, the limiter stops calling it and applies the fallback posture immediately.

9. Hard vs soft limits

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

10. Multi-region

Strict global accuracy across regions would require 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. You accept bounded over-admit (a global limit of N might briefly admit a bit more than N) in exchange for low latency. Reserve strict global counting for the few limits that genuinely need it. This is the CAP/PACELC trade-off made concrete: under normal operation you trade consistency for latency.

11. Shadow mode (the highest-leverage practice)

Before enforcing a hard limit, run it in observation mode: the system computes the block decision but does not apply it, and emits what it would have blocked. This catches misconfigured policies before they cause an incident, you see "this new limit would have 429'd 40% of tenant X's legitimate traffic" in a dashboard instead of in a 3am page. Promote a limit from shadow to enforce only after the shadow metrics look right.

12. Observability

Essential metrics:

• 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,
• shadow-mode would-block counts.

At 3am someone must be able to answer: which limit fired, in which dimension, was the policy wrong, was there a traffic regression? If the design cannot answer that, it is not operationally governable , and "operationally governable" is the real bar, not a pretty algorithm.

13. Failure modes

Failure	Impact	Mitigation
Store down	no central counting	chosen posture (fail-open default) + local fallback budget + circuit breaker + alert
Hot key saturates a shard	shard CPU spike, latency	local pre-filter + composite keys + local budgets
Bad policy pushed	mass false 429s	shadow mode first; fast config rollback; per-policy block-rate alert
Gateway limiter becomes the bottleneck	platform-wide latency	push coarse limits to edge, keep the gateway check O(1)

14. Incremental plan

1. Vertical slice: one enforcement layer (gateway), fixed or sliding window, single Redis, one limit key, 429 + Retry-After, allow/deny metrics.
2. Correctness / ops: token bucket via atomic Lua, fail-open + circuit breaker, shadow mode, hot-reload config, per-policy metrics.
3. Scale: sharded store, hot-key local budgets + pre-filter, layered enforcement (edge/gateway/service).
4. Global: regional budgets with reconciliation, composite policies, cost/LLM semantic limits in the service.

15. Trade-offs to state explicitly

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; per-layer placement (catch early at edge vs rich context in service).

16. A worked, filled example

The repo ships a complete filled SDD for a distributed rate limiter (sliding-window-counter variant, 200k QPS, sub-ms budget, fail-open) as the agent's good example: good-system-design-example.md.

References

• Andrew Tanenbaum, Computer Networks, token bucket and leaky bucket traffic shaping.
• Martin Kleppmann, Designing Data-Intensive Applications, 2017, consistency vs latency, accepting bounded imprecision.
• Michael Nygard, Release It!, 2nd ed., 2018, circuit breaker, bulkhead, fail-fast as a stability decision.
• Werner Vogels / Amazon, design for failure (the store will fail).
• Pat Helland, Life Beyond Distributed Transactions, CIDR 2007, local budgets as independent, asynchronously-reconciled state.
• Eric Brewer, CAP theorem (PODC 2000); Abadi, PACELC (2012): the latency-vs-consistency framing for multi-region budgets.
• Stripe Engineering, Scaling your API with rate limiters, token bucket in production practice.
• Redis docs, Rate limiting with Redis and EVAL/Lua for atomic decisions.