Design a rate limiter

For this problem, we'll design a distributed, server-side rate limiter in front of a public API, enforcing rules like "10 requests a second per API key, bursts of 20" across a fleet of 50 gateways. We'll leave network-layer DDoS protection and monthly billing quotas for later. Interviewers like this one because the single-machine version fits in ten lines, and then every real constraint (50 gateways, one shared count, a 10 ms budget, a Redis node that can die) turns a choice into a trade-off you have to defend.

011. Understand the problem

Functional requirements

Here's the scope I'd agree on in the first five minutes. The core requirements are:

1. The system should identify each caller (API key, user ID or IP) and allow or reject each request against a shared count.
2. The system should reject over-limit requests with 429 and tell the client when to retry.
3. The system should support different limits per caller and per endpoint (login stricter than reads, paid plans looser than free).
4. Operators should be able to change limits without redeploying the gateways.

At this point, ask your interviewer: "Is this protecting our API, or pacing us toward someone else's? Who calls it: anonymous browsers, logged-in users, partners with keys? How bad is 5% over the limit?" A limiter guarding a login form against password guessing and one metering a partner API have very different answers for accuracy and failure.

Non-functional requirements

1. Low latency. The check adds under 10 ms at p99, ideally 1 to 2 ms. It's on the path of every single request, so this number shapes the design.
2. Scale. About 1 million requests a second at peak, from 100 million daily users.
3. Availability over perfect accuracy. If the limiter is unhealthy, the API keeps serving. A few extra requests getting through is better than turning everyone away.
4. Close is good enough. A user who briefly gets 105 requests instead of 100 is not an incident. Login is the exception: there, exact matters more than available.

022. The set up

Plan the approach

We'll build the design one functional requirement at a time, starting with where the check runs. Then we'll use the non-functional requirements to drive the deep dives: the algorithm, correctness across gateways, latency at a million checks a second, failure, rule changes, and multiple regions.

Core entities

Three entities do all the work:

• Rule: what it matches (plan, path), what it counts by (API key, user, IP) and the allowance (rate and burst).
• Client key: the identity we count against, such as user:42, key:k_live_9, or an IPv6 /64 prefix.
• Bucket: the live state for one client key under one rule: tokens left and the time of the last refill.

API

The limiter's own interface is one internal call. The interesting API is the response the client sees, because a well-behaved client can only slow down if we tell it how.

# internal: made by the gateway middleware on every request
allow(clientKey="key:k_live_9", rule="free-api", cost=1) -> { allowed, remaining, retryAfterS }

# allowed: pass through, and advertise the budget
HTTP/1.1 200 OK
RateLimit-Policy: "free-api";q=20;w=2
RateLimit: "free-api";r=14;t=1

# rejected: say no, and say when
HTTP/1.1 429 Too Many Requests
Retry-After: 2
RateLimit: "free-api";r=0;t=2

429 and the optional Retry-After come from RFC 6585; Retry-After can be seconds or a date (RFC 9110). The RateLimit and RateLimit-Policy fields are from an IETF draft, not an RFC yet; GitHub and many others send x-ratelimit-limit, x-ratelimit-remaining and x-ratelimit-reset instead (GitHub Docs). Either is fine, as long as the 429 carries Retry-After.

Back-of-envelope estimates

All inputs are assumptions to confirm with your interviewer; the arithmetic is ours and rounded.

Notice what this tells us. Memory is small and buckets expire when idle, so this is a throughput and latency problem, not a storage problem. And one Redis node is out at 1M calls a second: we need a sharded cluster from day one.

033. High-level design

Let's start with the question that decides everything else: where does the check run?

In the client is a courtesy, not a control: anyone with curl skips it. In each application server feels natural, but a load balancer spreads one user across many servers and each counts only what it sees; with 10 servers and a limit of 100, a user gets close to 1,000 through. In the API gateway is where I'd put it. Every request already passes through it, it knows who the caller is after authentication, and a 429 costs the services nothing. Envoy, NGINX, Kong and the cloud API gateways all ship a limiter here for that reason (Envoy, Amazon API Gateway).

