Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Design Case Studies

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.

Intermediate 20 min Last reviewed

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 /search endpoint.
  • 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

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:default holding tokens and last_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

Rate limiter service with allowed, rejected and configuration paths A client sends a request to an API gateway. The gateway's limiter runs an atomic script on the Redis shard that owns the client's key. If allowed, the request goes to the backend service. If not, the gateway returns 429 with Retry-After. Separately, a rules service pushes limit rules to every gateway, and gateways send limiter metrics to monitoring. EVALSHA bucket allowed over limit push rules counts Client API gateway limiter middleware Redis shards key = identity + rule Backend the real API 429 + Retry-After Rules service plans, endpoints Metrics allowed, rejected Figure 1. The check is one round trip to the shard that owns the client's key. Rules travel separately and asynchronously, so changing a limit never touches the request path.
  1. 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.
  2. 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.
  3. 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:

race.pyruns with python3 (standard library)
# 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

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. 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?
  2. 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?
  3. 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

FailureImpactMitigation
Redis shard downChecks for its identities failReplicas with failover; fail open with a local fallback bucket
Redis slowEvery request slows downTight timeout on the check, then the fail-open path
Hot identity (one huge client)One shard overloadedLocal pre-check per gateway; split its key by endpoint
Gateway clock skewBuckets refill too fast or too slowNTP on gateways, ignore negative elapsed time
Bad rule deployedLegitimate traffic rejectedDark launch (log only) first, then enforce; kill switch
Rejected clients retry instantlyRejections amplify loadRetry-After header, cheap rejection path, client backoff guidance

Trade-offs we made

OptionWins whenLoses 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 cost argument 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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up