Rate limiting algorithms
Calculate token budgets and refill waits, compare fixed and sliding windows, and choose an atomic limiter policy under distributed failures.
25 min8 steps
By the end you can
- Calculate available tokens and the wait for a request to become eligible
- Compare token bucket, leaky bucket, fixed window and sliding window behavior
- Choose an atomic quota boundary and an explicit failure policy
- Choose a client retry response that avoids amplifying overload
Limit the resource the request consumes
A rate limiter decides whether a request may start. A concurrency limiter bounds work in flight. Pick the one that matches the constrained resource, and a subject (account, key, tenant) and cost per call. IP-only limits punish shared NATs.
Rate limit only
- 100/s still admitted
- In-flight work explodes at 10 s each
Plus concurrency cap
- Bounds active work
- Explicit rejection policy
A token bucket separates burst from sustained rate
Bucket capacity B, refill r/s. Idle time refills only up to B.
Refilled
+15
3 × 5
New balance
19
min(20, 4 + 15)
Loading question…
Compute eligibility without promising a queue
Six tokens at 2 tokens/s from empty: eligible in 3 s. A cost above capacity never passes. Most API limiters reject now and let the caller retry; a shaper queues, with a bound.
0 s
Request arrives, 0 tokens
1 s
2 tokens
2 s
4 tokens
3 s
6 tokens: eligible
Loading question…
Fixed windows have a boundary burst
A fixed window resets at aligned times, so a client can spend two windows back to back. A sliding log is strict but costs memory; sliding counters approximate.
0:59
100 requests
1:00
Counter resets
1:01
100 more: 200 in 2 s
Loading question…
A leaky bucket smooths departure
A leaky bucket here is a bounded queue drained at a fixed rate: smooth, but adds wait. A token bucket allows bursts. Ask whether an algorithm delays, marks or rejects.
Leaky bucket (shaper)
- Smooth output
- Adds waiting
- Expire stale jobs
Token bucket (meter)
- Burst up to B
- Reject immediately
- Fast interactive replies
A distributed balance needs one atomic decision
Read, check and decrement as separate calls lets two callers spend one token. Do refill, check and consume atomically at the quota authority.
Fail-open and fail-closed are product decisions
If the quota store fails: fail-open risks the downstream; fail-closed blocks real users. Decide per product (payments, login, public content).
On a rejection send 429 with Retry-After. Clients back off with jitter and stop at their deadline.
Check your mastery, then compare algorithms
Score 80% or more. State the initial balance and whether rejected work waits or leaves.
Mastery check
5 questions on fresh variants. One attempt each, no time limit. Score 80% or more to master the lesson.
In the sandbox, put a limiter before a service, apply a burst then sustained load, and compare token bucket with fixed window.
Answer this step to continue.