RateLimiter

System design deep dive · HLD

Design a Distributed Rate Limiter (API gateway scale): full high-level design.

Requirements, back-of-envelope capacity estimation, a high-level design diagram, a deeper deployment architecture diagram, sequence diagrams for the allowed and rejected paths, and an entity-relationship diagram for the rule config store - with the reasoning an interviewer expects behind every box, arrow, and Lua script.

Jump to HLD Architecture Sequence diagram ER diagram

1M req/sPeak platform traffic

<5msAdded p99 latency

45M+Active rate-limit keys

1. Clarify requirements before drawing any box

A rate limiter's whole job is to say no under exactly the right conditions, consistently, everywhere. That "consistently, everywhere" is the hard part - it is what turns a single-line "if count > limit" check into a distributed systems problem.

Functional requirements

Multi-scope enforcementEnforce limits per user, per IP, per API key, and per endpoint - often several scopes at once on a single request.

Multiple algorithmsSupport token bucket, leaky bucket, and sliding window counter, selectable per rule.

429 + Retry-AfterReject with HTTP 429 and a Retry-After header telling the caller exactly when to retry.

Tiers and burstDifferent sustained limits for free vs paid tiers, plus a short burst allowance above the sustained rate.

Non-functional requirements

Negligible overheadThe limiter check itself must add <5ms p99 to every request - it sits in front of every single call.

Cluster-wide consistencyEnforced consistently across dozens of stateless gateway nodes, not per-node in-memory (which would allow N× the real limit).

Graceful degradationMust survive a Redis node or shard failure without either blocking all traffic or silently disabling limits entirely.

Horizontal scaleScales to huge request volumes by adding gateway nodes and Redis shards, with no single choke point.

Explicitly out of scope Usage-based billing/metering, ML-based bot and anomaly detection, and full request-body content inspection are related but separate systems, called out here so the core rate-limiting design stays focused on the count-and-decide problem.

2. Back-of-the-envelope capacity estimation

These numbers decide the shape of everything downstream: how many Redis shards are needed, whether a single script call is cheap enough, and how much memory tens of millions of live counters actually cost.

Metric	Assumption	Resulting estimate
Average request rate	80 gateway nodes, ~2,500 req/s/node average	~200,000 req/s average platform-wide
Peak request rate	~5× average during traffic spikes / campaigns	~1,000,000 req/s peak, ~12,500 req/s/node
Distinct rate-limit keys	user_id × api_key × ip combinations in a rolling window	~45 million active keys at any given time
Redis ops/sec at peak	1 Lua script call/request, each script does ~3 internal ops (GET, INCR, PEXPIRE)	1M script calls/sec ×3 ≈ 3M internal ops/sec → ~24 shard primaries at ~130k ops/sec each
Memory footprint	~45M keys × ~150 bytes/key (counter + window fields + key overhead)	≈6.8 GB raw hot set, ×3 for HA replicas ≈ ~20 GB cluster-wide

Why this matters The 3M internal-ops/sec figure is the number that rules out a naive single Redis primary and rules out a relational database entirely for the hot path - it is also small enough in absolute memory terms (~20GB) that the real constraint is network round-trips and shard count, not storage.

3. High-level design (HLD)

The HLD names the major components and the one-directional data flow between them: where the check happens, where the source of truth for both rules and counts lives, and where results are logged - without yet committing to region counts or shard counts.

Stateless servicesFast-path infraDurable configAsync / edge

What each box owns

Gateway node pool + embedded rate limiter library

Every gateway node runs the same rate-limiter middleware in-process, ahead of routing to the backend. It resolves the relevant scope keys for the request (user, IP, API key, endpoint), pulls a locally-cached copy of the matching rule, and issues a single atomic check to Redis. Being stateless means any node can serve any request, which is exactly why the counter cannot live on the node itself.

Redis cluster + atomic Lua script

Holds the live counters for every active scope key and runs a small Lua script that performs the read-compare-increment sequence as one atomic operation inside Redis. This is the single source of truth for "how many requests has this key made in this window," shared by every gateway node cluster-wide.

Rule config store

A small relational store holding the actual limit definitions - which algorithm, what limit, what window, what tier - so limits can be changed by an operator without redeploying gateways. Gateways pull and cache these rules locally (refreshed every ~30s) rather than hitting the config store on every request.

Async metrics / logging pipeline

Every allow/deny decision is fire-and-forget published to a queue for aggregation - reject rate by rule, by tier, by endpoint - feeding on-call dashboards and alerting. This path must never sit on the critical request path; it is exactly as disposable as click-analytics is for other systems.

