Section 7: One Timestamp per Key - Deep Dive: Rate Limiting Algorithms
Executive Summary: The candidate names two walls: the algorithm that runs inside every load balancer, and how 500 of them share one quota. This section takes the first: five algorithms compared, the fixed-window boundary problem, exact token-bucket and GCRA math, then clocks and worker contention. The result is a token bucket stored as one 64-bit timestamp, with its rate set by a leased share.
"Where would you like to go deeper?"
You: "Two walls: the decision that runs 30,000 times a second on every LB in about 2 µs with no network, and how 500 LBs share Contoso's 10,000 req/s. What I lease has to fit the local algorithm, so I'll start with the algorithm."
The Five Candidates
The decision must be O(1), allow bursts deliberately, and accept a new rate every second without losing state. Against Contoso's rule (10,000 req/s, burst 10,000):
| Algorithm | State per key | Worst burst | Hot-path cost | Verdict |
|---|---|---|---|---|
| Fixed window | count + window id, 16 B | 20,000 in ~200 ms at a boundary | one increment | Rejected |
| Sliding log | a timestamp per request: 10,000 × 8 B = 80 KB | exact | prune O(N) | Rejected |
| Sliding window counter | two counts, 16 B | approximate (assumes the previous window was uniform) | two reads, one add | Kept for per-minute contracts |
| Leaky bucket as a queue | waiting requests | none, it smooths | adds waiting time at the LB | Rejected at the LB |
| Token bucket (GCRA) | one timestamp, 8 B | exactly the configured burst | one compare-and-swap | Chosen |
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson