Rate Limiting Algorithms — Token Bucket, Sliding Window & Distributed
Four algorithms, one job: cap the request rate
A rate limiter protects a service from abuse and overload by rejecting (or queuing) requests above a threshold. The algorithm choice trades burst tolerance, memory, and precision — and one of them has a famous bug.
The algorithms
| Algorithm | How | Trade-off |
|---|---|---|
| Fixed window | count per clock window (e.g. per minute) | simplest, least memory — but the boundary burst bug (below) |
| Sliding window log | store each request's timestamp; count those in the last N sec | exact, but memory grows with traffic |
| Sliding window counter | weighted blend of current + previous window | near-exact, O(1) memory — the common production pick |
| Token bucket | refill tokens at rate R, cap B; each request spends one | allows bursts up to B, sustains R (diagram) |
| Leaky bucket | queue drains at fixed rate | smooths output to a constant rate; adds queueing latency |
The fixed-window boundary bug
Limit = 100/min. A client sends 100 at 11:00:59 and 100 more at 11:01:00 — both windows pass, but that's 200 requests in one second. Sliding-window counter fixes it by weighting the previous window.
Distributed rate limiting (the real challenge)
With many app servers, the counter must be shared or each server enforces its own limit (N× too
lenient). Keep the counter in Redis and make the check-and-decrement atomic —
otherwise two servers read "99", both allow, and you've exceeded the limit (the counter++ race again):
-- atomic token-bucket check in one round trip (Redis Lua)
-- KEYS[1]=bucket ARGV: now, rate, capacity, cost
local tokens = refill(redis.call('HGET', KEYS[1], 'tokens'), now, rate, capacity)
if tokens < cost then return 0 end -- 429
redis.call('HSET', KEYS[1], 'tokens', tokens - cost)
return 1 -- allowed
-- simpler fixed-window: INCR key; if == 1 then EXPIRE key window; allow if <= limitTakeaways
- Token bucket = burst up to capacity, sustain the refill rate; leaky bucket smooths to a constant rate.
- Fixed window is cheap but has the 2×-boundary burst; sliding-window counter is the O(1) production fix.
- Distributed: a shared Redis counter with an atomic check (Lua/INCR) — or you re-create the lost-update race.
Re-authored for this guide; token-bucket diagram hand-authored as SVG. Follows ByteByteGo and the Stripe/ Cloudflare rate-limiting write-ups. See also: Caching, Redis, and (Concurrency) Race Conditions.
🤖 Don't fully get this? Learn it with Claude
Stuck on Rate Limiting Algorithms — Token Bucket, Sliding Window & Distributed? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Build the mental picture, not memorization.
I just read a lesson on **Rate Limiting Algorithms — Token Bucket, Sliding Window & Distributed** (System Design) and want to truly understand it. Explain Rate Limiting Algorithms — Token Bucket, Sliding Window & Distributed from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Socratic — adapts to where you're stuck.
Teach me **Rate Limiting Algorithms — Token Bucket, Sliding Window & Distributed** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Active recall exposes what you missed.
Quiz me on **Rate Limiting Algorithms — Token Bucket, Sliding Window & Distributed** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Intuition + hook + flashcards for long-term memory.
Help me remember **Rate Limiting Algorithms — Token Bucket, Sliding Window & Distributed** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.