Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Distributed Rate Limiting: One Budget, Many Counters, Synchronized Badly

Overview

Rate limiting looks like a one-line feature and is actually a small distributed system with its own consistency problem: the budget is a global quantity (requests per minute per client), but the counters live in many places — per-instance memory at each service pod, shared counters in Redis guarded by Lua scripts, token buckets at the edge load balancer — and those counters cannot agree in real time. This page maps the whole stack as one system: per-instance limiters that answer in microseconds with a partitioned view of the truth, shared counters that are authoritative but cost a network round trip and can become the new single point of failure, edge token buckets that absorb floods before they reach anything expensive, client-facing headers that turn the limiter into a coordination protocol with well-behaved clients, and the sync lag between nodes that quietly determines how much the limit can be exceeded. The failure modes are specific and quantitative — limit bypass during sync lag, fixed-window bursts at window boundaries, a Redis outage that forces an explicit fail-open or fail-closed choice — and the levers (local over-provisioning, tiered limits, identity tiering) all trade accuracy of enforcement for availability of enforcement.

The Nodes, Independently

Per-instance in-memory limiters. Each service pod keeps counters in its own memory: a token bucket or sliding window per key it has seen recently. Lookups and updates cost nanoseconds, there is no network dependency, and eviction of idle keys keeps memory bounded. The price is a partitioned view: each pod sees only the traffic that reached it, so a global per-client budget is unknowable at this layer — ten pods each admitting 100 requests/min can admit 1,000 against a nominal global limit of, say, 300.

Shared counters (Redis + Lua). The authoritative layer: a Redis cluster holds counters per (key, window), and a Lua script performs check-and-decrement atomically so concurrent requests cannot both pass on a stale read. Implementations range from simple INCR with an expiry (fixed window) to sorted-set sliding windows to GCRA-style smooth emission. Redis moves the counter off the request path’s correctness problem and onto the availability problem: it is now a dependency in the hot path of every request, and its failure mode must be chosen in advance.

Token buckets at the edge. The edge load balancer or API gateway runs coarse token buckets per client IP or API key — cheap, local, and placed to absorb floods before they consume any application capacity. The edge layer deliberately enforces a wider limit than the authoritative one: its job is shedding abuse, not metering the exact contract.

Client headers. X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset, and Retry-After (with 429 responses) are the protocol surface: they let well-behaved clients self-regulate, turning the limiter from a wall into a coordination mechanism. Headers must be computed from the most authoritative layer that answered, or clients will see contradictory budgets.

Concurrency limits, a sibling species. Rate limits meter arrivals per time window; concurrency limits meter simultaneous in-flight work, which is often what actually protects the backend — a slow 30-second request burns one slot for 30 seconds regardless of how few requests arrived. The two compose: a per-user 60 req/min budget plus a per-user 4-concurrent cap defends against both fast floods and slow hogging, and semaphore-style admission (admit at most N, reject with 503 when full) needs no clocks at all. Production limiters usually implement both, because the resource being protected — worker threads, DB connections, GPU memory — is a capacity, not a rate.

Sync lag between nodes. Whatever replicates the budget — a poll of Redis every few seconds, gossip between limiter nodes, or leased quota chunks — has a lag T. During T, nodes act on stale counters, and the fleet’s effective limit is a computable multiple of the nominal one.

How the Nodes Feed Each Other

A request meets layers in order of increasing accuracy and decreasing cheapness: the edge bucket rejects obvious floods with no network I/O; the per-instance limiter handles the fine-grained per-route limits locally; the Redis counter is consulted only for the budgets that genuinely need a fleet-wide view (per-tenant API quotas). Headers and 429s flow back from whichever layer rejected, and telemetry from all layers feeds the observability stack so limit tuning is data-driven. The layering is a caching hierarchy for admission state: each layer is a cheaper, staler approximation of the layer below it, and the design task is choosing how stale each layer may be — the same “accuracy versus proximity” trade that every cache hierarchy makes.

The Shared Invariants

A limiter is admission control, not correctness. Its errors must be chosen, not accidental: fail-open (protect the counter store, expose the backend) or fail-closed (protect the backend, break clients) is a per-route-class decision that belongs in config, not in whoever wrote the try/except. The budget is defined by (key, window, scope). Change any element and you have changed the semantics: per-IP punishes NAT offices, per-user punishes shared service accounts, per-API-key is the contract. The key choice is an identity decision first and a technical one second. Over-admission is computable. If the authoritative limit is L per window W, with N nodes syncing every T seconds and each node enforcing its last-known view locally, the worst-case burst is bounded by roughly N × L × (T/W + margin) — you do not eliminate the bypass, you price it and pick T to make the price acceptable. The counter store inherits every SPOF property it seems to remove. Centralizing the budget makes it accurate and makes its availability part of your request path — the same trade every shared “source of truth” makes.

Failure Propagation

