Skip to main content
← PROBLEMS / SYSTEM-DESIGN
An end-to-end domain learning journey

Design a Token
Bucket Rate Limiter.

Design a distributed rate-limiting service for an API Gateway cluster (40 stateless Envoy/Go/Java nodes) handling 400,000 global requests/sec across 10,000,000 active API keys. Each tenant has a configurable sustained rate (e.g., 100 req/s) and burst capacity (e.g., 250 tokens).
Start the journey5 stages
Loading diagram…
Design a Token Bucket Rate Limiter architecture sketch diagram
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

Design a distributed rate-limiting service for an API Gateway cluster (40 stateless Envoy/Go/Java nodes) handling 400,000 global requests/sec across 10,000,000 active API keys. Each tenant has a configurable sustained rate (e.g., 100 req/s) and burst capacity (e.g., 250 tokens).

From patterns to decisions.

Design a distributed rate-limiting service for an API Gateway cluster (40 stateless Envoy/Go/Java nodes) handling 400,000 global requests/sec across 10,000,000 active API keys. Each tenant has a configurable sustained rate (e.g., 100 req/s) and burst capacity (e.g., 250 tokens).

01
SYSTEM-DESIGN · STAGE 01L4 · FUNDAMENTALS

Fixed Window allows 2x burst.

Fixed Window allows 2x burst spikes across window boundaries (e.g., 100 reqs at 00:59 + 100 at 01:00). Separate GET and SET calls create a TOCTOU race condition under concurrency.

ChoiceWhat it buysWhat it costs
Trade-off 1Sliding Window Log is exact but stores a timestamp per request (high memory for 10M keys); Token Bucket uses O(1) memory per key.

Step 1

Explain boundary burst problem in Fixed Window.

Step 2

Show how Token Bucket enforces smooth refill while allowing bounded burst capacity.

Step 3

Demonstrate the TOCTOU race when two gateways read tokens=1 concurrently.

Alternative 1

Sliding Window Counter (approximates sliding window in O(1) memory, but lacks explicit burst capacity tuning).

Failure Mode 1

Under 50 concurrent requests, non-atomic GET/SET allows up to 50x the intended burst.

# Broken non-atomic pattern (DO NOT USE in production):
tokens = float(redis.get(key) or capacity)
if tokens >= 1:
    # Race window: 10 concurrent threads all pass this check!
    redis.set(key, tokens - 1)
02
SYSTEM-DESIGN · STAGE 02L5 · APPLIED DESIGN

Production Redis Lua script using.

Production Redis Lua script using redis.call('TIME') for clock-skew immunity, lazy refill, and PEXPIRE auto-eviction, wrapped in a Python client with EVALSHA + NOSCRIPT fallback.

ChoiceWhat it buysWhat it costs
Trade-off 1Lua script blocks the single Redis shard thread for ~3-5 microseconds, easily sustaining 80k+ RPS per shard.

Step 1

Read server time via redis.call('TIME') inside Lua.

Step 2

Compute refilled = math.min(capacity, tokens + (elapsed_ms * rate) / 1000.0).

Step 3

Deduct cost if refilled >= cost, persist via HSET + PEXPIRE, and return [allowed, remaining, retry_after_ms].

Alternative 1

Redis Cell (CL.THROTTLE) module using Generic Cell Rate Algorithm (GCRA) in C.

Failure Mode 1

Passing client now_ms instead of redis.call('TIME') causes token drift across gateways with skewed clocks.

TOKEN_BUCKET_LUA = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate_per_sec = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])

local t = redis.call('TIME')
local now_ms = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local data = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(data[1])
local last_ts = tonumber(data[2])

if tokens == nil then
    tokens = capacity
    last_ts = now_ms
else
    local elapsed_ms = math.max(0, now_ms - last_ts)
    tokens = math.min(capacity, tokens + (elapsed_ms * rate_per_sec) / 1000.0)
    last_ts = now_ms
end

local allowed = 0
local retry_after_ms = 0
if tokens >= cost then
    tokens = tokens - cost
    allowed = 1
