Module 03: Designing a Rate Limiter

Why this matters

A rate limiter is the component that answers "should this request be allowed right now, or rejected because the caller has done too much too fast?" It's how you protect a system from abuse, from accidental thundering herds, from a single misbehaving client exhausting shared capacity, and from cost blowouts on expensive downstream calls. You already met rate limiting as a concrete middleware in 09-security-deep-dive; this module zooms out to the design problem: how do you enforce a limit accurately and cheaply across a fleet of servers, where no single machine sees all of a user's traffic?

That's what makes it a favorite interview problem — it's deceptively small but forces precise thinking about algorithms (token bucket vs. sliding window each have real, testable differences in burst behavior and memory), shared distributed state (the counter has to live somewhere every server can atomically update — usually Redis), race conditions (two servers checking-then- incrementing the same counter concurrently), and the classic accuracy vs. cost vs. latency tradeoff. Get this right and you can reason about any "enforce a global constraint across a distributed fleet" problem, of which rate limiting is the cleanest example.

Concepts

Requirements and scope

Functional:

• Allow or reject a request based on whether the caller (by user id, API key, or IP) has exceeded a configured limit (e.g. 100 requests/minute).
• Support different limits for different callers/tiers and different endpoints.
• On rejection, return HTTP 429 Too Many Requests, ideally with a Retry-After header telling the client when to try again.

Non-functional:

• Low latency. The limiter sits in front of every request, so its own overhead must be tiny (sub-millisecond) — it can't become the bottleneck it's meant to prevent.
• Distributed accuracy. In a fleet of N app servers, the limit is global ("100/min per user across the whole service"), not per-server. State must be shared.
• Highly available & fail-open vs. fail-closed. If the limiter's datastore is unreachable, do you allow all traffic (fail-open, favors availability) or block it (fail-closed, favors protection)? A real decision tied to what you're protecting.
• Low memory. With millions of distinct callers, per-caller state must be compact.

Where the limiter lives

The limiter can sit at several layers, and the choice affects both what it can see and how much it protects:

• At the API gateway / load balancer / reverse proxy (recall the gateway/BFF from 11-advanced-api-paradigms). Centralizes enforcement before requests reach app servers; protects the whole backend. Common in practice.
• As middleware in each app server (like the 09-security-deep-dive middleware). Simpler to deploy with the app, but every instance must consult shared state to enforce a global limit — which is the crux of the design.
• As a dedicated rate-limiter service the app calls. Cleanest separation and reusable across services, at the cost of an extra network hop per request.

Wherever it lives, the enforcement logic needs a shared, fast, atomic counter store — almost always Redis — because the limit is global and many servers update the same counter concurrently.

The algorithms (this is the heart of the problem)

Five classic algorithms, in roughly increasing sophistication. Know the burst behavior, memory, and accuracy of each.

• Fixed window counter. Count requests per fixed time bucket (e.g. per minute); reset at the boundary. One integer per caller per window — tiny and simple. Flaw: a burst straddling the boundary can allow up to 2× the limit — 100 requests at 11:00:59 and 100 more at 11:01:00 pass, 200 in two seconds.
• Sliding window log. Store a timestamp for every request; on each new request, drop timestamps older than the window and count what's left. Perfectly accurate, no boundary flaw. Flaw: memory grows with request volume (a timestamp per request per caller) — expensive at scale.
• Sliding window counter. A hybrid: keep the current and previous fixed- window counts and weight the previous window by how much of it still overlaps the sliding window. Smooths the boundary burst of the fixed window using O(1) memory. A very common production choice — good accuracy, cheap.
• Token bucket. A bucket holds up to capacity tokens and refills at a steady refill_rate tokens/sec; each request consumes one token, and a request with no token available is rejected. Allows bursts up to the bucket capacity while enforcing a long-run average rate — often exactly the behavior you want (tolerate short spikes, cap sustained rate). O(1) state per caller (two numbers: token count + last-refill timestamp).
• Leaky bucket. Requests enter a fixed-size queue and are processed (leak out) at a constant rate; a full queue rejects new requests. Smooths bursty input into a steady output rate — good when the thing you're protecting needs a constant processing rate, at the cost of added latency (queued requests wait).

The most-reached-for defaults are token bucket (when bursts are acceptable and you want a simple average-rate cap) and sliding window counter (when you want accurate windowed limits with tiny memory). The token bucket's refill-and- consume cycle is the one to picture — tokens trickle in at a fixed rate, each request drains one, and an empty bucket rejects:

   refill_rate ──► ○ ○ ○ ○ ○      capacity = 5 (max burst)
   (e.g. 10/sec)   └─ bucket ─┘
                       │
        request ──► take 1 token? ──yes──► ALLOW (tokens -= 1)
                       │
                       └────────── no (empty) ──► REJECT → 429

