2. Rate Limiter Beginner → Advanced+Distributed

A. Realistic Interview Prompt

This problem is a deliberate contrast to URL Shortener: there, the interesting complexity was mostly architectural (caching, sharding, service separation). Here, a huge fraction of the signal comes from a much narrower, more algorithmic question — which counting algorithm, and how do you make counting atomic under concurrency — before the architecture even matters. Candidates who skip straight to "I'll use Redis" without picking and justifying an algorithm are leaving most of the interview on the table.

B. Difficulty

Beginner-friendly entry point (everyone can describe "count requests, reject over the limit") that becomes Advanced + Distributed the moment a second server enters the picture — which happens almost immediately in any real follow-up. Unlike URL Shortener, this problem front-loads a genuine algorithms-and-data-structures decision (five real algorithms, each with a real flaw) before the distributed-systems layer even starts.

C. What This Problem Tests

• Whether you know more than one rate-limiting algorithm and can articulate each one's specific failure mode, not just "token bucket is popular"
• Race-condition reasoning at the data-store level — read-then-write across concurrent nodes is the same class of bug as double-spending a resource, just expressed as a counter instead of a physical object
• Judgment on where an infra component belongs in a request path (in-app vs. sidecar vs. gateway) — an architectural decision independent of the algorithm
• A concrete, defensible opinion on fail-open vs. fail-closed — there is no universally correct answer, and the interviewer is testing whether you can reason about the trade-off, not guess the "right" one
• Comfort admitting a problem (multi-region enforcement) has no single clean answer, and reasoning through the options anyway instead of hand-waving

D. Requirements

Functional

1. Limit how many requests a client (identified by user ID, IP, or API key) can make within a configurable time window (e.g., 100 requests/minute per user)
2. When a client exceeds its limit, reject the request with HTTP 429 Too Many Requests and informative metadata (remaining quota, reset time) — not just a bare rejection
3. Support different limit rules for different clients/endpoints (configurable, not one hardcoded global number)

Non-Functional

• High throughput — the limiter sits in front of every request to the protected service, so it must sustain the scale target itself; this document uses 1M requests/sec across 100M DAU as a standard, illustrative target
• Low overhead — the check itself should add <10ms per request; a rate limiter that makes every request slower defeats its own purpose
• High availability — the limiter failing should never be allowed to take the entire protected service down with it (see the fail-open/fail-closed decision, P)
• Approximate correctness is acceptable — eventual consistency across nodes is fine; enforcing exactly 100 vs. occasionally letting through 101–105 during a node failure is an acceptable trade, not a bug worth heavy coordination to avoid

Out of scope: authenticating the client's identity itself (assume that already happened upstream — the limiter just consumes a client ID), billing/quota-purchase workflows.

E. Clarifying Questions

F. Assumptions

• Confirmed: per-client, configurable-window limiting with a 429+metadata response on rejection.
• Assumption: standalone rate-limiting layer living at the API Gateway, not a library embedded per-application — the more common, more interesting version of this problem, and the default most sources converge on.
• Assumption: eventual consistency across nodes is acceptable (per D) — this single assumption is what makes the whole design tractable without heavyweight distributed consensus.
• Assumption: fail-closed on infrastructure failure (protect the backend over allowing all traffic) — defended in P, not just asserted.
• Assumption: single-region base design (J–Q); multi-region is an explicit, clearly-flagged extension (R), not baked in from the start.

G. Capacity Estimation

A key difference from URL Shortener: there, QPS was derived from user behavior (DAU × clicks/day). Here, the target QPS is really a provisioning target for abuse/burst survival, not a number you derive from "average" traffic — a rate limiter that's sized for average traffic and falls over during the exact burst it exists to defend against has failed at its one job. So the 1M req/sec figure below is stated as a design target (matching Hello Interview's own framing), not derived from DAU × avg-requests the way Deep Dive numbers elsewhere in this document are.

H. Core Entities

I. API Design

Internal check interface (called by the Gateway on every request):
  isAllowed(client_id, rule_id) -> { allowed: bool, remaining: int, reset_at: timestamp }

HTTP contract exposed to the end client of the protected service:
  200 OK (allowed)
    Headers: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset
  429 Too Many Requests (denied)
    Headers: same as above, plus Retry-After
    Body: { "error": "rate_limit_exceeded", "retry_after": <seconds> }

