01. Rate Limiter — High-Level Design¶

~15 min read · Part 2 of 4 (Overview → HLD → LLD → Q&A)

This file turns the solutioning narrative into concrete boxes and the flows between them. Read the architecture top to bottom, follow a request through the allow path and the deny path, then look at what happens when the counter store fails.

Architecture¶

                 ┌──────────────┐
 client ───────▶ │ Load Balancer │  (spreads a key's traffic across all gateways,
                 └──────┬───────┘   no per-key affinity)
                        │
        ┌───────────────┼───────────────┐
        ▼               ▼               ▼
  ┌───────────┐   ┌───────────┐   ┌───────────┐
  │ Gateway   │   │ Gateway   │   │ Gateway   │   50 stateless gateways
  │  ┌──────┐ │   │  ┌──────┐ │   │  ┌──────┐ │
  │  │local │ │   │  │local │ │   │  │local │ │   in-memory token buckets
  │  │bucket│ │   │  │bucket│ │   │  │bucket│ │   (fast-path + fallback)
  │  └──────┘ │   │  └──────┘ │   │  └──────┘ │
  └─────┬─────┘   └─────┬─────┘   └─────┬─────┘
        │ decide?       │               │  allow → backend
        └───────┬───────┴───────┬───────┘
                ▼               ▼
        ┌─────────────────────────────┐        ┌──────────────┐
        │  Counter store (Redis        │        │ Policy store  │
        │  cluster, sharded by API key)│◀───────│ (limits/tiers,│
        │  slot(key) → window counters │  watch │  hot-reloaded)│
        │  [shard0][shard1]…[shard7]   │        └──────────────┘
        └──────────────┬──────────────┘
                       │ deny events (async)
                       ▼
               ┌──────────────┐
               │ Metrics /     │
               │ audit pipeline│
               └──────────────┘

Read it top to bottom. The load balancer spreads each API key's requests across all 50 gateways with no affinity, which is what makes local-only counting wrong and forces a shared count. Each gateway is stateless except for a small in-memory token bucket per key that it uses both as a fast-path (deny an obviously-over-limit key without a round-trip) and as a fallback ceiling when the counter store is unreachable. The authoritative count lives in a Redis cluster sharded by API key, so a given key's counter is on exactly one shard and all 50 gateways consult the same number for it. Policy — the limits and tiers — lives in a separate store the gateways watch and hot-reload, so a limit change is a data edit, not a deploy. Deny events flow asynchronously to a metrics pipeline; that path never blocks a decision.

Components¶

Load balancer. Spreads traffic across the stateless gateway tier and health-checks nodes out of rotation. The important property is what it does not do: it does not pin an API key to a gateway. That keeps the tier trivially scalable, but it is also the reason no gateway sees a key's full traffic and the count must be shared. (Key-affinity routing is a real alternative, discussed under Scaling.)

Gateway (enforcement point). The stateless workhorse. For each request it extracts the descriptors (API key, route, plan), consults its local token bucket, and — for traffic the local layer cannot decide alone — runs one atomic check against the counter shard for that key. On allow it forwards to the backend; on deny it returns 429 with Retry-After and X-RateLimit-* headers. Holding no durable state means any gateway handles any request and capacity is added by adding boxes.

Local token bucket. A per-key in-memory bucket on each gateway, refilling at a share of the global rate. It serves two jobs. As a fast-path it can deny a key that has already blown past its limit without touching the shard, which shields the shard from a hot key. As a fallback it becomes the enforcement ceiling when the shard is unreachable, so the fleet still caps traffic instead of flooding or blacking out. It is soft state: losing it costs a moment of looser enforcement, never correctness of stored data.

Counter store (sharded Redis cluster). The authoritative shared count. Keyed by API key so each key hashes to one shard, it holds the window counters the algorithm reads and increments atomically (via a Lua script, so read-compute-write is one hop). This is where the shared-count accuracy comes from and, by sharding, where the central bottleneck is avoided — 500k ops/s spread over 8 nodes is ~62k each.

Policy store. Holds limits, burst allowances, tiers, and the per-policy fail-open/closed choice as data. Gateways subscribe and hot-reload on change, so raising a paying customer's limit or clamping down on an abuser takes effect in seconds without a redeploy.

