Global multi-region rate limiter

➔? Design a global rate limit of 10,000 req/min per user enforced across US-East, EU-West, and AP-South regions

Concepts Involved

Rate Limiting Multi-Region Redis Consistency Fault Tolerance

Problem Statement

Design a rate limiter that enforces a single global limit of 10,000 requests/minute per user across three geographically distributed regions (US-East, EU-West, AP-South). A user hitting all three regions simultaneously must not exceed the global limit, regardless of request distribution across regions.

Core challenge: The hardest trade-off in distributed rate limiting: regional Redis gives low latency (~1ms) but loose global accuracy (each region counts independently). Central Redis gives strict accuracy but adds 50-150ms cross-region RTT per request. No solution is perfect — you must choose where on the consistency-latency spectrum to sit.

10,000

req/min global

single user limit

3 Regions

US / EU / AP

50-150ms apart

Trade-off

latency vs accuracy

fundamental tension

Token Leasing

best compromise

local speed + global accuracy

Functional Requirements

What the system must do · global rate limiting across multiple regions

Must Have (Core)

1. Single global limit across all regions (10,000 req/min per user)
2. Token leasing from central coordinator to regional limiters
3. Adaptive lease sizing based on regional traffic patterns
4. Async reconciliation every 5s between regions and coordinator
5. Graceful degradation when coordinator is unreachable (drain local lease)
6. No over-allocation — leases never exceed global pool total

Out of Scope (this design)

✗ Per-region separate limits (this enforces one global limit)
✗ Geographic-aware routing decisions
✗ Multi-tenant within regions
✗ DDoS mitigation (separate edge concern)
✗ User-facing APIs (this is infrastructure-level)

Non-Functional Requirements

Quality constraints shaping the multi-region rate limiting design

Property	Target	Why It Matters / Design Impact
Latency	<1ms per request	Local Redis only on hot path. No cross-region call per request.
Accuracy	Bounded overrun = max 1 reconciliation period (5s) of excess	Eventually consistent model. Bounded over-admit is acceptable trade-off for speed.
Availability	Continue serving from local lease even if coordinator unreachable	Graceful degradation: drain local budget then reject. No hard dependency on central store per request.
Consistency	Eventually consistent (5s reconciliation cycle)	Regions report usage and receive new leases every 5s. Global truth converges within one cycle.
Coordinator HA	Consensus-backed (Raft), no SPOF	Central coordinator uses Raft consensus for leader election. Failover within seconds.

Key tension: Latency vs. Accuracy. Cross-region RTT (50-150ms) makes per-request central calls unacceptable. Token leasing solves this by making most requests local-only, accepting bounded eventual consistency.

Scale Estimation

Given numbers from the question → derive infrastructure sizing

Given (from question): 10,000 req/min global limit per user · 3 regions (US, EU, AP) · RTT between regions 50-150ms

Step	What to Derive	Calculation	Result	Design Decision
1	Regional split (adaptive)	US 50%, EU 30%, AP 20% of global limit	US: 5K, EU: 3K, AP: 2K	Proportional to observed traffic. Rebalanced every 5s.
2	Lease request frequency	Every 5s or when local lease < 20% remaining	~12 cross-region calls/min per user	Only lease requests cross regions, not per-request checks.
3	Local Redis ops	Same as single-region (INCR/EXPIRE per request)	<1ms per check	Hot path is entirely local. No cross-region latency.
4	Worst-case overrun	3 regions × 5s × regional drain rate	Bounded: max 1 reconciliation period	Total leases never exceed global limit. Overrun is bounded.
5	Cross-region bandwidth	~12 lease requests/min × ~200 bytes each	Negligible	Lease protocol is lightweight. Reconciliation messages are tiny.

Interview tip: Start by acknowledging the fundamental trade-off (latency vs accuracy), then show the lease math. The key insight: cross-region calls happen only ~12 times/min (lease requests), not per-request. That's the core of token leasing.

APIs

Internal lease protocol between coordinator and regional limiters · per-request check is local only

INTERNAL LeaseRequest(user_id, region, requested_tokens) → LeaseGrant(tokens, ttl)

Region requests a token lease from central coordinator. Coordinator checks remaining pool and allocates proportionally.

// Region → Coordinator

LeaseRequest { user_id: "u_42", region: "us-east", requested_tokens: 5000 }

// Coordinator → Region

LeaseGrant { tokens: 5000, ttl: 60, lease_id: "lease_abc" }

INTERNAL ReportUsage(user_id, region, consumed_tokens, remaining)

Every 5s each region reports consumption to coordinator for reconciliation and lease rebalancing.

// Region → Coordinator (every 5s)

ReportUsage { user_id: "u_42", region: "us-east", consumed: 3200, remaining: 1800 }

PER-REQUEST Local rate check (Redis INCR — same as single-region)

