Design a Distributed Rate Limiter

System Design Interview•~30 min read•medium

Design a rate limiter for a public API that enforces per-user and per-IP request limits at scale. The service must handle high throughput, be deployable across multiple data center regions, and gracefully degrade when the rate-limiting backend is unavailable.

1. Understand Requirements & Scope

Core tension: single-server counters don't work across nodes; distributed counters add network round-trips. The 2 ms latency budget is tight — a Redis call is typically 0.5–1 ms in the same data center. Algorithm choice (token bucket, fixed window, sliding window log, sliding window counter) affects accuracy, memory, and implementation complexity.

Functional Requirements:

Enforce per-user and per-IP rate limits (e.g., 1,000 requests/minute per user).
Return a clear 429 response with retry-after headers when limits are exceeded.
Support multiple limit windows (per-second, per-minute, per-hour).
The limiter must work across multiple API server instances.
Degrade gracefully: if the rate-limit store is unreachable, choose fail-open or fail-closed based on product policy.

2. Back-of-the-Envelope Capacity Estimation

• API receives ~500,000 requests/second at peak.

• Rate limit decisions must add ≤ 2 ms to request latency (p99).

• The limiter must be consistent across 10+ API nodes in a region.

• Configurable limits: different limits per API key tier (free, pro, enterprise).

• No shared memory between API processes — distributed counter required.

3. High-Level Architecture Flow

Sliding window counter backed by Redis. Each incoming request: compute window boundaries → INCRBY the current window counter for the key (userId:windowStart) → read previous window counter → compute weighted count = prevCount × (remaining fraction of prev window) + currCount → if weighted count > limit, return 429.

[ Clients ] -> [ API Gateway (Rate Limiter Middleware) ]
                     |                           |
                     v (Check Rule Cache)        v (Atomic Lua Script)
              [ Local In-Memory Cache ]   [ Redis Cluster Counter ]

Fig 1. Architecture data flow and component topology.

4. Production Implementation & Code

-- 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)
end

Hardened Implementation Sequence

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.

5. Key Decisions & Operational Mitigations

Architectural Decisions & Trade-Offs

•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.
•Fail-open (allow on Redis failure): Protects availability; risk: abuse during outage. Use for non-critical APIs or when abuse impact is low.
•Fail-closed (block on Redis failure): Protects against abuse; risk: legitimate users blocked during outage. Use for billing/sensitive APIs.
•Lua scripts for atomicity: 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.

Operational Hazards & Mitigations

•Redis node failure: 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.
•Hot user: 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.
•Cross-region rate limiting: 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.

Interactive Knowledge Check • Question 1 of 3↓

Interactive Practice Quiz•Question 1 of 3

intermediate

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?