← Create New Paste

Designing a Rate Limiter: A System Design Interview Walkthrough

3 views
"Design a rate limiter" is a favorite system design question because it is small enough to finish in 45 minutes but deep enough to separate candidates. It touches algorithms, distributed state, failure modes, and API design. Here is a structured way to approach it. 1. Clarify requirements Ask before you draw anything: - What are we limiting: requests per user, per API key, per IP, or per endpoint? - What limits: for example 100 requests per minute per user, with bursts allowed? - Where does it run: in each service, in an API gateway, or as a shared service? - Is it a hard limit (reject) or soft (queue or degrade)? - What scale: how many requests per second, how many distinct keys? Writing these down shows the interviewer you design for a real problem rather than a generic one. 2. Pick an algorithm and explain the trade-offs - Fixed window counter: count requests in each calendar minute. Simple and cheap, but allows up to 2x the limit at window boundaries (100 at 12:00:59 and 100 at 12:01:00). - Sliding window log: store a timestamp for every request and count those in the last 60 seconds. Exact, but memory grows with request volume. - Sliding window counter: combine the current and previous fixed windows weighted by overlap. A close approximation with constant memory per key; a strong default. - Token bucket: each key has a bucket of capacity C that refills at rate R tokens per second; each request takes a token. Naturally supports bursts up to C while enforcing an average rate. Used widely, including by many cloud APIs. - Leaky bucket: requests enter a queue that drains at a fixed rate. Smooths traffic but adds latency. A good answer picks one, usually token bucket or sliding window counter, and says why. Token bucket sketch: def allow(key, now): tokens, last = store.get(key, (CAPACITY, now)) tokens = min(CAPACITY, tokens + (now - last) * RATE) if tokens < 1: store[key] = (tokens, now); return False store[key] = (tokens - 1, now); return True 3. Make it distributed With many API servers, local counters let each user exceed the limit by a factor of the server count. Options: - Centralized store such as Redis: keep the bucket state per key and update it atomically with a Lua script or a single INCR plus EXPIRE for window counters. Mention atomicity explicitly, since a read-then-write race lets bursts through. - Sticky routing: hash users to specific gateway nodes so each key is counted in one place, accepting some imbalance. - Local plus periodic sync: each node enforces a share of the limit and reconciles occasionally; cheaper but approximate. 4. Handle failure and latency What happens if Redis is down? Usually fail open (allow traffic) for user-facing APIs and fail closed for expensive or abuse-prone ones; say which and why. Keep the limiter on the hot path fast: a single round trip, connection pooling, and co-locating the store with the gateway. 5. Communicate limits to clients Return HTTP 429 Too Many Requests with headers such as X-RateLimit-Limit, X-RateLimit-Remaining, and Retry-After. This is a small detail that interviewers notice. 6. Extensions Different tiers per plan, limits by multiple dimensions at once, dynamic limits during incidents, and monitoring which keys are being throttled. Practicing this out loud, with someone interrupting to change the requirements, is the best preparation. If you lose your thread when an interviewer pushes on edge cases, Linkjob AI (https://linkjob.ai) offers real-time help during live job interviews and technical interviews, helping you keep your system design discussion structured.
Created Nov 15, 2026 11:58 Expires Nov 15, 2027 11:58