System design interview: design a rate limiter

1. Clarify the requirements

"Design a rate limiter" can mean a library, a service or a gateway feature. Pin down who is limited, by what key, and how exactly.

• Functional: limit requests per API key, user or IP address; different rules per endpoint and plan (say 100 a minute free, 1,000 paid); reject excess with 429 and say when to retry.
• Non-functional: add a few milliseconds at most, stay available when parts fail, and enforce one limit across all gateway nodes, not one per node. Small overshoot in a burst is usually fine.
• Out of scope unless asked: network-level DDoS protection (that happens before HTTP), monthly billing quotas, and queuing excess work for later.

2. Estimate the scale

The limiter runs on every request, so its cost scales with total traffic. The figures are assumed round numbers.

So per-key state must be a few numbers, not a list of timestamps, and the counter store must be sharded and in the gateways' zone.

3. Define the API

# Internal: one call per matching rule
check(key="apikey:k_123", rule="search-paid", cost=1)
  -> { allowed: true, limit: 1000, remaining: 742, resetAfterMs: 31000 }

# Public: what an over-limit client receives
HTTP/1.1 429 Too Many Requests
Retry-After: 31
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 31

Retry-After is standard HTTP; the X-RateLimit-* headers are only a convention, and APIs differ on whether the reset is seconds remaining or a Unix timestamp, so document your choice. Send them on successful responses too, so clients can slow down early.

4. Sketch the data model

No background job adds tokens. Each check refills lazily, tokens = min(capacity, tokens + elapsed x rate), so an expired key can safely be treated as a full bucket.

5. Choose the algorithm

This is the decision the interviewer most wants to hear. Name the options, then pick one.

A worked sliding window counter: limit 100 a minute, 80 requests last minute, 30 so far this minute, 15 seconds in. The sliding window still covers 75% of the previous minute, so the estimate is 30 + 80 x 0.75 = 90, and the request is allowed.

A sound default is token bucket for per-client API limits, because real clients are bursty. Use a sliding window counter when the contract reads "N per minute", and a leaky bucket queue for outbound calls to a partner API that only accepts a steady rate. (A leaky bucket used as a meter rather than a queue is equivalent to a token bucket.)

6. The architecture

1. 1IdentifyPick the most specific key available: API key, then user ID, then IP address. Only trust X-Forwarded-For when it was set by your own proxies.
2. 2CheckRun one script per matching rule on the shard that owns the key, with a timeout of a few milliseconds.
3. 3AnswerForward and attach the headers, or return 429 with Retry-After set to the time until enough tokens refill.

Where it lives. The gateway suits per-client limits: one enforcement point, before the backend does any work. Services add limits where cost varies by request. Client-side throttling saves wasted calls, but clients can be modified, so it never enforces anything.

7. Make it correct across many servers

The race. If a gateway reads the bucket, decides, then writes it back, two gateways can both read tokens = 1, both allow, and both write 0. The fix is one atomic step: Redis runs a Lua script without interleaving other commands, so the whole check is one round trip and one indivisible operation.

-- KEYS[1]: bucket key   ARGV: capacity, refill per second, cost
local cap  = tonumber(ARGV[1])
local rate = tonumber(ARGV[2]) / 1000            -- tokens per ms
local cost = tonumber(ARGV[3])
local t    = redis.call("TIME")                  -- one clock per shard
local now  = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local b      = redis.call("HMGET", KEYS[1], "tokens", "ts")
local tokens = tonumber(b[1]) or cap             -- missing key = full bucket
local ts     = tonumber(b[2]) or now
tokens = math.min(cap, tokens + math.max(0, now - ts) * rate)

local allowed = 0
if tokens >= cost then tokens = tokens - cost; allowed = 1 end
redis.call("HSET", KEYS[1], "tokens", tokens, "ts", now)
redis.call("PEXPIRE", KEYS[1], math.ceil(cap / rate))
return { allowed, math.floor(tokens) }

• Clock skew. If each gateway passes its own timestamp, one whose clock runs ahead refills buckets early. Reading TIME inside the script gives every check on a key the same clock. For a fixed window, set the expiry in the same script as INCR, or a crash between the two leaves a key that never expires.
• Sharding. Spread keys with Redis Cluster's hash slots (see sharding). A script must touch keys in one slot, so a sliding window counter puts the shared part of its two window keys in a hash tag, rl:{search:k_123}:<window>.
• Hot keys. One huge customer can saturate a shard. Let each gateway lease a batch of tokens (say 50) and spend them locally: Redis calls for that key drop 50-fold, and overshoot is bounded by the lease size times the number of gateways.
• Cache denials. A key denied with Retry-After: 30 can be rejected from local memory for 30 seconds, so abusive clients cost almost nothing.
• Multi-region. A global counter costs a cross-region round trip per request. Either split each limit across regions, or count locally and exchange counts every second or so, accepting overshoot of about one sync interval of traffic. That is consistency and CAP in practice: latency and availability over an exact global count.

8. What breaks, and what you do about it

9. Trade-offs to discuss

• Fail open or fail closed. Failing open keeps the product working but removes protection exactly when something is wrong; failing closed turns a limiter outage into a full outage. Choose per rule: open for general API traffic, closed for logins, password resets, one-time codes and payouts, where a missing limit is a security hole.
• Exact or cheap. A sliding log is exact and memory-hungry; counters and buckets are approximate and tiny. Token leases cut load further but loosen the limit.
• Reject or delay. A 429 pushes the problem to the client; a queue absorbs bursts but adds latency, which suits background work better than interactive requests.

10. How to talk through it in the interview

• Compare at least three algorithms; the fixed-window boundary is the classic probe.
• Raise the race condition yourself before the interviewer does.
• State the failure policy per rule, not one answer for everything.

Practicing this design with Natively

Practice the walk-through as a mock interview, with a friend asking the follow-ups or with you reading the prompt aloud. Natively transcribes the conversation live and can suggest talking points for each question as it comes in; comparing them with what you said is a quick way to spot gaps such as clock skew or the fail-open policy. If you sketch the bucket and gateway layout, a screenshot of the diagram can be captured and explained. The transcript and notes stay available afterwards, so you can see which algorithm comparison took too long.