Design an API Rate Limiter, stage 2 of 10: decide
Choose the algorithm
Good clients are bursty: a dashboard loads and fires 20 requests at once, then nothing for a minute. Bad clients are sustained: a loop that never stops. You want to allow the first and stop the second, with little memory per key across ~50,000 keys.
System so far· 4 parts
Select a component to see what it is responsible for and which state it owns.
- 1API clients → Load balancer: Requests with API key
- 2Load balancer → API instances: Round-robin across instances
- 3API instances → Postgres: Admitted requests; plan lookups (cached)
What you need to know
There are four common rate-limiting algorithms. They differ in what they remember per key:
Algorithm State per key Enforces Fixed window one counter N per calendar window Sliding log every accepted timestamp N in any window-length span Sliding window counter two counters an estimate of N in the last window Token bucket tokens and a timestamp a burst of B, then a steady rate r Try each pattern below. Watch the most in any 10 s figure for each algorithm: that is how much traffic the limiter really lets through in a short span, whatever the plan says.
Same requests, four limiters. The limit is 5 requests per 10 seconds. Pick a pattern or click the timeline to add requests. Requests (10)Fixed window10 through · most in any 10 s: 10Sliding log5 through · most in any 10 s: 5Sliding window counter6 through · most in any 10 s: 6Token bucket6 through · most in any 10 s: 615.0s- Fixed window:
- Counts per calendar window; the count resets at 10 s.
- Sliding log:
- Keeps every accepted timestamp from the last 10 s.
- Sliding window counter:
- Weights the previous window's count by how much of it still overlaps: an estimate, slightly off either way.
- Token bucket:
- Holds 5 tokens and refills one every 2 s, so a full bucket plus refills can admit a little over 5 in a 10 s span.
Check
With the burst at the boundary, which algorithm lets through twice the limit in under four seconds?A token bucket has two parameters. The capacity B is how big a burst the key may send at once. The refill rate r is the sustained rate. Each request takes a token; tokens refill continuously at r up to B.
When the bucket is empty, the time until the next token is
(1 − tokens) ÷ r. That number is what a rejection can send back asRetry-After.Work it out
A sliding log stores one 8-byte timestamp per accepted request. An Enterprise key allowed 100,000 requests a minute keeps how many kilobytes of timestamps?Check
An honest dashboard fires 20 requests on page load, then nothing for a minute. The plan is 600 a minute. Under a token bucket with r = 10/s, what decides whether the dashboard gets 429s?