Compare the token bucket and leaky bucket algorithms for limiting a single client's request rate. How does each one handle a burst of traffic that arrives all at once, and when would you pick one over the other?

## The question each one answers Both **token bucket** and **leaky bucket** are per-key algorithms for enforcing an average rate while giving different answers to the question "what happens to a sudden burst of requests?" Understanding the mechanism of each is easiest by tracing through what state they keep and how a request is evaluated against it. ## Token bucket — credit that accumulates Token bucket keeps two numbers per key: the current token count and a refill rate. The bucket has a maximum capacity `C` (say, 20 tokens) and refills at rate `R` tokens per second (say, 10/sec), either continuously or in discrete ticks. When a request arrives, the limiter: 1. computes how many tokens have accrued since the last check (elapsed time × R, capped at C), 2. adds them to the bucket, 3. checks whether at least one token is available. If yes, it removes one token and admits the request; if no, it rejects the request (429) or, in a shaping variant, queues it until a token appears. The key property is that **unused capacity accumulates**: a client idle for 2 seconds at a 10/sec refill rate has up to 20 tokens waiting (capped by C), so it can legitimately fire 20 requests instantly before being throttled to the steady 10/sec rate. This makes token bucket a rate limiter that tolerates bursts up to a cap. ## Leaky bucket — a queue that drains at a fixed rate Leaky bucket instead models a fixed-size queue (capacity `C`) that a background process drains at a constant rate `R`, one request at a time, into the backend. An incoming request is enqueued if there is room; if the queue is full, the request is rejected. - Unlike token bucket, there is **no accumulation** of unused "credit" — the queue can only ever be empty, partially full, or full. - Its enforced output rate is always exactly R regardless of how bursty the input was, because the drain rate is fixed. - A request that is queued behind others waits, adding latency. The defining trait of leaky bucket is that output is smoothed to a constant rate, at the cost of introducing queueing delay for anything arriving faster than R. ## Why both exist The reason both exist is that real client traffic is **bursty by nature**: - a mobile app reconnecting after a network blip - a batch job kicking off - a user refreshing a dashboard and a naive limiter that simply counts requests in a window either punishes normal bursts (too strict) or lets sustained abuse through between window boundaries (too loose). Token bucket exists to explicitly permit "you can spend saved-up capacity in a burst, but not sustain a higher rate than R afterward," which matches how legitimate clients behave and is why it is the default choice in most production API gateways (AWS API Gateway, Stripe, many service meshes) and is also the algorithm underlying Linux's tc traffic shaping. Leaky bucket exists where the operator needs a hard ceiling on instantaneous output rate regardless of input pattern — classic uses are network traffic shaping into a fixed-bandwidth uplink, or protecting a downstream system that genuinely cannot handle any burst at all, only a steady drip. ## The trade-off The trade-off is **burst tolerance versus rate uniformity**. - Token bucket's burst allowance is a feature for absorbing legitimate spiky usage without rejecting requests, but it is also a weakness from a pure protection standpoint: a client can still momentarily hit the backend at up to C requests instantaneously, which must be sized so the backend can absorb it. - Leaky bucket guarantees the backend never sees more than R requests per unit time, safer for fragile downstreams, but it either adds latency (queueing variant) or rejects legitimate bursts outright (no-queue variant), and sizing the queue itself becomes a new tuning problem — too small and it behaves almost like immediate rejection, too large and it hides backpressure by making clients wait a long time instead of failing fast. ## Failure modes Failure modes differ accordingly. - A **misconfigured token bucket** with too large a capacity C effectively becomes "no limit for the first C requests," which attackers exploit by staying just under threshold, refilling, then bursting again — a pattern indistinguishable from legitimate reconnect bursts unless C is tuned tightly. - A **misconfigured leaky bucket queue** that's too deep silently converts rate limiting into unbounded latency, which from the client's perspective looks like the service hanging rather than failing fast — often worse for propagating timeouts up a call chain than a clean 429 would be.