Design a Rate Limiter

1. Problem & Real-World Context

A rate limiter caps how many requests a client (user, API key, IP, or service) can make in a given time window, rejecting the rest. Every public API needs one — it's the difference between a bad actor (or a buggy retry loop) taking down your service and a clean 429.

Why interviewers ask this: it looks small, but it's a Trojan horse for testing whether you understand atomicity under concurrency, distributed state sharing, and availability trade-offs under partial failure — all with a problem simple enough to fit in 45 minutes. Weak candidates describe one algorithm and stop. Strong candidates get to the race condition unprompted.

Real deployments: Stripe and Amazon API Gateway use token bucket. Shopify uses leaky bucket. Envoy/Lyft's open-source rate limiter (widely adopted at Uber, Lyft, and elsewhere) uses the domain/descriptor rule model shown below.

---

2. Requirements

Functional

• Allow N requests per client per time window (e.g., 100 req/min), configurable per API/tier
• Reject over-limit requests with HTTP 429 + informative headers
• Rules must be updatable without redeploying services

Non-functional

• Low latency: the check itself must add single-digit milliseconds, not become the bottleneck it's meant to prevent
• High availability: the limiter is a dependency of every request — if it goes down, decide explicitly whether traffic fails open or closed (this decision is a scoring moment, not a footnote)
• Distributed correctness: must work when the client's requests land on different servers behind a load balancer, without under- or over-counting

Assumption to state out loud: rate limits are a protective mechanism, not a billing mechanism. That framing licenses eventual consistency later — if it were billing (metering paid API calls), you'd need strict accounting instead.

---

3. Capacity Estimation

Say the platform serves 10K requests/sec at peak across all clients, with 10M distinct active clients (users/API keys) in a rolling window.

• Limiter throughput required: one check per request → 10K checks/sec, in the request's critical path.
• State per client: token bucket needs 2 numbers — token count + last-refill timestamp. At 8 bytes each (or packed into a Redis hash), ~16–32 bytes/client.
• Total state size: 10M clients × 32 B ≈ 320 MB. This comfortably fits in a single Redis node's memory — the interesting scaling problem here is throughput and availability, not data volume. Don't over-engineer sharding for size; shard for HA and to spread the 10K QPS of atomic ops.
• Redis ops budget: a single Redis node does 100K+ ops/sec easily (single-threaded, sub-ms per op) — 10K checks/sec is not close to the ceiling. The real constraint is network hop latency (client → gateway → Redis → gateway), typically 1–2 ms round trip if co-located.

---

4. API Design

The rate limiter isn't user-facing — it's middleware sitting in front of your real API, typically inside an API gateway or a sidecar.

Internal check interface:

is_allowed(client_id, rule_id) → { allowed: bool, remaining: int, retry_after_seconds: int }

Response headers on every response (allowed or not — clients should always see their budget):

• X-RateLimit-Limit — max requests allowed in the window
• X-RateLimit-Remaining — requests left in the current window
• X-RateLimit-Retry-After — seconds to wait before retrying (present only on 429)

On breach: HTTP 429 Too Many Requests with the headers above. Some systems offer a second path — enqueue instead of drop (push to a message queue for delayed processing) rather than rejecting outright. Use this for background/batch clients where a delay is acceptable; never for interactive user-facing paths (a delayed login attempt is a worse UX than a clear error).

---

5. High-Level Architecture

flowchart LR
    C[Client] --> GW[API Gateway /<br/>Rate Limiter Middleware]
    RD[(Rules on Disk)] -.workers pull<br/>periodically.-> RC[Rules Cache<br/>in-memory]
    RC --> GW
    Redis[(Redis<br/>per-client counters)] <--> GW
    GW -->|allowed| S[Backend Services]
    GW -->|429| C
    GW -.rate limited,<br/>soft mode.-> MQ[Message Queue<br/>process later]

Walking a request through:

