System design interview: design a rate limiter

First in a series that works through classic system design interview questions the way I actually run them, on both sides of the table. Every post follows the same six beats: clarify, estimate, define the API, sketch the design, dive into the hard part, and break it. The rate limiter is the perfect opener because it looks trivial and is not.

The job, in one line: has this client made too many requests recently, and should this one be rejected? The naive answer (“keep a counter”) is right in spirit and wrong in every detail once you have more than one server.

Step 1: clarify before drawing a box

A good candidate refuses to start designing. The questions, and the answers I will assume:

Functional requirement is tiny: given a key and rule, return allow/deny plus a retry hint. The non-functional requirements are the whole problem:

• Low latency (single-digit ms, ideally sub-ms): it sits in every request path.
• High availability: it must not take the platform down with it.
• Accuracy, but only as much as we agreed we need.

Step 2: back-of-envelope picks the architecture

flowchart LR
    A[1M req/s] --> B[1M counter ops/s]
    C[20M keys x ~20 bytes] --> D[few GB hot state]
    D --> E[fits in memory<br/>= Redis, not a DB]
    style E stroke:#2e7d32,stroke-width:3px

The latency gap is the tension the rest of the design fights:

flowchart LR
    L[Local hashmap<br/>~10s of ns] -.4 orders of magnitude.-> R[Shared Redis<br/>~0.2-1 ms]
    style L stroke:#2e7d32,stroke-width:2px
    style R stroke:#c62828,stroke-width:2px

Step 3: the API and the response

allow(key, rule) -> { allowed, limit, remaining, retry_after }

Those fields become headers a well-behaved client backs off on:

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: 0
Retry-After: 12

Retry-After is load-bearing, not decoration: it turns a rejection into a signal instead of an immediate retry.

Step 4: high-level design

Interesting designs have boring diagrams and interesting deep dives.

flowchart LR
    C[Client] --> GW[API gateway<br/>rate-limit middleware]
    GW -->|allow?| RL[Limiter logic]
    RL -->|read/write| STORE[(In-memory store)]
    RL -->|allowed| SVC[Backend]
    RL -->|denied 429| C
    CFG[(Rule config)] -.-> RL
    style STORE stroke:#c62828,stroke-width:3px

Two hard questions: which algorithm runs in the limiter, and how does the count stay correct across a hundred gateways. Steps 5 and 6.

Step 5: the algorithms

Fixed window. One counter per key per bucket. Simple, but the reset is a cliff: a client sends the full limit either side of the boundary and lands 2x the limit in a two-second span.

flowchart LR
    subgraph W1[minute 1]
      direction LR
      A[quiet...] --> B[1000 reqs<br/>last second]
    end
    subgraph W2[minute 2]
      direction LR
      D[1000 reqs<br/>first second] --> E[quiet...]
    end
    B --> D
    B -.2000 reqs in ~2s.-> D
    style B stroke:#c62828,stroke-width:2px
    style D stroke:#c62828,stroke-width:2px

Sliding window log. Store a timestamp per request; on each new request drop the timestamps older than the window, count what remains, and allow only if it is under the limit. The window is a true 60-second span that slides with every request, so there is no boundary cliff at all.

flowchart LR
    OLD["t=3s<br/>(now expired)"]:::gone --> W
    subgraph W["sliding 60s window: these still count"]
      direction LR
      A["t=12s"] --> B["t=31s"] --> C["t=55s"]
    end
    W --> NEW["new req at t=61s:<br/>drop t=3s, count = 3,<br/>allow if 3 < limit"]
    classDef gone stroke:#c62828,stroke-width:2px,stroke-dasharray:4 4
    style W stroke:#2e7d32,stroke-width:2px

Exact, but memory grows with requests, not keys (one stored timestamp per request), which the back-of-envelope already ruled out.

Sliding window counter. The production default. Keep two counters (current + previous window) and weight the previous one by how far you are into the current:

flowchart LR
    P["prev window<br/>count x (1 - 0.25)"] --> S((estimated<br/>rate))
    Cur["current window<br/>count"] --> S
    S --> Chk{under limit?}
    style S stroke:#2e7d32,stroke-width:2px

Two counters per key, smooths the cliff, off by a few percent at the edges. Exactly the error “load protection” lets us accept.

Token bucket. The other production winner, and the first algorithm on this ladder that handles bursts on purpose. A burst is a short spike where requests arrive much faster than the average allowed rate: say 50 requests in one second under a 10-per-second limit. The real question is when a client that has been quiet suddenly spikes, do you let the spike through? A window algorithm says no. Token bucket says yes, up to a point. A bucket holds up to B tokens, refills at R/sec; each request spends one; empty means reject. A client that was idle has a full bucket and can spend it at once, then is throttled to the steady refill rate.

