Design a Rate Limiter, System Design Interview Guide

Every API call incurs an extra network hop for the rate limit check. At 5 ms the check is invisible to humans but measurable by services with tight SLAs. This target effectively rules out any approach that requires a synchronous DB read, Redis at sub-millisecond latency is the only practical option.

99.99% availability for the rate limiter must not lower the availability of the services it protects. If the Redis cluster is unreachable, the right default for most consumer APIs is to let traffic through rather than block everything. This is called "fail open."

The alternative, "fail closed", is appropriate when the rate limiter protects a payment endpoint or prevents fraud. Clarify with the interviewer which mode fits the use case.

Static constants hardcoded in the limiter only work for a single-tier product. Once you have Free, Pro, and Enterprise tiers, each with different request quotas, you need a config lookup: given a user ID, what is their limit? This lookup happens on every request, so it must itself be cached, a short TTL (60 s) in a local in-process cache is the standard approach.

The asymmetry between over-count and under-count is the key constraint. An over-count means a legitimate request gets a 429, a UX failure. An under-count means a request that should be blocked gets through, a security failure. These are not equally bad for most systems, which is why the NFR prioritises minimising under-counting while tolerating a small over-count rate.

In practice, brief under-counts are unavoidable at partition boundaries, during crash windows, and when using approximate counting modes (§09). The NFR means the steady-state design must not structurally under-count, not that zero under-count events are possible.

The 0.1% over-count tolerance is what makes the sliding window counter approximation viable as an alternative to the exact sliding window log. The approximation's error at the window boundary is at most prev_count × (elapsed/window), a fraction of the previous window's count, not the full limit, well within 0.1% under realistic traffic distributions. If this tolerance were tighter (e.g. 0%), you'd be forced into the sliding window log with its O(requests) memory cost.

100k requests/sec means 100k Redis Lua script executions per second at peak. A single Redis node handles ~200–400k Lua executions/sec (see §9), so a single node is sufficient at this scale, but only if key distribution is even. If all traffic concentrates on a small number of hot users, one shard becomes a bottleneck.