Hot path is purely local. No cross-region call. Deducts from local lease budget via Redis INCR with EXPIRE.

Data Model

Central coordinator state + regional Redis lease counters

Central Coordinator · Global Pool

// Global pool per user (source of truth)
global_pool:{user_id} → {
  total: 10000,
  allocated: { us: 5000, eu: 3000, ap: 2000 },
  remaining: 0    // total - sum(allocated)
}

Regional Redis · Lease State

// Lease counter per user per region
ratelimit:{user_id}:lease → {
  remaining: 1800,
  lease_ts: 1705312200,
  lease_ttl: 60
}

// Local consumption counter
ratelimit:{user_id}:counter → INTEGER (auto-incremented per request)
  TTL: matches lease window

Reconciliation Log

// Timestamped lease grant/return events
lease_history:{user_id} → [
  { ts: 1705312200, region: "us", action: "grant", tokens: 5000 },
  { ts: 1705312205, region: "us", action: "report", consumed: 820 },
  { ts: 1705312210, region: "ap", action: "return", tokens: 200 }
]

Architecture · Token Leasing with Async Reconciliation

Central coordinator allocates token leases to regions. Each region spends locally from its lease, requests more when depleted.

Decision	Choice	Why
Strategy	Token leasing: central coordinator grants "token budgets" to each region	Best compromise: local decisions (<1ms) for most requests. Cross-region call only when lease depleted.
Central store	Central Redis in one "home" region (or DynamoDB Global Tables)	Source of truth for global token pool. Each region requests lease from here.
Lease size	Proportional to region traffic: busy regions get larger leases	US gets 5000/min lease, EU gets 3000, AP gets 2000. Rebalanced every 10s based on actual usage.
Local enforcement	Regional Redis with token bucket (capacity = current lease)	No cross-region RTT on hot path. Deduct locally. Request new lease when < 20% remaining.
Reconciliation	Every 5s: regions report consumed tokens, coordinator rebalances leases	Eventually consistent. Max over-admit: one reconciliation period of excess (e.g., 5s worth).
Fallback	If central coordinator unreachable: continue with remaining local lease, don't request more	Graceful degradation: regions drain their local lease then start rejecting. Safe: cannot exceed previously allocated budget.

Token leasing explained: Central pool has 10,000 tokens/min. US region requests a lease of 5,000 tokens. Central deducts 5,000 from pool. US can now serve 5,000 requests locally without any cross-region call. When US is at 1,000 tokens remaining, it requests a new lease. Central allocates based on remaining pool.

The three options compared: (1) Central Redis — perfect accuracy, +50-150ms latency per request (usually unacceptable). (2) Per-region splitting (10K/3) — low latency, but user in one region only gets 3,333 even if other regions are idle. (3) Token leasing — best of both: local speed + adaptive allocation based on actual traffic.

Anti-patterns: Static per-region split (limit/N) · wastes capacity in idle regions, under-provisions active regions. Always call central store · adds 50-150ms to every request (defeats multi-region purpose). No reconciliation · regions drift from global truth indefinitely.

Real-world: Cloudflare · gossip-based count sharing between PoPs. Google · Chubby-like coordination for global quotas. Stripe · centralized rate limiting (accepts latency trade-off for payment accuracy). AWS · per-region quotas with global service quota as cap.

Resilience & Edge Cases

Failure	Impact	Recovery
Central coordinator down	Regions can't request new leases	Continue with remaining local lease (safe). When depleted, reject. Coordinator failover via consensus (Raft/Paxos).
User shifts all traffic to one region	That region's lease depletes fast, others idle	Fast lease rebalancing (every 5s). Idle regions return unused tokens to central pool. Active region gets larger next lease.
Network partition between regions	Partitioned region can't reconcile	Local lease continues independently. Global limit may briefly exceed by partition's remaining lease. Acceptable: bounded overage.
All regions request lease simultaneously	Central pool contention	Stagger lease requests. Each region requests at different offset within reconciliation period.
User abuse via rapid region switching	User tries to exploit reconciliation delay	Token leasing prevents this: total leases never exceed global limit. User can't get more than allocated across all regions combined.

Interview Cheat Sheet

Key points for global multi-region rate limiting

1. The fundamental trade-off · latency (regional) vs accuracy (central) — acknowledge this upfront
2. Token leasing · central allocates budgets, regions spend locally, reconcile periodically
3. Adaptive lease sizing · busy regions get larger leases, rebalanced every 5-10s
4. Bounded overrun · worst case = one reconciliation period of overage (acceptable trade-off)
5. Central coordinator HA · consensus-based (Raft), not single point of failure
6. Compare three approaches · central Redis (accurate/slow) vs static split (fast/wasteful) vs token leasing (best compromise)

System Design Case Study