flowchart TD
    REFILL[Refill R tokens/sec] --> BUCKET[(Bucket<br/>cap B tokens)]
    REQ[Request] -->|take 1| BUCKET
    BUCKET -->|token available| OK[Allow]
    BUCKET -->|empty| NO[Reject 429]
    style OK stroke:#2e7d32,stroke-width:2px
    style NO stroke:#c62828,stroke-width:2px

Two knobs cleanly separate average rate (R) from burst tolerance (B). State is a count plus a timestamp; refill is computed lazily.

Leaky bucket. Mirror image: requests queue and drain at a fixed rate, overflow rejected. Deliberately flattens bursts into a smooth outflow. Right in front of a fragile downstream, wrong in front of a normal API.

flowchart LR
    IN[Bursty requests] --> Q[(Queue)]
    Q -->|leak at fixed rate| OUT[Smooth outflow]
    Q -->|full| DROP[Reject]
    style OUT stroke:#2e7d32,stroke-width:2px
    style DROP stroke:#c62828,stroke-width:2px

Token vs leaky, the one-line difference: both cap the same average rate; they differ entirely in what they do with a burst. Feed the identical bursty input to each and watch the output:

flowchart LR
    IN["Burst in:<br/>10 reqs at once"] --> TB{Token bucket}
    IN --> LB{Leaky bucket}
    TB --> TBO["Out: burst passes<br/>if tokens saved<br/>(spiky)"]
    LB --> LBO["Out: steady drip<br/>1 at a time<br/>(smooth)"]
    style TBO stroke:#2e7d32,stroke-width:2px
    style LBO stroke:#1565c0,stroke-width:2px

Token bucket spends saved-up tokens and lets the burst through, then throttles. Leaky bucket ignores how bumpy the input is and releases at a constant rate. Same average, opposite burst behavior: pick token bucket when a legitimate spike should be served, leaky bucket when a downstream needs a smooth, predictable input.

The ladder, which is the artifact to reconstruct from memory:

Remember two: sliding window counter for general protection, token bucket to reward idle clients with burst capacity.

Step 6: the actual hard part is distribution

One machine works. A hundred gateways develop one disease: whose counter is it?

flowchart TD
    C[Client<br/>limit 1000/min] --> LB[Load balancer]
    LB --> G1[GW1: sees 1000]
    LB --> G2[GW2: sees 1000]
    LB --> G3[... x100]
    G1 --> BAD[Actual allowed:<br/>100,000/min]
    G2 --> BAD
    G3 --> BAD
    style BAD stroke:#c62828,stroke-width:3px

Local counters silently multiply the limit by the fleet size. Catching this is most of what the “distributed” part tests. Three ways out:

flowchart TD
    Q{how strict?} --> A["A: Shared store<br/>correct<br/>+1ms/req<br/>Redis = your uptime"]
    Q --> B["B: Sticky routing<br/>fast, local<br/>hot keys hurt<br/>reshuffle on scale"]
    Q --> C["C: Local + async sync<br/>fastest at scale<br/>briefly over-allows"]
    style A stroke:#1565c0,stroke-width:2px
    style B stroke:#6a1b9a,stroke-width:2px
    style C stroke:#ef6c00,stroke-width:2px

• A: shared central store. Global count, correct, simplest. Cost: the round trip on every request, and Redis availability becomes yours. What most systems do.
• B: sticky routing. Consistent-hash each key to one gateway, local counters correct again. Cost: hot keys overload their gateway; joins/leaves reshuffle and scramble counts.
• C: local + async reconciliation. Enforce locally for speed, sync to a shared view every second. Cost: bounded, short-lived over-allow. The “approximately right is fine” requirement cashed into an architecture.

The race condition in Option A. The obvious implementation reads the counter, checks it, then writes the increment back. Those are three separate steps, and two gateways can interleave between them:

sequenceDiagram
    participant G1 as Gateway 1
    participant R as Redis (count=999, limit=1000)
    participant G2 as Gateway 2
    G1->>R: GET count
    R-->>G1: 999
    G2->>R: GET count
    R-->>G2: 999
    Note over G1,G2: both computed 999+1 = 1000, both think "allowed"
    G1->>R: SET count = 1000 (allow)
    G2->>R: SET count = 1000 (allow)
    Note over R: two requests allowed, count is 1000 not 1001<br/>the limit leaked, and the counter is now wrong

This is a time-of-check-to-time-of-use bug. The read and the write have to be one indivisible step. The fix is not to wrap a GET then an INCR in a script (that just reproduces the same read-then-write shape). The fix is to lean on the one Redis command that is already atomic and returns the new value in the same call: INCR. There is no separate read to race against, because increment-and-return is a single operation.

