Token Bucket vs Leaky Bucket
Two ways to limit a rate: a token bucket that allows bursts and a leaky bucket that smooths them, compared with window counters, and how to run them across many servers.
Overview
A rate limiter decides whether a request may go ahead, based on how many requests the same caller (a user, an API key, an IP address) has made recently. It protects a service from overload and keeps one caller from using capacity meant for everyone.
The two classic algorithms answer one question differently: what to do with a burst, a sudden group of requests above the average rate. A token bucket lets a burst through at once, up to a set size, and then holds the caller to the average. A leaky bucket used as a queue lets requests out at a steady pace no matter how they arrive, so a burst waits instead. Window counters (fixed, sliding log, sliding counter) are a third family that counts requests per time window.
All of them are easy on one server. The real design work is running one limit across many servers, choosing what the client sees when it is limited, and deciding what happens when the limiter itself fails.
What you will be able to do
- Explain the token bucket and both forms of the leaky bucket, and trace one burst through each.
- Say why a fixed window can let through twice its limit, and how a sliding window fixes it.
- Choose an algorithm from the needs of the caller and of the protected service.
- Build a shared limit with an atomic Redis script, and say what it costs.
- Describe the response a limited client gets, and a layered set of limits like Stripe's.
Key concepts
- Token bucket
- Leaky bucket as a meter
- Leaky bucket as a queue
- Burst and sustained rate
- Fixed window
- Sliding window log and counter
- Distributed limits in Redis
- 429 and Retry-After
- Concurrency limits
Interview questions
- Compare the token bucket and the leaky bucket. When would you use each?
- What is wrong with a fixed window counter, and how do sliding windows fix it?
- How do you enforce one rate limit across many servers?
- What should a client receive when it is rate limited, and where should limits be placed?
- How did Stripe layer its rate limiters, and why more than one?
- How can limits adapt to the health of the service instead of being fixed?
- Design rate limiting for a public API with free and paid plans.
Sign up free to read the full topic
More System Design topics
Start free on Cariara · Coding problems · System design studio