CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 3 of 7 · 3 min read

Token bucket and leaky bucket

Two bucket pictures: one that allows bursts and one that smooths traffic.

Think of a jar of coins. Each request needs one coin. Coins are dropped into the jar at a steady pace, but the jar holds only so many. A visitor who has been away finds a full jar and can spend several coins at once.

That is the token bucket.

Token bucket

A token bucket holds tokens up to a fixed capacity. Tokens are added at a steady rate. Each request takes one token. With no token, the request is refused.

Example: capacity 4, refill 2 tokens per second. A request needs 1 token. A full bucket allows 4 requests at once.

The book names its two parameters: the bucket size (the largest number of tokens) and the refill rate (tokens added per second). Amazon and Stripe use this algorithm, according to the book. The number of buckets depends on the rules. Different endpoints may have separate buckets for each user. If a user may post once per second, add 150 friends a day and like 5 posts per second, that is 3 buckets per user. Limits by IP address need one bucket per address, and a limit on the whole system needs one global bucket.

A worked example. Capacity 4, refill 2 per second, the bucket starts full.

Time Event Tokens before Result Tokens after
0.0 s 6 requests arrive together 4 4 pass, 2 refused 0
1.0 s 1 second has passed, 2 tokens added 2 1 request arrives, passes 1
2.0 s 2 more tokens added 3 3 requests arrive, all pass 0
3.0 s 2 tokens added 2 no request 2
5.0 s 4 tokens added, capped at 4 4 5 requests arrive, 4 pass, 1 refused 0

The long-run speed is 2 per second, and the burst is up to 4. The bucket allows short bursts.

Strengths, from the book: easy to build, small in memory and tolerant of bursts. Its weakness is that the two parameters are hard to tune.

Now the other bucket. Think of a funnel with a small hole at the bottom. Liquid can be poured in fast, but it drips out at a fixed pace. If the funnel is full, the extra spills.

Leaky bucket

A leaky bucket is a queue of fixed size. Requests join the queue if there is room, and are taken out and processed at a fixed rate. If the queue is full, new requests are refused.

Example: a queue of 3 with an outflow of 1 request per second.

A queue where the first in is the first out is called FIFO. The book gives the two parameters: the bucket size (the queue length) and the outflow rate. Shopify uses it, the book says.

A worked example. Queue size 3, outflow 1 per second, 5 requests arrive at time 0.

  • 3 join the queue. 2 are refused.
  • Request 1 is processed at 1 s, request 2 at 2 s and request 3 at 3 s.
  • The service sees a steady 1 request per second, however spiky the arrivals.

Strengths, from the book: small in memory, and a steady output, which suits a service that needs a stable rate. Weaknesses: a burst fills the queue with old requests, so newer ones may be refused while the old wait; and the two parameters are hard to tune.

Token bucket Leaky bucket
Allows bursts Yes, up to the bucket size No, output is smoothed
Output rate Varies, up to the burst Fixed
Delays requests No, passes or refuses Yes, requests wait in the queue
Good for APIs where short bursts are fine Downstream services that need an even flow

Check yourself:

  • A token bucket has capacity 5 and refills 1 per second. It starts full. How many of 8 simultaneous requests pass?
  • What does a leaky bucket do to a burst that a token bucket would pass?