Design a Rate Limiter for 10M Users

Rate limiting is a favourite interview question because it looks like an algorithms problem and is actually a distributed-state problem. Anyone can describe a token bucket. The signal is in how you keep twenty application instances agreeing on one user's remaining quota without adding a network round trip to every single request.

Requirements before algorithms

Six questions, and each one changes the design:

1. What is the limit key? User ID, API key, IP, tenant, endpoint, or a combination. IP-based limiting punishes everyone behind a corporate NAT; user-based limiting does not work for unauthenticated endpoints like login — which is exactly where you most need it. Usually you need several limiters at once.
2. What is the limit? "100 requests per minute" and "6,000 per hour" behave completely differently under bursts.
3. Are bursts allowed? A client that saves quota all minute and spends it in one second is fine for some APIs and disastrous for others.
4. How accurate must it be? Occasionally letting 105 through instead of 100 is usually fine; for billing or an expensive AI endpoint it may not be.
5. Do different tiers get different limits? Free versus paid means the limit is data, looked up per request, not a constant.
6. What happens when the limiter itself is unavailable? The question people forget, and the one with the biggest blast radius.

10M users, 5% concurrently active   = 500,000 active users
Average 5 requests/sec each         = 2.5M rate-limit decisions/sec

Every decision must be:
  - fast: < 1 ms added latency (it is on every request)
  - correct across all instances
  - cheap: 2.5M Redis round trips/sec is far too many

That last constraint is what forces local pre-filtering.
State size: 500k keys × ~100 B ≈ 50 MB — memory is not the problem.

The five algorithms

Fixed window counter

Count requests in the current clock minute; reset at the boundary. Trivial, one counter, and wrong at boundaries: a client can send 100 requests at 10:00:59 and 100 more at 10:01:00 — 200 in one second while never exceeding "100 per minute."

key = "rl:{user}:{minute}"
INCR key ; EXPIRE key 60      → allow if value <= limit

Sliding window log

Store a timestamp per request, drop those older than the window, count what remains. Perfectly accurate, no boundary artefact, and memory grows with the limit — 10,000 requests per hour means 10,000 timestamps per user. Accurate but expensive.

Sliding window counter

The practical compromise: keep the current and previous fixed-window counts, and weight the previous one by how much of it still overlaps the sliding window.

Limit 100/min. Now = 10:01:15, so 75% of the window lies in 10:01,
25% in 10:00.

  previous window (10:00) count = 80
  current  window (10:01) count = 30

  estimate = 30 + 80 × 0.25 = 50  →  allow

Two counters per key, no boundary spike, small bounded error.
This is what most production limiters actually use.

Token bucket

A bucket holds up to B tokens and refills at R tokens per second; each request takes one. Bursts up to the bucket size are allowed, sustained rate is capped at R, and it needs only two numbers per key (token count and last refill time). The best default for public APIs, because real clients are bursty and the burst allowance is explicit rather than accidental.

Leaky bucket

A queue drained at a fixed rate. Smooths output completely — useful when you are protecting something that cannot tolerate bursts at all, like a downstream partner API with a hard contractual rate — at the cost of added latency, since requests wait rather than fail.

Choosing one

The actual hard part: shared state

With one server, an in-memory map is a correct rate limiter. With twenty servers behind a load balancer, twenty in-memory maps means the effective limit is twenty times what you promised — and it drifts as you autoscale.

Promised: 100 req/min per user
20 instances × 100 = 2,000 req/min actually allowed

Worse: the number changes with autoscaling, so your published API
limit silently depends on your deployment size.

The naive alternative — divide by instance count (5 each) — fails
because the load balancer does not distribute one user's requests
evenly. A user hitting one instance is limited to 5 while 95 of
their quota sits unused on other instances.

So the state must be shared, and the shared operation must be atomic. Read-then-write against Redis has the same race as the payment bug in duplicate payments: two instances both read 99, both allow, and you are at 101.

An atomic Redis implementation

A Lua script runs atomically on the Redis shard, so the entire check-and-consume is one indivisible operation. This is the reference implementation worth memorising.

-- KEYS[1] = rate limit key, e.g. rl:user:8817:search
-- ARGV = capacity, refill_per_sec, now_ms, cost
local capacity = tonumber(ARGV[1])
local refill   = tonumber(ARGV[2])
local now      = tonumber(ARGV[3])
local cost     = tonumber(ARGV[4])

local state  = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1])
local ts     = tonumber(state[2])

if tokens == nil then
  tokens = capacity
  ts = now
end

-- refill for elapsed time, capped at capacity
local elapsed = math.max(0, now - ts) / 1000.0
tokens = math.min(capacity, tokens + elapsed * refill)

local allowed = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
end

redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
-- expire well after a full refill so idle keys disappear
redis.call('PEXPIRE', KEYS[1], math.ceil((capacity / refill) * 2000))

local retry_after = 0
if allowed == 0 then
  retry_after = math.ceil(((cost - tokens) / refill) * 1000)
end
return { allowed, math.floor(tokens), retry_after }

Operational points that matter as much as the script:

