Design a Distributed
Rate Limiter.
SAY THIS: “Before proposing a topology for Design a Distributed Rate Limiter, I’ll clarify the core functional requirements, burst characteristics, data volume, and availability SLOs to define rigid system boundaries.”
What the system does
- Enforce per-user and per-IP rate limits, such as 1,000 requests per minute per user.
- Return HTTP 429 with retry guidance when a quota is exceeded.
- Support per-second, per-minute, and per-hour windows.
- Coordinate decisions across multiple API server instances.
- Support configurable limits by API key tier and endpoint.
- Define fail-open or fail-closed behavior when the rate-limit store is unavailable.
What to agree on
- Peak API traffic is approximately 500,000 requests per second.
- Rate-limit decisions should add no more than 2 ms at p99.
- The limiter should provide shared enforcement across 10 or more API nodes in a region.
- API processes do not share memory.
- Regional enforcement is the default scope; strict global enforcement requires additional coordination.
SAY THIS: “Let’s establish order-of-magnitude sizing for peak throughput, memory footprint, and network ingress to size the critical latency path before making technology choices.”
At an illustrative 200 bytes per record/session, high-volume state requires dedicated primary in-memory partitions. Add replicas, allocator overhead, policy indexes, and headroom.
Always validate throughput and p99 latency targets under skewed traffic distributions and replica failovers.
Keep state shared and partitioned.
SAY THIS: “I’ll separate low-latency ephemeral cache state from authoritative durable storage, ensuring strict consistency where needed and partitioning for scale.”
Cache / Ephemeral state
state:{partitionKey}:activeWindow
- In-memory key-value cache (Redis Cluster / Memcached).
- TTL expiration matching window validity bounds.
- Hash tags to co-locate keys for atomic Lua scripts or transactions.
Durable / Authoritative store
- Distributed NoSQL / relational database (DynamoDB, PostgreSQL).
- Durable write-ahead log with replica failover.
- Cache-aside pattern: read misses warm cache from durable store.
- Asynchronous CDC / event streaming to telemetry sinks.
Local-only node state is not a shared cluster quota: N nodes could admit roughly N × the configured limits. Ensure state co-location and transactional boundaries align with partition keys.
SAY THIS: “The gateway tier authenticates incoming traffic, validates payloads, and routes requests to decoupled services backed by partitioned caching and authoritative storage tiers.”
Use tight timeouts, circuit breakers, and rate-limiting middleware at ingress to protect downstream services from cascading collapse.
Define the contract.
SAY THIS: “The API contract establishes idempotent mutation semantics, clear error taxonomy, and explicit status codes so upstream clients can safely retry.”
Success Path
Forward the request or return HTTP 200/201. Include standard tracking and rate/quota telemetry headers in the response.
Failure & Fallback
Use explicit HTTP status codes: 400 for invalid input, 429 for quota violations, and 503 with Retry-After during maintenance or partitions.
View example API payload contract
HTTP/1.1 200 OK
Content-Type: application/json
Cache-Control: max-age=300
{
"status": "success",
"data": { "id": "res_98a7f", "processedAt": "2026-11-11T12:00:00Z" }
}Include idempotency keys on write endpoints to guarantee at-most-once processing across network retries.
SAY THIS: “For the critical execution path, we enforce idempotency and concurrency controls using atomic primitives, avoiding lock contention and split-brain states.”
- Request arrives at API node with userId and timestamp.
- Compute current 60-second window start: windowStart = floor(now / 60) * 60.
- Redis MULTI: INCR user:{userId}:{windowStart}, GET user:{userId}:{windowStart-60}, EXPIRE user:{userId}:{windowStart} 120.
- weightedCount = prevWindowCount × ((windowStart + 60 - now) / 60) + currWindowCount.
- If weightedCount > limit: set X-RateLimit-Remaining: 0, return 429 with Retry-After header.
- Else: decrement or allow — return 200 with X-RateLimit-Remaining header.
| STRATEGY / PATTERN | WHY CHOOSE IT? | TRADE-OFF / COST |
|---|---|---|
| Token bucket in Redis with Lua script | atomic, avoids race conditions, handles burst naturally. Slightly more complex Lua script to maintain. | Coordinate partition dependencies |
| Local in-memory limiter with gossip sync | low latency (no network call) but requires approximate counting — nodes can each allow up to limit/N individually, risking N× burst. | Coordinate partition dependencies |
| Centralized SQL counter | accurate but adds 5–20 ms per request — exceeds the 2 ms budget. | Coordinate partition dependencies |
View reference production code implementation
-- Atomic Redis Token Bucket Script (Runs in single-threaded event loop)
local tokens_key = KEYS[1]
local timestamp_key = KEYS[2]
local rate = tonumber(ARGV[1]) -- Refill rate (tokens per second)
local capacity = tonumber(ARGV[2]) -- Maximum burst capacity
local now = tonumber(ARGV[3]) -- Current epoch timestamp (seconds)
local requested = tonumber(ARGV[4]) -- Tokens requested (typically 1)
local current_tokens = tonumber(redis.call('get', tokens_key))
local last_refreshed = tonumber(redis.call('get', timestamp_key))
if current_tokens == nil then
current_tokens = capacity
last_refreshed = now
end
local delta = math.max(0, now - last_refreshed)
local tokens = math.min(capacity, current_tokens + (delta * rate))
if tokens >= requested then
redis.call('set', tokens_key, tokens - requested)
redis.call('set', timestamp_key, now)
redis.call('expire', tokens_key, 3600)
redis.call('expire', timestamp_key, 3600)
return 1 -- Allowed
else
return 0 -- Denied (HTTP 429)
endAvoid client-side read-modify-write loops without concurrency control. Use atomic scripts, row-level locks, or conditional mutations at the storage tier to guarantee linearizability.
View sequence trace & failure interaction flow
[ Clients ] -> [ API Gateway (Rate Limiter Middleware) ]
| |
v (Check Rule Cache) v (Atomic Lua Script)
[ Local In-Memory Cache ] [ Redis Cluster Counter ]SAY THIS: “The biggest operational risks involve node failover, partition skew, network isolation, and cascading downstream backpressure. Here is how we mitigate each.”
Fixed window allows up to 2× burst at the boundary (last second of window N + first second of window N+1). Sliding window eliminates this at O(1) memory cost.
Local is O(0ms) but each node allows limit requests independently — 10 nodes allow 10× limit. Redis adds ~1 ms but provides a shared accurate counter.
Protects availability; risk: abuse during outage. Use for non-critical APIs or when abuse impact is low.
Protects against abuse; risk: legitimate users blocked during outage. Use for billing/sensitive APIs.
Redis MULTI/EXEC provides optimistic locking; Lua scripts provide true atomicity. For rate limiting, a Lua script is preferred to avoid race between INCR and GET.
With Redis Sentinel or Cluster, replica promotion takes 10–30 s. During that window: fail-open (allow) or local fallback counter (allow up to local_limit = limit/node_count). Redis Cluster with consistent hashing for key distribution — each userId is pinned to one shard.
A single userId key in Redis becomes a hot key, concentrating load on one Redis shard. Mitigation: replicate hot keys to N replicas and read-balance across them; or shard the counter across K sub-keys (userId:0..K-1) and sum them — introduces K reads per request.
Each region maintains its own Redis counter. Eventual synchronization via async replication — allows up to sum(regional_limits) globally. True global rate limiting requires a global counter service (high latency) or token-bucket with quota allocation per region.
Close with the trade-offs.
SAY THIS: “In closing, we optimized for sub-millisecond p99 latency and high availability under partition. We trade strict distributed linearizability for predictable throughput and operational simplicity.”
If the interviewer asks…
- Sliding window vs fixed window: Fixed window allows up to 2× burst at the boundary (last second of window N + first second of window N+1). Sliding window eliminates this at O(1) memory cost.
- Redis vs local counter: Local is O(0ms) but each node allows limit requests independently — 10 nodes allow 10× limit. Redis adds ~1 ms but provides a shared accurate counter.
Keep the conclusion focused
- What guarantees are strictly enforced at runtime?
- What happens during network partitions or node failures?
- Which CAP trade-off was intentionally chosen and why?
A distributed rate limiter controls how many requests a user, API key, or IP address can make within a time window. It protects backend services from overload and abuse while keeping legitimate traffic available. The distributed challenge is sharing quota state across many API servers without adding too much latency.
“Put the limiter at the API gateway, keep policy configuration close to the request path, and use an atomic shared counter store such as Redis. Choose the algorithm, consistency scope, and outage behavior explicitly.”
Atomic Counter Rate Limiting Under Concurrency
Why are standard Redis GET and SET operations unsafe for implementing API rate limiting across multi-threaded gateway nodes?