1. Request hits the gateway. Gateway extracts client_id (user ID, API key, or IP) and looks up which rule applies (rules cache, refreshed from disk periodically — never a synchronous disk read on the hot path).
2. Gateway calls Redis atomically: "does this client have budget?" (mechanism in §7 — this is the part that must not race).
3. If yes: forward to backend, decrement/consume budget, return response with updated X-RateLimit-* headers.
4. If no: return 429 immediately (fail fast, no work sent downstream) — or route to the message queue if soft/delayed processing is configured for that client class.

Rules as data, not code — the Lyft/Envoy-style config lets ops change limits without a deploy:

domain: messaging
descriptors:
  - key: message_type
    value: marketing
    rate_limit: { unit: day, requests_per_unit: 5 }

domain: auth
descriptors:
  - key: auth_type
    value: login
    rate_limit: { unit: minute, requests_per_unit: 5 }

This also lets you set tighter limits on sensitive endpoints (login, password reset — brute-force surface) independently of general API traffic.

---

6. The Algorithms

There are five standard approaches. A senior candidate names 2–3; a staff candidate explains why each fails at the edges and picks based on the actual product need, not habit.

Token Bucket — Amazon, Stripe

A bucket holds up to capacity tokens, refilled at rate tokens/sec. Each request consumes 1 token; empty bucket → reject.

flowchart LR
    Req[Request] --> Check{Enough<br/>tokens?}
    Refill[Refill tokens<br/>at fixed rate] --> Check
    Check -- yes: consume 1 --> Server[Forward to server]
    Check -- no --> Drop[Reject: 429]

