Rate Limiting Architecture: Token Bucket vs Sliding Window in a Distributed System

Token bucket allows controlled bursts; sliding window enforces a hard cap on requests in any rolling interval. We run both in production on Redis 7.2—token bucket for API tier (customer-friendly bursts), sliding window log for auth endpoints (abuse-sensitive). The Redis Lua script below is what survived load testing; theory alone did not.

Requirements we actually had

• Public API: 1000 req/min per API key, allow burst to 150 in first second (mobile app startup storm)
• Login: 10 attempts per 5 min per IP, no burst forgiveness
• Distributed: 6 API gateway nodes, no sticky sessions
• Latency budget: sub-2 ms p99 for limit check

Token bucket (API tier)

Classic refill rate: 1000/60 ≈ 16.67 tokens/s, bucket capacity 150.

Properties under burst:

• Client idle 30 s then sends 150 requests: allowed (bucket filled)
• Client sends 150 req/s sustained: throttled after bucket drains—fair for well-behaved mobile apps

Redis implementation stores {tokens, last_refill_ts} hash per key. Atomic refill in Lua avoids race between GET and SET.

-- KEYS[1] = bucket key, ARGV[1] = capacity, ARGV[2] = refill_rate_per_ms, ARGV[3] = now_ms
local data = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(data[1]) or tonumber(ARGV[1])
local last = tonumber(data[2]) or tonumber(ARGV[3])
local delta = math.max(0, tonumber(ARGV[3]) - last)
tokens = math.min(tonumber(ARGV[1]), tokens + delta * tonumber(ARGV[2]))
if tokens < 1 then return 0 end
tokens = tokens - 1
redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', ARGV[3])
redis.call('PEXPIRE', KEYS[1], 60000)
return 1

Gotcha: clock skew across gateway nodes affects refill if you use local now(). We use Redis TIME in the script call path—one clock source.

Sliding window log (auth tier)

Store timestamp of each attempt in a sorted set; trim entries older than window; count members.

Properties:

• 10 requests in 5 min means no 20-request burst in 1 s followed by 9 minutes idle—stricter fairness
• Memory per key higher (one ZSET entry per attempt); acceptable at login volume

-- KEYS[1] = window key, ARGV[1] = now_ms, ARGV[2] = window_ms, ARGV[3] = limit
redis.call('ZREMOVEFRANGEBYSCORE', KEYS[1], 0, tonumber(ARGV[1]) - tonumber(ARGV[2]))
local count = redis.call('ZCARD', KEYS[1])
if count >= tonumber(ARGV[3]) then return 0 end
redis.call('ZADD', KEYS[1], ARGV[1], ARGV[1] .. '-' .. redis.call('INCR', KEYS[1] .. ':seq'))
redis.call('PEXPIRE', KEYS[1], tonumber(ARGV[2]))
return 1

Gotcha: KEYS[1] .. ':seq' for unique ZSET members—collision without suffix caused under-counting at high QPS.

Sliding window counter (rejected)

Approximate fixed window buckets (Redis Cell module style) were simpler but allowed 2× burst at window boundary—10 req at 4:59 and 10 at 5:01. Unacceptable for credential stuffing detection.

Comparison under load test (k6, 500 VUs)

Algorithm	Burst behavior	p99 check latency	Redis memory/key
Token bucket	Smooth allowance	1.1 ms	~64 B
Sliding window log	Hard cap	1.8 ms	~200 B @ 10 entries
Fixed window	Boundary spike	0.9 ms	~32 B

Gateway integration

Envoy 1.28 local rate limit handles per-node throttling; Redis handles global. Double-layer prevented Redis hot keys when one customer pinned to single gateway during K8s imbalance.

API shape choices interact—gRPC vs REST vs GraphQL team choices affected how we keyed limits (method + path vs operation name).

When limits trip during incidents, runbook lives in incident response engineering lead runbook.

What I'd do next

1. Expose Retry-After and X-RateLimit-Remaining consistently—mobile clients backoff correctly.
2. Evaluate Redis Cluster vs Dragonfly for ZSET memory at 10× auth traffic.
3. Shadow-mode new limits for a week—log would-block without blocking—to tune thresholds.

Multi-region Redis failure modes

Primary Redis in us-east-1; replica in us-west-2 for read-only analytics—not for limit checks (staleness). During failover test, 45 s of no limit enforcement when promoting replica—gateway defaulted to allow (fail-open) per product decision. Document fail-open vs fail-closed per route; auth stays fail-closed (503), public API fail-open with alert.

Client-visible contract

We standardized HTTP 429 body: { "error": "rate_limit", "retry_after_sec": N } matching Redis TTL math. Mobile team built exponential backoff from header—reduced support tickets 30% vs generic 403.

Global vs per-tenant limits

Enterprise tier negotiated 10× API limit—implemented as Redis key prefix rl:{tenant_id}:{api_key}. Hot tenant isolation prevented one customer's load test from draining shared token bucket miscalculation in early design.

GraphQL complexity interaction

GraphQL batch query counted as one HTTP request but fanned to 40 backend calls—rate limit at HTTP layer insufficient. Added field-cost weighted limit using query complexity plugin output; see gRPC vs REST vs GraphQL team choices.

Match algorithm to fairness requirements, not Redis tutorial defaults.