Design a Distributed Rate Limiter

A Distributed Rate Limiter throttles excessive client requests to prevent cascading system outages, mitigate DDoS/brute-force attacks, and enforce tiered SaaS subscription billing quotas.

Functional Requirements

1. Multi-Dimension Throttling: Limit requests based on IP address, authenticated user_id, API Key (tenant_id), or specific endpoints (e.g., login vs search).
2. Clear Feedback Headers: When rate limits are reached, reject requests with HTTP 429 Too Many Requests and include standard headers:
   • X-RateLimit-Limit: Maximum requests allowed per window.
   • X-RateLimit-Remaining: Number of remaining tokens in current window.
   • X-RateLimit-Reset: Unix epoch timestamp when limit refills.
   • Retry-After: Seconds until the client can retry.
3. Configurable Rules Engine: Support dynamic updates to rate-limiting rules without restarting services.

Non-Functional Requirements

• Sub-Millisecond Overhead: Rate-check latency must remain < 2 ms (p99) so it does not degrade overall API response time.
• Distributed Accuracy & Concurrency Safety: Zero race conditions across thousands of parallel web server nodes.
• High Fault Tolerance (Fail-Open Policy): If the rate-limiting Redis cluster fails or experiences a network partition, the system must degrade gracefully (fail-open or local in-memory estimate) rather than taking down all user traffic.

Choosing the appropriate rate-limiting algorithm depends on burst tolerance, memory constraints, and computational complexity:

In a distributed environment with 100 API gateway instances, a naive GET -> calculate -> SET pattern causes severe race conditions:

code
Copy
Server A: GET tokens (reads 1)
Server B: GET tokens (reads 1)
Server A: tokens = 1 - 1 = 0 -> SET tokens 0 (Request Allowed)
Server B: tokens = 1 - 1 = 0 -> SET tokens 0 (Request Allowed - Race Condition!)

The Winning Solution: Atomic Redis Lua Script

Redis executes Lua scripts in a single-threaded atomic transaction, guaranteeing no other command interleaves during execution.

lua
Copy
-- KEYS[1]: Rate limit key (e.g. "rate:user_981:api")
-- ARGV[1]: Bucket capacity (e.g. 100)
-- ARGV[2]: Refill rate per second (e.g. 10)
-- ARGV[3]: Current timestamp (Unix epoch seconds with ms)
-- ARGV[4]: Requested tokens (e.g. 1)

local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

local data = redis.call("HMGET", key, "tokens", "last_updated")
local tokens = tonumber(data[1])
local last_updated = tonumber(data[2])

if tokens == nil then
    tokens = capacity
    last_updated = now
else
    local elapsed = math.max(0, now - last_updated)
    tokens = math.min(capacity, tokens + (elapsed * refill_rate))
    last_updated = now
end

if tokens >= requested then
    tokens = tokens - requested
    redis.call("HMSET", key, "tokens", tokens, "last_updated", last_updated)
    redis.call("EXPIRE", key, math.ceil(capacity / refill_rate) * 2)
    return {1, math.floor(tokens)} -- Allowed, remaining tokens
else
    redis.call("HMSET", key, "tokens", tokens, "last_updated", last_updated)
    return {0, math.floor(tokens)} -- Rejected (HTTP 429)
end

Where to Place the Rate Limiter?

1. Edge CDN (Cloudflare / Fastly): Blocks volumetric DDoS and Layer 7 scraping before traffic enters cloud infrastructure.
2. API Gateway (Envoy / Kong / Zuul): Enforces fine-grained user authentication limits, tenant quotas, and tier enforcement (Free vs Enterprise).
3. Application Middleware: Enforces internal business rate limits (e.g., maximum 3 password reset attempts per hour).

Sharding & Scaling the Redis Layer

• Consistent Hash Partitioning: Rate limit keys ("rate_limit:{user_id}") are sharded across a Redis Cluster using 16,384 hash slots.
• Hash Tags: Use Redis hash tags (e.g., "rate_limit:{{tenant_123}}:resource") to ensure all limits for a specific tenant reside on the same Redis shard for batch script execution.

Fail-Open vs Fail-Closed Policy

• Mission-Critical Endpoints (e.g., /checkout, /login): If Redis becomes unreachable, Fail-Open with a local in-memory rate limiter (e.g., Token Bucket in local RAM per Envoy worker) to prevent catastrophic customer-facing downtime.
• High-Risk Financial Endpoints (e.g., /transfer_money): Fail-Closed to prevent double-spending attacks.

Multi-Region WAN Synchronization

Synchronizing Redis writes across cross-region datacenters (US-East to EU-West) introduces 100 ms WAN latency.

• Regional Token Buckets: Allocate regional sub-quotas (e.g., US gets 60\%, EU gets 40\% of global quota).
• Asynchronous Batch Synchronization: Edge servers track local token consumption and flush deltas to global Redis in batches every 100 ms.