Why this matters

The rate limiter worked example is deliberately different in character from the previous three: it's a cross-cutting infrastructure concern (referenced already in Chapter 9's API Gateway discussion) rather than a full end-user-facing product, and its "hardest part" is algorithmic and distributed-systems-flavored rather than about data modeling or fan-out.

Step 1: Clarify requirements

Clarifying questions: "Rate limit by what dimension — per user, per IP, per API key? What should happen when the limit is exceeded (reject outright, queue, degrade)? Does the limit need to be enforced precisely, or is some approximation acceptable? Is this for one server or distributed across many?"

Assumed answers: rate limit per API key; exceeding the limit returns an HTTP 429 (Too Many Requests) response; some approximation is acceptable in exchange for performance; must work correctly across many distributed application servers (directly connecting to Chapter 6's horizontal scaling — the rate limiter itself must account for the system it's protecting also being horizontally scaled).

Step 2: Estimate scale

Assume 100,000 distinct API keys, each individually rate-limited to
100 requests/minute, with the overall system handling up to 500,000
requests/second in aggregate across all keys combined -- the rate
limiter itself must add negligible latency per request at this volume,
since it sits in the critical path of EVERY single request.

Step 3: Sketch a high-level design

Client --> Load Balancer --> [Rate Limiter Check] --> Application Service
                                     |
                                     v
                          Shared, fast counter store (Redis)
                          (per-API-key request counts, since
                           MULTIPLE application server instances,
                           per Chapter 6, must share ONE consistent
                           view of each key's usage)

Step 4: Deep-dive — the hardest part: choosing a rate-limiting algorithm that's both correct and fast under distribution

Why this is the hardest part: "The core challenge here isn't the architecture diagram — it's picking an algorithm that correctly enforces the limit even with many distributed application servers all checking and updating the SAME shared counter simultaneously, without that shared counter becoming a bottleneck or a source of race conditions."

Fixed window counter: count requests in fixed time windows (e.g., "requests this calendar minute"); reset the counter at each window boundary.

Simple, but has a real correctness flaw: a burst of requests right at a
window boundary (e.g., 100 requests in the last second of one window,
another 100 in the first second of the NEXT window) allows 200 requests
in effectively 2 seconds, well above the intended 100/minute rate --
the fixed window boundary creates an exploitable edge case.

Sliding window log: record the timestamp of every individual request; count how many timestamps fall within the last 60 seconds, sliding continuously rather than resetting at fixed boundaries.

Precisely correct -- no boundary exploit -- but requires storing every
individual request's timestamp, which is memory-expensive at high volume
(500,000 req/s means a LOT of timestamps to store and query against).

Token bucket (the chosen approach): each API key has a "bucket" that holds up to N tokens, refilling at a steady rate (e.g., 100 tokens/minute); each request consumes one token, and a request is rejected if the bucket is empty.

# Conceptual token bucket check, using Redis for the shared, distributed state
def check_rate_limit(api_key: str, max_tokens: int = 100, refill_rate_per_sec: float = 100/60) -> bool:
    now = time.time()
    bucket = redis.hgetall(f"bucket:{api_key}")
    last_refill = float(bucket.get("last_refill", now))
    tokens = float(bucket.get("tokens", max_tokens))

    elapsed = now - last_refill
    tokens = min(max_tokens, tokens + elapsed * refill_rate_per_sec)  # refill based on elapsed time

    if tokens < 1:
        return False  # rate limited -- reject with HTTP 429

    redis.hset(f"bucket:{api_key}", mapping={"tokens": tokens - 1, "last_refill": now})
    return True  # allowed

Reasoning stated explicitly: "I'd choose token bucket specifically because it avoids the fixed window's boundary-burst exploit, handles legitimate bursty-but-average-compliant traffic more gracefully than a strict sliding window would (directly the companion Networking book's Chapter 4 point about token bucket's real-world traffic-shaping advantage), and is far more memory-efficient than a sliding window log, since it only needs to store two numbers per key (token count and last refill time) rather than every individual request timestamp."

Step 5: Discuss trade-offs and failure modes

"There's a real race condition risk here: two application servers could both read the same bucket's token count simultaneously, both see enough tokens, and both allow a request that together exceed the limit — I'd use Redis's atomic operations (or a Lua script executed atomically within Redis) to make the read-check-decrement sequence a single atomic operation, directly the same check-then-act race condition problem the companion Database book's Chapter 3 and Concurrency book's Chapter 3 both cover, just at the infrastructure-component level here. If the shared Redis store itself becomes unavailable, I'd need to decide explicitly: fail open (allow all requests, risking overload, but keeping the system available) or fail closed (reject all requests, guaranteeing the rate limit is never violated, at the cost of a full outage) — I'd lean toward failing open for most APIs, since an overload risk is usually preferable to a complete, self-inflicted outage, but this is a genuine, context-dependent judgment call worth stating explicitly rather than assuming."

Common mistakes

1. Proposing a fixed window counter without recognizing its boundary-burst exploit, missing the specific correctness flaw that makes it a weaker choice than token bucket for most real use cases.
2. Not addressing the distributed race condition on the shared counter, missing that multiple application servers checking and updating the same counter concurrently is exactly the check-then-act hazard covered in this book series' Concurrency and Database volumes, now appearing at the infrastructure level.
3. Not explicitly deciding and stating a fail-open vs. fail-closed policy for the rate limiter's own backing store failing — this is a real, concrete failure mode (Chapter 12) that a complete design should address rather than leave implicit.
4. Choosing a sliding window log without acknowledging its real memory cost at high volume, missing the trade-off against token bucket's much smaller per-key storage footprint.

Chapter summary / cheat sheet

• Rate limiter algorithms: fixed window (simple, but has a boundary-burst exploit), sliding window log (precisely correct, but memory-expensive at scale), token bucket (the chosen approach — avoids the boundary exploit, memory-efficient, handles bursty-but-compliant traffic gracefully).
• The distributed correctness challenge: multiple application servers checking/updating the same shared counter is a check-then-act race condition requiring atomic operations (Redis atomic ops or a Lua script) — the same hazard covered at the code level in this book series' Concurrency and Database volumes, now at the infrastructure level.
• A complete design explicitly addresses what happens if the rate limiter's own backing store fails — fail open (availability-preferring) versus fail closed (strictness-preferring) is a genuine, context-dependent judgment call worth stating explicitly.
• This worked example's "hardest part" is algorithmic and concurrency-flavored, a deliberately different character from the previous three worked examples' data-modeling and fan-out-flavored challenges — together, the four demonstrate that Chapter 13's framework adapts to genuinely different kinds of hard problems, not just one recurring shape.

---

End of Book

"Designing at Scale: A Practical Guide to System Design" — 17 chapters, complete.

Next book in the suggested reading order: HLD & LLD.