System design primer: design a rate limiter, with real numbers

Most rate limiter answers I hear in mocks are one box on a diagram labelled "rate limiter" and then the candidate moves on. That box is the whole question. Let us do it properly, with numbers. Thanks to Kenji for reviewing the draft.

1. Requirements (spend 5 minutes here)

• Public API behind a gateway. 10 million daily active users.
• Limit: 100 requests per user per minute. Some endpoints (login, OTP) much stricter.
• Peak traffic: 50,000 requests per second across all users.
• Many gateway nodes, so the limit must be shared, not per node.
• The check must add less than 5 ms to a request.
• If the limiter itself fails: fail open for normal reads, fail closed for login and OTP.

Ask about that last point in the interview. It shows you think about failure, and the answer changes per endpoint.

2. Back-of-the-envelope (5 more minutes)

Say 2 million users are active in any given minute.

• Fixed window counter: one key per user per minute. Key around 30 bytes, value 8 bytes, Redis overhead around 50 more. Call it 100 bytes. 2M × 100 B = about 200 MB. Fits one Redis node easily.
• Sliding window log: store every request timestamp in a sorted set. Up to 100 entries per user, and a sorted set entry costs around 60+ bytes in practice. 2M × 100 × 64 B = about 12.8 GB. Ouch.
• Throughput: 50k checks per second. One Redis node handles 100k+ simple operations per second, so one primary works, but with no headroom. Shard by user id across 3 nodes for headroom and failure isolation.

That 12.8 GB number is the moment a good candidate changes their mind about the design. Interviewers love seeing the maths change your decision.

3. The algorithms

Fixed window counter

INCR a key like rl:user123:202609241405, set EXPIRE 60 on first use, reject when the count passes 100. Simple and cheap. The problem: a user sends 100 requests at 14:05:59 and 100 more at 14:06:00. That is 200 requests in 2 seconds, and both windows are happy.

Sliding window log

ZADD the timestamp, ZREMRANGEBYSCORE everything older than 60 seconds, ZCARD to count. Exact. And we just calculated why it is too expensive at this scale.

Sliding window counter

Keep counters for the current and previous minute, and weight the previous one by how much of it still overlaps the last 60 seconds. Example: we are 40 seconds into the current minute. Previous minute had 80 requests, current has 30. Estimate = 30 + 80 × (20 / 60) = 56.7. Under 100, allowed. Two small counters per user, roughly 400 MB total, and no boundary burst. Approximate, but very good in practice.

Token bucket

Each user has a bucket with capacity 100 that refills at 100/60 tokens per second. A request takes a token. It allows short bursts up to the capacity, which most real APIs want. You store two numbers per user: tokens and last refill time. The catch: read, refill, take and write must happen atomically, or two gateway nodes will both see "1 token left" and both allow the request.

4. The Redis part people hand-wave

Atomic means a Lua script. Redis runs the whole script without interleaving other commands.

-- KEYS[1] = bucket key, e.g. rl:{user123}
-- ARGV: capacity, refill rate (tokens/sec), now (ms), cost
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])

local data = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(data[1]) or capacity
local ts = tonumber(data[2]) or now

local elapsed = math.max(0, now - ts) / 1000
tokens = math.min(capacity, tokens + elapsed * rate)

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

redis.call('HSET', key, 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', key, math.ceil(capacity / rate * 1000) * 2)
return { allowed, tostring(tokens) }

Notes on this script:

• Redis converts Lua numbers to integers when returning them, which is why tokens goes back as a string.
• now comes from the gateway, so clock skew between gateways matters. You can call redis.call('TIME') inside the script instead, so every gateway shares one clock.
• PEXPIRE removes idle users. After capacity / rate seconds an idle bucket is full again anyway, so the key carries no information.

5. Where it runs and what the client sees

• As middleware in the API gateway, before any business logic.
• Rejected requests get 429 Too Many Requests with a Retry-After header, plus remaining-quota headers so well-behaved clients can slow down by themselves.
• A Redis round trip inside the same zone is under a millisecond, well inside our 5 ms budget.
• Log every 429 with the key and the rule that fired. You will need it the first time a big customer complains.

6. How I would split 45 minutes

1. Requirements: 5 minutes
2. Numbers: 5 minutes
3. Algorithm choice with trade-offs: 10 minutes
4. Deep dive (atomicity, the script, sharding): 15 minutes
5. Failure modes and monitoring: 5 minutes
6. Buffer for the interviewer's follow-ups: 5 minutes

Another mock worth watching for how the candidate scopes requirements before designing anything:

For further reading, the system-design-primer repository on GitHub is still the best free starting point.

Per request: one Redis call, about 1 ms. Memory: around 200 to 400 MB for 2 million active users with counters or buckets, versus about 12.8 GB with a sliding log.