Why return quota metadata instead of a bare 429: it lets well-behaved clients back off precisely until reset_at instead of blind-retrying (which just adds more load exactly when the system is already stressed) — a product decision as much as a technical one, and worth stating explicitly rather than assuming a bare rejection is enough.

J. Basic / Naive High-Level Design (V1)

The simplest thing that satisfies the functional requirements in isolation: an in-process counter, local to each API server instance.

V1 — each server counts independently. Looks fine with one server; breaks the instant there are two.

Why this breaks immediately, not eventually: with N servers behind a load balancer, a client hitting different servers on different requests gets counted N separate times — effectively an N× larger limit than intended, with zero coordination between servers to catch it. Unlike URL Shortener's V1 (which works fine at small scale and degrades gracefully), this V1 is already broken the moment there's more than one server — which is true of essentially any real deployment. This is exactly why a shared external counter store is not an optimization here, it's a correctness requirement from step one.

K. Data Model & Store Choice

Why Redis (or an equivalent in-memory KV store), not a relational DB: the access pattern is an extremely high-frequency read-and-increment on small, short-lived keys — exactly what an in-memory store with atomic single-command operations and native TTL/expiry is built for. A relational DB would add durability guarantees this data doesn't need (losing a rate-limit counter on restart is harmless — the client just gets a fresh window) and disk-backed latency this problem's <10ms budget can't afford.

Key schema: ratelimit:{rule_id}:{client_id} — using Redis Cluster hash-tag braces ({...}) around the part of the key that must colocate on one shard, which matters specifically for the sliding-window-counter algorithm's two-key design (current + previous window) in M, since both keys for one client must live on the same shard to be read together.

L. End-to-End Flow

M. Deep Dive 1 — Choosing the Rate-Limiting Algorithm

Requirement this addresses: the functional limiting itself — but the choice of algorithm is where most of the real trade-offs live, and it's worth resolving before any distributed-systems concern.

A real accuracy data point worth citing: Cloudflare's own production measurement of their sliding-window-counter implementation found only 0.003% of requests were wrongly allowed or rejected out of 400 million requests — strong evidence that the "approximate" algorithms are accurate enough in practice to justify their far lower memory cost over the exact-but-expensive sliding-window-log.

Recommendation: token bucket when burst tolerance for legitimate clients matters (the common case — most real APIs have some batch/retry-driven burstiness); sliding-window counter when the priority is smoothing out the fixed-window boundary exploit with minimal memory, and burst tolerance isn't a goal. Both are reasonable defaults — naming the boundary-burst flaw of fixed-window and the memory cost of sliding-log is the real signal, more than which of the remaining two you personally prefer.

N. Deep Dive 2 — Atomicity Under Concurrency

Requirement this addresses: correctness when multiple Gateway instances check the same client's counter concurrently — the single most important correctness property in this entire design.

The race, explicitly: "read the current count," "check against the limit," and "increment" look like one operation but are three. If two Gateway instances both read the count as 99 (limit 100) at nearly the same instant, both may independently decide "allowed" and both increment — the client is now at 101, and the check that was supposed to prevent exactly this just failed. This is the identical shape of bug as two threads racing for the last parking spot in the LLD handbook's Parking Lot problem — a check-then-act race — just expressed here as a distributed counter instead of a shared object.