Metrics / audit pipeline. Consumes deny events and counter samples asynchronously to drive dashboards, alerting, and abuse investigation. Decoupled from the decision so that analytics load or an outage here never adds latency to a request or changes an allow/deny.

Primary allow path (request under the limit)¶

A request reaches a gateway through the load balancer, carrying an API key.
The gateway resolves the applicable policy from its hot-reloaded local copy (limit 100/s, burst 50, fail-open).
It checks the local token bucket first. If the bucket has already flagged this key as blatantly over-limit for this window, it denies immediately — no round-trip. Otherwise it proceeds.
It runs one atomic check against the counter shard for that key: the Lua script computes the sliding-window rate, and if it is under 100/s it increments and returns allow with remaining.
The gateway forwards the request to the backend and passes the X-RateLimit-* numbers back on the response. The hot path was one local check plus, at most, one sharded op.

Primary deny path (request over the limit)¶

Same first steps: gateway, policy resolution, local bucket check.
The atomic check against the shard computes the rate as ≥100/s. The script does not increment (or increments a rejection tally) and returns over-limit with the time until the window frees a slot.
The gateway short-circuits: it returns 429 with Retry-After set from the reset time and X-RateLimit-Remaining: 0, and it does not forward to the backend — the whole point is to spend nothing downstream on a rejected request.
It also nudges its local bucket so that a key sustaining rejections starts getting denied locally, moving future denials off the shard entirely.
A deny event is emitted asynchronously to the metrics pipeline. The response has already been sent; nothing about analytics is on the decision path.

Storage choices¶

Counters: in-memory, sharded Redis cluster. The access pattern is a keyed read-compute-write per request with a sub-millisecond budget and a natural TTL per window — exactly Redis's strengths, especially with a Lua script making the operation atomic in one round-trip. Sharding by API key distributes both storage and op load and keeps each key's count authoritative on one node. It is deliberately not durable: a lost counter re-establishes itself within one window (≤1 s), and durability would buy nothing for a value that expires in a second.
Policy: a small, strongly-consistent config store. Limits and tiers are read constantly but written rarely, and correctness matters (you must not enforce a stale limit against a customer who just paid for more). A config store or a consistent KV (etcd, Consul, or a replicated relational table) with a watch/notify channel fits — small data, hot-reloaded.
Metrics/audit: append-optimized store. Deny and usage events are write-heavy, append-only, and queried by aggregation over time and key. A time-series or columnar store (ClickHouse, Prometheus/Mimir, BigQuery) behind the async pipeline suits it, and keeping it separate protects decision latency from analytics load.

Scaling¶

Decision throughput. The gateway tier scales horizontally by adding boxes; nothing is pinned to a node. The coordination point is the counter store, and it scales by sharding on the API key: at 500k req/s, 8 shards carry ~62k ops/s each, and doubling to 16 shards halves that to ~31k. Because the shard key is the API key, adding shards is a rebalance of the key space, not a rewrite of the logic.

Avoiding the round-trip. The local token bucket removes the shard op for a growing share of traffic: once a hot or abusive key is denied locally, its requests never reach the shard. If a single key doing 100k/s of abuse is fully absorbed by local buckets across the 50 gateways, that is 100k ops/s the counter store never sees.

Hot key. One key drawing a huge share of traffic lands entirely on one shard — the same skew the URL shortener faced, here on the write path. Defenses stack: the local token bucket on each gateway absorbs most of an over-limit key's requests without a round-trip, so the shard sees the allowed rate (~100/s) plus a trickle of probes rather than the full flood. If a legitimate key with a very high limit is hot, its counter can be split into sub-counters on multiple shards (partition the limit, e.g. 4 shards each enforcing 25/s) and summed, trading a little accuracy for spreading the op load.

Key-affinity alternative. Routing each API key to a fixed gateway (consistent hashing at the LB) would let that gateway hold the key's counter locally and enforce exactly with zero round-trips — the appealing shortcut. The cost is that the LB is no longer stateless-simple, a gateway failure reshuffles keys and briefly double-counts, and a hot key overloads its one home gateway. The mainstream choice is the shared-shard design above, keeping the LB dumb and the gateways interchangeable.

Operational signals¶

