Design a Distributed Rate Limiter

1. Problem Statement & Scope Clarification

System Mission

Design a distributed, highly available, ultra-low-latency Rate Limiter service (similar to AWS WAF, Cloudflare Rate Limiting, and Stripe's multi-tier throttling gateway) capable of protecting API infrastructure from volumetric DDoS attacks, credential stuffing, scraping, and downstream database resource starvation across multi-tenant microservices.

Functional Requirements

1. Decision Latency & Check API (isAllowed): Evaluate in $< 2\text{ ms}$ ($P99$) whether an incoming request is permitted based on client identity, endpoint, and token weight.
2. Multi-Dimensional Rule Evaluation: Support hierarchical throttling policies:
   • Layer 3/4 & 7 IP-based rate limiting (volumetric perimeter defense).
   • Per-Tenant / Per-User-ID limits (tiered SLA enforcement, e.g., Free vs Enterprise tier).
   • Per-Route / Per-Method cost weighting (e.g., GET /users cost = 1; POST /transfers/export cost = 10).
3. Standardized HTTP 429 Compliance: Return standard headers X-RateLimit-Limit, X-RateLimit-Remaining, and Retry-After (in seconds).
4. Dynamic Rule Reloading: Allow security administrators to update rate limits in real time without restarting middleware clusters or flushing counters.

Non-Functional Requirements (SLAs & SLOs)

• High Availability: $99.999\%$ uptime SLA across multi-AZ AWS regions.
• Fail-Open Policy (FAIL_OPEN): If the rate-limiting tier experiences complete network isolation or Redis cluster failure, user traffic MUST be allowed through to prevent self-inflicted global outages.
• Low Decision Latency: $P50 < 0.5\text{ ms}$, $P99 < 2.0\text{ ms}$.
• Memory Footprint: Strict $O(1)$ memory per active tracking entity.

2. Capacity & Scale Estimation (Back-of-the-Envelope Math)

Traffic & Generation Scale

• Global Peak Request Volume: $500,000\text{ Requests/sec}$ ($500\text{k QPS}$).
• Active Tracked Entities (Daily Active Keys): $50,000,000$ unique client keys (IP, API_Key, UserID).
• Peak Throughput per Region: Assuming 3 active AWS regions, peak per-region traffic $= 166,666\text{ QPS}$.

Memory Footprint Derivation

Using the Token Bucket algorithm, each client tracking record in Redis requires:

• Key name: rl:{usr_998124}:/api/v1/orders $\approx 32\text{ bytes}$
• Hash fields (tokens as float64, last_refreshed as int64): $\approx 16\text{ bytes}$
• Redis Hash overhead (dict entry, jemalloc alignment): $\approx 48\text{ bytes}$
• Total per Key: $\approx 96\text{ bytes}$.

$\text{Total Memory Footprint} = 50,000,000\text{ keys} \times 96\text{ bytes} \approx \mathbf{4.8\text{ GB RAM}}$ With a Redis cluster replication factor of 2 (Primary + Replica) and a $50\%$ memory buffer for key eviction overhead: $\text{Cluster Memory Required} = 4.8\text{ GB} \times 2 \times 1.5 = \mathbf{14.4\text{ GB RAM}}$

Redis Cluster Node Sizing

A single Redis thread handles $\approx 60,000 - 80,000\text{ EVALSHA ops/sec}$. $\text{Required Primary Shards} = \frac{166,666\text{ QPS}}{60,000\text{ ops/shard}} \approx 3\text{ Primary Shards}$ We provision an AWS ElastiCache Redis Cluster with 3 primary shards and 3 read replicas (cache.r6g.xlarge with 26.32 GiB RAM per node), providing $10\times$ headroom for traffic spikes.

3. Multi-Tier Defense Architecture & AWS Component Mapping

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

4. API Interface Design & Wire Protocol

Rate Limiter Internal Check Protocol (ratelimit.proto)

protobufCopy
syntax = "proto3";

package hispeeddesign.ratelimit.v1;

service RateLimiterService {
  // Evaluates rate limit status for a given key and token cost
  rpc CheckRateLimit (RateLimitRequest) returns (RateLimitResponse);
}

message RateLimitRequest {
  string tenant_id = 1;        // e.g. "org_apple"
  string client_identifier = 2;// e.g. "usr_9981" or "ip_192.0.2.1"
  string route = 3;            // e.g. "/v1/transfers"
  int32 token_cost = 4;        // Default: 1
}

message RateLimitResponse {
  enum Decision {
    ALLOWED = 0;
    THROTTLED = 1;
    FAILED_OPEN = 2;           // Emitted if Redis was unreachable
  }
  Decision decision = 1;
  int64 limit = 2;             // Maximum bucket capacity
  int64 remaining = 3;         // Remaining available tokens
  int64 reset_after_seconds = 4; // Seconds until bucket fully refills
  string violation_reason = 5;
}

5. Storage Engine & Atomic Lua Implementation

To prevent race conditions without acquiring distributed locks, token bucket state is evaluated and mutated atomically inside Redis using a single Lua script.

Production Token Bucket Lua Script (token_bucket.lua)

luaCopy
-- KEYS[1]: Rate limit key, e.g., "rl:{tenant_123}:/api/v1/orders"
-- ARGV[1]: Max bucket capacity (burst limit), e.g., 100
-- ARGV[2]: Refill rate per second (sustained limit), e.g., 10
-- ARGV[3]: Token cost for this request, e.g., 1
-- ARGV[4]: Current timestamp (Unix epoch in seconds with microsecond float), e.g., 1767225600.125
-- ARGV[5]: Key TTL in seconds, e.g., 3600

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

-- 1. Retrieve existing bucket state
local data = redis.call("HMGET", key, "tokens", "last_updated")
local tokens = tonumber(data[1])
local last_updated = tonumber(data[2])

if tokens == nil then
    -- Bucket does not exist yet: initialize to full capacity minus current cost
    tokens = capacity
    last_updated = now
else
    -- 2. Compute newly accumulated tokens based on elapsed time
    local elapsed = math.max(0, now - last_updated)
    tokens = math.min(capacity, tokens + (elapsed * refill_rate))
    last_updated = now
end

-- 3. Evaluate request allowance
local allowed = 0
local remaining = tokens
local retry_after = 0

if tokens >= cost then
    allowed = 1
    tokens = tokens - cost
    remaining = math.floor(tokens)
else
    allowed = 0
    remaining = 0
    -- Time required to accumulate enough tokens for this request cost
    retry_after = math.ceil((cost - tokens) / refill_rate)
end

-- 4. Persist updated bucket state back to Redis atomically
redis.call("HMSET", key, "tokens", tokens, "last_updated", last_updated)
redis.call("EXPIRE", key, ttl)

return { allowed, remaining, capacity, retry_after }