Distributed state and race conditions

The subtle, high-signal part. In a fleet, a naive "read counter, check limit, write counter+1" is a read-modify-write race: two servers read count=99 simultaneously, both see it's under 100, both write 100, and two requests pass when only one should. The fix is to make the check-and-increment atomic:

• Atomic increment — Redis INCR returns the new value in one atomic op, so each request gets a unique count; the first read that exceeds the limit rejects. Combine with EXPIRE to reset the window.
• Atomic compound logic via a Lua script. Token bucket needs to read tokens, compute refill, decrement, and write back atomically — a Redis Lua script runs the whole read-modify-write as one atomic unit on the server, eliminating the race without round-trips.

This is the same class of problem as the distributed lock and idempotency work in 10-distributed-systems-patterns: whenever multiple nodes mutate shared state, you need an atomic primitive or you get lost updates. Rate limiting is the cleanest illustration.

Accuracy vs. cost vs. latency (the tradeoffs)

Every algorithm and deployment choice trades among three things:

• Accuracy — how precisely you enforce the limit (sliding window log is exact; fixed window is loose at boundaries).
• Memory/cost — per-caller state size × number of callers (log is expensive; counter/token-bucket are O(1)).
• Latency — a shared central store adds a network hop per request; some designs trade accuracy for speed by allowing each server a local sub-limit and syncing periodically (fast, but the global limit becomes approximate).