The healthy signal is the allow/deny ratio holding steady at its expected baseline and the p99 decision latency sitting under a millisecond — a launch or a traffic spike that pushes the deny ratio up without moving decision latency is the limiter doing its job. The first metric to degrade under trouble is p99 decision latency: when it climbs while the deny ratio is normal, the counter shards are slow or a Redis node is failing over, and the local fast-path is not covering enough traffic. The misleading metric is the average decision latency — it stays flat because the local fast-path and cache-like Redis hits are fast, hiding a tail where round-trips to a struggling shard have gone from 0.4 ms to 40 ms; watch p99, not the mean. The graph an experienced operator opens first during an incident is counter-store ops/s per shard: it should sit near the expected ~62k and be roughly even across shards, so a single shard spiking toward its ceiling means a hot key is not being absorbed locally, and a fleet-wide drop toward zero means gateways have flipped to the fail-open fallback and are no longer consulting the shared count.

Failure modes and resilience¶

Counter shard unreachable (the fail-open moment). A gateway cannot reach the shard for a key within its sub-millisecond budget. It must not wait. Per the policy's on_error setting it falls back to its local token bucket enforcing that key's per-server share. Put the scenario on it: with the shard for a key down, each of the 50 gateways falls back to enforcing 100/50 = 2/s locally, so the fleet still caps that key at roughly its 100/s intended rate — approximate, but bounded — instead of either flooding the backend (naive fail-open) or 429-ing every legitimate request (naive fail-closed). When the shard returns, gateways resume the shared count and the local buckets drain.
Redis node loss / failover. The keys on that shard lose their authoritative count for the failover window. Mitigation: run the cluster with replicas so a node loss promotes a replica in seconds; during the gap, gateways fail open to local buckets for the affected keys only, and counters re-establish within one window (≤1 s) since they are short-lived by construction.
Clock skew across gateways. Sliding-window math uses timestamps, and gateways with drifting clocks disagree on window boundaries, causing small over- or under-counting. Mitigation: do the time arithmetic inside the Redis Lua script using the store's clock as the single reference, so all 50 gateways share one clock for the boundary decision rather than 50 slightly different ones.
Policy store outage. New limit changes stop propagating. Redirects — decisions — keep working on the last-known policy, which each gateway caches locally, so an outage here freezes policy rather than breaking enforcement. It is off the critical path by design.
Hot-key shard overload. One key's traffic saturates its shard. Mitigation: the local fast-path absorbs the over-limit portion; for legitimate high-limit keys, split the counter across shards as described under Scaling.
Thundering fallback. If a large shard outage flips many gateways to fail-open at once, backend load can jump. Mitigation: the local buckets bound the jump (each gateway still enforces its share), and load-shedding at the backend is the backstop — the limiter degrades to approximate rather than absent.

Where this shows up in production¶

Stripe — runs a Redis-backed token-bucket rate limiter in front of its API, with separate limiters for request rate, concurrency, and load-shedding, so a spike in one dimension can't starve the others.
Cloudflare — enforces limits at the edge with a sliding-window-counter (weighting the previous window by overlap) to bound both memory and boundary bursts across a globally distributed fleet.
Envoy / Lyft ratelimit — the reference gRPC rate-limit service: gateways call ShouldRateLimit with descriptors and a Redis backend increments fixed-window counters atomically, exactly the descriptor-and-shared-counter shape here.
AWS API Gateway — exposes a token-bucket model directly as a steady rate plus a burst capacity, the same two knobs (refill rate, bucket size) used in this design.
GitHub API — publishes X-RateLimit-Limit/Remaining/Reset headers and layers primary and secondary limits, the multi-scope "tightest limit wins" pattern in the functional requirements.
Shopify — famously uses a leaky-bucket model for its API, showing the alternative shaping discipline where requests drain at a fixed rate rather than being counted per window.
Google Doorman — distributed client-side rate limiting where a central server allocates capacity shares to clients, the "vend a share, enforce locally" answer to avoiding a per-request round-trip.
Redis CL.THROTTLE (redis-cell) — implements the Generic Cell Rate Algorithm as a single atomic command, the productionized version of doing the token-bucket math inside the store.
Nginx limit_req — a per-node leaky-bucket limiter, the canonical example of purely-local enforcement and its blind spot: it only knows the traffic reaching that one node.