Rate Limiting

One-liner: Cap how many requests a client can make per window to protect capacity and enforce fairness; token bucket is the default answer.

Say this#

SAY THIS

Token bucket — bucket refills at rate r up to capacity b; each request takes a token; allows bursts up to b. (AWS, Stripe, Nginx limit_req variant.)
Leaky bucket — requests queue and drain at a fixed rate; smooths output, no bursts.
Fixed window counter — count per calendar window (per minute); cheap but 2x burst at window edges.
Sliding window log — store timestamps of each request; exact but memory-heavy.
Sliding window counter — weighted blend of current and previous fixed windows; cheap and nearly exact (Cloudflare's approach).
Throttling vs shedding — reject (429) vs queue/delay.
429 Too Many Requests + Retry-After — the response; also X-RateLimit-Limit/Remaining/Reset headers.
Keys — per user, per API key, per IP, per endpoint, per tenant; global vs per-node limits.
Distributed limiter — shared counters in Redis (INCR + EXPIRE, Lua script for atomicity) or Redis Cell.
Local + global — approximate per-node limits with periodic sync to reduce Redis traffic.
Backpressure / load shedding — adaptive limits based on queue depth or latency.
Quota — long-window limit (per day/month) vs rate limit (per second).

How it works#

Token bucket in Redis (atomic Lua):

TEXT

tokens = min(capacity, tokens + (now - last) * rate)if tokens >= 1: tokens -= 1; allow  else: deny, Retry-After = (1 - tokens)/ratestore tokens,last with TTLtokens = min(capacity, tokens + (now - last) * rate)
if tokens >= 1: tokens -= 1; allow  else: deny, Retry-After = (1 - tokens)/rate
store tokens,last with TTL

Sliding window counter: count = prev_window_count * (1 - elapsed_fraction) + curr_window_count; allow if ≤ limit.

Placement:

TEXT

client -> CDN/WAF (per-IP, DDoS) -> API gateway (per key, per route; Redis) -> service (per tenant, per resource)client -> CDN/WAF (per-IP, DDoS) -> API gateway (per key, per route; Redis) -> service (per tenant, per resource)

Enforce at the gateway so services don't duplicate it; use Redis with a Lua script so check-and-decrement is atomic.
Return 429 with Retry-After; clients back off exponentially with jitter.
Make limits visible via headers; document them.
Fail open or closed when Redis is down? Usually fail open with a local fallback limiter.

Trade-offs#

Choice	Pro	Con
Token bucket	Allows bursts, simple, O(1) memory	Burst can still hurt if b is large
Leaky bucket	Perfectly smooth egress	Adds latency; queue can overflow
Fixed window	Trivial, cheap	2x burst at boundaries
Sliding log	Exact	O(requests) memory per key
Sliding counter	Nearly exact, O(1)	Approximation assumes uniform distribution
Centralized Redis	Global accuracy	Extra hop per request; Redis is a dependency
Per-node local	No network	Limit × node count drift; uneven LB makes it worse

Numbers#

Redis INCR-based limiter: ~0.2-1 ms added per request; single Redis node sustains ~100k ops/s order of magnitude.
Fixed window worst-case burst: 2x the limit in a span shorter than the window.
Typical public API limits: GitHub 5,000 req/h per authenticated user; Stripe ~100 req/s in live mode; Twitter/X per-15-minute windows.
HTTP status: 429; include Retry-After in seconds.

Say this#

How it works#

Trade-offs#

Numbers#

In the interview#