4. Detailed architecture diagram

The architecture diagram is where the interviewer checks the detail that actually matters for a rate limiter: is the counter genuinely shared across every node that could receive the request, and what happens the instant Redis is unreachable.

Decision	Choice	Reasoning
Algorithm	Sliding window counter (hybrid), configurable per rule	Beats fixed window's boundary-burst flaw and sliding window log's unbounded memory; token bucket/leaky bucket remain available per-rule for burst-shaping use cases (see deep dive).
Counter state location	Centralized Redis cluster, not per-node memory	Per-node in-memory counters would let each of the 80 gateway nodes independently grant the full limit - the effective limit becomes N× the configured value. Only a shared store makes the limit real.
Redis topology	Regional clusters + async cross-region reconciliation, not one global cluster	A single global cluster adds cross-continent round-trip time to every request's critical path; regional clusters keep the check local, trading a brief double-counting window during failover for latency.
Redis outage behavior	Fail-open with a conservative local cap	Fail-closed turns a Redis blip into a full API outage. Fail-open with a tight local fallback cap keeps traffic flowing while accepting a small, logged risk of under-enforcing limits.

5. Sequence diagrams for the two critical flows

A sequence diagram is where an interviewer checks whether the check-then-act is genuinely atomic, and what the system does the moment its dependency disappears.

5.1 Allowed request (normal path)

Step 2 is a cheap local lookup against a rule cache refreshed every ~30s from the config store, so it never adds a network hop. Steps 3-5 are the only round trip the check adds - one EVALSHA call, because the Lua script does the read, compare, increment, and TTL-set as one atomic unit rather than four separate round trips.

5.2 Rejected request, plus the Redis-unreachable fallback

Steps 1-4 are the ordinary deny path: the Lua script itself decided the bucket was empty, so no application-level race is possible. Steps 5-9 are the degraded path - a Redis timeout falls back to a small in-memory approximate counter per node with a deliberately lower cap than the real limit, and every request served this way is logged for later reconciliation once Redis recovers.

6. Entity-relationship (ER) diagram and schema

The hot-path counters live in Redis, not a relational table - but the rules that define those counters, and any per-entity overrides, are configuration data with real structure, joins, and audit needs, which is exactly what a relational schema is good at.

Key modeling decisions

rule_scopes holds per-entity overridesA specific abusive user or a VIP partner can get a tighter or looser limit without creating a new row per user in rate_limit_rules.

scope_key mirrors the Redis key schemaBoth the config store and the hot path use the same composite string, e.g. "apikey:sk_live_42", so config and enforcement never drift.

counters is a snapshot table, not the source of truthA reconciliation job writes it every ~60s from Redis for audit/debugging; it is never read on the request path.

algorithm is a column, not a code branchDifferent endpoints can run token bucket for bursty upload APIs and sliding window for steady read APIs without any gateway code change.

Storage choice	Use for	Watch out for
Relational (Postgres) - rate_limit_rules, rule_scopes	A few thousand rules total, changed rarely, needing strong consistency and easy admin joins/queries.	Never put this on the request hot path - gateways cache rules locally and refresh on an interval instead.
Redis in-memory, Lua-atomic - the live counters	Tens of millions of keys, updated on every single request, needing sub-millisecond round trips.	Sustaining 1M+ writes/sec with row-level locking on a relational engine is simply not viable at this throughput - that is precisely why the hot path never touches SQL.
Relational, batch-written - counters audit snapshot	Compliance/debugging trail of "what did the limiter believe at time T," written every ~60s.	Treat it as eventually-consistent and lossy by design; it is a mirror, not a ledger.

7. Deep dives interviewers actually probe

Token bucket vs leaky bucket vs sliding window counter vs sliding window log - which one and why?

Token bucket allows bursts up to the bucket size and refills at a steady rate - great for "burst allowance" requirements but slightly fiddly to reason about at the boundary. Leaky bucket smooths output to a strictly constant rate, which is better for protecting a downstream system than for a fair public API. Sliding window log keeps a timestamp per request and is perfectly accurate, but memory grows with request count per key - unacceptable at 45M keys. Sliding window counter approximates the true sliding window by blending the previous and current fixed windows by their time overlap, giving near-log accuracy at fixed-window memory cost, which is why it is the default here, with token bucket available per-rule where true burst tolerance is wanted.