Now let's satisfy the requirements one at a time. Each picture is the previous one plus a few new boxes, drawn in colour; what we already had turns gray.

1) Identify the caller and allow or reject each request

We need:

• API gateway fleet: about 50 stateless instances behind a load balancer. Authenticates and routes.
• Limiter middleware: runs inside each gateway, before routing. Builds the client key and asks for a decision.
• Redis: one shared place for the counts, so all 50 gateways agree.
• Services: whatever is behind the gateway.

1. A client sends a request; the load balancer hands it to any gateway.
2. The limiter middleware builds the client key: API key for partners, user ID from the token for logged-in users, IP (a /64 prefix for IPv6) for anonymous traffic.
3. It asks Redis whether that key has budget left, and takes one unit if so.
4. If allowed, the gateway forwards the request to the service.

Many corporate users share one IP behind a NAT, which is why IP is the key of last resort. Most real systems layer rules: a loose per-IP limit to slow floods, then a precise per-user or per-key limit for fairness. A request must pass every rule that matches.

2) Reject over-limit requests with 429, and say when to retry

No new boxes. We only add the "no" path, and it's the cheapest response in the system.

1. A request arrives.
2. The limiter's check finds the bucket empty and gets back "retry in 2 s".
3. The gateway answers 429 Too Many Requests immediately, with Retry-After and the remaining-quota headers.

Send the quota headers on successful responses too. A good client watches remaining fall and slows down before it ever sees a 429.

3) Support different limits per caller and per endpoint

The free plan gets 10 a second, enterprise gets 1,000, and login gets 6 a minute per IP no matter who you are. We add one box:

• Rule cache: the full rule table, held in memory in every gateway. Rules are read on every request, so they can't live behind a network call.

1. The limiter matches the request (plan, path, method) against the rules in memory, and gets back the key type, rate, burst and failure mode for each matching rule.
2. It checks one bucket per matching rule in Redis.

- id: free-api
  match: { plan: free, path: "/v1/*" }
  key: api_key
  rate_per_second: 10
  burst: 20

- id: login
  match: { path: "/v1/login" }
  key: ip
  rate_per_second: 0.1     # 6 per minute
  burst: 5
  on_store_failure: closed

4) Let operators change limits without a redeploy

A partner launches and needs a temporary increase; an attack needs an emergency limit. Redeploying 50 gateways for either is too slow. We add:

• Rules API: where operators edit rules. Validates them and keeps every version.
• etcd: a small, strongly consistent config store with watches.

