Rate Limiting (Token Bucket/Leaky Bucket/Sliding Window)
Overview
Rate limiting caps how many requests a client can make in a given time window, protecting a service from overload, abuse, and runaway cost. The token-bucket and leaky-bucket algorithms are the two classic mechanisms for enforcing those limits.
Key Concepts
The token-bucket algorithm keeps a bucket that refills with tokens at a fixed rate up to a maximum capacity. Each request removes one token; if the bucket is empty the request is rejected, typically with an HTTP 429 response. Because a full bucket can be spent all at once, token bucket permits short bursts up to its capacity while still bounding the long-run average rate.
The leaky-bucket algorithm treats the bucket as a queue that drains (leaks) at a fixed rate. Incoming requests are added to the queue and processed at that constant rate; if the queue is full, new requests are dropped. This shapes bursty input into a smooth, steady output stream. Rate limiting is most often enforced at the API gateway so every backend service is protected in one place.
Trade-offs
| Aspect | Token bucket | Leaky bucket |
|---|---|---|
| Model | Tokens added at a fixed rate; requests spend tokens | Requests queue and leak at a fixed rate |
| Bursts | Allows bursts up to bucket capacity | Smooths bursts into steady outflow |
| Output rate | Variable (up to the burst size) | Constant |
| Overflow behavior | Reject when no tokens remain | Drop when the queue is full |
| State kept | Token count plus a timestamp | Queue of pending requests |
| Best for | APIs that tolerate short bursts | Traffic shaping to a steady rate |
Prefer token bucket when short bursts are acceptable, which fits most public APIs. Prefer leaky bucket when a downstream dependency needs a smooth, constant arrival rate. In a horizontally scaled service the counter must be shared across nodes - often in a fast store like Redis - so the limit is global rather than per-instance; otherwise each node enforces its own limit and the effective ceiling multiplies.
Interview Tips
- State where you enforce the limit (usually the gateway) and what you return when it trips (429 with a
Retry-Afterheader). - Pick token bucket when bursts are fine and leaky bucket when the downstream needs a constant rate.
- For a horizontally scaled service, mention a shared store like Redis so the limit applies globally rather than per node.
Summary
- Rate limiting caps request rate to protect services from overload, abuse, and runaway cost.
- Token bucket refills tokens at a fixed rate and allows bursts up to the bucket capacity.
- Leaky bucket drains a queue at a constant rate, smoothing bursts into steady output.
- Enforce limits at the API gateway and return HTTP 429 when the limit is exceeded.
- In a distributed service, keep counters in a shared store so limits apply globally.