Part 3 of 6 · 2 min read
The algorithms
How each one counts.
The book lists five algorithms. Four are built here. The leaking bucket is the fifth, and it is a queue that is drained at a fixed rate, so it controls the speed of processing and not only the admission of requests.
| Algorithm | How it counts | Good at | Weak at |
|---|---|---|---|
| Token bucket | A bucket holds up to a set number of tokens, refilled at a steady rate. Each request takes one token | Allows short bursts, uses little memory, easy | Two settings to tune: size and refill rate |
| Fixed window counter | One counter per fixed time window. Each request adds one. Over the limit is refused until the next window | Simple and cheap | A burst at the edge of two windows can pass twice the limit |
| Sliding window log | Keeps the timestamp of each accepted request. Old timestamps are dropped, and the rest are counted | Exact in any rolling window | Uses much memory when the limit is high |
| Sliding window counter | Combines the current window count and a share of the previous window count | Cheap and close to exact | An estimate, since it assumes requests were evenly spread |
The edge problem of the fixed window is worth seeing in numbers. The book's example allows 5 requests per minute. Five requests at the end of one minute and five at the start of the next are both inside their windows, so all ten pass, yet in the one-minute span around the boundary ten requests got through. The sliding methods do not have this flaw.
The sliding window counter uses a formula. Take a limit of 7 per minute, with 5 hits last minute and 3 so far this minute. A new request arriving 30 per cent into this minute sees 70 per cent of last minute's window still in range. The estimate is 3 + 5 x 0.7 = 6.5, rounded down to 6, and 6 is under 7, so the request passes.
Time must come from an injected clock (Level 5, module 5):
interface Clock { long nowMillis(); }
A test sets the fake clock to any time. Without it, tests of a one-minute window would have to wait one minute.
Check yourself: 1. Which algorithm allows bursts on purpose? 2. What goes wrong at the edge of two fixed windows? 3. What does the sliding window counter assume?