Design a Rate Limiter

A rate limiter sits in front of an API and says "no" to clients that send too much. Every request asks "may this one through?", and the answer must come back within a millisecond or two, from any of dozens of gateway servers, which all have to agree on how many requests each client has made.

Interviewers like it because it is small enough to finish and still touches shared state, atomic updates, races, clocks, and what to do when a dependency dies. The counting algorithms themselves are covered in Rate Limiting; this case study is about building the whole service. It follows the steps in A Framework for Any Design.

#Clarify the problem

"Design a rate limiter" can mean a class in one process or a service for a whole company. Find out which before you say "token bucket".

• Functional: limit requests per API key, per IP and per account, with rules that vary by endpoint and plan; reject excess requests with 429 and say when to retry; let operators change rules without a deploy.
• Non-functional: under 2 ms added at p99; the API stays up if the limiter is down; counts are shared across all gateways, accurate to within a few percent; rule changes apply within about 10 seconds.
• Out of scope: billing, usage dashboards, bot detection beyond simple limits.

#Estimate the scale

Turn the daily number into rates. A day has 86,400 seconds.

• Average: 1 billion ÷ 86,400 ≈ 11,600 requests a second; call it 12,000.
• Peak: assume 3x the average, so 36,000 a second.
• Counter operations: a typical request is checked against two rules (its API key and its IP), so the counter store sees 2 × 36,000 = 72,000 operations a second at peak.

#Define the API

Every response from the API:
  X-RateLimit-Limit: 100        bucket size for the tightest rule
  X-RateLimit-Remaining: 36     tokens left after this request
 
Rejected request:
  429 Too Many Requests
  Retry-After: 1                seconds until a token is available
  body: { "error": "rate_limited", "rule": "key-free-plan", "retry_after_s": 1 }
 
Gateway to counter store, one atomic call per rule:
  take(key, capacity, refill_per_sec, cost = 1)
    -> { allowed, remaining, retry_after_ms }
 
Operators:
  PUT /admin/rules/{rule_id}    body: the rule (see the data model)
  400 if the rule is invalid; gateways pick up changes within 10 s

The decision worth arguing is the status code. 429 means "you, this client, sent too much"; 503 means "we are overloaded". Use 429 for limits, because a well-behaved client reads Retry-After and slows down. Keep 503 for load shedding, when the whole service is struggling regardless of who is asking. Mixing them up makes clients retry at the wrong times.

#Model the data

rule
  rule_id          "key-free-plan"
  match            endpoint pattern and plan, e.g. "/v1/*", plan = free
  key_by           api_key | ip | account
  capacity         100            burst size
  refill_per_sec   10             long-run rate
  on_store_down    open | local | closed
 
counter            key = "rl:{rule_id}:{subject}"   e.g. "rl:key-free-plan:k_8f3a"
  tokens           float, 8 bytes
  last_refill_ms   integer, 8 bytes
  TTL              capacity / refill_per_sec = 100 / 10 = 10 s

Rules are a few hundred records in any durable config store. Gateways poll them into memory every 10 seconds, so no request waits on them.

Counters are the opposite: 20 million records of about 100 bytes, updated on almost every request, needed in about half a millisecond. That calls for an in-memory key-value store (such as Redis) that can run a small script atomically and expire keys. Durability barely matters: losing a counter just gives one client a fresh bucket.

The TTL is a neat trick. A bucket idle for capacity ÷ rate = 10 seconds is full again, and a missing key counts as full, so expiry changes no answer and frees memory.

#High-level design

Run the limiter as a library in every gateway node. A separate limiter service would add a network hop to every request and one more fleet to keep alive. The counter store is split into 4 shards by key, each with a replica.

Step through an allowed request, a rejected burst and a shard dying.

#Deep dives

Interviewers push on four places: the algorithm, the shared counter, store failure, and the key you limit by.

#Choosing the algorithm per rule

Pick the algorithm per rule, by what the rule protects. Rate Limiting explains how each one counts.

Say it like this: "Token bucket for the API limits, because clients legitimately burst when a page loads. A sliding log for login, because the limit is 5 and I want it exact. A daily quota is a fixed window with a 24-hour expiry." What would change my mind: if the backend cannot absorb bursts at all, a leaky bucket that queues requests fits better.

#A shared counter with atomic updates

