Design an API Rate Limiter

Distributed Rate Limiting System Design

Overview

A rate limiter caps how many requests a client can make in a time window — "100 requests per minute per API key" — and rejects the excess. It protects backends from being overwhelmed by retry storms, scrapers, or abusive clients. It also enforces fair usage across tenants and supports paid API tiers. Stripe, GitHub, and many public APIs return 429 Too Many Requests from a limiter sitting in front of their services.

It is labeled "Medium" because the hard part is precision. The interviewer wants you to distinguish the algorithms (fixed window, sliding window log, sliding window counter, token bucket, leaky bucket), explain how each behaves at the window boundary, make the counter correct under concurrency across many limiter instances, and place the limiter where it belongs. Saying only "use a counter in Redis" is too shallow; a strong answer names the fixed-window boundary-burst bug and fixes the distributed counting race.

In this walkthrough you'll scope the limiter, size it, pick a data model, design the algorithm comparison carefully, draw the architecture, and examine the algorithms, distributed atomic counting, and the fail-open/fail-closed decision.

Functional requirements

• Limit requests. Allow up to N requests per client per time window; reject the rest.
• Configurable rules. Limits vary by client tier, by route, and by window length (e.g. 10/sec burst and 1000/hour sustained on the same key).
• Correct rejection response. Rejected requests get 429 with headers telling the client how long to wait.

Out of scope (state it): authentication itself (the limiter consumes an already-resolved client identity — API key or user id), billing, and DDoS scrubbing at the network layer (a limiter is application-layer; volumetric L3/L4 attacks need upstream protection).

Non-functional requirements

• Low latency. The limiter is in the request critical path on every call. Its own decision must add single-digit milliseconds — target < 5 ms p99.
• High availability + fail-open vs fail-closed. If the limiter's datastore is down, decide deliberately: fail-open (usual default for user-facing APIs) or fail-closed (safer for fragile backends). State which and why.
• Accuracy. It should rarely allow well over the limit or reject well under it; small over-counting at window edges may be acceptable depending on the algorithm chosen.
• Distributed correctness. Many limiter instances behind a load balancer must share one logical count per key, without races.

Estimations

State assumptions; the goal is to justify the datastore, not to be exact.

Rounded assumptions

• Total request rate across the platform: ~1M requests/sec at peak.
• Distinct active clients (keys) in any minute: 10M.
• Each request needs at least one counter operation.
• Hot counter state is small: roughly ~100 bytes/key × 10M ≈ ~1 GB, plus Redis overhead.

How the numbers affect the design

Core entities / data model

The state is intentionally tiny:

These fields cover the counter and token-bucket algorithms; leaky bucket is the exception — instead of a counter it holds a small bounded queue per key.

Rules (limit N, window W, per tier/route) live in a small config store, cached in each limiter instance and refreshed periodically — rules change rarely and must not add a remote config-store lookup per request.

The store is Redis (or a Redis-compatible in-memory store): fast, with the two things a limiter needs: counter updates that two requests can't corrupt by racing, and keys that auto-expire after a set time (a TTL) so stale windows clean themselves up. Deep dive 2 shows how those keep counts correct across many instances.

Client contract

The rate limiter is middleware, not a product API, but it still has a contract with clients — the decision it returns and the headers they rely on:

On every request, the limiter answers: allow or deny.

Allowed:  request proceeds; response carries
  X-RateLimit-Limit: 100
  X-RateLimit-Remaining: 37
  X-RateLimit-Reset: 1718800000   (epoch when the window resets)

Denied:
  HTTP/1.1 429 Too Many Requests
  Retry-After: 12                 (seconds until the client may retry)
  X-RateLimit-Remaining: 0

429 is the correct status. Retry-After (computed from the window/bucket state) and the X-RateLimit-* headers let well-behaved clients back off precisely instead of hammering — without them, clients retry immediately and amplify the overload the limiter exists to prevent.

High-level architecture

The limiter runs as middleware at the API gateway. On each request it consults a sharded Redis counter atomically; allowed requests pass to the backend, denied requests get a 429 immediately.