• Use the server's clock, not the caller's. Pass redis.call('TIME') or a single trusted source; clock skew across instances otherwise corrupts the refill maths.
• One key, one shard. A limiter key must not span slots, so keep all state for a key in one hash. In Redis Cluster this happens naturally per key.
• Cost can vary. Charging an expensive endpoint 10 tokens and a cheap one 1 gives you weighted limiting with no extra machinery — very useful for AI or search endpoints.
• Do not replicate for correctness. Redis replication is asynchronous, so a failover can lose recent counter state. That is acceptable — the worst case is a brief window of extra allowance — but do not design as if it were strongly consistent.

Local pre-filtering at scale

2.5M Redis calls per second for limit decisions is both expensive and a new single point of failure. Two standard reductions:

• Local token leases. An instance fetches a small batch of tokens from Redis (say 10) and serves them from memory, refetching when exhausted. Redis traffic drops ~10x, at the cost of a small over-allowance when many instances hold unused leases. Tune the batch to trade accuracy for round trips.
• Local hard-block cache. Once Redis says a key is over its limit, cache that verdict locally for a second or two. Abusive clients — the ones generating most of your limiter load — are then rejected with zero network calls. This is the highest-value optimisation, because traffic is dominated by the clients you are blocking.

Layer 1  CDN / WAF        crude per-IP flood protection, free, absorbs attacks
Layer 2  API gateway      per-API-key limits, before any business logic runs
Layer 3  Service          per-user, per-endpoint, cost-weighted, tier-aware
Layer 4  Downstream       per-dependency concurrency caps (bulkheads)

Cheapest rejection wins. Never let a flood reach layer 3.

Where to enforce it

Enforce as early as the information allows. IP-level flood protection belongs at the edge, where it costs you nothing. Per-API-key limits belong at the gateway, before your application spends a database connection on the request. Per-user, tier-aware, cost-weighted limits need application context, so they live in the service — but by then the volume should already be much smaller.

Rate limiting is also not the same as concurrency limiting, and you usually want both. Rate limits protect you from too many requests over time; concurrency limits (bulkheads) protect you from too many simultaneous requests to one slow dependency, which is the failure mode in what happens when 10M users hit your API and the reason for the bulkhead pattern.

Responding correctly

HTTP/1.1 429 Too Many Requests
Retry-After: 3
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 3
Content-Type: application/json

{ "error": "rate_limit_exceeded",
  "message": "Too many requests. Retry in 3 seconds.",
  "retry_after_seconds": 3 }

• Send the limit headers on successful responses too, so well-behaved clients can self-throttle before they ever get a 429.
• 429, not 403. 403 means "never allowed"; 429 means "not right now." Clients and SDKs treat them very differently.
• Do not retry a 429 immediately. Honour Retry-After, and use exponential backoff with jitter — synchronised retries after a limit event are their own thundering herd.
• Log rejections with the key and rule so you can tell an attack from a limit set too low. Most "we are under attack" reports are a misconfigured limit.

Fail open or fail closed

Redis is unavailable. Do you allow everything or reject everything? There is no universally right answer, which is why it is a good interview question — the point is to decide deliberately, per limiter.

The middle option is usually right: if Redis is gone, fall back to per-instance in-memory limits with a proportionally reduced quota. You lose precision but keep a ceiling, so an outage of the limiter cannot become an outage of the service or an open door.

How to answer this in an interview

"I'd start with the key and the requirement: per user, per API key or per IP —
 usually several limiters layered — and whether bursts are allowed, because
 that picks the algorithm. I'd default to token bucket: two numbers per key,
 and the burst allowance is an explicit parameter rather than an accident of
 window alignment. If strict per-minute accuracy were required, sliding window
 counter instead.

 The real problem is distributed state. Per-instance counters mean twenty
 instances allow twenty times the published limit, and dividing by instance
 count fails because the load balancer doesn't spread one user evenly. So state
 goes in Redis, and the check-and-consume must be one atomic Lua script —
 read-then-write has the same race as a non-idempotent write.

 At 2.5M decisions/sec I can't do a Redis round trip per request, so instances
 lease small batches of tokens locally, and once a key is over its limit I cache
 that verdict locally for a second — abusive clients then cost zero network
 calls, which is most of the traffic.

 I'd enforce in layers: per-IP at the edge, per-key at the gateway, per-user and
 cost-weighted in the service. Return 429 with Retry-After and RateLimit
 headers on every response, not just rejections.

 And I'd decide failure behaviour explicitly: degrade to local per-instance
 limits if Redis is down — imprecise but still a ceiling — except for login and
 payments, where I'd fail closed."

Summary

• Pick the key and burst requirement before the algorithm; token bucket is the best default.
• Per-instance counters multiply your published limit by your instance count.
• Shared state in Redis, with check-and-consume in one atomic Lua script.
• Local token leases and cached block verdicts remove most Redis round trips.
• Enforce in layers — edge, gateway, service — so the cheapest rejection wins.
• Return 429 with Retry-After, and send limit headers on success too.
• Decide fail-open versus fail-closed per limiter; degrading to local limits is the usual best answer.

Part of Top 10 System Design Interview Questions.