logo
CHEATSHEETSTOOLSABOUT中文

System Design - Distributed Rate Limiter

A Rate Limiter controls the rate of traffic sent by a client or consumer to a network service. In distributed systems, rate limiters protect backends from Denial-of-Service (DoS) attacks, brute-force attempts, cascading failures, and noisy-neighbor resource starvation.

For a deeper dive into traffic management principles, see Throttling and Backpressure.

1. Requirements & Scope

Functional Requirements

  • Limit Requests: Throttle requests that exceed configured quotas (e.g., 100 requests per minute per user ID or IP address).
  • Client Feedback: When a request is rejected, return HTTP status 429 Too Many Requests accompanied by standard informative headers:
    • X-Ratelimit-Limit: Total requests permitted in the current period.
    • X-Ratelimit-Remaining: Number of requests left in the period.
    • Retry-After: Number of seconds until the client can safely retry.
  • Configurable Rules: Support flexible limiting rules (per IP, per authenticated user, per API endpoint, or per tier).

Non-Functional Requirements

  • Ultra-Low Latency: The rate check sits directly in the critical request path and must add < 2ms overhead.
  • High Availability & Fault Tolerance: If the rate limiting cluster crashes or experiences network partitions, it must fail-open (allow traffic through) to prevent bringing down the entire service.
  • Distributed Accuracy: Limits must be accurately enforced across multiple stateless application instances.

2. Rate Limiting Algorithms Comparison

Choosing the right algorithm is the centerpiece of a rate limiter design interview:

Algorithm Pros Cons Best Use Case
Token Bucket Easy to implement; memory-efficient; allows short bursts of traffic. Tuning token generation rate and capacity can be tricky. General-purpose API gateways (Amazon, Stripe).
Leaking Bucket Enforces a constant output rate (smooth traffic flow). Bursty traffic can result in queue buffer bloat or dropped fresh requests. E-commerce checkout or queue processing.
Fixed Window Counter Very low memory footprint (integer counter per window). Traffic spikes at window boundaries can allow 2× the limit across boundary edges. Simple hourly/daily quotas.
Sliding Window Log 100% accurate; no boundary burst anomalies. High memory consumption (stores timestamps for every request). Low-volume, high-security endpoints (e.g. login).
Sliding Window Counter Low memory footprint; smooths boundary bursts with rolling approximation. Slight mathematical approximation (~0.05% error). Production standard for high-scale distributed APIs.

The Boundary Problem of Fixed Window

If an endpoint permits 100 requests per minute from 12:00:00 to 12:01:00:

  • A user sends 100 requests at 12:00:59.
  • The user sends another 100 requests at 12:01:01.
  • Both windows pass, but 200 requests were serviced within a 2-second span!

Sliding Window Counter Solution

Instead of rigid intervals, calculate a rolling estimate: Requests in Window = Requests in Current Window + ( Requests in Previous Window × (1 - Overlap Fraction) ) If the current window is 30% through, weight the previous window count by 70%. If the sum exceeds the threshold, drop the request.

3. High-Level Architecture

[ Client Request ]
        │
        ▼
[ Global Load Balancer ]
        │
        ▼
[ API Gateway / Reverse Proxy (Envoy / NGINX) ]
        │
        ├───► [ Rate Limiter Middleware ]
        │            │
        │            ▼
        │     [ Centralized Cache: Redis Cluster ]
        │     (Atomic Lua scripts executing Sliding Window Counter)
        │
        ▼ (If Allowed)
[ Backend Microservices ]

4. Distributed Coordination & Race Conditions

In a multi-server setup, multiple concurrent requests from the same user might hit different API Gateway instances simultaneously.

The Race Condition

Thread 1 (Instance A) ───► Reads counter = 99
Thread 2 (Instance B) ───► Reads counter = 99
Both check: 99 < 100 -> Both ALLOW the request!
Both write back: counter = 100 (Actual count should have been 101, violating limit)

Solution: Redis + Atomic Lua Script

To guarantee atomicity without expensive distributed locks, execute the increment, timestamp comparison, and expiration logic inside an atomic Redis Lua script:

-- KEYS[1]: rate limit key (e.g., ratelimit:user123:endpoint)
-- ARGV[1]: current timestamp
-- ARGV[2]: window duration in seconds
-- ARGV[3]: max allowed requests

local current_time = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])
local clear_before = current_time - window

-- Remove old entries outside the rolling window
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, clear_before)

-- Count remaining requests in current window
local current_requests = redis.call('ZCARD', KEYS[1])

if current_requests < limit then
    -- Add current request timestamp
    redis.call('ZADD', KEYS[1], current_time, current_time)
    redis.call('EXPIRE', KEYS[1], window)
    return 1 -- Allowed
else
    return 0 -- Throttled
end

5. Deployment Options: Centralized vs. Decentralized

Option A: Centralized Redis Cluster

  • Mechanism: Every API Gateway node queries a central Redis cluster for each incoming request.
  • Trade-off: Consistent state across the globe, but adds 1-2ms network round-trip latency and creates a central point of dependency.

Option B: Local Token Bucket with Asynchronous Sync (Hybrid)

  • Mechanism: Each gateway node keeps an in-memory token bucket and periodically syncs usage deltas to a central store or mesh daemon (like Envoy's global rate limit service).
  • Trade-off: Near zero latency on local hits; handles temporary Redis outages gracefully. May permit slight burst leakage across nodes during convergence intervals.

6. Resilience & Edge Cases

  1. Fail-Open Strategy: If the Redis cluster is unreachable or timing out, the rate limiter should log an alert and allow the request through rather than rejecting valid user traffic.
  2. Multi-Tier Rules:
    • Layer 1 (IP address): Blocks rogue crawlers and DDoS bots at the edge/WAF.
    • Layer 2 (User ID / API Token): Enforces paid customer subscription quotas.
    • Layer 3 (Service-Level): Protects downstream shared databases from being overwhelmed.
  3. Client-Side Throttling: Well-behaved clients should inspect Retry-After headers and implement exponential backoff with jitter to avoid hammering the service repeatedly upon rejection.
Loading...