Token Bucket

A token bucket controls how fast a client, an API caller, or a network flow is allowed to do work. You picture a bucket that holds at most B tokens. Tokens are dropped into the bucket at a constant refill rate of R tokens per second. Every request must take one token (or a number of tokens proportional to its cost) before it runs.

If a token is available, the request proceeds and the token is removed. If the bucket is empty, the request is either rejected immediately, retried later, or held in a queue, depending on how the system is configured.

The two numbers fully define the behavior. The refill rate R sets the sustained average throughput. The capacity B sets how large a burst you tolerate after an idle period. A bucket with R = 100 tokens/second and B = 100 lets a client send up to 100 requests in one instant if it has been quiet, then settle to 100 per second after that.

Real implementations almost never run a background timer that adds tokens. Instead they store two values per client: the current token count and the timestamp of the last update. When a request arrives, the code computes how much time has passed, multiplies by the refill rate, adds that many tokens up to the capacity ceiling, and only then checks whether a token can be spent. This lazy refill makes each check O(1) and avoids one timer per client.

Concretely the math is: tokens = min(capacity, tokens + (now - last_refill) * rate); last_refill = now. If tokens is at least the request cost, subtract the cost and allow it; otherwise reject. Storing just a counter and a timestamp means the whole limiter for one key fits in a few bytes, which is why it scales to millions of keys in Redis.

In a distributed system the state lives in a shared store so all servers see the same count. Redis is the common choice, with the read-modify-write done atomically inside a Lua script or via the INCR and EXPIRE commands so two concurrent requests cannot both spend the last token.

Reach for token bucket when real traffic is bursty but you still want a hard average cap. A user who opens an app and fires ten requests in one second is normal; token bucket absorbs that burst from saved-up tokens and then throttles them to the steady rate. This is why it is the default for public APIs.

Compare it to two neighbors. Leaky bucket smooths output to a perfectly constant rate and never allows bursts, which is good for traffic shaping but punishes legitimate spikes. A fixed window counter is simpler but suffers a boundary problem where a client can send a full window's worth at the end of one window and the start of the next, briefly doubling the intended rate. Token bucket avoids both issues.

The trade-offs to watch: in a distributed setup every request needs a round trip to the shared store, so the limiter can become a hotspot and adds latency. Clock skew between nodes can corrupt the time-based refill. And tuning matters: a large capacity allows bigger bursts that may still overwhelm a fragile backend, so the burst size should match what your downstream can actually survive.

Stripe rate limits its API with a token bucket and returns HTTP 429 with a Retry-After header when you run dry. A typical live-mode account gets on the order of 100 read or write requests per second, and because of the bucket you can briefly exceed the steady rate after an idle stretch without being blocked.

AWS uses token buckets all over its platform. EC2 API request throttling, DynamoDB's older provisioned-capacity model with burst credits, and gp2 EBS volume IOPS bursting are all token-bucket designs: you accumulate credits while idle and spend them during spikes.

On the client side, a well-behaved caller pairs token bucket with exponential backoff. When it sees a 429, it waits the suggested time, then retries, which keeps it inside the server's bucket instead of hammering an already-empty one.