map / coding / rate-limiter

Coding · principle 5 of 6

Rate limiters

A token bucket allows bursts up to its size while enforcing a long-run average rate.

01 · Why it’s true

A rate limiter protects a service by capping how much work each client can send. The token bucket is the classic design: tokens are added at a steady rate R up to a maximum B; each request takes a token, and requests that find the bucket empty are rejected or delayed.

That allows short bursts of up to B requests while keeping the long-run average at R. It needs only two numbers per client — the token count and the last refill time — so it’s cheap. In a fleet of servers, the hard part is keeping counts shared (for example, in a central store) or splitting the limit between servers.

02 · Picture it

refill: R tokens per secondcapacity B = biggest burstrequesttakes 1 tokentoken left → allowedbucket empty → rejected (429)Long-run rate is capped at R; a quiet client can save up to B tokens and spend them inone burst.
refill: R tokens per secondcapacity B = biggest bursteach request takes 1 tokentoken left → allowedbucket empty → 429Long-run rate is capped at R; a quietclient can save up to B tokens andspend them in one burst.
A token bucket: steady refill, bounded bursts.

03 · In the interview

  • A classic coding and design question: implement a rate limiter.
  • Choosing between token bucket, fixed window, and sliding window, and explaining the edge cases.
  • Making it work across many servers.

04 · Practice question

“Implement a rate limiter that allows each user 100 requests per minute with short bursts.”

A strong answer covers

  1. Token bucket per user: capacity 100, refilled at 100 per 60 seconds.
  2. On each request, add tokens for the time elapsed since the last update (capped at capacity); if at least one token remains, take it and allow, otherwise reject with 429.
  3. Store only (tokens, last_update) per user, refilling lazily when a request arrives — no background timer needed.
  4. Across servers: a central store with atomic updates, or split the limit between servers; discuss the latency and accuracy trade-off.