System Design Interview · Very Common

Design a Rate Limiter

Interviewers love this because it tests knowledge of algorithms, Redis, distributed systems, and API design. Know all 4 algorithms and their trade-offs cold.

The 4 Rate Limiting Algorithms

1. Token Bucket ✓ Most Used

Bucket holds max N tokens. Tokens added at rate R/sec. Each request consumes 1 token. If empty → reject.

✓ Pros

· Allows bursts up to bucket capacity

· Smooth average rate

· Memory efficient: 2 values per user

✗ Cons

· Burst at boundary: user can consume all tokens then immediately get refill

· Race condition without atomic ops

→ AWS API Gateway, Stripe, most production rate limiters. Best overall.

2. Leaky Bucket

Requests enter a queue (bucket). Processor drains at fixed rate R. If queue full → reject. Output is always at constant rate.

✓ Pros

· Perfectly smooth output rate

· Simple queue-based implementation

✗ Cons

· Recent requests may be starved by old ones stuck in queue

· Does NOT allow bursts at all

→ Traffic shaping, network QoS. When output rate must be strictly constant.

3. Fixed Window Counter

Divide time into fixed windows (e.g. per minute). Count requests in current window. If count > limit → reject. Reset counter at window boundary.

✓ Pros

· Very simple

· Low memory: 1 counter per user per window

✗ Cons

· Boundary burst: user can fire 2× limit by bursting at end + start of adjacent windows

→ Simple rate limiting where boundary bursts are acceptable.

4. Sliding Window Log

Store timestamp of every request in a sorted set. On each request: remove old timestamps, count remaining, if < limit → allow and add new timestamp.

✓ Pros

· Most accurate — no boundary burst

· Precise request counting

✗ Cons

· High memory: stores every timestamp

· O(N) cleanup per request

→ Strict rate limiting for critical APIs. When accuracy > memory.

5. Sliding Window Counter

Compromise between Fixed Window and Sliding Log. Count = curr_window × (time_in_window / window_size) + prev_window × (1 - weight). Approximation.

✓ Pros

· Low memory (2 counters)

· Smooths out boundary bursts (95% accurate)

· Better than fixed window

✗ Cons

· Slight inaccuracy (assumes uniform distribution in prev window)

→ Production systems needing accuracy without log overhead. Cloudflare uses this.

Redis-Based Token Bucket Implementation

Why Lua scripts? Redis operations are not atomic when combined. A Lua script executes atomically on the Redis server — no race conditions without using locks.

-- Lua script (runs atomically in Redis)
-- Keys: [key]  Args: [maxTokens, refillRate, refillInterval, now, cost]
local key = KEYS[1]
local maxTokens = tonumber(ARGV[1])
local refillRate = tonumber(ARGV[2])
local refillInterval = tonumber(ARGV[3])
local now = tonumber(ARGV[4])
local cost = tonumber(ARGV[5])

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

-- Calculate new tokens to add since last refill
local elapsed = now - last_refill
local new_tokens = math.floor(elapsed / refillInterval * refillRate)
tokens = math.min(maxTokens, tokens + new_tokens)
last_refill = now

if tokens >= cost then
    tokens = tokens - cost
    redis.call('HMSET', key, 'tokens', tokens, 'last_refill', last_refill)
    redis.call('EXPIRE', key, 86400)  -- TTL: auto-cleanup
    return 1  -- ALLOWED
else
    redis.call('HMSET', key, 'tokens', tokens, 'last_refill', last_refill)
    return 0  -- REJECTED
end

# Python usage
import redis
import time

r = redis.Redis()
script = r.register_script(LUA_SCRIPT)

def is_allowed(user_id: str, max_tokens=100, refill_rate=10, cost=1) -> bool:
    result = script(
        keys=[f"rate:{user_id}"],
        args=[max_tokens, refill_rate, 1000, int(time.time() * 1000), cost]
    )
    return result == 1

# HTTP middleware usage
def rate_limit_middleware(request):
    if not is_allowed(request.user_id):
        return Response(429, {
            "error": "Too Many Requests",
            "retry_after": 1  # seconds
        })
    return next_handler(request)

Distributed Rate Limiting

Single Server: Client → Server → Redis → Allow/Reject Simple. Redis as central authority. Multi-Region Challenge: US: Server A (allows 40 req) EU: Server B (allows 65 req) Total: 105 req for 100 limit → VIOLATED Solutions: Option 1: Global Redis Cluster All servers point to SAME Redis cluster + Accurate across all regions - Redis becomes a bottleneck + single point of failure - Cross-region latency for Redis reads Option 2: Sticky Sessions (Client → Same Server) LB routes same user to same server Server has local in-memory counter + Fast (no network hop) - Server failure loses counter state - Doesn't work with horizontal scaling Option 3: Local + Sync (Gossip Protocol) Each server has local counter Servers gossip their counts periodically (every 100ms) Allow if local_count + estimated_global < limit + No Redis dependency - Small window of over-limit (acceptable for most APIs) Industry standard: Option 1 for critical APIs, Option 3 for high-throughput ones

Rate Limit Response Headers

Header	Example Value	Meaning
X-RateLimit-Limit	1000	Max requests allowed in window
X-RateLimit-Remaining	742	Remaining requests in current window
X-RateLimit-Reset	1735689600	Unix timestamp when window resets
X-RateLimit-Retry-After	42	Seconds until client can retry (429 only)
X-RateLimit-Window	3600	Window duration in seconds

Trade-offs Summary

Consideration	Option A	Option B	Recommendation
Algorithm	Token Bucket (burst OK)	Sliding Window Log (strict)	Token Bucket for most APIs
Storage	Redis (centralized)	In-memory (local)	Redis for accuracy; in-memory for ultra-low latency
Scope	Per user	Per IP	Per API key (authenticated) + IP (unauthenticated)
Rate limit granularity	Per second	Per minute/hour	Multiple: 10/sec AND 1000/min
Failure mode	Fail open (allow all)	Fail closed (block all)	Fail open for availability; fail closed for security
Client transparency	Silent rejection	429 + Retry-After header	Always return 429 with Retry-After

Bottlenecks

⚠️ Redis is the bottleneck at 1M+ requests/sec

→ Redis Cluster shards by user_id hash. 100M ops/sec is achievable with 10-node cluster. Each node handles ~10M ops/sec.

⚠️ Redis goes down — all requests allowed (fail open) or all blocked (fail closed)

→ Rate limiter should fail open for availability. Log the Redis failure. Circuit breaker: if Redis error rate > 50% in 10 sec, bypass rate limiting temporarily.

⚠️ Memory growth: 1M users × 1 counter each = 1M keys in Redis

→ Set TTL on every key = window_size × 2. Auto-cleanup removes inactive users. At 100 bytes per key × 1M users = only 100 MB.

← Twitter Distributed Cache →