System Design HLD-19.03
Design a rate limiter service
Design a distributed rate limiter: where it sits, shared counters in Redis, atomic Lua scripts, failing open or closed, and limits across regions.
The problem
An API serves thousands of customers. One of them ships a bug that calls you in a tight loop, another runs a batch job at midnight, and a third is a scraper. Without limits, any one of them can take capacity from everyone else. A rate limiter decides, for every request, whether this client is over its allowance, and rejects the excess quickly and cheaply with 429 Too Many Requests.
On one server this is a dictionary of counters. The design problem starts when you have fifty gateway servers in three regions: the counters must be shared so that a client cannot get fifty times its limit by spreading requests, the check must add almost no latency, concurrent requests must not race past the limit, and the limiter itself must never become the reason the API is down.
Requirements
Functional
- Limit requests per identity: API key, user id, or IP address for anonymous traffic.
- Rules per plan and per endpoint, for example 100 requests per second for the paid plan and 5 per second on the expensive
/searchendpoint. - Allow short bursts above the steady rate.
- Rejected requests get 429 with headers saying the limit, what remains and when to retry.
- Rules change without redeploying gateways.
Non-functional
- Scale: 500,000 requests per second at peak across all gateways, 10 million active identities.
- Latency: the check adds under 2 ms at p99.
- Accuracy: within a few percent of the limit; brief small overshoots are acceptable, sustained ones are not.
- Availability: if the limiter fails, the API must keep working.
Out of scope
- Billing and quotas by the month (a slower, exact counting problem), and DDoS protection at the network layer ( DDoS protection and abuse prevention ).
Estimates
- Check rate: one limiter call per request, so 500,000 per second at peak. Assume one Redis shard handles about 100,000 short script calls per second (measure your own); that is 5 shards at full load, so plan 10 for headroom and failover.
- Memory: a token bucket is two numbers per identity and rule. With 10 million identities, two rules each and about 100 bytes per key with overhead, that is about 2 GB. Small, so the whole state fits in memory with room to spare.
- Latency: a Redis round trip inside one data centre is well under a millisecond, which fits the 2 ms budget. A cross-region round trip of tens of milliseconds does not, so every region needs its own counters.
- Traffic to Redis: each call is a few hundred bytes, so 500,000 calls per second is on the order of 100 to 200 MB/s across the cluster, spread over the shards.
API
The limiter is an internal service, usually a library or sidecar inside the gateway, with one call:
POST /v1/check
body: { "identity": "key_8f2c", "rule": "plan:paid:default", "cost": 1 }
200 OK { "allowed": true, "remaining": 37, "reset_ms": 420 }
What the client sees when it is over the limit:
HTTP/1.1 429 Too Many Requests
RateLimit-Limit: 100
RateLimit-Remaining: 0
Retry-After: 1
Data model
- Rules live in a small configuration store and are pushed to every gateway:
{ rule_id, match: { plan, endpoint }, algorithm: "token_bucket", capacity: 200, refill_per_sec: 100 }. Gateways hold them in memory and refresh on change. - Counters live in Redis ( Distributed caches: Redis and Memcached ), one key per identity and rule, for example
rl:{key_8f2c}:paid:defaultholdingtokensandlast_refill_ms, with an expiry so idle identities disappear on their own. The part in braces is the hash tag that decides the shard, so all of one identity's keys live together.
High-level design
- Allowed The gateway identifies the caller (API key, else IP), finds the matching rules in memory and runs one atomic script on the Redis shard that owns that identity. Tokens remain, so the request goes on to the backend.
- Rejected The bucket is empty. The gateway answers 429 immediately with Retry-After, without touching the backend. Rejection must be cheap, because overloaded clients often send even more.
- Rules and metrics Rules are pushed to gateways in the background and cached in memory. Gateways report allowed and rejected counts per rule, which is how you dark launch a new limit before enforcing it.
Deep dives
Deep dive 1: Where the limiter lives
- In the client (an SDK that throttles itself): polite clients benefit, but you cannot trust it, so it is never enough.
- In the API gateway ( API gateway and backend-for-frontend ): the usual answer. Every request passes through, the caller is already authenticated, and rejected requests never reach your services.
- In each service: needed when limits depend on business context the gateway lacks, such as "5 password resets per account per hour", or to protect an expensive internal dependency.
Most systems combine the last two: coarse per-client limits at the gateway, a few precise business limits inside services. Either way the limiter is a shared library or sidecar that talks to one counter store, so the logic and rules are written once.
Deep dive 2: Shared counters and races
Local counters on each gateway do not work: with 50 gateways behind a load balancer, a client gets up to 50 times its limit. The counters must be shared, and Redis is the usual choice: in memory, sub-millisecond, with expiry built in.
Sharing introduces a race. If each gateway reads the counter, decides, and then writes it back, two gateways can read the same value at the same moment and both admit a request. Run this simulation of two gateways racing:
# Two gateways share one counter (limit 10 per window). Each receives 8
# requests at the same moment. Compare read-then-write with an atomic INCR.
LIMIT = 10
def read_then_write():
store = {"count": 0}
admitted = 0
# Interleave: A reads, B reads, A writes, B writes, repeated 8 times.
for _ in range(8):
seen = [store["count"], store["count"]] # both gateways GET
for v in seen: # both decide, then SET
if v < LIMIT:
admitted += 1
store["count"] = v + 1 # lost update: same value
return admitted, store["count"]
def atomic_incr():
store = {"count": 0}
admitted = 0
for _ in range(8):
for _gw in ("A", "B"):
store["count"] += 1 # INCR returns new value
if store["count"] <= LIMIT:
admitted += 1
return admitted, store["count"]
for name, fn in [("GET then SET", read_then_write),
("atomic INCR", atomic_incr)]:
ok, final = fn()
print(f"{name:12} admitted {ok:2} of 16, counter = {final}")Output
GET then SET admitted 16 of 16, counter = 8
atomic INCR admitted 10 of 16, counter = 16 With read-then-write, all 16 requests got through a limit of 10, and the counter shows only 8 because updates were lost. The fix is to make check-and-update a single atomic step on the server. For a fixed window counter, INCR already is: it returns the new value, and the gateway admits the request if that value is within the limit. A token bucket needs to read, refill and subtract, so it runs as a Lua scriptA script that Redis runs as one indivisible operation: no other command runs on that shard until it finishes., which Redis executes atomically:
-- KEYS[1] bucket key. ARGV: capacity, refill per second, now (ms), cost
local cap, rate = tonumber(ARGV[1]), tonumber(ARGV[2])
local now, cost = tonumber(ARGV[3]), tonumber(ARGV[4])
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1]) or cap
local ts = tonumber(b[2]) or now
tokens = math.min(cap, tokens + math.max(0, now - ts) / 1000 * 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 * 1000))
return { allowed, math.floor(tokens) }
The gateway loads the script once and calls it by its hash (EVALSHA), so each check is one round trip. Two details are worth saying in an interview. The now value comes from the gateway, so gateway clocks must be roughly in sync; math.max(0, ...) stops a gateway whose clock is behind from removing tokens. And the expiry means an idle identity's key vanishes once its bucket would be full again anyway, so memory tracks active clients only.
Deep dive 3: When Redis is slow or down
The limiter protects the API, so it must not become a way to take the API down. Give each check a tight timeout (a few milliseconds) and decide in advance what happens when it fails:
- Fail open: allow the request. The API stays up, unprotected for a while. Right for most public APIs.
- Fail closed: reject the request. Right where the limit guards something dangerous or expensive, such as login attempts or SMS sending.
A middle path is a local fallback: each gateway keeps an in-memory bucket per identity with the limit divided by the number of gateways. It is approximate, but it keeps some protection while Redis recovers. Add a kill switchA configuration switch that turns a feature off immediately, without a deploy. to disable a rule that turns out to be wrong.
Deep dive 4: Limits across regions
Clients near Frankfurt hit the Frankfurt gateways; a global client may hit three regions at once. A single global Redis would add a cross-region round trip to every request. The options:
- Per-region limits: each region enforces its own share, for example the full limit in the client's home region and a smaller share elsewhere. Simple and fast; a client spreading across regions can exceed the global limit by the sum of the shares.
- Local counting, asynchronous sync: each region counts locally and periodically exchanges counts with the others, adjusting how much each may admit. Close to the global limit, with brief overshoots during the sync interval.
- One global store: exact, but slow and a cross-region dependency on every request. Rarely worth it except for low-rate, high-value limits.
We choose per-region limits by default, with asynchronous sync only for the few customers whose contracts specify an exact global limit.
Try it
Try this:
- Switch to the fixed window and find the burst that straddles a one-second boundary. How many requests get through in that one-second span, compared with the sliding window counter?
- Back on the token bucket, lower the bucket size. The bursts shrink but the sustained rate stays at 10 per second. Which setting would you expose per plan?
- Which algorithm would be cheapest to keep in Redis per identity? Compare the sliding log, which stores every timestamp, with the two numbers of a token bucket.
Bottlenecks and failure modes
| Failure | Impact | Mitigation |
|---|---|---|
| Redis shard down | Checks for its identities fail | Replicas with failover; fail open with a local fallback bucket |
| Redis slow | Every request slows down | Tight timeout on the check, then the fail-open path |
| Hot identity (one huge client) | One shard overloaded | Local pre-check per gateway; split its key by endpoint |
| Gateway clock skew | Buckets refill too fast or too slow | NTP on gateways, ignore negative elapsed time |
| Bad rule deployed | Legitimate traffic rejected | Dark launch (log only) first, then enforce; kill switch |
| Rejected clients retry instantly | Rejections amplify load | Retry-After header, cheap rejection path, client backoff guidance |
Trade-offs we made
| Option | Wins when | Loses when |
|---|---|---|
| Token bucket in a Lua script (chosen) | Allows bursts, two numbers per key, atomic in one round trip | Logic in a script; relies on gateway clocks |
| Fixed window with INCR | Simplest possible atomic check | Up to twice the limit across a window boundary |
| Fail open (chosen) | Limiter outages never take the API down | No protection until it recovers |
| Per-region limits (chosen) | Fast, no cross-region dependency | A client spread across regions can exceed the global limit |
Extensions
- Concurrency limits: cap requests in flight per client, not just per second, for slow, expensive endpoints.
- Priority-aware load shedding when the whole fleet is overloaded, rejecting the least critical traffic first ( Load shedding and graceful degradation ).
- Cost-based limits: charge expensive calls more tokens than cheap ones, which the
costargument already supports.
In the wild
Stripe
Scaling your API with rate limiters (opens in a new tab)Stripe describes four layers: a request rate limiter (N requests per second per user, with the ability to briefly burst above the cap for events like flash sales), a concurrent requests limiter, and two load shedders that reserve capacity for critical traffic, for example rejecting non-critical requests beyond an 80 percent share when 20 percent is reserved. They implement the limiters with the token bucket algorithm on Redis, and design them to fail open so that bugs or a Redis outage do not affect requests. Before enforcing a new limiter, they dark launch it to watch what it would have blocked, and they keep kill switches to turn limiters off if they misfire.
Check yourself
-
Fifty gateways each keep their own in-memory counter with the full limit. What goes wrong?
Show answer
B. A client can get up to fifty times its limit Behind a load balancer the client's requests spread across gateways, and each one allows the full limit.
-
Why does a token bucket check run as a Lua script rather than GET then SET?
Show answer
B. So the read, refill and update happen atomically and concurrent gateways cannot both pass Read-then-write lets two gateways see the same value and both admit; the script runs as one indivisible step.
-
Redis is unreachable for a public read API. What is usually the right behaviour?
Show answer
B. Fail open, ideally with a rough local limit per gateway The limiter should not become a single point of failure; fail closed only where the limit protects something dangerous.
-
A client sends traffic to three regions at once. What happens with per-region limits?
Show answer
B. It can exceed its global limit by up to the sum of the regional shares Per-region limits trade a bounded overshoot for avoiding cross-region round trips on every request.
Recap
- Put coarse per-client limits in the gateway and business limits inside services.
- Share counters in Redis; local counters multiply the limit by the number of gateways.
- Make check-and-update atomic with INCR or a Lua script; read-then-write races.
- Decide failure behaviour up front: fail open for most APIs, closed for dangerous actions.
- Enforce per region by default; sync counts asynchronously only where exact global limits matter.
Next up
- Crack the system design round learning path