flowchart LR
    Client[Client]
    subgraph Gateway["API Gateway"]
      RL[Rate Limiter Middleware]
    end
    Client -->|request| RL
    RL -->|"atomic counter update by key"| Redis[(Redis Cluster - sharded by key)]
    Redis -->|"count vs limit"| RL
    RL -->|"under limit: forward"| Backend[Backend Services]
    RL -->|"over limit: 429 + Retry-After"| Client
    Config[(Rule Config)] -.->|"cached rules"| RL

The limiter shards the counter store by client key so a given key always lands on one shard, making per-key atomic counting possible. Rules are cached in-process to avoid a config lookup per request. (Why the gateway edge, rather than inside each service or as a separate hop? See the placement options below.)

Read the diagram in this order:

1. The client sends a request to the API gateway.
2. The gateway runs its rate-limiter middleware before forwarding the request.
3. The limiter reads the rule for this client and route from its in-memory rule cache (no network call).
4. The limiter updates the client's counter in the Redis shard that owns that key.
5. If the request is under the limit, the gateway's limiter forwards it to the backend.
6. If the request is over the limit, the gateway's limiter returns 429 Too Many Requests immediately.

Where to place the limiter

Placement is the first design decision — it decides how much abusive traffic you absorb before rejecting it, and what client info you can see. Three options, worst to best:

flowchart LR
    Client[Client] -->|request| GW[API Gateway]
    GW <-->|"gRPC allow/deny"| RLS[Rate Limit Service]
    RLS <-->|"atomic count vs limit"| Redis[(Redis Cluster - sharded by key)]
    GW -->|"under limit: forward"| Backend[Backend Services]
    GW -.->|"over limit: 429"| Client

flowchart LR
    Client[Client] --> LB[Load Balancer]
    subgraph Fleet["API Gateway fleet"]
      GW1["Gateway instance 1<br/>+ limiter middleware"]
      GW2["Gateway instance 2<br/>+ limiter middleware"]
      GWn["Gateway instance N<br/>+ limiter middleware"]
    end
    LB --> GW1
    LB --> GW2
    LB --> GWn
    GW1 <-->|"atomic count vs limit, by key"| Redis[(Shared Redis - sharded by key)]
    GW2 <--> Redis
    GWn <--> Redis
    GW1 -->|"under limit"| Backend[Backend Services]
    GW2 --> Backend
    GWn --> Backend

Rule updates (the control plane)