Twenty gateways each counting alone would let a client spread across them through up to twenty times its limit. So the count lives in one place per key: the shard of the counter store that owns that key, chosen by consistent hashing so adding a shard moves only a small share of keys.

The danger is splitting the check from the update. Here is the race, with one token left and two gateways.

take(key, capacity, rate, cost):
  now = store's own clock, in ms
  tokens, last = read key            (missing key: tokens = capacity, last = now)
  tokens = min(capacity, tokens + (now - last) / 1000 * rate)
  if tokens >= cost:
      tokens = tokens - cost
      allowed = true
  else:
      allowed = false
  write key = (tokens, now), expire after capacity / rate seconds
  return allowed, floor(tokens), time until tokens >= cost

Two details show you have built one. First, the script uses the store's clock, not the gateway's: gateway clocks drift apart by milliseconds, and if A's clock is behind B's, now - last goes negative and the refill math breaks. Second, do not retry a timed-out take. The store may have taken the token before the reply was lost, so a retry would charge the client twice. Treat a timeout as "store down" for that one request.

Say the cost of replication out loud. Each shard copies to its replica asynchronously, so if a primary dies, the last few hundred milliseconds of decrements are lost: a few extra requests, once, which fits "a few percent loose".

#Failing open or closed

The counter store will be unreachable sometimes. Decide in advance, per rule, what the gateway does then.

The arithmetic for the fallback: the free plan refills 10 a second, so each of 20 gateways allows 10 ÷ 20 = 0.5 a second for that key. A client spread evenly gets about 20 × 0.5 = 10 a second in total, the same as normal. That is why on_store_down is a field on the rule, not a global switch.

#Per-user and per-IP rules together

A request can match several rules: the IP rule, the API key rule and an endpoint rule. Check them all, allow only if every one allows, and return the longest Retry-After. Check the cheapest, broadest rule first (per IP) so a flood is rejected before it costs a second store call.

• IP alone is a poor identity. An office or a mobile carrier can put thousands of users behind one address. Use IP for anonymous traffic and floods, and the key or account once known.
• IPv6 needs a prefix. One home is often given a whole block of addresses (commonly a /64), so limit by that prefix, or a single client can rotate through endless addresses.
• Login needs two keys. Limit per IP (one attacker trying many accounts) and per target account (many IPs trying one account). Either alone misses one attack.

#Bottlenecks and failures

At 10x (360,000 requests a second at peak), the counter store sees 720,000 operations a second. At about 50,000 per shard that is roughly 15 shards; run 16. Consistent hashing means going from 4 to 16 moves keys gradually, and a moved key simply starts as a full bucket. The gateways scale by adding nodes, since they hold only rules and a small deny cache.

The first thing to break is usually a hot key: one abusive client sending 50,000 requests a second lands every check on one shard. The local deny cache from the tracer handles this: after the first rejection, that gateway stops asking the store until the next token is due. Add a local pre-limit per IP in each gateway to drop obvious floods before they reach the store at all.

The deny cache does not help a big customer whose plan allows 20,000 requests a second, because those requests are allowed. For such keys, let each gateway take tokens in batches: one call takes 50, and the gateway spends them locally. Store calls drop 50-fold; the cost is that a gateway can hold a few unspent tokens when the limit is hit.

#What a strong answer sounds like

Most candidates know the token bucket. Levels differ on many servers, races and failure.

A weak answer: "We'd make the store highly available so it never goes down." Every dependency goes down; the interviewer wants to hear what you do then.

#Follow-up questions

#How do you limit across several regions?

A store shared across regions puts a round trip of tens of milliseconds on every request. Instead, give each region its own counters and split the limit by each region's share of traffic, or sync regional counts every second and accept a small overshoot.

#How would you limit by cost instead of by request?

Pass cost to the take call: a bulk export takes 10 tokens, a read takes 1. If the cost is only known after the request finishes, take an estimate up front and charge the difference afterwards.

#How do you roll out a new, stricter limit safely?

Run it in shadow mode first: the gateway evaluates the rule and logs who would have been rejected, but lets them through. After a few days of logs you know which customers it hits, and can warn them before enforcing.

#Why not just put the limit in the load balancer?

Many load balancers can limit per IP, a good first layer against floods, but they do not know the API key or plan. Use both layers.

#What to practise next

The counter store here is a small, specialised key-value store. Build a general one, with replication and quorums, in Design a Key-Value Store.