Token Bucket Rate Limiting

Foundations

A rate limiter decides, per caller, whether a request may proceed. A token bucket holds up to capacity tokens and refills at rate tokens per second; each request spends one token, and a request that finds the bucket empty is denied. Capacity bounds the burst a caller can send at once, and the refill rate bounds the long-run average.

No timer refills idle buckets. Each check computes the refill lazily: add the elapsed time since the last check times rate, capped at capacity, then try to spend one token. So each caller costs two stored numbers, tokens and the last check time, and one atomic update per request. A denied caller is told how long until the next token arrives.

Take capacity 2 and a refill of 1 token per second. Requests at 0.0 and 0.1 spend both tokens, and one at 0.2 is denied, about 0.8 seconds before a token returns. By 1.5 the bucket has refilled to 1.5 tokens, so a request passes and 0.5 remains.

• Requirements

  Each worked system starts from a scoped list of verbs and numbers.

  Open lesson

• Caching

  The read path sits behind cache-aside.

  Open lesson

Case Scenario

To see how a token bucket allows bursts but caps the average, consider per-key API limits like GitHub's or Stripe's: each API key may call the service 100 times a minute, and an over-limit caller receives 429 with a hint about when to retry. One atomic refill-and-spend in a shared store decides each request.

An API key may be allowed 100 calls per minute, but real callers do not arrive at perfectly even intervals. The service should accept a legitimate short burst, reject sustained excess with a useful retry time, and keep one caller from consuming the expensive handler. Each decision must take one atomic round trip to a shared counter store, never a query to the primary database.