Back to System design

Rate Limiting: Token Bucket, Leaky Bucket, Sliding Window

medium
Scale: O(1) per check (Redis Lua); ~1M checks/s at scale Storage: O(active keys) — one counter per (identity, window) Cloudflare, Stripe, Twitter
FundamentalsAPI DesignReliability

Rate limiting means refusing requests when a caller sends too many. "100 requests per minute per user" is a rate limit.

ScaleO(1) per check (Redis Lua); ~1M checks/s at scale
StorageO(active keys) — one counter per (identity, window)

Key Concepts

1
The algorithms are small. The hard part is where you keep the count when you have twenty servers.
2
Token bucket. Each user has a bucket that refills at a steady rate, up to a maximum. Every request spends one token. No tokens, no request.
Token bucket.
3
Because the bucket can hold a few tokens, short bursts are allowed — which matches how apps really behave. An app opening six connections on startup is not abusing you. You store two numbers per user: how many tokens are left, and when you last refilled.
4
Leaky bucket. Requests queue and drain at a fixed rate, no matter how fast they arrive. This smooths traffic instead of allowing bursts. It suits a fragile system downstream that cannot take a spike.
Leaky bucket.
5
Fixed window. Count requests per clock minute, reset at the top of each minute. Simple, and wrong at the edges: 100 requests at 10:00:59 and 100 more at 10:01:00 is 200 requests in one second, and neither minute broke the limit.
Fixed window.
6
Sliding window log. Store the timestamp of every request and count the ones inside the last minute. Exact, and expensive: a limit of 1,000 per hour means storing 1,000 timestamps per user.
Sliding window log.
7
Sliding window counter. Keep one counter per window and blend the previous window into the current one. Three quarters of the way through a minute, count 25% of last minute's total plus this minute's. It is approximate and close enough, which is why most production limiters use it.
Sliding window counter.
8
Now the real problem: where does the count live?
Now the real problem: where does the count live?
9
Keeping counts in each server's memory is free and wrong. With 20 servers, a "100 per minute" limit becomes 2,000 per minute, because each server counts to 100 on its own.
10
Keeping counts in Redis is correct and adds a network round trip to every request. That is about 1 ms. On a 200 ms request, fine. On a 3 ms request, not fine.
11
The middle option is to give each server a share — 100 divided by 20 servers — and reconcile every few seconds. You accept some inaccuracy at the boundary to keep the check local.
12
Decide what happens when Redis is down. Do you let traffic through or reject it? For abuse prevention, reject. For a paid API, let it through — turning away paying customers to enforce a quota is the worse outcome. Either way, decide it deliberately rather than discovering it during an incident.
Decide what happens when Redis is down.
13
What you return matters. Send 429 with a Retry-After header, plus headers saying the limit, how many remain and when it resets. Without those, well-behaved clients cannot slow down properly, and they retry all at once.
What you return matters.429Retry-After
14
What the interviewer is probing.
What the interviewer is probing.
15
1. "Limit users to 100 requests a minute." Probing: whether you ask what a minute means. Stalls: a counter that resets on the clock minute. Moves up: naming the boundary burst — 200 requests in one second — before being shown it.
1. "Limit users to 100 requests a minute."
16
2. "You have 20 servers." Probing: whether you noticed local counting breaks. Stalls: "Each server counts to 100." Moves up: that gives 20 times the limit; shared store, or a per-server share with reconciliation.
2. "You have 20 servers."
17
3. "Redis is down." Probing: a deliberate failure policy. Stalls: "It will not be." Moves up: fail open or fail closed as a product decision, different for abuse and for paid APIs.
3. "Redis is down."
18
4. "How much memory?" Probing: why the log version is rare. Stalls: "Not much." Moves up: about 820 MB of counters for 10 million users, against about 80 GB for full logs.
4. "How much memory?"
19
5. "What does the client see?" Probing: whether a limit is a contract or a wall. Stalls: "A 429." Moves up: 429 plus Retry-After and the limit headers, with jitter so everyone does not retry at the same instant.
5. "What does the client see?"Retry-After

Related Problems

CAP Theorem and PACELCeasyLoad Balancing: L4 vs L7, Algorithms, Health CheckseasyCaching Strategies: Cache-aside, Write-through, Write-backeasySQL vs NoSQL: When to Pick WhicheasySharding Strategies: Range, Hash, Directory, Geomedium

Components

  • Limiter middleware in the API gateway or sidecar.
  • Redis cluster (or local cache + periodic global sync).
  • Config service for per-route, per-tier quotas (dynamic, hot-reloadable).
  • 429 response builder with Retry-After / RateLimit headers.
  • Metrics: rejections per route, per tenant; hot-tenant alerts.
  • Bypass / allowlist for internal services.
  • Audit log for rejected requests (for support triage).

Memory, worked 

  Users to track                                 10,000,000
  ---------------------------------------------------------
  Token bucket / sliding counter
    Key (user id)                                    ~16 B
    Value (count + timestamp)                          16 B
    Redis overhead per key                            ~50 B
    Per user                                          ~82 B
    10M users                                        ~820 MB
  Sliding window log, 1,000 requests/hour limit
    Timestamp per request                                8 B
    Worst case per user      1,000 x 8 B        =      8 KB
    10M users                                   =     80 GB

That single comparison is the reason sliding-window-log is rare in
production and sliding-window-counter is common: a 100x memory difference
for an accuracy difference most APIs cannot measure.

  Redis throughput
    Requests per second to limit                  50,000
    Operations per check (GET+SET, or one Lua)     1-2
    Redis single node capacity            ~100,000 ops/s
    Headroom                                  comfortable,
                                              until it is not:
                                              shard by user id.

Distributed placement 

  Local counters only
    Cost: none. Latency: none.
    Wrong by: the server count. 20 servers x 100/min = 2,000/min.
    Use when: the limit is a coarse safety valve, not a contract.
  Central store (Redis) on every request
    Correct within one round trip.
    Adds: ~1 ms in-region, plus a hard dependency on the store being up.
    Failure policy must be stated: fail-open (let traffic through) or
    fail-closed (reject)? For abuse prevention, fail-closed; for a paid API,
    fail-open, because rejecting paying customers to enforce a quota is the
    worse outcome.
  Per-server allowance with reconciliation
    Each server gets limit / server_count, syncing every few seconds.
    Accurate in aggregate, approximate at the boundary.
    Handles server count changes badly unless the allowance is recomputed
    on membership change -- say that before you are asked.
  Where to enforce
    Edge/CDN: cheapest, stops traffic before it costs you anything.
    API gateway: sees the authenticated identity, which is usually the key
    you actually want to limit on.
    Service: last resort, most expensive, but the only place that knows the
    cost of the specific operation.

Failure modes in production

Synchronised retry storm
Symptom: rejected clients return together each minute; load spikes on
the boundary.
Cause: Retry-After with an identical value for everyone.
Fix: jitter the value per client.

  Limit applied to the wrong key
    Symptom: an office or a mobile carrier NAT gets throttled as one user.
    Cause: limiting by IP.
    Fix: limit by authenticated identity where available; keep IP limits as
    a coarse outer layer with a much higher ceiling.
  Redis hot key on a shared quota
    Symptom: one tenant's traffic saturates a single Redis shard.
    Cause: a per-tenant key that concentrates all traffic for the busiest
    tenant.
    Fix: shard the counter into N sub-keys summed on read, or give large
    tenants their own allowance.
  Clock skew across limiter nodes
    Symptom: windows disagree; a client is limited on one node and not
    another.
    Cause: local wall clocks.
    Fix: derive the window from the store's time, not the caller's.