Rate Limiter

"Design a rate limiter for a public API. It must work across many API gateway replicas, add almost no latency, and let us set different limits per user, per IP and per partner."

Every public API needs one, and every large system has several: at the edge against floods, at the gateway per client, inside services to protect a fragile dependency. The problem is small enough to design end to end in 45 minutes and deep enough to separate levels: a junior candidate names "token bucket"; a senior one explains why a sliding-window counter is accurate enough, how to make the check atomic across 20 gateway replicas, what happens when the counter store is down, and why rate limiting alone does not stop an overload.

In BoxOffice, the rate limiter is the second line of defense of the flash sale: the WAF stops obvious floods, the waiting room meters admissions, and the gateway enforces "5 hold attempts per minute per account" and the quotas of reseller partners.

1. Clarify the requirements

The word "rate limiter" hides several different products. Ask before drawing (interview framework).

Functional requirements

1. Limit the number of requests a client can make in a time window; the client can be a user ID, an API key, an IP address, or a combination.
2. Several rules per request, e.g. 10 req/s per user and 1 000 req/min per API key and 100 req/s per IP on /login.
3. Rejected requests get HTTP 429 Too Many Requests with a hint of when to retry.
4. Rules are configurable without redeploying (per endpoint, per plan: free, partner, internal).
5. Expose metrics: allowed vs. rejected per rule and client.

Non-functional requirements

Out of scope (say it explicitly)