The 1M unique users figure matters for memory sizing (see §3, it's small) and for config cache design: 1M users × 60 s TTL means the in-process cache on each API server holds at most a few thousand live entries at any moment, not 1M.

Rate limit decisions must be debuggable ("why was user X blocked?") and auditable for abuse detection. Logging synchronously in the request path is ruled out immediately, even a 1 ms write to a log store adds to the p99 latency budget and would push the limiter past its 5 ms target at volume.

The 30 s bound is generous enough to allow an async pipeline: the middleware emits a 429 event to a local buffer, a background thread flushes to a durable message queue (Kafka), and a stream processor writes to a columnar analytics store (ClickHouse) for querying. This path never touches the hot request thread.

The load balancer's job is distribution, not enforcement. Enforcing rate limits at the LB would require shared state between LB nodes, turning a stateless routing layer into a stateful bottleneck. Keeping limits in the middleware layer behind the LB means the LB stays simple and horizontally scalable.

One non-obvious requirement: if you rate limit by IP, the LB must forward the original client IP in X-Forwarded-For. Many default configurations replace the source IP with the LB's own address, meaning all traffic appears to come from one IP, and IP-based limits collapse into a global limit.

Deployment options differ meaningfully. An API gateway plugin (Kong, Nginx Lua) is the simplest: one place to configure, one place to update. But it shares the gateway's blast radius, a middleware bug can take down all routing. A sidecar proxy (Envoy) isolates the rate limiter's failure domain at the cost of a network hop per request. In-process middleware (Express.js, FastAPI) is fastest but per-service, making language-agnostic enforcement impossible.

Redis is the only practical choice for the counter store given the <5 ms p99 latency target. A traditional DB adds 5–15 ms per write under load; Redis at sub-millisecond latency is the only store that keeps the check invisible in the request path.

The Lua script is the correctness mechanism. Two separate commands (GET then INCR) leave a TOCTOU window: two concurrent requests can both read the same count, both decide "allowed," and both write, admitting two requests when one should be blocked. The Lua script runs atomically on the Redis thread, eliminating this race entirely without distributed locks.

Quota rules can't be hardcoded constants once you have per-tenant pricing tiers. The config store holds the mapping from user ID (or plan) to their limit, window size, and algorithm. Reads happen on every request, so a raw DB lookup would add another round-trip, the local in-process cache with a 60-second TTL prevents this.

The 60-second TTL is a deliberate product decision: upgrades propagate within 60 s (acceptable), but downgrades also take 60 s to enforce. For fraud-prevention use cases where immediate downgrade is required, push invalidation via a pub/sub event from the config service is the correct extension.

Synchronous 429 logging is ruled out by the latency budget: even a 1 ms log write adds to p99 and compounds at 100k QPS. The async pipeline (middleware → message queue → analytics store) decouples observability from the request path entirely, the middleware emits a fire-and-forget event and never waits for it.

The three stages each have a specific job. A durable message queue (Kafka) sits between the middleware and the analytics store, it absorbs traffic spikes without backpressure and retains events for replay if a consumer has a bug. A stream processor (Flink or a simple Kafka consumer) aggregates raw events and writes to a columnar analytics store (ClickHouse) that powers abuse dashboards and per-user 429 queries. Raw events can additionally be archived to object storage (S3) for long-term retention and ad hoc queries, optional at this scale but standard practice for compliance-sensitive deployments.

A token bucket holds up to max tokens. Tokens refill at a fixed rate (e.g. 10/sec). Each request consumes one token. If the bucket is empty, the request is rejected with a 429. This maps naturally to user intuition: you have a quota that refills over time, and bursting is allowed as long as you have tokens saved up.

Redis representation: a hash with two fields, tokens (float) and last_refill (unix ms). On each request the Lua script computes tokens earned since the last call, adds them up to the max, then attempts to consume one. The entire read-modify-write is atomic.

Why it handles bursts well: if a user makes no requests for 30 seconds, they accumulate up to max tokens. Their next burst of requests drains the bucket instantly, which is intentional. The downstream system must be designed to handle these bursts, but for most APIs this is preferable to queuing.

Divide time into fixed buckets (e.g. every 60 seconds). Each bucket holds a counter, keyed by rl:{userId}:{windowTs} where windowTs = floor(now / window) × window. Increment on every request; reject if the count exceeds the limit. The key expires automatically at the end of the window.

Redis representation: a single integer key. INCR rl:u123:1711584000 followed by EXPIRE on first write. Two commands, but the race between them is acceptable here, unlike token bucket, there is no read-before-write, so the TOCTOU window is narrow (only the EXPIRE can be lost, not the count).

The boundary problem: a user can legally make 100 requests at 11:59:59 and another 100 at 12:00:00, both within their respective windows, but 200 requests in 2 seconds. Any downstream service sized for 100 req/min sees a 200-request spike. This is the seam problem, and it's why fixed window is not recommended as a default.

A hybrid that approximates a true sliding window using only two fixed-window counters. The formula: count = prev_count × (1 − elapsed/window) + curr_count. The previous window's count is weighted by how much of it overlaps the current sliding window. As elapsed time grows, the previous window contributes less.

Redis representation: two integer keys, the current window bucket and the previous window bucket. The Lua script reads both, applies the formula, and checks against the limit. Still O(1) memory per user regardless of request rate.

Error bound: the approximation assumes request traffic within the previous window was uniformly distributed. Under this assumption, the maximum error at the boundary instant is prev_count × (elapsed / window), a fraction of the previous window's count, not the full limit. As elapsed time grows from 0 toward the window size, the previous window's contribution shrinks to zero. In practice this means the error is well under 1% of the limit for realistic traffic distributions. Cloudflare uses this algorithm at global scale.

Why this over token bucket? Token bucket allows front-loaded bursts. Sliding window counter smooths the rate across the window boundary without queuing. If your NFR says "no more than N requests per minute, measured continuously", not "N tokens that refill at N/60 per second", the sliding window counter is the more accurate implementation.

Requests enter a FIFO queue and are processed at a fixed drain rate (e.g. 10 req/s). Bursts are absorbed into the queue rather than rejected immediately. If the queue is full, new arrivals are dropped. The output rate is perfectly smooth, downstream services see a constant, predictable load regardless of input burstiness.

Redis representation: a list used as a queue, with a background worker draining it at the fixed rate, call LPUSH on arrival, RPOP on each drain tick. A simpler stateless variant stores only the next allowed timestamp per user: on each request, check if now >= next_allowed; if yes, allow and set next_allowed = now + (1 / rate); if no, reject with a Retry-After of next_allowed - now. This avoids the queue entirely while preserving the fixed-rate output guarantee, at the cost of rejecting bursts immediately rather than queuing them.

Why it's rarely the right choice for APIs: queuing adds latency. A burst of 100 requests at 10 req/s drain rate means the 100th request waits 10 seconds before being processed. For an interactive API with a <5 ms p99 target, this is catastrophic. The user experiences a long hang instead of a clean 429.

When it is the right choice: backend processing pipelines where throughput matters more than latency, and where a 429 is worse than a delay, for example, payment processing, batch job submission, or webhook delivery where out-of-order drops are worse than queuing.

A fifth option not shown in the diagram above. Instead of counters, store a sorted set of request timestamps. To check the limit, prune entries older than the window and count what remains. This is the only algorithm that gives a perfectly exact sliding window count with no approximation error at window boundaries.

The cost is memory: O(requests) per user rather than O(1). A user making 1,000 requests per window requires 1,000 timestamp entries in Redis. At scale this becomes significant. The Redis operation ZREMRANGEBYSCORE to prune old entries also adds latency proportional to the number of expired entries removed.

-- Redis Lua script: token bucket check-and-refill
-- KEYS[1] = "rl:{userId}"  -- persistent per-user key (no window: state carries across windows)
-- ARGV[1] = max tokens, ARGV[2] = refill rate/sec, ARGV[3] = now (unix ms)

local key = KEYS[1]
local max = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])   -- tokens per second
local now = tonumber(ARGV[3])           -- milliseconds

