Design rate limiting for an API gateway

This question tests whether you can turn a vague requirement — "don't let clients overwhelm us" — into concrete mechanics: which algorithm counts, where the count lives, and how the count stays consistent across many machines.

The mental model: a rate limiter is a counter with a reset policy; the hard part is where the counter lives.

Start with the algorithm. The three real options: fixed window, sliding window, token bucket. Fixed window counts requests per wall-clock bucket — simple, but a burst at a bucket boundary can slip through 2× the limit. Sliding window smooths that at memory cost. Token bucket is the practical default: a bucket holds up to capacity tokens, refilled at rate per second, each request consuming one token. Bursts up to capacity are allowed; steady state is rate.

allow(request):
  now = clock.now()
  tokens = min(capacity, tokens + (now - lastRefill) * rate)
  lastRefill = now
  if tokens >= 1: tokens -= 1; return ALLOW
  return DENY

The interesting part is state placement. A single-machine limiter uses in-memory counters — cheap and fast, but useless behind a load balancer: ten nodes each enforce the limit independently, so a 100 rps limit permits 1000 rps. A distributed limiter keeps the counter in Redis — INCR with expiry — but adds a network round trip per request and makes Redis a single point of failure. The middle ground is sharded counters: each node runs the algorithm on its own slice, and the effective limit is per-shard — slightly imprecise, operationally simple, very common in production.

The gateway layer is where this pays off: limits enforced before traffic reaches services, keyed per API key, IP, or tenant, with a uniform 429 plus Retry-After so well-behaved clients can back off instead of hammering.

Tradeoffs and edge cases: token buckets allow bursts by design — set capacity close to rate if you don't want them. Distributed counters face clock-skew in the refill math; use monotonic time. And the limiter must never take down your own API: if Redis dies, fail open with degraded limits and a cooldown, because a limiter that 500s is an outage you caused yourself.