Changing a limit is a separate control-plane path from the per-request data plane above. An admin (or an API owner changing a customer's tier) writes the new rule; each Rate Limiter instance (the same middleware from the architecture diagram above) then refreshes its in-memory rule cache so future requests use it — without ever adding a config lookup to the request path.

flowchart LR
    Admin[Admin / API owner] -->|"update rule"| RulesSvc[Rules Service]
    RulesSvc -->|"write rule"| ConfigDB[(Config Store)]
    ConfigDB -.->|"each instance polls every ~30s"| Caches["Rate Limiter instances<br/>(in-memory rule cache)"]
    RulesSvc -.->|"optional: publish change event"| Caches
    Caches --> Apply[Next request uses the new rule]

Two ways the new rule reaches the instances:

• Poll / TTL refresh (simple). Each instance re-reads the config store on an interval (e.g. every ~30s) — effectively a TTL on the cached rules. A change becomes consistent within that window. Because rules change rarely and a limit taking effect a few seconds late is harmless, polling is usually enough.
• Push / pub-sub (instant). On a change, the Rules Service publishes an event over a pub/sub channel (e.g. Redis pub/sub, or a message bus like Kafka) that every limiter instance subscribes to, so they refresh immediately. More moving parts — reach for it only when you need instant propagation, such as tightening a limit during an incident.

So the in-memory rules do have an implicit TTL (the refresh interval) — that is exactly how an update reaches every instance without a per-request config lookup.

Data plane and control plane together

Both flows meet at one component — the Rate Limiter Middleware. The data plane runs on every request: check the shared counter in Redis and allow or 429. The control plane runs rarely: an admin changes a rule, which propagates to each limiter's in-memory rule cache. Fast per-request counting on one side, occasional rule pushes on the other.

flowchart LR
    Client[Client]
    subgraph Gateway["API Gateway"]
      RL["Rate Limiter Middleware<br/>(in-memory rule cache)"]
    end
    %% data plane — every request
    Client -->|request| RL
    RL <-->|"atomic count vs limit, by key"| Redis[(Redis Cluster - sharded by key)]
    RL -->|"under limit: forward"| Backend[Backend Services]
    RL -->|"over limit: 429 + Retry-After"| Client
    %% control plane — rare rule changes
    Admin[Admin / API owner] -->|"update rule"| RulesSvc[Rules Service]
    RulesSvc -->|"write rule"| ConfigDB[(Config Store)]
    ConfigDB -.->|"poll ~30s / push on change"| RL

Deep dives

1. The algorithms — what each actually does

This is where the marks are. Be precise about boundary behavior.

window 12:00:00–12:01:00          window 12:01:00–...
 req :05 :12 :30 :41 :58           counter resets to 0
 cnt  1   2   3   4   5   ✓
 req :59 → cnt would be 6 → ✗ REJECT (until 12:01:00)

limit = 5 / minute

      window 12:00      |      window 12:01
 ...................●●●●●|●●●●●...................
                    :59  |  :00
                    └── 10 requests in ~2 seconds ──┘
 window 12:00 counts 5, window 12:01 counts 5 — neither exceeds the limit

 12:00:10  add → {10}                          count 1  ✓
 12:00:25  add → {10,25}                        count 2  ✓
 12:00:45  add → {10,25,45}                     count 3  ✓
 12:00:52  add → {10,25,45,52}                  count 4  ✓
 12:00:58  add → {10,25,45,52,58}               count 5  ✓
 12:01:05  drop ≤ 12:00:05 (none) → still 5  →  ✗ REJECT
 12:01:12  drop ≤ 12:00:12 (drops :10) → 4   →  ✓ add → {25,45,52,58,72}

 previous window 12:00–12:01 : 80 requests
 current  window 12:01–12:02 : 20 requests   (now = 12:01:15)

 |<──── previous (80) ────>|<──── current (20) ────>|
            [═══════ rolling 60s window ═══════]
            covers the last 75% of the previous window

 estimate = 20 + 80 × 0.75 = 80   →  80 < 100  →  ✓ allow

flowchart TB
    R["refill +R tokens/sec<br/>(R = 1, added up to capacity B)"] --> BKT["token bucket · capacity B = 10<br/>idle → fills up → burst allowance"]
    BKT -->|"each request removes 1 token"| OK["request allowed"]
    BKT -.->|"bucket empty"| REJ["429 Too Many Requests"]
    classDef good fill:#dcfce7,stroke:#16a34a,color:#14532d;
    classDef rej fill:#fee2e2,stroke:#dc2626,color:#7f1d1d;
    class BKT good
    class REJ rej

 idle a while        → bucket full (10 tokens)
 burst of 10 now     → all 10 ✓, bucket = 0
 11th immediately    → ✗ (empty)
 wait 3s (+3 tokens) → next 3 ✓, then ✗ again

flowchart LR
    IN["bursty in<br/>●●● ● ●●"] --> Q["queue · capacity Q = 10<br/>full → 429"]
    Q -->|"leak at fixed R = 2/sec"| OUT["steady out<br/>even, R/sec"]
    Q -.->|"queue full"| REJ["429 REJECT"]
    classDef q fill:#e0f2fe,stroke:#0284c7,color:#0c4a6e;
    classDef rej fill:#fee2e2,stroke:#dc2626,color:#7f1d1d;
    class Q q
    class REJ rej

 burst of 10 arrives → all queued
 drained at 2/sec    → smooth output over 5s
 an 11th while full  → ✗ REJECT

Multiple limits on one key. A key often has several rules at once — e.g. a 10/sec burst limit and a 1000/hour sustained limit. Treat each as its own counter (the key already encodes {window}), evaluate every applicable rule on each request, and reject if any one is exceeded. The X-RateLimit-* headers then report the most-constraining rule — the one closest to its limit — so the client backs off for the right amount of time.

2. Counting correctly across many instances

With many limiter instances behind the load balancer, two requests for the same key can read the counter at the same instant, both see "under limit," and both allow — letting the client slip over. The fix is to make the count update atomic: a single, all-or-nothing step the datastore finishes before anyone else can touch that key.

• Fixed window — the simple case. Do "add one and read the new total" as that single atomic step, not a separate read then write (Redis's INCR does exactly this). On a window's first request, also tell the key to delete itself after the window length — a TTL, via Redis's EXPIRE — so the window resets on its own. One subtlety: "add one" and "set the expiry" are two steps, and if the process crashes between them the key can live forever with a stuck count. The cheap cures: re-set the expiry on every request (harmless to repeat), or create the key already carrying its expiry. The fully robust version bundles both steps into one atomic mini-program the datastore runs for you (in Redis, a small Lua script run via EVAL).
• Token bucket. Each request must read the current tokens, add the ones earned since last time, then write the result back after consuming one — a read-modify-write. Two requests doing that at once race. Same fix: run the whole read-modify-write as one atomic server-side step (the small script again). A sliding-window counter sidesteps this — it only ever adds one and reads, never a read-modify-write.
• Spreading the load (sharding). At ~1M ops/sec you need many counter servers, so split the keys across them — each key always lives on one server (consistent hashing by key). The atomic step works precisely because a key's whole state sits on a single server. One very heavy key can overload its server, but that key's own limit caps the blast radius.

The one idea to take away: turn "read it, decide, write it back" into a single atomic step, so two requests can never both act on the same stale count.

3. Fail-open vs fail-closed

If the limiter's datastore (Redis) is unreachable, it still has to answer allow or deny — so decide deliberately:

• Fail-open (allow) keeps the product up at the cost of temporarily unbounded traffic — the usual choice for user-facing APIs.
• Fail-closed (reject) protects a fragile backend at the cost of an outage.

Make the choice explicit and tie it to which failure is worse for this system. A local in-process counter can serve as a degraded fallback so you do not fully lose limiting when the shared store has a short outage — but with N instances each enforcing the limit independently, total allowed traffic can reach up to N× the limit until the shared store returns.

Tradeoffs & bottlenecks

• Accuracy vs cost. Sliding window log is exact but memory-heavy; sliding window counter trades a small, bounded approximation for O(1) memory. Pick based on how much boundary burst you can tolerate.
• Burst tolerance. Token bucket allows bursts (good for spiky clients); leaky bucket suppresses them (good for fragile downstreams). They're opposite tools.
• Centralized counter latency vs local accuracy. A shared Redis is accurate but adds a network hop per request; a purely local per-instance counter is fast but lets total traffic reach N × instances. Some systems run local counters that periodically sync, trading exactness for latency.
• Hot-key shard pressure. One abusive key concentrates load on its shard; its own limit bounds the blast radius, but extreme cases may need that key's traffic shed upstream.
• Fail-open vs fail-closed. Availability vs backend protection — there's no universally right answer, only an explicit, justified one.

Extensions if asked

If the interviewer wants to push beyond the core limiter, add only the extension that changes the design discussion:

• Abuse and bot defense. Add IP/device fingerprinting, per-route limits, and temporary bans.
• Queueing instead of rejecting. For some systems, you may delay requests instead of returning 429.
• Notification or retry backoff. If rejected clients need later delivery, use queues and retries.

What interviewers look for & common mistakes

What interviewers usually reward:

• Precise algorithm comparison, especially naming the fixed-window boundary burst (2N in ~2 seconds) and how sliding window counter fixes it cheaply.
• Atomic distributed counting — identifying the read-modify-write race and using INCR+EXPIRE or a Lua EVAL for atomicity, plus sharding by key.
• Right placement at the gateway/middleware so abuse is rejected before reaching services.
• Correct response — 429 + Retry-After and the rate-limit headers.
• An explicit fail-open/fail-closed decision for store outages.

Before you finish, do a quick mistake check:

• Did you explain why the counter update is atomic?
• Did you handle expiry atomically for fixed-window counters?
• Did you name the fixed-window boundary burst?
• Did you explain the memory cost of sliding-window log?
• Did you distinguish token bucket from leaky bucket?
• Did you return 429 plus Retry-After for rejected requests?