Primary concepts and the hard part
Requirements
Retry-After and remaining-quota headers1M requests/sec at the edge Identities tracked: ~50M active keys State per identity: ~50 bytes → 2.5 GB, fits comfortably in Redis memory
API / Model
TTL-based expiry is worth pointing out: the counters garbage-collect themselves, so there's no cleanup job and memory is bounded by active identities, not total identities.
High-level architecture
Limits are enforced in two layers inside the API gateway fleet: an L1 local bucket in every gateway, and a Redis cluster that holds the shared count. Volumetric attacks are dropped before traffic reaches either layer.
- Client traffic first passes CDN L3/L4 scrubbing, and the Load balancer spreads what is left across the gateways.
- The gateway finds the rule for the caller's identity and endpoint in its local copy of the Config service rules.
- It checks the caller's L1 local bucket in memory, with no network call.
- Every N requests or X milliseconds, the L2 batched sync reconciles that bucket with the Redis cluster, which is sharded by identity. A Lua script there runs the check-and-decrement atomically in one round trip, so every gateway works from the same global count.
- If the bucket, as of its last sync, has a token, the request is allowed and goes to Backend services. If not, the gateway returns 429 Too Many Requests with
Retry-Afterand theX-RateLimit-*headers.
Two flows run beside the request path. The Config service distributes rule changes to the gateways, which cache them and fall back to safe defaults when it is unreachable, so a limit can change without a deploy. The dotted edge from Redis to Backend services is the failure path: when Redis is unreachable, gateways keep enforcing their local buckets, let traffic through, and log and alert.
Same limiter at 100x the traffic, which is roughly what the largest edge networks see. Dashed outlines mark what's new or reshaped compared with today's design.
| Today | At 100x | |
|---|---|---|
| Requests | 1M/sec | 100M/sec |
| Active identities | ~50M | ~1B |
| Bucket state if every key had one | ~2.5 GB | ~50 GB |
| Redis syncs, one per ~100 requests | ~10k/sec | ~1M/sec |
| Where traffic lands | a few regions | ~300 edge PoPs, ~20 regions |
What changes, and the number that forces it
- Per-IP limits move to the edge. At 100M requests/sec a large share of traffic is abusive, and hauling it to a region just to reject it pays for bandwidth and gateway capacity twice. Coarse per-IP buckets run in the CDN's edge PoPs with local state only, so floods and scrapers are rejected where they land. Per-key and per-user limits stay in the regions, where identity is known.
- Most keys stop getting a bucket. Of ~1B active identities, the vast majority never come near their limit, yet each bucket would cost memory and a stream of Redis syncs. Each gateway runs a count-min sketch to spot heavy hitters, and only keys above ~50% of their limit get a real token bucket and join the sync. Sync volume now tracks the keys that matter, not all of them. A key that jumps from idle to over-limit inside one sketch window slips through briefly, which the bounded-overshoot contract already allows.
- Redis goes regional, and global limits become leases. One Redis for a global limit would put a cross-region round trip in every sync. Each region runs its own cluster, and a global quota service leases each region a share of every global limit, rebalanced every few seconds by observed demand. Overshoot is bounded by
regions × lease slack, a number you can still compute and state. Correctness-critical limits ("one free trial per account") stay exact by checking one home region synchronously. - The biggest tenants get their own shards. At 100x, a single large customer sends more traffic than whole regions did before. Their keys live on dedicated Redis shards (or sub-buckets
key#0..#N), so one tenant's burst can't raise latency for everyone sharing a shard. - Rules are pushed as versions, not polled. 30-second polling from ~300 PoPs and thousands of gateways is a load pattern of its own, and a bad rule would reach everywhere at once. Rule sets become versioned artifacts, pushed through the same channel as edge config, run in shadow mode, then rolled out region by region.
What stays the same
Token bucket as the default algorithm, Lua scripts for atomic check-and-decrement, identity-sharded Redis, fail open on local buckets while alerting, 429 with Retry-After, and layered limits: IP at the edge, API key at the gateway, user at the service. What changes is where each layer runs and how much state it bothers to keep.
Trade-offs and deep dives
FIXED WINDOW limit 100/min
[10:00:00─10:00:59] ████████████ 100
[10:01:00─10:01:59] ████████████ 100
▲
100 at 10:00:59 + 100 at 10:01:00
= 200 in one second. BOUNDARY BURST BUG.
SLIDING WINDOW LOG exact, stores every timestamp
[t1 t2 t3 ... t100] ← memory grows with traffic. Accurate but costly.
SLIDING WINDOW COUNTER the practical compromise
count = curr + prev × (fraction of prev window still in view)
~exact, O(1) memory.
TOKEN BUCKET ← recommended default
capacity B = 100 (burst), refill R = 10/sec
┌──────────────┐
│ ● ● ● ● │ ← refills at R
└──────┬───────┘
│ 1 token per request
▼ empty → reject
Allows bursts up to B, enforces long-run average R.
Real traffic IS bursty; idle clients should be allowed to catch up.Why token bucket wins in most interviews: it matches real traffic shape, needs only two numbers of state (tokens, last_refill_ts), and refill is computed lazily on access rather than by a background timer. Use leaky bucket instead only when the downstream genuinely cannot absorb bursts (a third-party API with a hard cap), because leaky bucket smooths output completely at the cost of queueing latency.
| Approach | Latency | Accuracy | Notes |
|---|---|---|---|
| Centralized Redis per request | +1-2ms | exact | Redis in the path of every request; a Redis blip is an outage |
| Local counters, quota divided by N | 0ms | poor | Unfair under uneven load balancing; breaks when N autoscales |
| Two-tier (local + async sync) | ~0ms typical | good | Recommended: local bucket absorbs the common case, syncs to Redis on a batch/threshold |
| Gossip between gateways | 0ms | eventual | Complex, rarely worth it |
The two-tier answer in detail: each gateway holds a local allowance and decrements it locally with zero network cost. It syncs with Redis every N requests or every X milliseconds, reconciling its local view with the global count. Overshoot is bounded by (number of gateways × sync batch size) — a number you can compute and state. This buys you near-zero added latency and removes Redis from the hot path, at the cost of small, bounded inaccuracy. For a 100/min limit, brief overshoot to 105 is fine. For a "1 free trial per account" limit, it is not — so use exact centralized checks for correctness-critical limits and two-tier for traffic-shaping limits. Making that distinction is the senior move.
GET then SET is a read-modify-write race: two gateways both read 5 tokens, both decrement, both write 4, and two requests consumed one token. Redis executes Lua scripts atomically on its single thread, making check-and-decrement one indivisible operation and one round trip.
If Redis is down: failing closed rejects all traffic and turns a limiter outage into a total outage. Failing open lets traffic through unlimited and risks overwhelming backends. The usual answer is fail open on the local bucket — keep enforcing the per-gateway local limit so you're not completely unprotected, serve traffic, and alert loudly. State the choice and the reasoning; interviewers care more about the reasoning than the choice.
Hash by identity, so all state for one key lives on one node and the Lua script is a single-node atomic operation. Cross-slot operations would break atomicity — a good detail.
One enormous customer's key concentrates on one Redis shard. Either give large tenants dedicated shards, or shard their key into sub-buckets (key#0..#9, each with 1/10 the limit) and pick one at random per request.
Per user ID is fairest but requires authentication, so the authentication endpoint itself must be limited by IP. IP limiting is blunt: corporate NAT means thousands of users share an IP, and attackers rotate proxies. The realistic answer is layered limits — IP at the edge, API key at the gateway, user ID at the service, plus per-endpoint overrides for expensive operations.
Possible follow-up questions
Retry-After.Retry-After, self-throttle) but never a substitute — you can't trust the client.