-- KEYS[1]=counter, ARGV[1]=limit, ARGV[2]=window secs
local count = redis.call('INCR', KEYS[1])   -- atomically increments AND returns new value
if count == 1 then
  redis.call('EXPIRE', KEYS[1], ARGV[2])    -- first hit of the window: start the clock once
end
if count > tonumber(ARGV[1]) then
  return 0                                    -- over limit: deny
end
return 1                                      -- allowed

Two things make this correct where the naive version was not:

• INCR does the read and the write in one atomic step. Two concurrent gateways calling INCR get 1000 and 1001 back, distinct values, so exactly one of them sees the value that crosses the limit. Nobody reads a stale 999.
• EXPIRE only on the first hit (count == 1). Setting the TTL on every request would push the expiry forward each time, so under sustained traffic the window would never roll over and the key would never reset. Setting it once, when the window’s first request creates the key, fixes the window to a real 60-second span and still garbage-collects the key when the client goes idle.

The Lua wrapper earns its keep even though INCR is already atomic: it bundles the increment and the conditional EXPIRE into a single atomic unit and a single round trip, so a crash can never leave a counter with no TTL (a key that leaks forever and never resets).

Step 7: how it breaks

flowchart TD
    DOWN{Store unreachable?} -->|Fail open| OPEN[Allow all<br/>site stays up, no protection<br/>= general limiter]
    DOWN -->|Fail closed| CLOSED[Reject all<br/>protected, but limiter outage<br/>= platform outage<br/>= security/billing only]
    style OPEN stroke:#2e7d32,stroke-width:2px
    style CLOSED stroke:#c62828,stroke-width:2px

• Fail open vs closed is a decision you make on purpose. A limiter that can take the site down became the risk it was meant to prevent, so general limiters fail open; hard security/billing boundaries fail closed. “It depends, and here’s what on” is the right answer.
• Retry storms. A rejected client that retries immediately sends more traffic than an unthrottled one. This is why Retry-After matters and why the server must protect itself anyway.
• Hot keys. One noisy key hammers a shard or gateway. Shed it cheaply with a small local pre-check at the edge.

Follow-ups an interviewer reaches for: per-tier rules, distributed config that propagates in seconds, and observability, which at 1M req/s is its own big-data problem.

In practice: wrap, don’t write

The whiteboard version implements an algorithm. The production version usually should not. Most modern runtimes already ship rate-limiting primitives (fixed window, sliding window, token bucket, concurrency) that are correct, tested, and tuned. On a real service the job is not “implement windowing,” it is pick an algorithm and a partition key, then make every decision observable.

flowchart LR
    APP[App code] -->|acquire| DEC[Monitoring decorator]
    DEC -->|delegate| INNER[Built-in limiter<br/>partitioned by key]
    INNER -->|lease| DEC
    DEC -->|metrics + logs| OBS[(Telemetry)]
    DEC -->|acquired| APP
    DEC -->|denied| M429[Map to 429<br/>+ Retry-After]
    style DEC stroke:#1565c0,stroke-width:3px
    style INNER stroke:#2e7d32,stroke-width:2px

The partition key is exactly the “key” from Step 1: same key means same limiter instance and a shared budget. The valuable engineering is the glue you write once:

• A thin decorator over the built-in limiter that logs and emits a metric around every acquire and the lease it returns. Callers still depend only on the standard limiter contract, so monitoring is transparent.
• 429 mapping. Exhaustion becomes 429 Too Many Requests with the runtime’s recommended Retry-After surfaced on the response. Treat that 429 as an expected, benign outcome so it does not count against availability SLOs.
• Telemetry in two layers. Periodic in-flight gauges per limiter (acquired and failed leases, incremented on acquire and decremented when the lease is disposed, not cumulative totals), plus a per-request signal on each acquire.

The gotchas are all the same shape, “the limiter must remember state across requests”:

This is the same lesson as the rest of the post from the other direction: the counter, the atomicity, and the expiry are hard enough that when the platform already solved them correctly, the leverage is in observability and correct wiring, not in rewriting the algorithm.

The pattern under the pattern

Every question in this series rewards the same move: let the requirements tell you how much correctness you must buy, then spend exactly that much. The candidate who asks “how strict?” in the first two minutes is the one who can justify an approximate algorithm and a fail-open policy twenty minutes later, because both trace straight back to that answer. The boxes are easy. Knowing which corner you may cut, and why, is the job.

Next: designing a URL shortener, where the real fight is read-heavy scaling and the cache underneath, not the hashing everyone expects.