local data = redis.call("HMGET", key, "tokens", "last_refill")
local tokens = tonumber(data[1]) or max
local last = tonumber(data[2]) or now

-- Refill: add tokens proportional to elapsed time
local elapsed = (now - last) / 1000.0
local new_tokens = math.min(max, tokens + elapsed * refill_rate)

if new_tokens < 1 then
  return {0, math.ceil((1 - new_tokens) / refill_rate * 1000)}  -- {denied, retry_ms}
end

-- Consume one token (HSET replaces deprecated HMSET, supported since Redis 4.0)
redis.call("HSET", key, "tokens", new_tokens - 1, "last_refill", now)
redis.call("PEXPIRE", key, math.ceil(max / refill_rate * 1000))  -- expire after full refill time
return {1, 0}  -- {allowed, 0}

Without a TTL, inactive users accumulate dead counter keys forever. With a TTL set to the window size, a user who stops making requests will have their key automatically evicted when the window closes. For a 1-minute window, keys live at most 1 minute after the last request.

This is what keeps Redis memory bounded (see §3, even at 1M users, active keys are tiny) and means you never need a background cleanup job.

Redis Cluster distributes keys across 16,384 hash slots assigned to N primary nodes. For rate limiting, each user's counter key hashes to exactly one shard, so all operations for a given user are atomic on that shard. No cross-shard transactions are needed.

A 3-primary cluster with each primary handling ~200–300k Lua executions/sec (consistent with the ceiling established in §09) gives headroom to ~600k–900k QPS before horizontal scaling is needed. Add shards by resharding, Redis Cluster handles this online.

Above ~5M QPS, even Redis Cluster becomes a bottleneck. The alternative: each API server maintains an in-process counter and periodically (every 100 ms) syncs with Redis via INCRBY. Between syncs, the distributed count can be off by at most servers × local_count. This is an explicit trade: approximate counting for linear write scalability.

This design is used by Cloudflare and is acceptable when "at most 5% over-count" is a tolerable SLA. It's unacceptable for security-critical limits (authentication attempts, payment API).

Enterprise products often have nested limits: per-user, per-team, and per-organization, all enforced simultaneously. A request must pass all three checks. The implementation: the Lua script is called once per dimension, in order. If any check fails, the 429 is returned immediately with the header naming which dimension was exhausted: X-RateLimit-Violated: org.

If a user can send requests to two different regions simultaneously, per-region counters will each allow the full quota, effectively doubling the limit. True global rate limiting requires cross-region counter sync. Options: (1) route all requests for a user to their "home" region (sticky routing, single point of failure); (2) use a globally replicated database (Google Spanner or DynamoDB Global Tables) that offers low-latency strongly-consistent reads across regions; (3) accept approximate counting with gossip-based sync.

Most systems choose option 3: allow a known over-count window at region boundaries, monitor for abuse via the audit log, and address egregious violations reactively.

How gossip-based sync works: each region periodically (e.g. every 100–500 ms) broadcasts its local counter delta to peer regions. Each region maintains a per-region counter vector and sums them to get the global count. This is a form of CRDT (Conflict-free Replicated Data Type), specifically a G-Counter, where each region owns one slot in the vector and only increments it. Merging is simply taking the max of each slot across all received vectors. Convergence time equals the gossip interval plus network RTT between regions (typically 100–300 ms cross-continent), giving a bounded over-count window of at most limit × (gossip_interval / window_size).