else
    retry_after_ms = math.ceil(((cost - tokens) / rate_per_sec) * 1000)
end

local ttl_ms = math.ceil((capacity / rate_per_sec) * 2000)
redis.call('HSET', key, 'tokens', tostring(tokens), 'ts', tostring(last_ts))
redis.call('PEXPIRE', key, ttl_ms)
return {allowed, math.floor(tokens), retry_after_ms}
"""
03
SYSTEM-DESIGN · STAGE 03L6 · SCALE & TRADE-OFFS

Centralized 1-RTT Redis Lua is.

Centralized 1-RTT Redis Lua is simpler and strictly accurate at 400k RPS across 8 shards; local-quota batching is needed only when scaling past 2M+ RPS or across multi-region WAN links.

ChoiceWhat it buysWhat it costs
Trade-off 1Centralized checking adds ~0.8 ms network RTT per request vs ~0.01 ms for local batching.

Step 1

Size 8 Redis shards for 400k RPS (~50k RPS/shard, < 1 ms p99).

Step 2

Show how local batching reduces Redis QPS 10x but breaks strict small-limit enforcement (e.g., 5 req/min).

Step 3

Choose centralized Redis Lua + L1 deny-cache for single-region, or local batching for multi-region.

Alternative 1

Envoy Global Rate Limit gRPC service with local memory batching.

Failure Mode 1

Batching 10 tokens locally when a tenant's limit is 5 req/s allows up to 400 req/s across 40 nodes.

def check_rate_limit(redis_client, sha: str, api_key: str, cap: int, rate: float, cost: int = 1):
    key = f"rl:{{{api_key}}}"
    try:
        allowed, rem, retry_ms = redis_client.evalsha(sha, 1, key, cap, rate, cost)
    except Exception as e:
        if "NOSCRIPT" in str(e):
            allowed, rem, retry_ms = redis_client.eval(TOKEN_BUCKET_LUA, 1, key, cap, rate, cost)
        else:
            raise
    return bool(allowed), int(rem), int(retry_ms)
04
SYSTEM-DESIGN · STAGE 04L6 · SCALE & TRADE-OFFS

An L1 in-memory deny-cache on.

An L1 in-memory deny-cache on each gateway intercepts repeated requests for an already-throttled key for min(100 ms, retry_after_ms), cutting Redis traffic on that hot key by > 99%.

ChoiceWhat it buysWhat it costs
Trade-off 1L1 deny-cache can over-block by up to 100 ms even if another process hadn't consumed, which is negligible on an already-exhausted bucket.

Step 1

Check local deny_cache.get(api_key) before calling Redis.

Step 2

On Redis allowed == 0, store blocked_until = monotonic_ms + min(100, retry_after_ms).

Step 3

Wrap Redis calls in a 3 ms timeout + circuit breaker falling back to local rate/40 bucket.

Alternative 1

Edge WAF / Cloudflare rate limiting in front of the API gateway.

Failure Mode 1

Unbounded l1_deny dict without LRU eviction leaks memory under random-key DDoS.

import time

class GatewayRateLimiter:
    def __init__(self, redis_client, sha: str, num_nodes: int = 40):
        self.redis = redis_client
        self.sha = sha
        self.num_nodes = num_nodes
        self.l1_deny: dict[str, float] = {}  # api_key -> blocked_until_ms

    def allow(self, api_key: str, cap: int, rate: float) -> tuple[bool, int]:
        now = time.monotonic() * 1000.0
        if self.l1_deny.get(api_key, 0.0) > now:
            return False, 100
        try:
            ok, rem, retry_ms = check_rate_limit(self.redis, self.sha, api_key, cap, rate)
            if not ok:
                self.l1_deny[api_key] = now + min(100.0, float(retry_ms))
            return ok, retry_ms
        except Exception:
            # Fail-open with local fallback or allow; here fail-open on Redis timeout
            return True, 0
05
SYSTEM-DESIGN · STAGE 05L7 · STAFF / PRINCIPAL

Each region runs a local.

Each region runs a local Redis Cluster enforcing regional quotas, while an asynchronous gossip/CRDT sync worker periodically redistributes unused token budgets across regions based on traffic share.

ChoiceWhat it buysWhat it costs
Trade-off 1Avoids 80-150 ms cross-ocean RTT on every API call at the cost of 1-second eventual consistency.

Step 1

Keep the hot path strictly intra-region (< 1 ms) using regional Redis Clusters.

Step 2

Split global quota across regions dynamically via a 1-second async quota-rebalancer (CRDT PN-Counter or central coordinator).

Step 3

Accept bounded eventual consistency (e.g., < 5% overshoot during sudden cross-region failover).

Alternative 1

Geo-pinning tenants to a home region so all requests for tenant X route to one Redis cluster.

Failure Mode 1

If cross-region sync stalls, each region must cap at a safe static fallback fraction to avoid 3x global overload.

# Async regional quota allocation: weight regional rate by trailing 10s traffic share
def allocate_regional_rates(global_rate: float, regional_rps: dict[str, float]) -> dict[str, float]:
    total = sum(regional_rps.values()) or 1.0
    return {region: max(global_rate * 0.1, global_rate * (rps / total)) for region, rps in regional_rps.items()}

Theory & Tips and Tricks

Practical heuristics & interview traps

  • 01Interview anchor: A single atomic Redis Lua script eliminates read-modify-write race conditions and cuts network round-trips from 2 to 1, keeping rate-limiter p99 overhead under 1.5 ms.
  • 02Trade-off tip: Centralized checking adds ~0.8 ms network RTT per request vs ~0.01 ms for local batching.
  • 03Watch out for: Unbounded l1_deny dict without LRU eviction leaks memory under random-key DDoS.
Behavioral Progression · Design Token Bucket Rate Limiter

Design Token Bucket Rate Limiter — Normal → Load / Fault → Recovery

Send Request
1. Normal Request Ingress
Traffic: 1x baseline · Latency (p99): 4 ms
Process State
2. Core Execution & State Lookup
Traffic: 1x baseline · Latency (p99): 9 ms
Inject 10x Spike
3. Scale Spike / Failure Injection
Traffic: 10x burst · Latency (p99): 185 ms

A single atomic Redis Lua script eliminates read-modify-write race conditions and cuts network round-trips from 2 to 1, keeping rate-limiter p99 overhead under 1.5 ms.

Synthesis / One connected design

Putting Design a Token Bucket Rate Limiter Together

A single atomic Redis Lua script eliminates read-modify-write race conditions and cuts network round-trips from 2 to 1, keeping rate-limiter p99 overhead under 1.5 ms.

A candidate architecture, not a universal answer

Putting Design a Token Bucket Rate Limiter Together

Step 1
Step 2
Step 3
  1. Read server time via redis.call('TIME') inside Lua.
  2. Compute refilled = math.min(capacity, tokens + (elapsed_ms * rate) / 1000.0).
  3. Deduct cost if refilled >= cost, persist via HSET + PEXPIRE, and return [allowed, remaining, retry_after_ms].
An L1 in-memory deny-cache on each gateway intercepts repeated requests for an already-throttled key for min(100 ms, retry_after_ms), cutting Redis traffic on that hot key by > 99%.
Interview Readiness Check

An L1 in-memory deny-cache on each gateway intercepts repeated requests for an already-throttled key for min(100 ms, retry_after_ms), cutting Redis traffic on that hot key by > 99%.

Walk through bottlenecks, back-of-the-envelope math, and failure recovery.

Practice / Explain the consequences

Make the trade-off yourself.

Practice Check

Test your understanding

Question 1 of 3

Why are standard Redis GET and SET operations unsafe for implementing API rate limiting across multi-threaded gateway nodes?

Key takeaway

Design a Token Bucket Rate Limiter

A single atomic Redis Lua script eliminates read-modify-write race conditions and cuts network round-trips from 2 to 1, keeping rate-limiter p99 overhead under 1.5 ms.