-- Sliding window counter, atomic check-and-increment
-- KEYS[1] = rl:{scope_key}
-- ARGV[1] = limit, ARGV[2] = window_seconds, ARGV[3] = now_ms
local key       = KEYS[1]
local limit     = tonumber(ARGV[1])
local window_ms = tonumber(ARGV[2]) * 1000
local now       = tonumber(ARGV[3])
local curr_win  = math.floor(now / window_ms)
local elapsed   = now - (curr_win * window_ms)
local weight    = 1 - (elapsed / window_ms)          -- overlap with previous window

local data = redis.call('HMGET', key, 'win', 'curr', 'prev')
local stored_win = tonumber(data[1]) or curr_win
local curr_count = tonumber(data[2]) or 0
local prev_count = tonumber(data[3]) or 0

if stored_win < curr_win then
  prev_count = (stored_win == curr_win - 1) and curr_count or 0
  curr_count = 0
end

local estimated = (prev_count * weight) + curr_count
if estimated + 1 > limit then
  return {0, 0, window_ms - elapsed}                 -- deny, remaining=0, retry_after_ms
end

redis.call('HSET', key, 'win', curr_win, 'curr', curr_count + 1, 'prev', prev_count)
redis.call('PEXPIRE', key, window_ms * 2)
return {1, math.floor(limit - estimated - 1), 0}     -- allow, remaining, retry_after_ms=0

How is the check kept atomic and race-free across concurrent requests from different gateway nodes?

The naive approach - GET the count in application code, compare to the limit, then SET the incremented value - has a classic time-of-check-to-time-of-use race: two requests from the same key hitting two different gateway nodes can both read count=99 (limit 100), both decide "allow," and both increment, letting 101 through. Redis executes Lua scripts single-threaded and to completion with no other command interleaved, so the entire read-compare-increment-expire sequence above is one indivisible operation from every gateway node's point of view - there is no window in which two nodes can observe the same stale count. The script is preloaded once via SCRIPT LOAD and invoked with EVALSHA, so the round trip is a single hash reference rather than sending the whole script body on every call.

Redis is unreachable for 30 seconds - fail open or fail closed, and why?

Fail-closed (reject everything when the limiter can't reach Redis) turns a transient Redis blip into a full API outage for every customer, including well-behaved ones - the cure becomes worse than the disease it guards against. Fail-open with a conservative local fallback is the standard choice: each gateway node keeps a small in-memory approximate counter with a cap noticeably lower than the real limit (since it can't see other nodes' traffic), allows requests under that cap, and logs every request served this way for reconciliation once Redis recovers. The trade is a short window of imprecise, slightly-too-generous enforcement in exchange for keeping the whole API available - almost always the right trade for a rate limiter, as opposed to say a payments ledger where fail-closed is correct.

How do you stop the Redis cluster itself from becoming the bottleneck at very high scale?

Shard rate-limit keys across the cluster by consistent hashing on the scope key, so no single shard owns a disproportionate share of hot keys, and add shards horizontally as key count or ops/sec grows - this is exactly why the capacity section sized 24 shard primaries rather than one. On the client side, gateway nodes use persistent connection pools and pipeline independent checks for a single request (e.g. per-user and per-API-key limits checked together) into one round trip instead of two. For extremely hot single keys (a viral endpoint hitting one API key from every node at once), a short-lived local pre-aggregation window - batch a few milliseconds of local increments before flushing one combined increment to Redis - trades a small amount of precision for a large reduction in ops against that one hot shard.

What's the single biggest bottleneck if traffic grows 10×?

Not Redis's raw ops capacity - that scales by adding shards. The real ceiling is the fixed network round-trip cost of one synchronous Redis call sitting on every single request's critical path: at 10M req/s even a well-tuned 1ms Lua round trip starts dominating gateway CPU time spent waiting rather than serving. The fix is to stop checking Redis on every request at all: gateways hold a short-lived local token lease (e.g. "you may serve up to 200 requests for this key without asking again, or until 2 seconds pass"), refreshing the lease asynchronously in the background, which turns most requests into a local, lock-free check and reserves the Redis round trip for lease renewal only - a similar idea to the fail-open fallback, but used proactively for throughput rather than reactively for availability.

8. Summary: what a strong answer covers

Named the exact race the naive approach hasJustified every number with a calculationCentralized state, not per-node counters Picked fail-open with a reasoned trade-offMade observability async and non-blockingCompared all four algorithms honestly

Interview tip When asked to design a rate limiter, the strongest signal is naming the check-then-increment race explicitly and explaining precisely why a single atomic Lua script closes it - most candidates describe "store counts in Redis" without ever addressing why the increment must be atomic, which is the actual crux of the problem.