Distributed rate limiter across N app servers

➔? You have 20 app servers behind a load balancer. Design a limiter so a user's limit holds across all of them.

Concepts Involved

Rate Limiting Redis Load Balancer Fault Tolerance Consistency

Problem Statement

Design a rate limiter that enforces a global per-user limit across 20 horizontally-scaled app servers, ensuring a user cannot exceed their quota by hitting different servers, while minimizing the per-request latency overhead of coordination.

Core challenge: With N app servers and a round-robin load balancer, the same user's requests hit different servers each time. Local counters are useless — you need a shared counter store. But every request now pays the cost of a network hop to that store. The race condition: two servers read the same counter, both allow, both increment — user gets 2x their limit.

app servers

round-robin LB

Race Condition

read-check-increment

must be atomic

<2ms

overhead per request

Redis RTT budget

Atomic

Lua script / INCR

no TOCTOU bug

Functional Requirements

What the system must do · the core distributed rate limiting behaviours

Must Have (Core)

1. Enforce global per-user limit across all 20 servers
2. Atomic check-and-increment (no race condition between servers)
3. Return standard 429 response with RateLimit headers
4. TTL-based counter expiry (automatic window rotation, no garbage collection)
5. Fail-open fallback with local counters when Redis is unavailable

Out of Scope (this design)

✗ Tiered plans (all users share same limit in this design)
✗ Per-endpoint limits (single global limit per user, not per route)
✗ Geographic distribution (single-datacenter deployment)
✗ DDoS protection (L3/L4 mitigation is a separate concern)
✗ Analytics / usage dashboards (separate metering pipeline)

Non-Functional Requirements

The quality constraints that shape every architectural decision

Property	Target	Why It Matters / Design Impact
Latency	<2ms per rate check (single Redis RTT)	Rate check runs on every request. Must be invisible to end-user. Same-datacenter Redis gives sub-ms.
Consistency	Exact count (no race condition)	Atomic INCR eliminates TOCTOU bug. User cannot exceed limit by hitting different servers.
Availability	99.99% with Sentinel failover	Redis Sentinel promotes replica in ~5s. Local fallback during gap prevents total outage.
Throughput	Support 200K checks/sec (all 20 servers combined)	Each server does 10K req/sec. Single Redis handles 1M+ ops/sec — 5x headroom.
Fault tolerance	Survive Redis primary failure with <5s failover	Sentinel auto-promotes. During gap: local counters enforce limit/N per server (conservative).

Key tension: Consistency vs. Availability. We choose consistency (exact enforcement) during normal operation, but degrade gracefully to approximate local limits during Redis failure — accepting slightly over-conservative limiting over letting users exceed quota.

Scale Estimation

Given numbers from the question → derive infrastructure sizing

Given (from question): 20 app servers · 10K req/sec per server · 200K total req/sec · 1M unique users · limit = 100 req/min

Step	What to Derive	Calculation	Result	Design Decision
1	Redis ops/sec	200K INCR/sec (one atomic op per request)	200K ops/sec	Well within single Redis capacity (1M+ ops/sec). No cluster needed.
2	Redis memory	1M unique keys × ~50 bytes each (key + integer value + TTL metadata)	~50MB	Trivial memory footprint. Fits in smallest Redis instance.
3	Network bandwidth	200K round trips/sec × ~1KB each (request + response)	~200MB/sec	Standard 10Gbps link handles this. Dedicated Redis NIC recommended.
4	Failover local limit	Global limit (100) ÷ N servers (20)	5 req/min local	Conservative but safe. User gets degraded experience for ~5s during failover.
5	Lua script overhead	EVALSHA (cached) vs EVAL (retransmit) per call	~0.1ms	Pre-load script SHA on server startup. EVALSHA avoids script retransmission.

Interview tip: Start with total ops/sec (200K) to prove a single Redis can handle it. Then show the failover math (limit/N) — this demonstrates you've thought about the degraded state. The key insight: Redis single-threaded model gives you atomicity for free.

APIs

Middleware intercepts all requests · Lua script provides atomic check-and-increment

MIDDLEWARE Rate Limit Check (every request)

Extracts user_id from JWT token. Executes Redis Lua script atomically. Runs BEFORE request handler.

// Redis Lua script (atomic INCR + EXPIRE)

local count = redis.call('INCR', KEYS[1])

if count == 1 then redis.call('EXPIRE', KEYS[1], ARGV[1]) end

return count

// Server logic: if count > limit → 429

429 Too Many Requests Response

Returned when INCR result exceeds user limit. Includes standard headers for client self-throttling.