Sync-lag bypass. An attacker (or a poorly sharded batch job) spreads requests across all N pods; each pod admits against its stale local view. With a 1,200 req/min limit, 12 pods, and 5-second sync, a burst on the order of 12 × 1,200 × (5/60) ≈ 1,200 extra requests sails through per window — the effective limit is materially a multiple of the nominal one, and the fix is not “more Redis” but leased local quotas with a chosen margin. Redis as the new SPOF. A Redis brownout makes every limiter call slow; if the code path treats timeout as deny, the API fails closed and a counter-store hiccup becomes a full outage; if it treats timeout as allow, the backend absorbs 100% of traffic — the exact overload the limiter existed to prevent. The failure of the metering layer is the failure of the protection, which is why serious deployments fail open toward cheap local fallbacks rather than uniformly. Fixed-window bursts. Two fixed windows adjacent in time allow a client to send the full budget at the end of one window and again at the start of the next: 2× the nominal rate in a one-second span. Sliding windows or GCRA smooth this at the cost of more state. Hot keys. One top-talker’s counter becomes the hottest key in Redis; adding replicas does not help because it is a single key, so the standard cures are sharded counters (split the budget into M sub-counters and sum lazily) or edge absorption. Retry storms at reset. Clients that ignore Retry-After and poll at window reset create synchronized spikes — the limiter’s own signal, misused, becomes an attack on itself. Noisy neighbors are the fairness failure: a single tenant consuming its full quota on a shared backend degrades latency for everyone within their own limits, because limits cap arrivals but say nothing about the cost each arrival carries. The cures are cost-based limits (below), per-tenant concurrency caps that bound resource occupation rather than arrival count, and load shedding that is tenant-aware rather than first-come-first-served — otherwise your most successful customer is indistinguishable from your worst attacker, and both get the same treatment at 3 a.m.

Design Levers

Local over-provisioning with leased quotas is the structural fix for sync lag: each pod leases a quota chunk (global/N × margin, say 1.2×) from the shared store, enforces locally, and renews asynchronously — the fleet stays correct within a computable bound even when the store is unreachable for a while, exactly the lease-and-fencing reasoning used for distributed locks. Tiered limits place each budget where its accuracy is worth its cost: coarse IP buckets at the edge, per-user shared quotas in Redis, per-route fine limits locally protecting one expensive endpoint. Identity tiering picks the key with judgment — API key for partners, user ID for signed-in traffic, IP only as an anonymous fallback, with documented exceptions for NAT-heavy audiences. Headers as contract let the cooperative majority self-throttle, which is cheaper than enforcing on them; emitting Remaining and Reset accurately is part of the limiter, not a nicety. Cost-based limits replace “one request = one token” with weights, because endpoints differ in cost by orders of magnitude: a search query that fans out to four shards is not worth one “list my orders” against a primary-key index. The budget becomes a per-window cost allowance (say 100 units/min), each endpoint declares a cost (2, 10, 50), and the limiter deducts weights — the same idea as weighted fair queueing or burst credits. It maps API tiers onto resources honestly, prevents the cheap-endpoint flood from starving expensive ones, and gives the client header surface a natural extension (X-RateLimit-Cost). The lever has a price: cost tables become a published contract that clients plan against, so changing a weight is a de facto API change with its own migration.

Degrade to last-known state: on counter-store failure, fall back to the most recent local bucket rather than a constant — the limiter should get worse gradually, not switch from perfect to absent. And algorithm choice is a lever, not a preference: fixed windows for simplicity where 2× bursts are tolerable, sliding windows where fairness matters, token buckets where bursts are legitimate.

A Concrete Worked Example

A public API sells 1,200 requests/min per key and runs 12 pods behind an L7 balancer. v1: each pod keeps its own fixed-window counter of 1,200/min. Measured reality: a customer sharding across 12 connections sees an effective limit of ~14,400/min (12 × 1,200) — the contract is fiction. v2: Redis + Lua check-and-decrement per request; accurate, but Redis p99 of 2 ms adds load to every call, and a 30-second Redis incident either fails the whole API closed or lets everything through. v3, the equilibrium: each pod leases a 110-quota chunk per 5-second interval (12 pods × 110 × 12 intervals ≈ 15,840/min ceiling in the absolute worst case, but normal traffic draws its lease and renews quietly), the edge holds a 3,000/min IP bucket that absorbed a credential-stuffing attempt the same quarter, and headers expose Remaining computed at the Redis layer when it answered. During a deliberate Redis failover test, pods ran on stale leases for 40 seconds: over-admission was bounded and measured at 1.3× — priced, chosen, and documented.

Interview Questions

  1. Design rate limiting for an API with 1,000 req/min per user, deployed as 30 stateless pods. Where does state live, what is the over-admission bound during sync lag, and what happens on a Redis outage?
  2. Why does a fixed-window counter allow a 2× burst, and what would you change if the backend cannot tolerate it? State the memory cost of your alternative.
  3. Your limiter’s counter store becomes a hot-spot under one tenant’s traffic. Why does adding Redis replicas not help, and what are two designs that do?
  4. Fail-open or fail-closed on counter-store failure: defend both, then say which you would choose for (a) a login endpoint, (b) a public search endpoint, and why the answer differs.
  5. What makes Retry-After and X-RateLimit-Remaining part of the limiter’s design rather than metadata, and what failure emerges when they are wrong or missing?

Key Takeaways

  • Distributed rate limiting is a caching hierarchy for admission state: each layer is cheaper and staler than the one below, and the design work is choosing the staleness budget per layer.
  • Over-admission during sync lag is not a bug to eliminate but a quantity to compute and price: roughly N × limit × (sync_interval/window + margin).
  • Centralizing counters buys accuracy and sells availability — the counter store becomes part of the request path, so fail-open versus fail-closed must be an explicit, per-route decision with local fallbacks.
  • The limit key is an identity decision (API key vs user vs IP) with fairness consequences, not a technical detail; tiered limits let each budget live where its accuracy is worth its cost.
  • Client headers turn the limiter into a coordination protocol; cooperative self-throttling is the cheapest enforcement you will ever get.

Cross-References