The fix — an atomic Lua script executed server-side inside Redis, not two separate round-trips from the application. A simplified token-bucket version (adapted from Redis's own published rate-limiter recipes):

-- runs atomically inside Redis; no other client's script can interleave
local bucket = redis.call('HMGET', key, 'tokens', 'last_refill')
local now = redis.call('TIME')[1]              -- server time, not the caller's clock
local tokens, last_refill = tonumber(bucket[1]) or capacity, tonumber(bucket[2]) or now
local refills = math.floor((now - last_refill) / refill_interval)
if refills > 0 then
  tokens = math.min(capacity, tokens + refills * refill_rate)
  last_refill = last_refill + refills * refill_interval
end
local allowed = 0
if tokens >= 1 then tokens = tokens - 1; allowed = 1 end
redis.call('HMSET', key, 'tokens', tokens, 'last_refill', last_refill)
return {allowed, tokens}

Why Lua, not MULTI/EXEC: Redis transactions (MULTI/EXEC) queue a fixed batch of commands and run them atomically, but they can't branch on a value read earlier in the same transaction — you can't say "read the count, and only increment if it's below the limit" inside one MULTI block. A Lua script runs as a single atomic unit but is a real program: it can read, compute, and conditionally decide to write, all inside that one atomic step. That conditional-branch-on-a-just-read-value is exactly what this problem needs and MULTI/EXEC structurally cannot provide.

Why the script calls Redis's own TIME command instead of the caller passing a timestamp: if each Gateway instance used its own local clock, clock drift between instances could let a client be double-counted or under-counted right at a window boundary. Computing time inside Redis, on one clock, removes an entire class of subtle multi-node bugs for free.

O. Deep Dive 3 — Scaling to 1M Requests/Sec

Requirement this addresses: Throughput (D, G) — a single Redis instance's ~100K–200K ops/sec ceiling is well below the 1M/sec target.

Sharding via consistent hashing on client_id: ~10 Redis shards, each handling ~100K ops/sec, clear the 1M/sec target with room to spare. Consistent hashing (not simple modulo) is chosen specifically because it's the standard, well-understood way to add/remove shards later while only remapping a small fraction of keys — the same rationale used anywhere shards need to grow without a full rehash. Critically, a given client's key must always land on the same shard — you cannot split one client's counter across two shards and still check it atomically, so this isn't just a load-balancing choice, it's a correctness requirement (same principle as the hash-tag braces in K).

A client's key always resolves to the same shard — required for the atomic check in N to mean anything.

Connection pooling: a fresh TCP handshake per check can cost ~20–50ms — several times the entire <10ms per-check latency budget from D. Pooled, persistent connections between each Gateway instance and its Redis shards are not an optimization here, they're required to meet the stated latency NFR at all.

P. Deep Dive 4 — High Availability & the Fail-Open/Fail-Closed Decision

Requirement this addresses: Availability (D) — specifically, what happens when the rate-limiting store itself is unreachable.

Why fail-closed: the rate limiter's entire purpose is backend protection; choosing fail-open specifically fails at that purpose during the one event (infrastructure stress) most likely to coincide with the traffic spikes it exists to defend against. This is a defensible, opinionated choice — a candidate arguing fail-open with a clear justification (e.g., "this API's uptime SLA is more important than a rare overload") is equally strong, as long as the trade-off is named, not assumed away.

Making the fail-closed path rare in practice: Redis Cluster or Sentinel gives each shard a master-replica pair with automatic failover, so a single node failure — the common case — never actually reaches the fail-closed branch at all. Fail-closed is the safety net for the rare case where HA itself fails, not the primary defense.

Q. Deep Dive 5 — The Hot-Key / Single Abusive Client Problem

Requirement this addresses: a distinct scaling problem from O — O assumes well-distributed aggregate traffic; this addresses one concentrated source (an abusive client, or a DDoS from one IP range) overwhelming its single shard.

Why sharding (O) can't fix this on its own: consistent hashing on client_id is exactly what makes the atomic check correct (O) — but it also means one client's traffic can never be spread across multiple shards without breaking that same correctness guarantee. A hot key is hot by definition on exactly one shard.

• Coarse pre-filtering at the edge/CDN (Cloudflare-style), before traffic ever reaches the sharded Redis layer — cheap, approximate blocking of obviously abusive patterns (packet rate, known bad IP ranges) that never needs per-client precision.
• Auto-blocklisting — once a client has been rejected repeatedly, skip the Redis check entirely and reject immediately; cheaper than paying for a Lua-script round-trip for a client you already know you're going to reject.
• Dedicated capacity for known high-volume legitimate clients (API partners) — so a large but legitimate client doesn't compete with the general pool's shard capacity in the first place.

R. Deep Dive 6 — Multi-Region / Global Rate Limiting

This is genuinely the most open-ended part of the problem — there is no single canonical answer across sources, and naming that honestly, then reasoning through the real options, is stronger than picking one and pretending it's obviously correct.

Recommendation: home-region pinning as the default (it's the same sharding idea already used within a region, just applied globally); fall back to async cross-region sync only for the genuinely hard case of a single client's traffic legitimately spanning regions (e.g. a mobile user roaming) where a single "home" doesn't make sense.

S. Deep Dive 7 — Where to Enforce the Limit

Requirement this addresses: an architectural placement decision, independent of the algorithm (M) or the store (K) — revisits J's rejected in-process approach with the fuller comparison.

The trade-off worth naming for the Gateway choice: the Gateway itself must now scale to the full 1M req/sec target (it already had to handle this traffic anyway, so this is not new load, but it is new responsibility), and a Gateway-level bug or outage has a wider blast radius — it affects every downstream service uniformly, unlike a per-service sidecar failure which is contained to one service.

T. Full Solution at Scale — Final Architecture

Everything above is the composition of M through S — no new component introduced here.

U. Design Evolution

• V1 — in-process local counter (J): broken the moment there's more than one server.
• V2 — shared Redis, fixed-window counter: fixes cross-instance blindness, but inherits the 2× boundary-burst flaw (M).
• V3 — switch to sliding-window-counter or token bucket: fixes the boundary-burst flaw (M).
• V4 — atomic Lua script: fixes the concurrent read-then-write race (N).
• V5 — shard via consistent hashing + connection pooling: hits the 1M req/sec target (O).
• V6 — Redis HA + fail-closed policy: survives store failures without silently defeating the limiter's purpose (P).
• V7 — edge pre-filter + blocklisting: handles concentrated abuse a shard-balanced design can't (Q).
• V8 — home-region pinning: extends the design globally (R).

What stays stable throughout: the isAllowed(client_id, rule_id) check contract and the 429+headers response shape from I — every version below the surface changes without callers noticing.

V. Consistency Model

Almost everything here is deliberately eventually/approximately consistent by design (D's NFR) — a client occasionally slipping through at 101/100 during a failover is an accepted, bounded inaccuracy, not a bug, because the system's job is coarse protection, not exact metering. The one place near-strong consistency is non-negotiable is within a single shard's Lua-script execution (N) — that step must be atomic or the entire limiter is pointless even at the smallest scale. This is the inverse emphasis of URL Shortener's model (strong uniqueness, eventual everything else) — here almost everything is eventual except one narrow, single-shard atomic operation.

W. Failure Scenarios

• A Redis shard goes down: fail-closed protects the backend; HA (master-replica + auto-failover) keeps this rare (P).
• One client's traffic is concentrated on one shard: edge pre-filtering and blocklisting absorb it before it reaches Redis (Q).
• Clock drift between Gateway nodes: mitigated by computing time inside the Lua script via Redis's own TIME command, not the caller's clock (N).
• Cross-region race briefly exceeds the global limit: accepted trade-off under async sync (R) — bounded by the sync interval, not unbounded.
• The Gateway fleet itself is overloaded: a standard horizontal-scaling problem for the Gateway, distinct from the rate-limit store's own scaling story (O, X).

X. Bottlenecks & Scaling Boundary

Y. Design Trade-Offs

Z. Common Bad Designs

• In-process counters with no shared store. Works in a single-server demo, is silently broken (not just slow) the moment a load balancer adds a second instance — the most common mistake specifically on this problem.
• Fixed-window counter presented as "the" solution with no mention of the boundary-burst flaw. It's a fine algorithm to lead with, but not naming its 2× exploit is a missed signal.
• Check-then-increment as two separate Redis calls (a GET followed by a separate INCR) instead of one atomic script — the same check-then-act race as the custom-alias mistake in the URL Shortener problem, recurring here at the counter level (N).
• Fail-open by default, unexamined. Might be the right call for a specific product, but asserting it without naming the trade-off (backend exposure during exactly the event that triggered the outage) is the actual mistake, not the choice itself.
• Sliding-window-log presented as the default "correct" choice without acknowledging its memory cost at scale — exact is not automatically better once the memory bill is 7.5× the alternative for a 0.003%-class accuracy difference.

AA. Interviewer Follow-Ups

AB. Interviewer Evaluation Rubric

• Weak candidate: "I'll count requests and reject over N" with no algorithm named, no mention of concurrency, defaults to an in-process counter.
• Mid-level: proposes fixed-window + shared Redis; doesn't yet know the boundary-burst flaw or the check-then-increment race.
• Senior: proactively picks token bucket or sliding-window-counter and explains why over fixed-window; identifies the atomicity race unprompted and proposes a Lua script or equivalent atomic primitive; separates the placement decision (Gateway vs. sidecar) from the algorithm decision explicitly.
• Staff+: discusses the hot-key problem and fail-open/closed trade-off without being asked; has a real, reasoned opinion on multi-region rather than deferring or hand-waving; can price out memory/throughput trade-offs with real numbers (as in G).

AC. Interview Simulation

AD. Online Solution Comparison

Additional cross-referenced repos (search-level only): Salah856/System-Design, sm2774us/System_Design, anshme/rate-limiter (a working implementation of Alex Xu's design), Kong's rate-limiting plugin docs (a real production API Gateway's own configuration model).

AE. Interview Cheat Sheet