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{Minimum Primary Shards} = \left\lceil \frac{166,666\text{ QPS}}{60,000\text{ ops/shard}} \right\rceil = 3\text{ Primary Shards (runs at } \approx 93\%\text{ CPU, no headroom)}$$

Three shards only just cover the peak, so we provision an AWS ElastiCache Redis Cluster with 6 primary shards and 6 read replicas (cache.r6g.xlarge, 26.32 GiB RAM per node). Six primaries give $360,000\text{ ops/sec}$ of capacity, i.e. $\approx 2.2\times$ headroom over the regional peak, and the local batch-leasing optimisation in Section 6.3 cuts Redis QPS by another order of magnitude, which is where the real safety margin comes from. Memory is not the constraint: the $14.4\text{ GB}$ working set fits on a single node.

---

3. Multi-Tier Defense Architecture & AWS Component Mapping

Synthesizing vector architecture diagram...

Follow a request from the top through three tiers, each with a different job. In "Tier 1: Edge Defense", WAF counts requests per IP and blocks floods (2,000 per 5 minutes) before they reach AWS compute. In "Tier 2: Gateway Defense", API Gateway applies the token bucket for that API key and route, and the Lambda authorizer validates the JWT and reads the tenant's plan tier. In "Tier 3: Distributed Microservice Middleware", Envoy runs an atomic Lua script (EVALSHA) on the Redis shard that holds that tenant's counters, so all instances share one count. Allowed requests reach the services, and throttled ones get 429 with Retry-After. Each tier stops a different abuse: raw volume, per-key overuse, and per-tenant business limits.

Data Flow Walkthrough

1. Multi-Tier Filtering: Traffic passes through Route 53 to CloudFront Edge PoPs. AWS WAF evaluates volumetric Layer 3/4 rules (e.g. 2,000 req/5min per IP) to shed DDoS attacks before reaching VPC resources.
2. Identity & Cost Resolution: API Gateway invokes an AWS Lambda Authorizer to validate JWT signatures, extract tenant tier (Free, Pro, Enterprise), and assign token costs based on route sensitivity (e.g. GET /users = 1 token; POST /transfers = 10 tokens).
3. Atomic Lua Token Bucket: Envoy middleware dispatches an atomic EVALSHA call to the targeted Redis shard. The Lua script evaluates fractional token accrual based on Redis master time (redis.call('TIME')), checks remaining tokens, deducts cost, and updates state in $< 1\text{ ms}$.
4. Resilient Circuit Breaking: If Redis is unresponsive ($> 5\text{ ms}$ timeout), a local circuit breaker immediately trips to FAIL_OPEN state, passing the request through with X-RateLimit-Status: Bypass to prevent rate limiter outages from causing total service blackout.

Concrete Step-by-Step Request Walkthrough: Tracing Multi-Tier Rate Limiting & Fail-Open Fallback

---

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;
}

Public HTTP Contract: Headers on Every Response & the 429Rejection

The gRPC check above is internal. What API clients see is a small, standardized header set (RFC 6585 for the status code; the IETF RateLimit header draft for the counters):

httpCopy
HTTP/1.1 429 Too Many Requests
Content-Type: application/problem+json
X-RateLimit-Limit: 500
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 6
Retry-After: 6

{
  "type": "https://hispeeddesign.com/errors/rate-limited",
  "title": "Rate limit exceeded",
  "detail": "Tenant org_acme exceeded 500 tokens/sec on POST /v1/transfers (cost 10).",
  "retry_after_seconds": 6
}

Drop vs. queue when the limit is exceeded: this design drops (returns 429) because the caller is a live HTTP client that can back off. For asynchronous producers (batch exports, webhooks) the alternative is to enqueue the excess into an SQS shadow queue and drain it at the sustained rate, which turns a hard limit into a soft one at the cost of delayed processing and unbounded queue growth under sustained abuse.

---

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]: Key TTL in seconds, e.g., 3600
--
-- The current time is NOT passed by the client. It is read from the Redis primary itself
-- (redis.call('TIME')) so every middleware node refills against one authoritative clock.
-- Note: this makes the script non-deterministic, which is safe because Redis >= 5 replicates
-- script *effects* (the resulting HSET/EXPIRE), not the script text, to replicas.

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

local t = redis.call("TIME")                       -- {seconds, microseconds}
local now = tonumber(t[1]) + tonumber(t[2]) / 1e6  -- float seconds with microsecond precision

-- 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: start full; the cost is deducted in step 3
    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("HSET", key, "tokens", tokens, "last_updated", last_updated)
redis.call("EXPIRE", key, ttl)

return { allowed, remaining, capacity, retry_after }

---