Pros: allows controlled bursts up to bucket capacity (a client that's been idle can spend saved-up tokens fast) — this matches real traffic patterns better than a hard ceiling. Memory-efficient (2 numbers/client). Simple to reason about. Cons: two parameters to tune (capacity, refill rate) — get them wrong and you either strangle legitimate bursts or let through more than intended. Bucket granularity choice: one bucket per endpoint, per user, per IP, or a single global bucket — pick based on what you're protecting against (abusive single client vs. protecting a specific expensive endpoint).

Leaky Bucket — Shopify

Like token bucket, but requests queue in a FIFO and are processed at a strictly fixed outflow rate — smooths rather than allows bursts.

flowchart LR
    Req[Request] --> Full{Queue<br/>full?}
    Full -- yes --> Drop[Reject]
    Full -- no --> Queue[FIFO Queue]
    Queue -- fixed rate --> Server[Process]

Pros: stable, predictable outflow — good when the downstream system needs a constant load (e.g., protecting a fragile legacy system from any spike at all). Cons: cannot handle bursts — legitimate traffic spikes get smoothed into added latency, which is the wrong trade for most user-facing APIs.

Fixed Window Counter

A counter per (client, window) that resets each window boundary (e.g., each new minute).

Pros: trivial to implement, minimal memory (1 number/client). Cons: the boundary burst problem — 100 requests at 0:59.9 and another 100 at 1:00.1 both pass (two different windows), giving 200 requests in a ~200ms span against a "100/min" limit. This is the #1 gotcha interviewers probe for — if you propose fixed window, expect the follow-up "what happens right at the window edge?"

Sliding Window Log

Store every request's exact timestamp (Redis sorted set: score = timestamp). On each new request, drop timestamps older than now - window, then count what remains.

Pros: exact — the limit is genuinely never exceeded in any rolling window, by construction. Cons: memory scales with request rate, not client count — a client making the max allowed rate stores every single timestamp. At high limits (10K req/min per client) this gets expensive fast, and you're paying storage cost even for rejected requests.

Sliding Window Counter (the pragmatic default)

Hybrid: approximate the sliding window using two fixed-window counters.

count ≈ requests_in_current_window + requests_in_previous_window × overlap_fraction

Example: window = 1 min, limit = 100, we're 30% into the current window. count = current_count + previous_count × 0.7.

Pros: smooths the boundary-burst problem from fixed window down to a small, well-understood error margin (assumes previous window's requests were evenly distributed — usually a safe assumption, not exactly true but "not as bad as it sounds"), while staying nearly as cheap as fixed window (2 numbers, not N timestamps). Cons: an approximation — not appropriate if the limit is a hard legal/contractual ceiling that must never be crossed even once.

Comparison Table

Verdict: token bucket is the default answer for user-facing APIs (bursts are normal user behavior — a user reloading a page rapidly shouldn't get punished harder than one spacing requests out). Reach for sliding window counter when boundary bursts specifically must be tightened without paying sliding-window-log's memory cost. Use leaky bucket only when the downstream system, not the client, is what needs protecting from variance.

---

7. The Core Problem: Atomicity & Distributed Correctness

This is where the interview is actually won or lost — everything above is textbook; this is systems thinking.

The race condition

Two gateway instances (or two threads on one instance) both serving the same client, hitting Redis concurrently:

req A: reads counter = 3
req B: reads counter = 3
req A: writes counter = 4
req B: writes counter = 4     ← should be 5. One increment silently lost.

Classic lost update. Under load, this means clients occasionally get more budget than configured — usually harmless (protective, not billing), but if it happens systematically it defeats the limiter's purpose.

Wrong fix: application-level locks around the read-modify-write. Correct in principle, catastrophic for latency — you've turned a sub-millisecond check into a lock-contended bottleneck, which is precisely the tail latency this component was supposed to prevent.

Right fix — push the atomicity into Redis itself:

1. Lua script: Redis executes Lua scripts atomically (single-threaded execution model) — check-and-decrement becomes one round trip, one atomic unit, no window for another request to interleave.
2. Native atomic structures: INCR (atomic increment) + EXPIRE (auto-reset the window) composed correctly, or a sorted set with ZREMRANGEBYSCORE + ZADD + ZCARD for the sliding-window-log approach — each op individually atomic, and Redis's single-threaded execution means no other client's script interleaves mid-sequence.

flowchart TB
    A[Two requests arrive<br/>concurrently] --> B{Naive: app-level<br/>read then write}
    B --> C[Lost update<br/>race condition]
    A --> D{Correct: Lua script<br/>or INCR+EXPIRE}
    D --> E[Atomic in Redis<br/>no race possible]

The synchronization problem

A client's requests don't all land on the same gateway instance — a load balancer spreads them across N instances. If each instance keeps its own local counter, the client effectively gets N × limit budget, defeating the limit entirely.

Option A — sticky sessions: route a given client always to the same gateway instance, so its local counter is authoritative. Works, but couples rate limiting to load balancing, creates uneven load distribution, and breaks (temporarily over-admits) on instance failover — exactly when you least want it to.

Option B — centralized store (the right answer): all gateway instances share one Redis (or Redis Cluster) as the single source of truth for counters. No coupling to LB behavior, survives instance churn cleanly. This is the standard production answer.

Staff-level nuance: centralizing in Redis adds a network hop to every single request. At true global scale (multi-region), a fully consistent global counter means cross-region round trips on the hot path — unacceptable latency. The resolution: local approximate counters + async sync to a regional/global store, accepting a small, bounded over-admission window. This is defensible specifically because limits are protective, not metering — restate that assumption here if asked "but doesn't that mean the limit isn't exact?"

---

8. Scaling & Bottlenecks

• Sharding: partition Redis by hash(client_id) — each client's counter lives on exactly one shard, preserving atomicity per-client without needing cross-shard coordination. A single abusive client hammering one shard is, definitionally, the client being rate-limited — self-correcting hotspot.
• Multi-datacenter: run the limiter co-located with each regional API gateway cluster to keep the Redis round-trip local; sync aggregate counts across regions asynchronously (eventual consistency — see above).
• Failure mode — fail open vs fail closed: if Redis is unreachable, do you let all traffic through (fail open) or reject all traffic (fail closed)? For most public APIs: fail open — a rate limiter outage shouldn't cause a full service outage; the protective mechanism failing is better than the protected service failing. For security-sensitive endpoints (login, password reset — brute-force protection is the point) fail closed is defensible. State which you'd pick and why per endpoint class — this binary, justified, is a strong interview signal.
• Monitoring: track 429 rate per rule (spikes = either an attack or a misconfigured limit hurting real users — you want to distinguish these), Redis p99 latency (limiter shouldn't become the tail-latency source), and fail-open event count (silent — if Redis flaps, you want an alert, not silence).

---

9. Deep Dives / Follow-ups

• Per-tier limits: free/paid/enterprise tiers with different limits on the same endpoint — rule lookup becomes (client_id → tier) → rule, an extra indirection but same mechanism.
• Layer of enforcement: everything above is Layer 7 (HTTP, application-aware — can key on user ID, API key, endpoint path). You can also rate-limit at Layer 3/4 (IP-based, via iptables or a network-level tool) — cruder (can't distinguish users behind the same NAT/IP) but useful as a first line of defense against raw volumetric abuse before requests even reach the application tier.
• Hard vs soft limiting: hard = never exceed threshold, ever. Soft = allow brief overage (e.g., token bucket's burst capacity is a form of soft limiting) — most real systems are soft by design, because hard-everywhere creates a worse UX for marginal cases.
• Enqueue instead of reject: for non-interactive clients (batch jobs, webhooks), route over-limit requests to a message queue for delayed processing instead of a hard 429 — trades latency for a better completion guarantee. Wrong choice for a user waiting on a page load.

---

10. Staff-Level Lens

The naive version of this system (in-memory counter per instance, no shared store) doesn't fail in a demo — it fails in production, silently, the moment you autoscale. That's the trap: it works fine at 1 instance, and the bug (N× the intended limit) only appears once you scale out, which is usually after the review that approved the naive design. Surfacing this failure mode unprompted is the single highest-value thing you can say in this interview.

Second-order concern: rate limiting is a shared platform capability, not a per-team feature — decisions about default limits, per-tier overrides, and the fail-open/closed policy need an owning team and a rollout plan (shadow/log-only mode before enforcing, so you never 429 a paying customer on day one of rollout).

---

11. Interview Drill Questions

1. Why not just use a database instead of Redis for counters? — A relational DB gives durability you don't need (counters are ephemeral, reset every window) at 10-100x the latency for a hot read-modify-write path. Redis's in-memory, single-threaded, sub-ms atomic ops are purpose-built for exactly this access pattern.
2. What happens if two requests from the same client arrive at the exact same millisecond on two different gateway instances? — Tests whether you go straight to the race condition + Lua script / atomic Redis op answer without prompting.
3. How would you rate-limit by IP when clients are behind a corporate NAT (thousands of users, one IP)? — Surface the L3-vs-L7 trade-off: IP-based limiting over-punishes shared-IP populations; prefer L7 keying on authenticated user/API key wherever an identity is available, reserve IP-based limiting for pre-auth endpoints (login attempts) where no better identity exists yet.
4. Client complains their rate limit resets seem inconsistent. — Likely fixed-window boundary effect, or (if truly distributed) a sticky-session setup with instances that don't share state — walk through diagnosing which.
5. How do you avoid the rate limiter itself becoming a single point of failure? — Redis Cluster/replication for the store, fail-open policy for the gateway logic, and monitoring on limiter latency/availability separate from the services it protects.
6. Design just the schema/data structure for a global (not per-user) rate limit of "10K requests/sec across the whole platform." — A single shared counter becomes a write hotspot on one key; the practical fix is splitting into N sub-counters (one per shard/instance) each capped at limit/N, summed periodically — same sharding logic as per-client, applied to a single logical entity.

---

Trade-off Summary

---

Cross-links

[[Design a URL Shortener]] · [[System Design/Databases/Redis]] · [[Message Queues & Kafka]] · [[Consistent Hashing]] · [[synthesis/Job Switch Hub]]