DDoS protection at the network layer (that is the WAF/CDN's job), billing based on usage, abuse detection with machine learning. Mention that they exist in the layers around the limiter.

2. Back-of-the-envelope estimates

# Rate limiter: assumptions (illustrative)
peak_rps       = 50_000      # API requests per second at peak
gateways       = 20          # gateway replicas
active_clients = 1_000_000   # distinct keys active in a window
rules_per_req  = 2           # e.g. per-user + per-IP
bucket_b       = 100         # one counter in Redis: key + 2 numbers + overhead, bytes
user_limit_min = 600         # per-user limit: 600 requests per minute
log_entry_b    = 50          # one timestamp in a sorted set, with overhead
redis_ops_node = 100_000     # simple ops/s one Redis node sustains (order of magnitude)
rtt_ms         = 0.5         # gateway → Redis round trip in the same zone

counter_ops    = peak_rps * rules_per_req           # one atomic op per rule (or 1 script)
script_calls   = peak_rps                            # all rules in one Lua call
counters_mb    = active_clients * rules_per_req * bucket_b / 1e6
log_gb         = active_clients * user_limit_min * log_entry_b / 1e9
redis_nodes    = script_calls * 3 / redis_ops_node   # a script costs ~3 simple ops
local_error    = gateways                             # per-replica limits: worst-case factor
added_ms       = rtt_ms

rows = [
    ("counter_ops", counter_ops, "ops/s"), ("script_calls", script_calls, "calls/s"),
    ("counters_mb", counters_mb, "MB"), ("log_gb", log_gb, "GB"),
    ("redis_nodes", redis_nodes, "nodes"), ("local_error", local_error, "x limit"),
    ("added_ms", added_ms, "ms"),
]
print("| quantity | value | unit |\n|---|---:|---|")
for name, value, unit in rows:
    v = f"{value:,.0f}" if abs(value) >= 100 else f"{value:,.2f}"
    print(f"| `{name}` | {v} | {unit} |")

What the numbers tell us:

• Counters for a million clients take ~200 MB — one Redis node holds them easily. A sliding-window log (one timestamp per request) would need ~30 GB for the same clients: that is why the log is rarely used at scale.
• 50 k script calls/s at ~3 operations each is ~1.5 Redis nodes of work ⇒ a small Redis Cluster (3 primaries + replicas), sharded by client key, with headroom.
• One round trip in the same zone adds ~0.5 ms — within budget, as long as the gateway talks to Redis over persistent, pipelined connections and all rules go in a single script call.
• Enforcing limit independently on each of 20 replicas lets a client get up to 20× the limit when the load balancer spreads its requests. ⇒ either a shared counter, or a local limit of limit / N with sticky routing, or a hybrid (see 6.3).

3. API

The limiter is usually not a public API but a filter inside the gateway; still, define its contract — internal and external.

# Internal (gateway → limiter library or sidecar)
check(rules=[("user:42", 10, 1s), ("ip:203.0.113.7", 100, 1s)], cost=1)
    → {allowed: true|false, remaining: 7, resetMs: 380, retryAfterMs: 0}

# External: what the API client sees
HTTP/1.1 429 Too Many Requests
Retry-After: 2
RateLimit-Policy: "per-user";q=10;w=1
RateLimit: "per-user";r=0;t=2
Content-Type: application/problem+json

{"type": "https://bx.example/problems/rate-limited", "title": "Too many requests",
 "detail": "Limit of 10 requests per second per user exceeded", "retryAfterSeconds": 2}

• 429 (RFC 6585) plus Retry-After (seconds or a date) is the contract. Well-behaved clients retry after that time, with exponential backoff and jitter.
• The RateLimit / RateLimit-Policy header fields are being standardized by the IETF HTTPAPI working group; many APIs still use the older X-RateLimit-Limit/Remaining/Reset. Either way: tell clients their budget before they hit the wall.
• Rules are data, not code, e.g. stored in a config service and cached by every gateway:

rules:
  - match: { path: "/v1/events/*/holds", method: POST }
    key: user
    limit: { requests: 5, per: 60s }          # 5 hold attempts per minute per account
  - match: { path: "/v1/*" }
    key: api_key
    limit: { requests: 1000, per: 60s, burst: 200 }
    plans: { partner: 10000, internal: unlimited }
  - match: { path: "/v1/auth/login" }
    key: ip
    limit: { requests: 10, per: 60s }
    on_store_failure: closed                   # security-sensitive: fail closed

4. Data model

The state is tiny and short-lived: per (rule, client) a counter or a token count with a timestamp, expiring automatically.

# Token bucket (Redis hash)              key TTL = time to refill completely × 2
rl:tb:user:42          → { tokens: 7.4, ts: 1767261600123 }

# Fixed window counter (Redis string)    key TTL = window
rl:fw:user:42:29454360 → 9            (window id = floor(now / 60 s))

# Sliding window counter: two fixed windows, current and previous
rl:sw:user:42:29454360 → 4
rl:sw:user:42:29454359 → 9

# Sliding window log (Redis sorted set)  score = timestamp
rl:log:user:42         → { 1767261600123, 1767261600201, ... }

5. High-level design

flowchart LR
    c([Clients]) --> waf["WAF / CDN<br/>coarse per-IP limits"]
    waf --> lb["Load balancer"]
    lb --> gw1["API gateway #1<br/>rate-limit filter"]
    lb --> gw2["API gateway #N<br/>rate-limit filter"]
    gw1 --> r[("Redis Cluster<br/>counters, Lua")]
    gw2 --> r
    cfg["Rules config<br/>service"] -. pushed / cached .-> gw1
    cfg -. pushed / cached .-> gw2
    gw1 --> svc["Backend services"]
    gw2 --> svc
    gw1 -. allowed / 429 .-> m["Metrics"]

One request through the filter:

sequenceDiagram
    autonumber
    participant C as Client
    participant G as API gateway
    participant R as Redis
    participant S as Service
    C->>G: POST /v1/events/42/holds (user 42)
    G->>G: match rules (local cache)
    G->>R: EVALSHA token_bucket {user:42, ip:…} now cost=1
    R-->>G: allowed=1, remaining=4
    G->>S: forward request
    S-->>G: 201 Created
    G-->>C: 201 + RateLimit: r=4
    C->>G: 6th attempt within the minute
    G->>R: EVALSHA token_bucket …
    R-->>G: allowed=0, retry after 9 s
    G-->>C: 429 Too Many Requests, Retry-After: 9

6. Deep dives

6.1 The algorithms

The boundary problem of fixed windows is easiest to see with a trace. Limit: 10 requests per second; a client sends 10 requests at t = 0.99 s and 10 more at t = 1.01 s:

# How many of 20 requests (10 at t=0.99 s, 10 at t=1.01 s) does each algorithm allow?
limit, window = 10, 1.0
trace = [0.99] * 10 + [1.01] * 10

def fixed_window(ts):
    counts, ok = {}, 0
    for t in ts:
        w = int(t // window)
        if counts.get(w, 0) < limit:
            counts[w] = counts.get(w, 0) + 1
            ok += 1
    return ok

def sliding_log(ts):
    log, ok = [], 0
    for t in ts:
        log = [x for x in log if x > t - window]
        if len(log) < limit:
            log.append(t)
            ok += 1
    return ok

def sliding_counter(ts):
    counts, ok = {}, 0
    for t in ts:
        w = int(t // window)
        overlap = 1 - (t % window) / window
        estimate = counts.get(w - 1, 0) * overlap + counts.get(w, 0)
        if estimate < limit:
            counts[w] = counts.get(w, 0) + 1
            ok += 1
    return ok

def token_bucket(ts, capacity=limit, rate=limit / window):
    tokens, last, ok = capacity, 0.0, 0
    for t in ts:
        tokens = min(capacity, tokens + (t - last) * rate)
        last = t
        if tokens >= 1:
            tokens -= 1
            ok += 1
    return ok

print("| algorithm | allowed of 20 |\n|---|---:|")
for f in (fixed_window, sliding_log, sliding_counter, token_bucket):
    print(f"| `{f.__name__}` | {f(trace)} |")

The fixed window lets 20 requests through in 20 ms — twice the limit — because they fall in two different windows. The log and the token bucket allow exactly 10. The sliding window counter allows 11: it assumes the previous window's requests were spread evenly, while here they all came at its very end — a small, bounded error in exchange for two numbers of state. This is why production limiters use a token bucket or a sliding window counter.

6.2 Making it atomic across replicas

The naive implementation has a race:

gateway A: GET rl:user:42      → 9          gateway B: GET rl:user:42 → 9
gateway A: 9 < 10 → allow, SET 10           gateway B: 9 < 10 → allow, SET 10
                       → 11 requests allowed, counter says 10

Read-check-write must be one atomic operation on the store. In Redis, use INCR (atomic) for counters, or a Lua script, which runs atomically on the shard that owns the key:

-- token_bucket.lua   KEYS[1] = bucket key   ARGV: capacity, refill per second, cost
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])
local t        = redis.call('TIME')                       -- server clock: no skew between gateways
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 capacity
local ts     = tonumber(b[2]) or now
tokens = math.min(capacity, tokens + (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(capacity / rate * 1000) * 2)
local retry_ms = 0
if allowed == 0 then retry_ms = math.ceil((cost - tokens) / rate * 1000) end
return { allowed, tostring(tokens), retry_ms }               -- floats → string (Redis truncates numbers)

Details that show seniority:

• One call per request for all rules (pass several keys) — but in Redis Cluster all keys of one script must hash to the same slot: use a hash tag, e.g. rl:{user:42}:tb and rl:{user:42}:fw; rules keyed by different entities (user and IP) need separate calls, pipelined.
• Use the server's clock (TIME) instead of each gateway's: 20 gateways with clocks 50 ms apart would refill the bucket inconsistently.
• TTL on every key: idle clients disappear by themselves; memory stays proportional to active clients.
• Load the script once (SCRIPT LOAD) and call it with EVALSHA to avoid sending the source on every request.

6.3 Where to enforce, and local vs. global

flowchart LR
    cl["Client SDK<br/>courtesy limit"] --> edge["Edge / WAF<br/>per IP, coarse"]
    edge --> gw["API gateway<br/>per user / key / plan"]
    gw --> mesh["Service mesh<br/>per caller service"]
    mesh --> svc["Service<br/>concurrency limit<br/>to its DB / provider"]

Global vs. local. A shared Redis gives an exact global limit at the cost of a network hop. Alternatives when that hop is too expensive (multi-region, very high rates):

• Local buckets with limit / N: no network, but wrong when traffic is unevenly spread; acceptable with consistent-hash routing of each client to one gateway.
• Local + periodic sync: each gateway counts locally and pushes deltas to the shared store every 100 ms, reading back the global total — approximate (overshoots by at most one sync interval of traffic), very fast. This is roughly how large CDNs do it.
• Per-region limits: limit per region and accept that a client using two regions gets up to 2× — usually fine.

# rate limiting per API key: 20 req/s per key, bursts of up to 40.
# Requests WITHOUT an X-Api-Key header have an empty key and are not limited
# (in production you would also limit them per client IP).
limit_req_zone  $http_x_api_key  zone=per_key:10m  rate=20r/s;
limit_req_status  429;
    location /catalog/ {
        limit_req  zone=per_key  burst=40  nodelay;

6.4 When the limiter itself fails

• Fail-open (allow when Redis is unreachable) keeps the API available — the right default for ordinary limits, because the limiter exists to protect the backend, and a short period without limits is rarely worse than a full outage. Pair it with a local fallback bucket so the protection degrades instead of disappearing.
• Fail-closed (reject) for limits that guard security: login attempts, password reset, OTP verification — otherwise an attacker who can overload Redis also disables brute-force protection.
• Put a tight timeout (a few ms) on the Redis call and a circuit breaker around it: a slow limiter is worse than none, because it adds latency to every request (reliability patterns).

7. Bottlenecks, failure modes and trade-offs

The trade-offs to say out loud: accuracy vs. latency (exact global counters cost a network hop; approximate local ones are free), availability vs. protection (fail-open vs. fail-closed, chosen per rule), and fairness vs. simplicity (per-IP limits are easy but punish users behind a shared NAT).

8. Try it in the playground

The rate-limiter scenario places an API gateway with rate limiting in front of a backend that has a fixed capacity.

Open the full playground

9. Follow-up questions an interviewer asks

10. Self-assessment rubric

Related: API gateway, Hands-on 3 (Nginx rate limiting), Hands-on 4 (gateway and identity), Redis, Reliability patterns.

How it connects

Which classes does this case test? Each branch is a class whose ideas the design relies on (blue), with the palette components where they show up (green):

flowchart LR
    CASE(["Rate limiter"]) --> EDG["Edge<br/>where limits live: WAF, gateway"]:::tech
    CASE --> CAC["Caching<br/>Redis counters, Lua atomicity"]:::tech
    CASE --> REL["Reliability<br/>fail-open vs fail-closed, load shedding"]:::tech
    CASE --> CLI["client contract<br/>429, Retry-After, jitter"]:::tech
    CASE --> PERF["Performance<br/>k6 at a known arrival rate"]:::tech
    EDG -.-> k1["waf · cdn · lb · apigw"]:::comp
    CAC -.-> k2["cache"]:::comp
    REL -.-> k3["metrics"]:::comp
    classDef comp fill:#1e9e5a22,stroke:#1e9e5a
    classDef tech fill:#2f6fed22,stroke:#2f6fed

Classes it tests: Edge — API gateway · Caching — Redis · Reliability — patterns (load shedding, backoff with jitter) · Performance · Hands-on 3 and Hands-on 4. Palette components: waf · cdn · lb · apigw · cache · metrics. Scenarios: rate-limiter.

References

• XU, A. System Design Interview — An Insider's Guide, vol. 1, ch. 4 "Design a Rate Limiter"¹.
• Stripe's four kinds of limiters (request rate, concurrency, fleet load shedder, worker utilization)².
• Cloudflare's sliding-window counter at the edge³.
• HTTP status 429⁴ and handling overload at Google⁵.