// Response Headers

HTTP/1.1 429 Too Many Requests

X-RateLimit-Limit: 100

X-RateLimit-Remaining: 0

X-RateLimit-Reset: 1705312260

Retry-After: 34

Data Model

Redis key schema + Lua script caching strategy

Redis · Atomic Counters

// Rate limit counter key
ratelimit:{user_id}:{minute_timestamp} → INTEGER (auto-incremented)
  Example: ratelimit:user_42:1705312200 → 73
  TTL: 60 seconds (auto-expire at window end)

// Key lifecycle:
// 1. First request in window: INCR creates key (value=1), EXPIRE sets 60s TTL
// 2. Subsequent requests: INCR atomically increments
// 3. Window ends: key auto-expires via TTL (no GC needed)

Lua Script · Cached via EVALSHA

// Script loaded on server startup → returns SHA hash
SCRIPT LOAD "local c=redis.call('INCR',KEYS[1]) if c==1 then redis.call('EXPIRE',KEYS[1],ARGV[1]) end return c"
→ SHA: "a3f5b2c..."

// Each request uses EVALSHA (avoids retransmitting script)
EVALSHA a3f5b2c... 1 ratelimit:user_42:1705312200 60

// If SHA not found (after Redis restart): EVAL full script, then cache again

Architecture · Redis Atomic Counter with Lua Script

Single Redis command combines check + increment atomically — eliminates the race condition

Decision	Choice	Why
Shared store	Redis (single-threaded, atomic operations)	Sub-ms latency. Single-threaded model guarantees sequential execution of Lua scripts.
Atomicity	Lua script: GET + compare + INCR + EXPIRE in one call	No TOCTOU (time-of-check-time-of-use) race. One network RTT, one atomic operation.
Algorithm	Fixed window with INCR + EXPIRE (or sliding window via sorted set)	INCR is O(1), ideal for high throughput. Sorted set for exactness if needed.
Key format	ratelimit:{user_id}:{window_timestamp}	Automatic window rotation. Old keys expire via TTL.
Fail mode	Fail-open with local fallback (limit/N per server)	If Redis dies, each server enforces limit/20 locally. Slightly conservative but safe.
High availability	Redis Cluster with read replicas (write to primary only)	Counter writes always go to primary. Failover via Sentinel.

The Lua script pattern: local count = redis.call('INCR', key); if count == 1 then redis.call('EXPIRE', key, window_size) end; return count. Single atomic operation: increment counter, set TTL on first request of window. Server compares returned count against limit.

The race condition explained: Without atomicity: Server A reads count=99, Server B reads count=99. Both see < 100 limit. Both increment. Count becomes 101. User exceeded limit. Fix: Redis INCR returns the new value atomically — if returned value > limit, reject (and optionally DECR to not waste quota).

Anti-patterns: Sticky sessions · defeats load balancing, doesn't scale. Local counters only · user gets N× their limit. Read-then-write without Lua · TOCTOU race under concurrency. Distributed lock around counter · too slow, creates contention.

Real-world: Stripe · Redis-backed sliding window, Lua scripts. GitHub · Redis INCR per API token. Shopify · leaky bucket in Redis (Lua). Cloudflare Workers · Durable Objects for per-key counters.

Resilience & Edge Cases

Failure	Impact	Recovery
Redis primary down	No shared counter available	Sentinel promotes replica. During failover (~5s): local counters with limit/N as conservative fallback.
Network partition (app ↔ Redis)	Some servers can't reach Redis	Local fallback with degraded limits. Reconnect with exponential backoff.
Redis latency spike	P99 request latency increases	Circuit breaker on Redis calls. If latency > 5ms, fall back to local counters temporarily.
Hot key (one user = 90% traffic)	Redis CPU spike on single shard	Pre-reject locally if request rate is obviously above limit (e.g., > 10x). Only borderline cases hit Redis.
Clock skew between servers	Window boundaries differ slightly	Use Redis server time (TIME command) for window calculation, not local clock.

Interview Cheat Sheet

The 6 things to say for distributed rate limiting across N servers

1. Shared Redis counter · single source of truth across all app servers
2. Atomic Lua script · INCR + EXPIRE in one command, eliminates TOCTOU race
3. Single network RTT · one Redis call per request (<1-2ms in same datacenter)
4. Fail-open with local fallback · if Redis down, each server enforces limit/N locally
5. TTL-based cleanup · keys auto-expire, no garbage collection needed
6. The race condition · always explain why read-then-write fails and how INCR solves it

System Design Case Study