The rate limiter question is compact, deceptively hard, and asked everywhere. It tests whether you understand distributed systems coordination problems — specifically, how to enforce a global limit across a cluster of servers when no single server sees all requests. At L5 the probe is the algorithm choice. At L6 the probe is distributed coordination without a single point of failure.
The Question
“Design a rate limiter. API clients are limited to N requests per second. Requests that exceed the limit return 429 Too Many Requests.”
Common variants: “Design Cloudflare’s rate limiting,” “Add rate limiting to a payment API,” “Design a per-user request quota system.”
Step 1 — Clarify
1. What are we rate limiting on? Per IP, per user/API key, per endpoint, or combinations? Answer: typically per API key at the application level, per IP at the network edge.
2. What granularity? Requests per second, per minute, per hour, per day? Multiple windows simultaneously (100 req/min AND 1,000 req/hour)?
3. Hard limit or soft? Hard: the 101st request this minute is always rejected. Soft: occasional burst allowed. Most production systems use hard limits.
4. Where does the limiter live? Middleware inside the API service, or a standalone sidecar/gateway? Standalone scales independently and is language-agnostic — correct answer for L5+.
5. What’s the SLO? The rate limiter must add < 1ms p99 latency to every request. It is in the hot path.
Step 2 — Estimate
- 50,000 API servers in a large deployment, each handling 10K req/sec - Total: 500M requests/sec — individual counters per API key must be updated atomically at this rate
- Redis cluster: 100K-500K ops/sec per node — need ~1,000-5,000 Redis nodes for 500M req/sec. In practice, shard by API key.
- Counter storage: 1M API keys × 4 bytes per counter × 60 windows = 240 MB — fits in memory
Step 3 — API (internal interface)
// Called by every API gateway before routing the request
bool allow_request(api_key: string, endpoint: string) → { allowed: bool, remaining: int, reset_at: epoch_ms }
// For the management API
PUT /v1/limits/:api_key { requests_per_minute: int, requests_per_hour: int } GET /v1/limits/:api_key/status → { current_count, limit, window_reset_at }
Step 4 — Algorithm choice (the core probe)
Four real algorithms. The senior answer names all four, picks one with justification, and explains what changes at L6.
Fixed window counter
Divide time into fixed 1-minute windows. Count requests per window per API key. Reset at window boundary.
Win: Simple. O(1) time and space. One Redis INCR per request.
Lose: Boundary burst problem. A client can send 100 requests at 12:00:59 and 100 more at 12:01:01 — that’s 200 requests in 2 seconds while the “limit” is 100/minute. The window reset creates a seam they can exploit.
Sliding window log
Store the timestamp of every request in the last 60 seconds. On each request, count entries in the log and reject if > limit.
Win: Perfectly accurate. No boundary burst.
Lose: O(N) storage per API key (N = limit). For 1,000 req/min across 1M API keys, that’s 1 billion stored timestamps — expensive.
Sliding window counter (hybrid) ← correct answer for most interviews
Approximate the sliding window using two fixed-window counters: the current window and the previous window. Estimate the request count for the sliding window as:
rate = prev_count × (1 - elapsed_fraction) + curr_count
Where elapsed_fraction = how far into the current window we are. If we’re 30 seconds into a 60-second window, the weight of the previous window is 0.5.
Win: O(1) space per API key. Accurate within ~0.003% of the true sliding window (published by Cloudflare). No boundary burst exploit.
Lose: Approximate (but the error is tiny). Slightly more complex than fixed window.
This is what Cloudflare uses in production — they published a blog post on it. Saying “Cloudflare published their sliding window counter approach” is an L5+ signal.
Token bucket
Each API key has a bucket of capacity N tokens. Tokens refill at rate R per second. Each request consumes one token. If the bucket is empty, the request is rejected.
Win: Allows controlled bursting — a client can use saved-up tokens in a burst. Better user experience for legitimate burst traffic.
Lose: Two values to track per key (current tokens, last refill timestamp). Slightly harder to implement atomically.
When to use: When the product requirement explicitly allows bursting (e.g., “allow up to 50 requests in any 1-second burst as long as the 1-minute average is under 100/min”). For strict per-second limits, sliding window counter is simpler.
The senior recommendation: Default to sliding window counter (Cloudflare’s approach) for strict per-second/per-minute limits. Token bucket for burst-tolerant limits where the product explicitly needs it.
Preparing for a distributed systems interview?
→Download the free Interview Pack
→ Subscribe now to access source code repository - 200 + coding lessons