1. The operator edits a rule through the Rules API, which validates it (no rate: 0 on /* by accident).
2. The API writes the new version to etcd.
3. Every gateway holds a watch on the rules prefix; etcd pushes the change, and each gateway swaps its in-memory table within about a second.

If etcd is unreachable, gateways keep serving with the last rules they had. That's the property you want from a control plane: when it's down, nothing on the data path notices.

044. Deep dives

The board above is correct on a whiteboard. Now we push it against the non-functional requirements. For a senior candidate I expect the algorithm, atomicity and the failure mode; for staff, I expect you to bring up sharding limits, rule rollout and regions on your own.

1) Which algorithm should we count with?

All 200, in about one second. That's the classic flaw, and a good way into the four algorithms you should know.

2) How does the count stay correct across 50 gateways?

-- KEYS[1] = bucket key, ARGV[1] = rate (tokens/s), ARGV[2] = capacity, ARGV[3] = cost
local rate, cap, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local t   = redis.call('TIME')                      -- Redis clock, not the gateway's
local now = tonumber(t[1]) + tonumber(t[2]) / 1e6

local b      = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1]) or cap                 -- a new key starts full
local ts     = tonumber(b[2]) or now
tokens = math.min(cap, tokens + (now - ts) * rate)   -- refill for the time that passed

local allowed, retry = 0, 0
if tokens >= cost then tokens = tokens - cost; allowed = 1
else retry = math.ceil((cost - tokens) / rate) end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(cap / rate) + 1)   -- idle buckets disappear
return { allowed, math.floor(tokens), retry }

3) How do we serve a million checks a second inside 10 ms?

4) What happens when Redis is slow or down?

This is the question that separates a design from a sketch.

5) How do we roll out a rule change safely?

We already push rules by watch. The deep question is what stops a bad rule from limiting your biggest customer on launch day.

6) What if we run in three regions?

055. The final design

Here's everything on one board: clients, edge, the gateway fleet with its limiter, the Redis Cluster, the services, and the control plane. The numbered steps follow one request, then one rule change.

Let's trace it:

1. A request reaches the WAF / CDN, which drops volumetric floods before they reach us.
2. The load balancer hands it to any of the 50 gateways.
3. The limiter builds the client key and matches the rules in the rule cache, in memory.
4. It runs one EVALSHA on the Redis primary that owns the key's slot. If Redis is slow, it falls back to the local buckets.
5. Allowed: the request goes to the service, with quota headers on the response.
6. Rejected: 429 with Retry-After, straight from the gateway.
7. Separately, the on-call engineer edits a rule through the Rules API, which validates and versions it.
8. etcd's watch pushes it to every gateway's rule cache within about a second.

066. What interviewers look for by level

Mid-level

• Limiter in the gateway, with a reason.
• Identifying callers sensibly (key, user, IP).
• One algorithm explained correctly, usually token bucket or sliding window.
• A shared counter in Redis, and a 429 with Retry-After.

Senior

• Atomic check-and-take with a Lua script, and why not a lock.
• A clear algorithm trade-off table.
• Sharding by key, with sizing, pooled connections and no replica reads.
• A deliberate failure mode, different for login.

Staff+

• Accuracy treated as a tunable cost: local pre-limits, blocked-until caches, token leases.
• Rule rollout: validation, shadow mode, kill switches.
• Multi-region shares rebalanced from usage.
• Observability for "why was I limited?", and how the limiter fits with load shedding and client backoff.

077. Follow-up questions

What if requests have very different costs?

Charge more than one token. A search that fans out to ten shards, a bulk export, or an LLM call measured in tokens takes cost tokens instead of one; the script above already takes a cost argument. Many GraphQL APIs score each query before running it and charge that score.

What if we need 10 million checks a second?

Ten times the shards works, because keys don't interact. The better answer cuts calls: each gateway leases a batch of tokens for a hot key (say 10 at a time), spends them locally and returns to Redis only when it runs out. Envoy's quota-based mode shares a global limit this way, from periodic load reports (Envoy). You trade a little accuracy for a big drop in Redis traffic.

What if a customer says they're being limited unfairly?

You need an answer in minutes. Log every rejection with key, rule, remaining tokens and gateway, and chart limited requests per key. Most cases turn out to be a shared office IP behind one NAT, or a retry loop in the customer's own code, and the chart shows which.

What if clients retry the moment they get a 429?

Then your limiter amplifies the problem. Return Retry-After on every 429, make your own SDKs honour it, and fall back to exponential backoff with jitter so thousands of clients don't retry in lockstep (Amazon Builders' Library). Only auto-retry idempotent requests, or POSTs with an idempotency key.

What if we need to limit concurrent requests, not requests per second?

That's a different counter: add when a request starts, remove when it ends, reject over the limit. Stripe runs one beside its rate limiter for expensive endpoints (Stripe). The trap is a crashed request that never removes itself, so store each in-flight request in a sorted set scored by start time and clear entries older than the request timeout.

088. How to say it in the interview

When I ask this question, I'm listening for three things: do you know where the check runs, can you make it atomic without making it slow, and do you have a plan for when it breaks.