The fail-open vs. fail-closed decision belongs here too: if Redis is down, fail-open keeps the product working but drops protection; fail-closed keeps protection but causes an outage. For most user-facing traffic, fail-open is the common default (a rate limiter shouldn't take the whole site down); for protecting something expensive or dangerous (a payment endpoint, a costly downstream), fail-closed may be right. State the choice and its justification.

Reference architecture

The full enforcement path: every request enters through the edge, is checked by limiter middleware against shared atomic counters, and either passes to the backend or is rejected with a 429. A config service feeds per-client limits, and a fail-open/closed branch handles the counter store being unreachable:

                                      ┌──────────────────────┐
                                      │   Config service     │
                                      │ per-client/per-route │
                                      │ limits (tiers)       │
                                      └───────────┬──────────┘
                                        push limits│
                                                   ▼
  ┌────────┐        ┌───────────────────────────────────────────┐
  │ Client │ ─────► │        API Gateway / Edge                  │
  └────────┘        │  ┌─────────────────────────────────────┐  │
                    │  │   Rate-limiter middleware           │  │
                    │  │   key = user/API-key/IP + route     │  │
                    │  └──────────────┬──────────────────────┘  │
                    └────────────────┬┴─────────────────────────┘
                                     │  atomic check-and-update
                                     ▼
                          ┌────────────────────────┐
                          │  Redis / Redis Cluster │
                          │  token-bucket / sliding│
                          │  window counters;      │
                          │  INCR+EXPIRE or Lua    │
                          └───────┬────────┬───────┘
                    reachable     │        │   UNREACHABLE
                 allowed / 429    │        │        │
                                  ▼        │        ▼
                    ┌──────────────────┐   │   ┌──────────────────────┐
                    │  Backend App     │   │   │ fail-open  → allow    │
                    │  servers         │◄──┘   │ fail-closed→ reject   │
                    └──────────────────┘       └──────────────────────┘
                    (rejected requests → 429 Too Many Requests + Retry-After)

Component walkthrough:

• Client — the caller identified by user id, API key, or IP; that identity becomes the counter key that scopes the limit.
• API Gateway / Edge with rate-limiter middleware — the enforcement point, sitting in front of every request (the "where the limiter lives" choice). The middleware builds a per-caller-per-route key and consults shared state before the request ever reaches an app server, so its own overhead must be sub-ms.
• Redis / Redis Cluster (atomic counter store) — the shared global state every edge node updates. It holds token-bucket tokens+timestamps or sliding-window counters, mutated atomically via INCR+EXPIRE or a Lua script so concurrent nodes can't race (read-modify-write correctness). Clustering shards the millions of per-caller counters when they outgrow one node.
• Config service — pushes per-client and per-route limits (free/pro/enterprise tiers, per-endpoint caps) into the middleware, so one code path serves all tiers by looking up the caller's parameters rather than hard-coding limits.
• Backend App servers — the protected resource. Allowed traffic passes through; this is what the limiter shields from abuse and thundering herds.
• Fail-open / fail-closed branch — the decision path when Redis is unreachable. Fail-open lets traffic through (favors availability, default for public endpoints); fail-closed rejects it (favors protection, right for payment or expensive-downstream routes). Rejections return 429 + Retry-After.

Command reference

Algorithm comparison — memorize this table; it's the crux of the interview.

Key numbers and mechanics:

429 Too Many Requests  +  Retry-After: <seconds>   ← the rejection response
Redis INCR + EXPIRE     ← atomic fixed-window counter, race-free
Redis Lua script        ← atomic token-bucket read-modify-write
fail-open   = allow on store outage   (favors availability)
fail-closed = reject on store outage  (favors protection)

Token-bucket implementation (the one to be able to write from memory):

import time

class TokenBucket:
    def __init__(self, capacity: int, refill_rate: float):
        self.capacity = capacity          # max tokens (burst size)
        self.refill_rate = refill_rate    # tokens added per second
        self.tokens = float(capacity)
        self.last = time.monotonic()

    def allow(self, cost: int = 1) -> bool:
        now = time.monotonic()
        # refill based on elapsed time, capped at capacity
        self.tokens = min(self.capacity,
                          self.tokens + (now - self.last) * self.refill_rate)
        self.last = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True          # allowed
        return False             # rejected → 429

The distributed version moves tokens/last into Redis and runs the refill-check-decrement as an atomic Lua script so concurrent servers can't race. As FastAPI middleware:

from fastapi import Request
from fastapi.responses import JSONResponse

async def rate_limit_middleware(request: Request, call_next):
    key = f"rl:{client_id(request)}"
    allowed, retry_after = redis_token_bucket(key, capacity=100, rate=100/60)
    if not allowed:
        return JSONResponse(
            status_code=429,
            content={"detail": "rate limit exceeded"},
            headers={"Retry-After": str(retry_after)},
        )
    return await call_next(request)

Hands-on exercises

Written and pseudocode exercises — reason about correctness and tradeoffs.

1. Expose the fixed-window boundary flaw

With a limit of 100 requests/minute using a fixed window, construct the exact sequence of requests and timestamps that lets 200 requests through in a ~2- second span without violating the per-window count. Then explain in one sentence which two algorithms fix it and how.

2. Pick the algorithm per scenario

For each, name the best-fit algorithm and justify in one line: (a) an API that should tolerate short bursts but cap the sustained rate; (b) a downstream that must be fed at a strictly constant rate; (c) a limit that must be accurate at the window boundary but use minimal memory; (d) a compliance requirement for exactly N per rolling hour, memory no object.

3. Write the token bucket from memory

Without looking, implement TokenBucket.allow() — refill by elapsed time, cap at capacity, consume on success. Then answer: what do capacity and refill_rate each control in observable behavior, and how would you set them for "burst of 50, sustained 10/sec"?

4. Find and fix the race condition

This distributed limiter is wrong. Identify the race and rewrite it to be correct.

def allow(user_id):
    key = f"rl:{user_id}:{current_minute()}"
    count = redis.get(key) or 0        # read
    if int(count) >= 100:              # check
        return False
    redis.set(key, int(count) + 1)     # modify-write
    redis.expire(key, 60)
    return True

5. Size the state

You have 50M distinct API keys, each needing token-bucket state of two 8-byte numbers (~16 bytes, call it ~50 bytes with Redis key overhead). Estimate total memory. Does it fit in one Redis node (~256 GB)? Now redo it for the sliding window log if each active caller averages 1,000 requests in the window — what happens to the memory, and what does that tell you about algorithm choice at scale?

6. Design the fail mode

Your rate limiter's Redis becomes unreachable during a spike. Design the behavior for two different endpoints: a public read-only search endpoint, and a POST /payments/charge endpoint. Choose fail-open or fail-closed for each and justify from what each endpoint protects. Reference the availability-vs- protection framing.

7. Multi-tier and multi-key limits

Design limits that apply simultaneously: 10 req/sec per IP and 1,000 req/hour per API key and 100 req/min per endpoint-per-user. Explain how you'd evaluate all three per request, what you return when any one trips, and how you'd keep the total Redis round-trips low (hint: pipeline / a single Lua script).

8. Diagnose and fix a flawed design

Critique and fix this design.

"Each app server keeps an in-memory dictionary counts[user_id] and allows 100 requests/minute per user by incrementing it, resetting every minute with a local timer. We run 20 app servers behind a round-robin load balancer. On reject we return 403 Forbidden. If a server restarts, its counts reset. We chose this because it's fast and needs no external dependency."

Independent challenge

No solution given. Design a rate limiter for a public API with tiered pricing — free, pro, and enterprise tiers with different limits — that also needs to protect an expensive downstream ML inference service whose calls cost real money. Your design must enforce per-tier limits accurately across a fleet, pick an algorithm justified by the burst behavior you want, choose a fail mode justified by what's being protected, and return proper 429s with Retry-After. Reuse the atomic-state reasoning from 10-distributed-systems-patterns: the per-tier counters live in shared storage and must be updated race-free under concurrent load. Then estimate the Redis memory for your expected number of active keys.

Common mistakes & troubleshooting

• Per-server local counters for a global limit. N servers → N× the intended limit. The limit is global; the state must be shared.
• Read-modify-write race on the counter. Concurrent check-then-increment lets extra requests through. Use an atomic primitive (INCR, or a Lua script for compound logic).
• Wrong status code. Returning 403 (or 503) instead of 429 Too Many Requests with Retry-After. 429 is the specific, correct signal.
• Ignoring the fixed-window boundary flaw. Claiming a fixed-window enforces the limit when a boundary-straddling burst doubles it. Know the flaw and when it matters.
• Sliding window log at scale. A timestamp per request per caller blows up memory. Use the sliding window counter (O(1)) unless exactness is mandatory.
• No fail-mode decision. Not saying what happens when Redis is down. Choose fail-open or fail-closed per what's protected and state it.
• Confusing token bucket and leaky bucket. Token bucket allows bursts to capacity; leaky bucket smooths to a constant output rate. They produce different traffic shapes — pick by the behavior you want.

Checkpoint quiz

Write down your answer to each question before expanding it — checking without attempting first is the single easiest way to fool yourself into thinking you've learned this.

1. What HTTP status code and header does a rate limiter return on rejection, and what does the header tell the client?
2. Explain the fixed-window boundary flaw with a concrete example, and name two algorithms that fix it.
3. Contrast token bucket and leaky bucket in terms of burst behavior and output shape. When would you pick each?
4. Why can't a fleet of servers each keep a local counter to enforce a global limit, and what does the correct design use instead?
5. Describe the read-modify-write race on a shared counter and the specific Redis mechanism that eliminates it for compound (token-bucket) logic.
6. What is the fail-open vs. fail-closed decision, and which would you pick for a public search endpoint versus a payment endpoint?
7. At 50M callers, why does the sliding window log become impractical while the sliding window counter stays cheap?

Cumulative review

Closed-book. Don't reopen modules 00–03 while attempting these — the point is to find out what actually stuck.

1. A social API has 300M DAU, each making 20 requests/day. Compute average and peak request QPS (state your peak factor and the seconds-per-day constant you used), then say whether this is "one database" or "shard everything" scale and why.
2. Walk the seven-step framework in order for "design a pastebin." For each step give one sentence of what you'd produce. Which step most determines whether you need sharding, and why?
3. For a URL shortener at 100M new URLs/day, justify from the numbers why the design needs a cache and read replicas but not an exotic write path — and name the id-generation strategy that avoids both a central bottleneck and a per-creation uniqueness read.
4. Turn this bare assertion into a proper tradeoff statement using the module-01 template: "We'll use a token bucket." Invent the requirement that justifies it.
5. A candidate designs a distributed rate limiter with per-server in-memory counters and returns 403 on reject. Name the two independent bugs (one about correctness of the limit, one about the response) and fix each.
6. Give the storage formula and apply it: 20M chat messages/day, 1 KB each, kept 3 years, replicated 3×. State the total and the architectural conclusion.
7. Explain, using the latency ladder, why moving a rate limiter's counter from a cross-region database to a same-datacenter Redis matters for a component that sits in front of every request — put rough numbers on the per-request cost of each.
8. For both the URL shortener and the rate limiter, identify the single shared distributed-systems primitive that makes the write path correct under concurrency, and name the module (00–03) where you'd expect to have learned the general pattern.

Further reading & sources

• Stripe — Scaling your API with rate limiters - Stripe's production account of token buckets, concurrency limits, and load shedding on a real payments API.
• Cloudflare — How we built rate limiting capable of scaling to millions of domains - the engineering behind sliding-window counting at massive scale, mirroring this module's accuracy-vs-memory tradeoffs.
• Token bucket algorithm - the canonical reference for the refill/consume model and how it enforces an average rate while allowing bursts.
• Leaky bucket algorithm - the companion algorithm that smooths bursty input into a constant output rate.
• Redis — INCR and atomic counters - the atomic primitive that eliminates the read-modify-write race central to distributed rate limiting.
• Redis — EVAL / Lua scripting - how to run the compound token-bucket read-modify-write atomically server-side without round-trip races.
• Rate Limiting and Abuse Prevention - the algorithms in depth (fixed and sliding window, token and leaky bucket) and how to apply them against abuse.
• Retries, Prioritization, and Rate Limiting in Queues - rate limiting applied to background workers calling a limited downstream API.

Free PDF notes

Download these notes as a printable PDF, with every diagram and interview questions: SD-C-013: Distributed Rate Limiting. Each section in one file: Phase 2, APIs (PDF).

Next

04-designing-a-distributed-cache-and-key-value-store — the last two problems used a cache and a partitioned store as black boxes; next you'll design the black box itself: consistent hashing, replication, eviction, and the CAP/consistency tradeoffs that decide how a distributed key-value store behaves under failure.