Deep dive · Core

Design a rate limiter

Deceptively small. It tests algorithmic precision, distributed-counter accuracy, and whether you understand that the rate limiter itself must never become the bottleneck or the outage.

What it trains: Token bucket, sliding window, distributed counters

1. Requirements

Functional

Limit requests per identity (API key, user ID, or IP) to N per time window
Support different limits per endpoint and per customer tier
Return 429 with Retry-After and standard X-RateLimit-* headers

Non-functional

Adds under ~5ms to every request — it sits in front of everything
Must handle full production traffic: hundreds of thousands of checks per second
Fail open: if the limiter is down, serve traffic rather than reject everything
Reasonably accurate; a small overshoot is acceptable, a 10× overshoot is not

2. Back-of-envelope numbers

100K requests/sec means 100K counter operations/sec — the limiter is the highest-QPS component you own
Per-identity state is ~20 bytes; 10M active identities ≈ 200 MB, comfortably in memory
A Redis round trip is ~1ms in-region; local in-memory checks are microseconds — that gap drives the design
At 20 API gateway nodes, a naive per-node limit of N gives an effective global limit of 20N

3. Architecture

   ┌────────┐
   │ Client │
   └───┬────┘
       │
 ┌─────▼───────────────────────────────────┐
 │  API gateway node                       │
 │   ┌────────────────────┐                │
 │   │ Local token bucket │ ← fast path    │
 │   │  (in-process)      │   (µs, approx) │
 │   └─────────┬──────────┘                │
 └─────────────┼───────────────────────────┘
               │ sync / borrow quota (async, batched)
        ┌──────▼────────────────┐
        │  Redis cluster        │
        │  sliding-window /     │
        │  token-bucket counters│
        │  (Lua = atomic)       │
        └──────┬────────────────┘
               │ allow                 │ deny
        ┌──────▼──────┐        ┌───────▼────────────┐
        │  Upstream   │        │ 429 + Retry-After  │
        │  service    │        └────────────────────┘
        └─────────────┘

A local approximate check on the hot path, backed by a shared store for global accuracy — the standard two-tier design.

Where it lives

Put the limiter at the API gateway or in a sidecar, before authentication does expensive work but after cheap identification. Limiting inside each service means duplicating the logic and giving up a global view; limiting at the gateway gives you one place to configure and observe.

The check

Build a key from identity + endpoint + window, apply the algorithm atomically, and return allow/deny plus remaining quota. Atomicity matters: a read-then-write from a hundred nodes at once will overshoot badly, which is why the operation is a Redis Lua script rather than GET followed by INCR.

4. Deep dives

This is where levels are decided. Go deep on one or two of these rather than shallow on all of them.

The algorithms, and when each is right

Interviewers expect you to name at least three and pick one with a reason.

Fixed window: count per clock-aligned bucket. Trivial and cheap, but allows a 2× burst across the boundary — 100 requests at 11:59:59 and 100 more at 12:00:00.
Sliding window log: store a timestamp per request and count those inside the window. Perfectly accurate, but memory grows with request volume — expensive at scale.
Sliding window counter: weight the previous window's count by how much of it overlaps the current one. Approximate within a few percent, uses two integers. This is the usual production choice.
Token bucket: tokens refill at a fixed rate up to a capacity; each request takes one. Allows controlled bursts, which is what API consumers actually want. Two numbers of state: token count and last refill time.
Leaky bucket: processes at a constant rate with a queue — good for smoothing traffic to a fragile downstream, bad when latency matters.

Making it distributed

With many gateway nodes, per-node counters multiply the effective limit by the node count. Shared Redis counters give a correct global limit at the cost of a network round trip on every request. The production compromise is two-tier: each node holds a local bucket carrying a slice of the global quota, and reconciles with Redis asynchronously every few hundred milliseconds. You accept a small overshoot in exchange for keeping the hot path in-process.

Atomicity

Read-modify-write across the network races. Use a Redis Lua script (or INCR with an expiry set on first write) so the count-and-decide happens in one atomic step on the server. Set the TTL when creating the key, or abandoned keys will accumulate until they eat your memory.

Failure behaviour

Decide fail-open versus fail-closed and justify it. For general API protection, fail open — a limiter outage should not become a total outage. For abuse-sensitive paths like login or payments, fail closed, or fall back to a stricter local-only limit. Saying 'it depends on the endpoint' and giving both cases is the senior answer.

The response contract

Return 429 with Retry-After, plus X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset. Well-behaved clients then back off instead of hammering you, which turns rate limiting from a wall into a protocol.

5. Tradeoffs to argue

Local vs centralised counters

Upside: Local checks add microseconds and survive a Redis outage

Cost: Effective limit is multiplied by node count unless quota is coordinated

Sliding log vs sliding counter

Upside: The log is exactly correct

Cost: Memory grows with traffic; the counter is approximate but constant-size

Fail open vs fail closed

Upside: Fail open protects availability

Cost: An attacker who takes out the limiter gets unlimited access

6. Questions the interviewer will ask

Show me exactly how a fixed window lets a client send 2× the limit.
Redis becomes unreachable. What does the next request do?
How do you rate-limit a customer whose traffic spans three regions?
A customer complains they're throttled below their limit. How do you debug it?

7. Mistakes that sink this answer

Non-atomic read-then-increment across distributed nodes
Forgetting key expiry and unbounded memory growth
Never stating the fail-open/fail-closed decision
Choosing the sliding window log without acknowledging its memory cost

Practice this live

Run a mock system design interview and get scored against your target level.

Start mock interview