Rate Limiting

Token Bucket and Leaky Bucket

Token bucket is the workhorse. A bucket holds up to B tokens and refills at r tokens per second; each request consumes a token and is rejected (or queued) when the bucket is empty. The two parameters map directly to product language: r is the sustained rate, B is the burst allowance. With r = 10/s and B = 100, a client averaging 10 requests per second is never limited and can burst 100 at once after idling, matching real traffic, which is bursty, without permitting a sustained flood. Implementation is tiny: store tokens and last-refill timestamp per key, and compute the refill lazily on each request. This is what AWS API Gateway and Stripe describe for their limits, and Nginx's limit_req is the same family.

Leaky bucket enforces a perfectly smooth output rate: requests enter a queue (the bucket) and drain at a constant rate; arrivals that overflow the queue are dropped. Where token bucket admits bursts immediately, leaky bucket shapes them into a steady stream, adding queueing delay. It suits downstream systems that genuinely need smooth inflow, calling a fragile third-party API at exactly its contracted rate, or pacing writes to a database, more than user-facing request limiting, where making a burst of 50 requests wait in line feels worse than serving them instantly from banked tokens.

Interview shorthand: token bucket limits the average rate while allowing configurable bursts; leaky bucket limits the instantaneous output rate and smooths bursts into delay.

Fixed and Sliding Windows

Fixed window counting is the simplest scheme: keep a counter per key per window (user 42, minute 10:04), increment on each request, reject above the limit, and let the counter expire. One Redis INCR plus EXPIRE per request. Its flaw is the boundary burst: with a limit of 100 per minute, a client can send 100 requests at 10:04:59 and 100 more at 10:05:01, 200 requests in two seconds, double the intended rate, because the counter reset.

Sliding window log fixes this exactly: store a timestamp per request (a Redis sorted set), and on each request drop entries older than the window and count the remainder. Precise, but memory scales with request volume per key, storing 10,000 timestamps for a high-limit key is wasteful.

Sliding window counter is the standard compromise, used by Cloudflare: keep fixed counters for the current and previous windows and estimate the rolling count as current + previous * (overlap fraction). If the previous minute saw 80 requests and we are 30 percent into the current minute which has 20, the estimate is 20 + 80 * 0.7 = 76. It assumes uniform distribution within the previous window, an approximation Cloudflare measured as accurate enough in practice, and costs two counters per key regardless of traffic. For most systems the practical choice is sliding window counter or token bucket; fixed window is acceptable when the boundary burst is tolerable.

Distributed Rate Limiting

One server's in-memory bucket stops working the moment a load balancer spreads a client across 20 instances, each instance would allow the full limit, multiplying it by 20. The common fix is centralized state in Redis: counters or bucket state keyed by client, updated atomically. Because a get-compute-set sequence from multiple app servers races, the update must be atomic, which in practice means a Lua script executed inside Redis that reads the bucket, refills by elapsed time, decrements, and returns allow or deny in one step. A Redis node handles on the order of 100k such ops per second; beyond that you shard limiter keys across a Redis cluster, which is clean because each client's state lives on one shard.

The centralized approach adds a network round trip (commonly 1 ms in-region) and a dependency: decide explicitly whether the limiter fails open (Redis down means allow traffic, protecting availability) or fails closed (deny, protecting the backend), most user-facing systems fail open with an alert.

The alternative trades precision for speed: local limiting with synchronization. Each node enforces limit/N locally, or nodes keep local counters and asynchronously sync through Redis or a gossip layer, letting the effective global limit overshoot briefly. Envoy supports both patterns, a local token-bucket filter and a global rate limit service (gRPC calls to a Redis-backed limiter). A hybrid is common and worth naming: a generous local limit as a cheap first-pass shield against extreme floods, then the precise global check in Redis.

Client Experience and 429 Handling

When rejecting, return HTTP 429 Too Many Requests with headers clients can act on: Retry-After (seconds until it is worth retrying) and the X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset trio popularized by GitHub, with an IETF draft standardizing RateLimit headers. Well-behaved SDKs read these and pace themselves, Stripe's client libraries retry 429s automatically with exponential backoff.

Clients must retry with exponential backoff plus jitter: 1s, 2s, 4s, 8s with a random offset. Without jitter, a thousand clients rejected at the same instant retry at the same instants, producing synchronized waves, the thundering herd, that keep the service pinned. This mirrors what TCP and every cloud SDK do internally.

Design the limiting dimensions and tiers explicitly: per API key or user for fairness and pricing (free tier 100 req/min, paid 10,000), per IP for unauthenticated abuse, per endpoint because an expensive search costs more than a status check, sometimes charging weighted costs against one budget, and a global concurrency cap as a load-shedding backstop. Distinguish rate limiting (per-client fairness and abuse control) from load shedding (dropping excess work under overload regardless of client) since both return 429 or 503 but answer different questions. Also decide reject versus throttle: user-facing APIs reject fast with 429; internal batch pipelines often prefer to delay, leaky-bucket style, rather than fail.

Tradeoffs