Distributed Rate Limiting at Scale: Token Bucket vs Leaky Bucket (Redis Lua Scripts & Concurrency)

1.1 Continuous-Time Dynamic Invariants: Token Bucket vs. Leaky Bucket

Continuous-time algorithms maintain an internal numerical accumulator that evolves dynamically as a function of elapsed physical time $\Delta t = t_{\text{now}} - t_{\text{last}}$. Instead of requiring asynchronous background timer threads to increment or decrement state counters at discrete clock intervals—an anti-pattern that creates massive lock contention and $O(K)$ background CPU load for $K$ active keys—modern production engines evaluate state lazily on request arrival.

The Token Bucket Invariant (Traffic Metering with Burst Allowance)

The Token Bucket algorithm parameterizes traffic using a capacity $C$ and a refill rate $r$. The system allows short bursts of up to $C$ requests arriving at instantaneous rate $\lambda \to \infty$, while bounding the sustained long-term arrival rate to $r$. When a request with weight $\text{cost}$ arrives at physical timestamp $t$, the gateway calculates the replenished token volume since the previous request timestamp $t_{\text{last}}$ and evaluates admission via the following continuous-time recurrence relation:

The Leaky Bucket: Traffic Shaping Queue vs. GCRA Traffic Metering

The term Leaky Bucket denotes two distinct systems engineering concepts that are frequently conflated:

1. Asynchronous Traffic Shaping FIFO Buffer: Incoming requests enter a bounded physical queue of capacity $C$. A background worker pool drains the queue and forwards requests downstream to POST /v1/payments/checkout at a strictly constant rate $r$. If an inbound request arrives when the queue depth $|Q| = C$, the request is dropped immediately. While this guarantees zero downstream jitter, it introduces queueing delay $\tau_{\text{delay}} = \frac{|Q|}{r}$, making it unsuitable for synchronous, low-latency API paths.
2. Traffic Metering via Generic Cell Rate Algorithm (GCRA): Standardized in ATM network specifications (ITU-T I.371), GCRA is the continuous-time dual of the Token Bucket without queueing buffers. Instead of tracking token credits, GCRA tracks time debt using a single scalar timestamp known as the Theoretical Arrival Time ($\text{TAT}$).

flowchart TD
    subgraph TB["Token Bucket (Lazy Credit Accumulation)"]
        A1["Request Arrives at t_now (cost)"] --> A2["Compute Delta t = t_now - t_last"]
        A2 --> A3["tokens = min(C, t_prev + r * Delta t)"]
        A3 --> A4{"tokens >= cost?"}
        A4 -- "Yes (Admitted)" --> A5["Persist tokens = tokens - cost
t_last = t_now
Forward to /v1/payments/checkout"]
        A4 -- "No (Exhausted)" --> A6["Drop / HTTP 429
State Unchanged"]
    end

    subgraph LB["Leaky Bucket: Traffic Shaper (FIFO Queue)"]
        B1["Request Arrives"] --> B2{"Queue Depth < C?"}
        B2 -- "Yes" --> B3["Push to FIFO Queue
Queue Depth += 1"]
        B3 --> B4["Async Drain Worker: Pop at constant rate r
Dispatch to Downstream Engine"]
        B2 -- "No (Overflow)" --> B5["Drop / HTTP 429"]
    end

    subgraph GCRA["Leaky Bucket: GCRA (Time Debt Metering)"]
        C1["Request Arrives at t_now"] --> C2["TAT_candidate = max(t_now, TAT_prev) + (1 / r)"]
        C2 --> C3{"TAT_candidate - t_now <= (C / r)?"}
        C3 -- "Yes (Conforming)" --> C4["Persist TAT = TAT_candidate
Forward to /v1/payments/checkout"]
        C3 -- "No (Non-Conforming)" --> C5["Drop / HTTP 429
TAT Unchanged"]
    end
    

1.2 Discrete & Window-Based Approximations

1. Fixed Window Counter & Proof of the $2\times$ Burst Vulnerability

The Fixed Window Counter quantizes time into discrete epoch buckets $W_k = \lfloor t / T_w \rfloor$. A single integer counter $N(W_k)$ is incremented for each arrival. While trivial to implement with atomic increments, Fixed Window rate limiters suffer from an inherent boundary vulnerability that permits up to $2\times$ the configured SLA limit to hit downstream services across window boundaries.

2. Sliding Window Log ($O(N)$ Spatial Complexity)

The Sliding Window Log eliminates boundary spikes by persisting the exact timestamp of every accepted request in a sorted set $S = \{t_1, t_2, \dots, t_k\}$. Upon an arrival at $t_{\text{now}}$, entries older than $(t_{\text{now}} - T_w)$ are evicted, and $|S| < C$ is verified. However, for $10,000\text{ req/min}$, maintaining timestamps in memory requires $\approx 80\text{ KB} - 1.2\text{ MB}$ per active tenant key, causing memory exhaustion under millions of active users.

3. Sliding Window Counter (Cloudflare Weighted Average Model)

The Sliding Window Counter achieves sub-millisecond precision with strict $O(1)$ memory by computing a weighted sliding average across only two consecutive fixed windows: the previous window count $W_{\text{prev}}$ and the current window count $W_{\text{curr}}$.

1.3 Algorithmic Complexity & Systems Trade-off Matrix

While the continuous-time Token Bucket and GCRA formulations provide exact, low-overhead mathematical models on a single execution thread, implementing them across distributed clusters requires translating these invariants into concurrent physical memory engines. In the next section, we examine how concurrency anomalies—specifically Time-of-Check to Time-of-Use (TOCTOU) race conditions—corrupt state, and how to implement zero-race-condition atomicity via Redis Lua scripts.

2.1 The Concurrency Hazard: Distributed Race Conditions in Naive Implementations

A standard naive implementation of rate limiting in distributed architectures relies on discrete Redis read and write operations. The gateway worker executes a check-then-act sequence: it fetches the current token count via GET, evaluates availability in application runtime memory, computes the decremented value, and writes the state back to Redis via SET.

This pattern constitutes a classic Time-of-Check to Time-of-Use (TOCTOU) vulnerability. In a distributed deployment of the api-gateway-auth service protecting the POST /v1/payments/checkout endpoint, network latency and asynchronous thread scheduling create an execution window during which multiple gateway instances read identical state snapshots before any single instance can persist its mutation.

Consider an incoming burst of 10 concurrent HTTP requests from enterprise tenant cust_ent_9942 (IP: 198.51.100.42, configured capacity $C = 1000$, refill rate $r = 16.667\text{ req/s}$) arriving at a moment when the Redis state holds exactly $\text{tokens} = 1.0$. The requests are distributed across three gateway pods:

• Pod 1 (api-gateway-auth-4x2kl): Receives Requests 1, 2, 3, 4.
• Pod 2 (api-gateway-auth-9m8wq): Receives Requests 5, 6, 7.
• Pod 3 (api-gateway-auth-zz11a): Receives Requests 8, 9, 10.

Due to network round-trip time ($R_{\text{RTT}} \approx 0.5\text{ms} \text{ to } 1.5\text{ms}$), all three pods issue parallel GET commands to Redis. The single-threaded Redis engine executes these read commands sequentially, returning "1.0" to all three pods. Each pod independently verifies that $\text{tokens} \ge 1.0$, marks its assigned requests as approved, forwards all 10 requests upstream to the checkout service, and asynchronously issues SET tokens 0.0.

Outcome: 10 requests pass the gateway filter when only 1 request was authorized by policy. The tenant exceeds their allocated throughput burst limit by $900\%$, resulting in downstream payment gateway socket pool exhaustion.

sequenceDiagram
    autonumber
    participant P1 as Gateway Pod 1
(api-gateway-auth-4x2kl)
    participant P2 as Gateway Pod 2
(api-gateway-auth-9m8wq)
    participant P3 as Gateway Pod 3
(api-gateway-auth-zz11a)
    participant R as Redis Master
(aeEventLoop)
    participant DB as Upstream Payment Service
(POST /v1/payments/checkout)

    Note over P1,P3: Tenant: cust_ent_9942 | Bucket State: tokens=1.0, cost=1.0
    P1->>+R: GET ratelimit:cust_ent_9942:checkout:tb:tokens (t=0.0ms)
    P2->>+R: GET ratelimit:cust_ent_9942:checkout:tb:tokens (t=0.1ms)
    P3->>+R: GET ratelimit:cust_ent_9942:checkout:tb:tokens (t=0.2ms)
    
    R-->>-P1: Value: "1.0" (Processed at t=0.3ms)
    R-->>-P2: Value: "1.0" (Processed at t=0.4ms)
    R-->>-P3: Value: "1.0" (Processed at t=0.5ms)

    Note over P1: Local Eval: 1.0 >= 1.0 -> ALLOW
New State: 0.0
    Note over P2: Local Eval: 1.0 >= 1.0 -> ALLOW
New State: 0.0
    Note over P3: Local Eval: 1.0 >= 1.0 -> ALLOW
New State: 0.0

    P1->>DB: Forward Req 1..4 (HTTP 200 Initiated)
    P2->>DB: Forward Req 5..7 (HTTP 200 Initiated)
    P3->>DB: Forward Req 8..10 (HTTP 200 Initiated)

    P1->>+R: SET ratelimit:cust_ent_9942:checkout:tb:tokens 0.0 (t=1.2ms)
    P2->>+R: SET ratelimit:cust_ent_9942:checkout:tb:tokens 0.0 (t=1.3ms)
    P3->>+R: SET ratelimit:cust_ent_9942:checkout:tb:tokens 0.0 (t=1.4ms)
    R-->>-P1: OK
    R-->>-P2: OK
    R-->>-P3: OK
    
    Note over DB: CRITICAL FAILURE: 10 concurrent requests processed.
9 unauthorized requests bypass rate limiter.
    

• Optimistic Locking (WATCH / MULTI / EXEC): When multiple gateway instances monitor the rate limit key with WATCH, only the first transaction commit succeeds; the remaining $N-1$ instances fail with a null transaction reply. Under a flash crowd of 5,000 req/s, the resulting CAS abort rate exceeds $98\%$, triggering client-side retry storms.
• Pessimistic Distributed Locks (Redlock / Mutex): Acquiring an explicit distributed lock per incoming API request introduces a minimum of two to four network round-trips ($3\text{ms} \text{ to } 12\text{ms}$ latency) onto the ingress critical path, collapsing gateway throughput.

2.2 Deterministic Atomic Lua Scripts: Token Bucket & Sliding Window Counter

To eliminate distributed TOCTOU race conditions without locking overhead, state evaluation and mutation must execute as a single, indivisible transaction directly inside the Redis engine.

2.2.1 The Single-Threaded Execution Model & EVALSHA

Redis executes commands and embedded Lua scripts within a single-threaded event loop (aeEventLoop backed by epoll or kqueue). When a Lua script executes, Redis guarantees strict linearizability and stop-the-world isolation: no other client command, pipeline, or secondary script can interleave.

Production architectures decouple script registration from execution using the SCRIPT LOAD and EVALSHA protocol, reducing the network payload to a 20-byte SHA1 digest and saving CPU cycles on syntax parsing.

2.2.2 Cluster-Authoritative Timestamps vs. Wall-Clock Skew

A critical failure mode in distributed rate limiters is passing the client's local system timestamp into the rate limiter. Gateway pods running across different nodes suffer from asymmetric clock drift caused by NTP adjustments and hypervisor virtualization pauses. To guarantee mathematical determinism, rate limiting scripts must derive time strictly from the Redis server's internal clock via redis.call('TIME').

2.2.3 Redis Cluster Sharding & Hash Tags

In a distributed Redis Cluster topology spanning multiple master shards, data is partitioned across 16,384 logical hash slots using the CRC16 algorithm:

2.2.4 Production Script 1: Continuous-Time Token Bucket (Redis Hash)

-- ==============================================================================
-- PRODUCTION REDIS LUA SCRIPT: CONTINUOUS-TIME TOKEN BUCKET
-- Key Schema: KEYS[1] -> ratelimit:{cust_ent_9942}:/v1/payments/checkout:tb
-- Arguments:  ARGV[1] -> rate (tokens/sec), ARGV[2] -> capacity C, ARGV[3] -> cost
-- Returns:    [allowed (1|0), remaining_tokens, reset_time_sec, retry_after_sec]
-- ==============================================================================
local key = KEYS[1]
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local cost = tonumber(ARGV[3]) or 1.0

-- 1. Fetch cluster-authoritative timestamp directly from Redis server
local time_res = redis.call('TIME')
local now = tonumber(time_res[1]) + (tonumber(time_res[2]) / 1000000.0)

-- 2. Retrieve current bucket state from Hash
local data = redis.call('HMGET', key, 'tokens', 'last_updated')
local current_tokens
local last_updated

if not data[1] then
    -- Cold start / First request: initialize bucket to full capacity
    current_tokens = capacity
    last_updated = now
else
    current_tokens = tonumber(data[1])
    last_updated = tonumber(data[2])
end

-- 3. Calculate continuous-time replenishment with non-negative clamp
local delta = math.max(0.0, now - last_updated)
local tokens = math.min(capacity, current_tokens + (delta * rate))

-- 4. Evaluate admission decision
local allowed = 0
local remaining = 0
local reset_time = 0
local retry_after = 0

if tokens >= cost then
    allowed = 1
    tokens = tokens - cost
    remaining = tokens
    last_updated = now
    retry_after = 0
    reset_time = math.ceil((capacity - tokens) / rate)

    -- Persist updated state atomically
    redis.call('HMSET', key, 'tokens', tostring(tokens), 'last_updated', tostring(last_updated))

    -- Set dynamic TTL: time to full refill + 60s buffer
    local dynamic_ttl = math.max(60, math.ceil((capacity - tokens) / rate) + 60)
    redis.call('EXPIRE', key, dynamic_ttl)
else
    allowed = 0
    remaining = tokens
    redis.call('HSET', key, 'tokens', tostring(tokens))

    local deficit = cost - tokens
    retry_after = math.ceil(deficit / rate)
    reset_time = math.ceil((capacity - tokens) / rate)
end

return {
    allowed,
    math.floor(remaining),
    reset_time,
    retry_after
}

2.2.5 Production Script 2: Sliding Window Counter (Dual EXPIRE-Backed String Keys)

-- ==============================================================================
-- PRODUCTION REDIS LUA SCRIPT: SLIDING WINDOW COUNTER (DUAL-KEY EXPIRE)
-- Key Schema: KEYS[1] -> ...:swc:curr, KEYS[2] -> ...:swc:prev
-- Arguments:  ARGV[1] -> limit, ARGV[2] -> window_size (sec), ARGV[3] -> cost
-- Returns:    [allowed (1|0), remaining_quota, reset_time_sec, retry_after_sec]
-- ==============================================================================
local curr_key = KEYS[1]
local prev_key = KEYS[2]
local limit = tonumber(ARGV[1])
local window_size = tonumber(ARGV[2])
local cost = tonumber(ARGV[3]) or 1

-- 1. Obtain cluster-authoritative timestamp
local time_res = redis.call('TIME')
local now_sec = tonumber(time_res[1])
local now_usec = tonumber(time_res[2])
local now = now_sec + (now_usec / 1000000.0)

-- 2. Read counter states from Redis strings (defaulting to 0 on cold keys)
local count_curr = tonumber(redis.call('GET', curr_key) or "0")
local count_prev = tonumber(redis.call('GET', prev_key) or "0")

-- 3. Calculate sliding window weight
local current_offset = now % window_size
local weight_prev = (window_size - current_offset) / window_size

-- 4. Calculate effective count: C_eff = count_prev * weight + count_curr
local estimated_count = (count_prev * weight_prev) + count_curr

local allowed = 0
local remaining = 0
local reset_time = math.ceil(window_size - current_offset)
local retry_after = 0

if (estimated_count + cost) <= limit then
    allowed = 1
    local new_curr = redis.call('INCRBY', curr_key, cost)
    redis.call('EXPIRE', curr_key, math.ceil(window_size * 2))

    local updated_estimated = (count_prev * weight_prev) + new_curr
    remaining = math.max(0, math.floor(limit - updated_estimated))
    retry_after = 0
else
    allowed = 0
    remaining = math.max(0, math.floor(limit - estimated_count))
    retry_after = math.max(1, reset_time)
end

return {
    allowed,
    remaining,
    reset_time,
    retry_after
}

2.2.6 Return Array Contract & HTTP Response Header Mapping

3.1 Jemalloc Memory Layout & Byte-Level Footprint Analysis

Redis does not allocate raw bytes directly from the Linux kernel for individual data structures. Instead, it relies on jemalloc, which groups allocations into predefined power-of-two size classes (bins). Every key-value pair stored in Redis incurs fixed overhead originating from internal Redis C structures:

• Dictionary Entry (dictEntry): 3 pointers (key, val, next) = $24\text{ bytes} \to$ jemalloc 32-byte bin.
• Redis Object Header (robj): 16-byte struct (type:4b, encoding:4b, lru:24b, refcount:4B, ptr:8B) $\to$ jemalloc 16-byte bin.
• Simple Dynamic String (SDS) Header: For short strings ($< 256\text{ B}$), sdshdr8 adds 4 bytes of metadata and null-terminator.

Memory Footprint Scaling Across Tenant Sizes

3.2 Throughput & Latency Micro-Benchmarks: Redis Lua vs In-Memory CAS

Rate limiting sits directly on the ingress hot-path. We benchmarked three distributed execution models against local in-memory synchronization under a sustained 100,000 QPS client workload across 4 client nodes hitting AWS EC2 c6i.4xlarge Redis instances:

Why a Single Redis Core Caps at ~45,000 EVALSHA ops/sec

While bare Redis INCR reaches $\sim 110,000\text{ ops/sec}$, a Token Bucket EVALSHA caps out at $\sim 45,000\text{ ops/sec}$ due to:

1. Lua VM Bridging: Passing C arguments to lua_State, converting SDS to Lua strings, and parsing return arrays consumes $\sim 60\%$ of CPU cycles.
2. Kernel Syscall Bottlenecks: 45,000 non-pipelined TCP round-trips generate 45,000 read() / write() syscalls per second.
3. Single-Threaded Queueing Cliff: As traffic approaches the $45,000\text{ QPS}$ limit, Little's Law ($L = \lambda W$) causes queue buildup, spiking p99 latency from $1.64\text{ ms}$ to $18.4\text{ ms}$.

4.1 Distributed Gateway Rate Limiting Architecture

Every incoming payment checkout request is intercepted at the middleware layer. The gateway extracts the authenticated tenant identity (such as enterprise tenant cust_ent_9942 configured for 1,000 req/min, or free tier tenant cust_free_1018 restricted to 10 req/min). The gateway queries Redis via EVALSHA using a preloaded Lua script. If the Redis cluster experiences network partitions or timeout degradation (>50ms), a local in-memory Token Bucket fallback activates immediately to protect uptime while shielding downstream payment processors.

flowchart TD
    Client["Client Request (POST /v1/payments/checkout)"] --> GW["API Gateway Middleware (api-gateway-auth)"]
    GW --> Ext["Extract Tenant ID (e.g., cust_ent_9942)"]
    Ext --> CB{"Circuit Breaker (50ms Timeout)"}
    
    CB -- "Redis Healthy (State: CLOSED)" --> EVALSHA["Redis Cluster: EVALSHA (Token Bucket Lua)"]
    EVALSHA -- "Allowed: 1" --> Success["Upstream Checkout Handler (200 OK)"]
    EVALSHA -- "Allowed: 0" --> Reject429["Reject with 429 Too Many Requests"]
    EVALSHA -- "NOSCRIPT Error" --> Reload["SCRIPT LOAD & Retry EVALSHA"]
    Reload --> EVALSHA
    
    CB -- "Redis Timeout / Error (State: OPEN)" --> LocalFB["In-Memory Token Bucket Fallback"]
    LocalFB -- "Local Allowed: 1" --> FallbackSuccess["Upstream Handler + Header (X-RateLimit-Fallback: 1)"]
    LocalFB -- "Local Allowed: 0" --> Reject429
    
    Success --> Headers["Inject X-RateLimit-* & Retry-After Headers"]
    FallbackSuccess --> Headers
    Reject429 --> Headers
    

4.2 Production Multi-Language Implementations

"""
Production-Grade Distributed Rate Limiter Middleware
Runtime: Python 3.10+ (AsyncIO + redis-py + FastAPI)
Protects: POST /v1/payments/checkout
"""
from __future__ import annotations
import asyncio
import hashlib
import logging
import math
import time
from dataclasses import dataclass
from typing import Callable, Dict, Final, Optional, Tuple

import redis.asyncio as aioredis
from fastapi import FastAPI, HTTPException, Request, Response, status
from fastapi.responses import JSONResponse
from redis.exceptions import ConnectionError as RedisConnectionError
from redis.exceptions import NoScriptError, RedisError, TimeoutError
from starlette.middleware.base import BaseHTTPMiddleware

logger = logging.getLogger("api_gateway.rate_limiter")
logger.setLevel(logging.INFO)

TOKEN_BUCKET_LUA_SCRIPT: Final[str] = """
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 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

local allowed = 0
local retry_after = 0

if tokens >= cost then
    allowed = 1
    tokens = tokens - cost
else
    allowed = 0
    local deficit = cost - tokens
    retry_after = math.ceil(deficit / refill_rate)
end

local ttl = math.max(60, math.ceil((capacity / refill_rate) * 2))
redis.call("HMSET", key, "tokens", tokens, "last_updated", last_updated)
redis.call("EXPIRE", key, ttl)

local missing_tokens = math.max(0, capacity - tokens)
local reset_seconds = math.ceil(missing_tokens / refill_rate)
local reset_epoch = math.floor(now + reset_seconds)

return {allowed, math.floor(tokens), reset_epoch, retry_after}
"""

@dataclass(frozen=True)
class TenantTier:
    tenant_id: str
    capacity: int
    refill_rate_per_sec: float

@dataclass(frozen=True)
class RateLimitResult:
    allowed: bool
    remaining_tokens: int
    reset_epoch: int
    retry_after: int
    is_fallback: bool

class LocalMemoryTokenBucket:
    """Thread-safe and async-safe local token bucket fallback during Redis outages."""
    def __init__(self) -> None:
        self._buckets: Dict[str, Tuple[float, float]] = {}
        self._lock = asyncio.Lock()

    async def consume(self, key: str, capacity: int, refill_rate: float, cost: int) -> RateLimitResult:
        now = time.monotonic()
        wall_now = time.time()
        async with self._lock:
            if key not in self._buckets:
                tokens = float(capacity)
                last_refill = now
            else:
                tokens, last_refill = self._buckets[key]
                elapsed = max(0.0, now - last_refill)
                tokens = min(float(capacity), tokens + (elapsed * refill_rate))
                last_refill = now

            if tokens >= cost:
                tokens -= cost
                self._buckets[key] = (tokens, last_refill)
                missing = max(0.0, capacity - tokens)
                reset_epoch = int(wall_now + math.ceil(missing / refill_rate))
                return RateLimitResult(True, int(tokens), reset_epoch, 0, True)
            else:
                deficit = cost - tokens
                retry_after = int(math.ceil(deficit / refill_rate))
                self._buckets[key] = (tokens, last_refill)
                missing = max(0.0, capacity - tokens)
                reset_epoch = int(wall_now + math.ceil(missing / refill_rate))
                return RateLimitResult(False, int(tokens), reset_epoch, retry_after, True)

class DistributedTokenBucketLimiter:
    def __init__(self, redis_client: aioredis.Redis, call_timeout_ms: float = 50.0) -> None:
        self._redis = redis_client
        self._timeout_sec = call_timeout_ms / 1000.0
        self._lua_script = TOKEN_BUCKET_LUA_SCRIPT.strip()
        self._sha1: Optional[str] = None
        self._local_fallback = LocalMemoryTokenBucket()
        self._sha_lock = asyncio.Lock()

    async def _ensure_script_loaded(self) -> str:
        if self._sha1 is not None:
            return self._sha1
        async with self._sha_lock:
            if self._sha1 is None:
                sha = await self._redis.script_load(self._lua_script)
                self._sha1 = sha
        return self._sha1

    async def check_rate_limit(self, tenant: TenantTier, route_key: str, cost: int = 1) -> RateLimitResult:
        redis_key = f"rl:{{tenant:{tenant.tenant_id}}}:{route_key}"
        now_epoch = time.time()
        try:
            return await asyncio.wait_for(
                self._eval_redis(redis_key, tenant, cost, now_epoch),
                timeout=self._timeout_sec,
            )
        except (TimeoutError, asyncio.TimeoutError, RedisConnectionError, RedisError) as ex:
            logger.warning("Redis rate limit call failed (%s). Activating local memory fallback.", repr(ex))
            return await self._local_fallback.consume(redis_key, tenant.capacity, tenant.refill_rate_per_sec, cost)

    async def _eval_redis(self, key: str, tenant: TenantTier, cost: int, now_epoch: float) -> RateLimitResult:
        sha = await self._ensure_script_loaded()
        args = [tenant.capacity, tenant.refill_rate_per_sec, cost, now_epoch]
        try:
            res = await self._redis.evalsha(sha, 1, key, *args)
        except NoScriptError:
            sha = await self._redis.script_load(self._lua_script)
            self._sha1 = sha
            res = await self._redis.evalsha(sha, 1, key, *args)

        allowed_flag, remaining, reset_epoch, retry_after = res
        return RateLimitResult(bool(allowed_flag == 1), int(remaining), int(reset_epoch), int(retry_after), False)

TENANT_POLICIES: Final[Dict[str, TenantTier]] = {
    "cust_ent_9942": TenantTier("cust_ent_9942", capacity=1000, refill_rate_per_sec=1000.0 / 60.0),
    "cust_free_1018": TenantTier("cust_free_1018", capacity=10, refill_rate_per_sec=10.0 / 60.0),
}
DEFAULT_POLICY: Final[TenantTier] = TenantTier("anonymous", capacity=5, refill_rate_per_sec=5.0 / 60.0)

class RateLimitingMiddleware(BaseHTTPMiddleware):
    def __init__(self, app: FastAPI, limiter: DistributedTokenBucketLimiter) -> None:
        super().__init__(app)
        self._limiter = limiter

    async def dispatch(self, request: Request, call_next: Callable) -> Response:
        if request.url.path == "/v1/payments/checkout" and request.method == "POST":
            tenant_id = request.headers.get("X-Tenant-ID", "anonymous")
            policy = TENANT_POLICIES.get(tenant_id, DEFAULT_POLICY)
            result = await self._limiter.check_rate_limit(policy, "payments_checkout", 1)

            if not result.allowed:
                response = JSONResponse(
                    status_code=status.HTTP_429_TOO_MANY_REQUESTS,
                    content={"error": "rate_limit_exceeded", "tenant_id": tenant_id, "retry_after": result.retry_after},
                )
                self._inject_headers(response, policy.capacity, result)
                return response

            response = await call_next(request)
            self._inject_headers(response, policy.capacity, result)
            return response
        return await call_next(request)

    @staticmethod
    def _inject_headers(response: Response, limit: int, result: RateLimitResult) -> None:
        response.headers["X-RateLimit-Limit"] = str(limit)
        response.headers["X-RateLimit-Remaining"] = str(max(0, result.remaining_tokens))
        response.headers["X-RateLimit-Reset"] = str(result.reset_epoch)
        if not result.allowed:
            response.headers["Retry-After"] = str(result.retry_after)
        if result.is_fallback:
            response.headers["X-RateLimit-Degraded"] = "true"

app = FastAPI(title="Payment Gateway Auth Service")
redis_pool = aioredis.ConnectionPool.from_url("redis://localhost:6379/0", max_connections=50, socket_timeout=0.050)
redis_client = aioredis.Redis(connection_pool=redis_pool)
rate_limiter = DistributedTokenBucketLimiter(redis_client=redis_client, call_timeout_ms=50.0)
app.add_middleware(RateLimitingMiddleware, limiter=rate_limiter)

@app.post("/v1/payments/checkout")
async def checkout_endpoint(request: Request) -> Dict[str, str]:
    return {"status": "success", "transaction_id": "txn_88491029410"}

package com.codingpancake.gateway.ratelimit;

import io.github.resilience4j.circuitbreaker.CircuitBreaker;
import io.github.resilience4j.circuitbreaker.CircuitBreakerConfig;
import io.github.resilience4j.circuitbreaker.CircuitBreakerRegistry;
import io.github.resilience4j.reactor.circuitbreaker.operator.CircuitBreakerOperator;
import org.redisson.api.RScriptReactive;
import org.redisson.api.RedissonReactiveClient;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.core.io.buffer.DataBuffer;
import org.springframework.http.HttpHeaders;
import org.springframework.http.HttpMethod;
import org.springframework.http.HttpStatus;
import org.springframework.http.MediaType;
import org.springframework.http.server.reactive.ServerHttpResponse;
import org.springframework.stereotype.Component;
import org.springframework.web.server.ServerWebExchange;
import org.springframework.web.server.WebFilter;
import org.springframework.web.server.WebFilterChain;
import reactor.core.publisher.Mono;

import java.nio.charset.StandardCharsets;
import java.time.Duration;
import java.time.Instant;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

@Component
public class RateLimitingWebFilter implements WebFilter {
    private static final Logger log = LoggerFactory.getLogger(RateLimitingWebFilter.class);

    private static final String LUA_TOKEN_BUCKET =
        "local key = KEYS[1]\n" +
        "local capacity = tonumber(ARGV[1])\n" +
        "local refill_rate = tonumber(ARGV[2])\n" +
        "local cost = tonumber(ARGV[3])\n" +
        "local now = tonumber(ARGV[4])\n" +
        "local data = redis.call('HMGET', key, 'tokens', 'last_updated')\n" +
        "local tokens = tonumber(data[1])\n" +
        "local last_updated = tonumber(data[2])\n" +
        "if tokens == nil then tokens = capacity last_updated = now else\n" +
        "    local elapsed = math.max(0, now - last_updated)\n" +
        "    tokens = math.min(capacity, tokens + (elapsed * refill_rate))\n" +
        "    last_updated = now\n" +
        "end\n" +
        "local allowed = 0\n" +
        "local retry_after = 0\n" +
        "if tokens >= cost then allowed = 1 tokens = tokens - cost else\n" +
        "    allowed = 0\n" +
        "    local deficit = cost - tokens\n" +
        "    retry_after = math.ceil(deficit / refill_rate)\n" +
        "end\n" +
        "local ttl = math.max(60, math.ceil((capacity / refill_rate) * 2))\n" +
        "redis.call('HMSET', key, 'tokens', tokens, 'last_updated', last_updated)\n" +
        "redis.call('EXPIRE', key, ttl)\n" +
        "local missing = math.max(0, capacity - tokens)\n" +
        "local reset_epoch = math.floor(now + math.ceil(missing / refill_rate))\n" +
        "return {allowed, math.floor(tokens), reset_epoch, retry_after}";

    public record TenantPolicy(String tenantId, long capacity, double refillRatePerSec) {}
    public record RateLimitDecision(boolean allowed, long remaining, long resetEpoch, long retryAfter, boolean isFallback) {}

    private final RedissonReactiveClient redissonClient;
    private final CircuitBreaker circuitBreaker;
    private final ConcurrentHashMap localBuckets = new ConcurrentHashMap<>();
    private volatile String cachedSha1 = null;

    private static final Map POLICIES = Map.of(
        "cust_ent_9942", new TenantPolicy("cust_ent_9942", 1000, 1000.0 / 60.0),
        "cust_free_1018", new TenantPolicy("cust_free_1018", 10, 10.0 / 60.0)
    );
    private static final TenantPolicy DEFAULT_POLICY = new TenantPolicy("anonymous", 5, 5.0 / 60.0);

    public RateLimitingWebFilter(RedissonReactiveClient redissonClient) {
        this.redissonClient = redissonClient;
        CircuitBreakerConfig cbConfig = CircuitBreakerConfig.custom()
            .slidingWindowSize(100)
            .failureRateThreshold(50.0f)
            .slowCallDurationThreshold(Duration.ofMillis(50))
            .waitDurationInOpenState(Duration.ofSeconds(5))
            .build();
        this.circuitBreaker = CircuitBreakerRegistry.of(cbConfig).circuitBreaker("redisRateLimiter");
    }

    @Override
    public Mono filter(ServerWebExchange exchange, WebFilterChain chain) {
        var request = exchange.getRequest();
        if (request.getMethod() == HttpMethod.POST && "/v1/payments/checkout".equals(request.getPath().value())) {
            String tenantId = request.getHeaders().getFirst("X-Tenant-ID");
            TenantPolicy policy = (tenantId != null && POLICIES.containsKey(tenantId)) ? POLICIES.get(tenantId) : DEFAULT_POLICY;

            return evaluateRateLimit(policy, "payments_checkout", 1)
                .flatMap(decision -> {
                    ServerHttpResponse response = exchange.getResponse();
                    applyHeaders(response.getHeaders(), policy.capacity(), decision);
                    if (!decision.allowed()) {
                        response.setStatusCode(HttpStatus.TOO_MANY_REQUESTS);
                        response.getHeaders().setContentType(MediaType.APPLICATION_JSON);
                        String body = String.format("{\"error\":\"rate_limit_exceeded\",\"tenant_id\":\"%s\",\"retry_after\":%d}", policy.tenantId(), decision.retryAfter());
                        DataBuffer buffer = response.bufferFactory().wrap(body.getBytes(StandardCharsets.UTF_8));
                        return response.writeWith(Mono.just(buffer));
                    }
                    return chain.filter(exchange);
                });
        }
        return chain.filter(exchange);
    }

    private Mono evaluateRateLimit(TenantPolicy policy, String route, long cost) {
        String redisKey = String.format("rl:{tenant:%s}:%s", policy.tenantId(), route);
        long nowSeconds = Instant.now().getEpochSecond();
        return executeRedisLua(redisKey, policy, cost, nowSeconds)
            .timeout(Duration.ofMillis(50))
            .transformDeferred(CircuitBreakerOperator.of(circuitBreaker))
            .onErrorResume(ex -> {
                log.warn("Redis unavailable: {}. Falling back to in-memory bucket.", ex.getMessage());
                return Mono.just(evaluateLocalFallback(redisKey, policy, cost));
            });
    }

    private Mono executeRedisLua(String key, TenantPolicy policy, long cost, long now) {
        RScriptReactive script = redissonClient.getScript();
        List

package main

import (
	"context"
	"crypto/sha1"
	"encoding/hex"
	"errors"
	"fmt"
	"math"
	"net/http"
	"strconv"
	"sync"
	"time"

	"github.com/gin-gonic/gin"
	"github.com/redis/go-redis/v9"
)

const LuaTokenBucketScript = `
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 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

local allowed = 0
local retry_after = 0
if tokens >= cost then
    allowed = 1
    tokens = tokens - cost
else
    allowed = 0
    local deficit = cost - tokens
    retry_after = math.ceil(deficit / refill_rate)
end

local ttl = math.max(60, math.ceil((capacity / refill_rate) * 2))
redis.call("HMSET", key, "tokens", tokens, "last_updated", last_updated)
redis.call("EXPIRE", key, ttl)
local reset_epoch = math.floor(now + math.ceil(math.max(0, capacity - tokens) / refill_rate))
return {allowed, math.floor(tokens), reset_epoch, retry_after}
`

type TenantPolicy struct {
	TenantID         string
	Capacity         int64
	RefillRatePerSec float64
}

type RateLimitResult struct {
	Allowed         bool
	RemainingTokens int64
	ResetEpoch      int64
	RetryAfter      int64
	IsFallback      bool
}

type localBucket struct {
	sync.Mutex
	tokens     float64
	lastRefill time.Time
}

type DistributedRateLimiter struct {
	client       *redis.Client
	scriptSHA    string
	scriptLock   sync.RWMutex
	fallbackMap  sync.Map
	redisTimeout time.Duration
}

func NewDistributedRateLimiter(client *redis.Client, timeout time.Duration) (*DistributedRateLimiter, error) {
	hasher := sha1.New()
	hasher.Write([]byte(LuaTokenBucketScript))
	sha := hex.EncodeToString(hasher.Sum(nil))

	limiter := &DistributedRateLimiter{client: client, scriptSHA: sha, redisTimeout: timeout}
	ctx, cancel := context.WithTimeout(context.Background(), 2*time.Second)
	defer cancel()
	_, err := client.ScriptLoad(ctx, LuaTokenBucketScript).Result()
	if err != nil {
		return nil, fmt.Errorf("failed to preload script: %w", err)
	}
	return limiter, nil
}

func (d *DistributedRateLimiter) CheckRateLimit(ctx context.Context, policy TenantPolicy, routeKey string, cost int64) (*RateLimitResult, error) {
	redisKey := fmt.Sprintf("rl:{tenant:%s}:%s", policy.TenantID, routeKey)
	nowEpoch := float64(time.Now().Unix())

	evalCtx, cancel := context.WithTimeout(ctx, d.redisTimeout)
	defer cancel()

	d.scriptLock.RLock()
	sha := d.scriptSHA
	d.scriptLock.RUnlock()

	val, err := d.client.EvalSha(evalCtx, sha, []string{redisKey}, policy.Capacity, policy.RefillRatePerSec, cost, nowEpoch).Result()
	if err != nil {
		return d.evaluateLocalFallback(redisKey, policy, cost), nil
	}

	results, ok := val.([]interface{})
	if !ok || len(results) < 4 {
		return d.evaluateLocalFallback(redisKey, policy, cost), nil
	}

	return &RateLimitResult{
		Allowed:         results[0].(int64) == 1,
		RemainingTokens: results[1].(int64),
		ResetEpoch:      results[2].(int64),
		RetryAfter:      results[3].(int64),
		IsFallback:      false,
	}, nil
}

func (d *DistributedRateLimiter) evaluateLocalFallback(key string, policy TenantPolicy, cost int64) *RateLimitResult {
	actual, _ := d.fallbackMap.LoadOrStore(key, &localBucket{tokens: float64(policy.Capacity), lastRefill: time.Now()})
	b := actual.(*localBucket)
	b.Lock()
	defer b.Unlock()

	now := time.Now()
	elapsed := now.Sub(b.lastRefill).Seconds()
	b.tokens = math.Min(float64(policy.Capacity), b.tokens+(elapsed*policy.RefillRatePerSec))
	b.lastRefill = now

	nowUnix := now.Unix()
	if b.tokens >= float64(cost) {
		b.tokens -= float64(cost)
		resetEpoch := nowUnix + int64(math.Ceil(math.Max(0, float64(policy.Capacity)-b.tokens)/policy.RefillRatePerSec))
		return &RateLimitResult{Allowed: true, RemainingTokens: int64(b.tokens), ResetEpoch: resetEpoch, RetryAfter: 0, IsFallback: true}
	}
	retryAfter := int64(math.Ceil((float64(cost) - b.tokens) / policy.RefillRatePerSec))
	resetEpoch := nowUnix + int64(math.Ceil(math.Max(0, float64(policy.Capacity)-b.tokens)/policy.RefillRatePerSec))
	return &RateLimitResult{Allowed: false, RemainingTokens: int64(b.tokens), ResetEpoch: resetEpoch, RetryAfter: retryAfter, IsFallback: true}
}

var Policies = map[string]TenantPolicy{
	"cust_ent_9942": {TenantID: "cust_ent_9942", Capacity: 1000, RefillRatePerSec: 1000.0 / 60.0},
	"cust_free_1018": {TenantID: "cust_free_1018", Capacity: 10, RefillRatePerSec: 10.0 / 60.0},
}
var DefaultPolicy = TenantPolicy{TenantID: "anonymous", Capacity: 5, RefillRatePerSec: 5.0 / 60.0}

func RateLimitMiddleware(limiter *DistributedRateLimiter) gin.HandlerFunc {
	return func(c *gin.Context) {
		if c.Request.URL.Path == "/v1/payments/checkout" && c.Request.Method == http.MethodPost {
			tenantID := c.GetHeader("X-Tenant-ID")
			policy, exists := Policies[tenantID]
			if !exists { policy = DefaultPolicy }

			decision, _ := limiter.CheckRateLimit(c.Request.Context(), policy, "payments_checkout", 1)
			c.Header("X-RateLimit-Limit", strconv.FormatInt(policy.Capacity, 10))
			c.Header("X-RateLimit-Remaining", strconv.FormatInt(decision.RemainingTokens, 10))
			c.Header("X-RateLimit-Reset", strconv.FormatInt(decision.ResetEpoch, 10))
			if decision.IsFallback { c.Header("X-RateLimit-Degraded", "true") }

			if !decision.Allowed {
				c.Header("Retry-After", strconv.FormatInt(decision.RetryAfter, 10))
				c.AbortWithStatusJSON(http.StatusTooManyRequests, gin.H{
					"error": "rate_limit_exceeded",
					"tenant_id": policy.TenantID,
					"retry_after": decision.RetryAfter,
				})
				return
			}
		}
		c.Next()
	}
}

func main() {
	rdb := redis.NewClient(&redis.Options{Addr: "localhost:6379", PoolSize: 100, ReadTimeout: 50 * time.Millisecond, WriteTimeout: 50 * time.Millisecond})
	limiter, _ := NewDistributedRateLimiter(rdb, 50*time.Millisecond)
	router := gin.Default()
	router.Use(RateLimitMiddleware(limiter))
	router.POST("/v1/payments/checkout", func(c *gin.Context) {
		c.JSON(http.StatusOK, gin.H{"status": "success", "transaction_id": "txn_go_992140281"})
	})
	_ = router.Run(":8080")
}

4.3 Edge Case & Production Failure Hardening

5.1 Incident Timeline & Post-Mortem: How 100,000 QPS Melted the Redis Cluster

At 09:00:00 UTC, a Tier-1 enterprise tenant (cust_ent_9942) initiated a flash ticket release on the critical route /v1/payments/checkout. The edge infrastructure consisted of 32 API Gateway pods running on Kubernetes, load-balanced across three Redis 7.0 primary master instances (redis-m1, redis-m2, redis-m3) hosted on AWS c6g.2xlarge compute instances:

sequenceDiagram
    autonumber
    actor Client as Inbound Traffic (100k QPS)
    participant LB as Edge Load Balancer
    participant GW as 32x Gateway Pods (Pool=100)
    participant Redis as Redis Master (redis-m1)
    participant Svc as Upstream Checkout API

    Client->>LB: POST /v1/payments/checkout (100,000 QPS)
    LB->>GW: Distribute ~3,125 QPS per pod
    Note over GW,Redis: 32 pods dispatch 100,000 sync EVALSHA calls/sec
    GW->>Redis: EVALSHA {cust_ent_9942} (Lua Execution)
    Note over Redis: Single Core hits 100% CPU
Queue depth > 18,000 cmds
Latency spikes: 0.8ms -> 4,200ms
    Redis-->>GW: Delayed Response / Connection Timeout (> 2,000ms)
    Note over GW: 3,200 Client Sockets Exhausted
All Gateway Worker Threads Blocked
Kubelet Health Check /healthz Fails
    GW-->>LB: Socket Hangup / Read Timeout
    LB-->>Client: HTTP 504 Gateway Timeout (94.8% Outage)
    Note over Svc: Core Checkout API starved of genuine traffic
    

5.2 The Architectural Fix: Local Token Batching & Asynchronous Synchronization

To decouple client request throughput from centralized Redis execution limits, we implement Leased Token Batching with Asynchronous Prefetching. Instead of querying Redis synchronously for a single token per HTTP request ($N=1$), each Gateway pod leases tokens in bulk batches ($N=50$) and manages consumption entirely in local RAM:

graph TD
    subgraph Client Traffic Layer
        C1["Inbound Client Requests (100,000 QPS)"]
    end

    subgraph API Gateway Pod
        subgraph Local Memory Engine
            CAS["Atomic In-Memory Counter
(Current: 42 tokens)"]
            LWM{"Tokens <= Low-Water Mark?
(Threshold: 10 tokens)"}
        end
        
        subgraph Synchronous Hot Path
            REQ["HTTP Request Interceptor"] --> CAS
            CAS -->|"Token Available (>0)"| PASS["Allow: Upstream /v1/checkout
(Latency: < 0.05ms)"]
            CAS -->|"Tokens Depleted (=0)"| DROP["Reject: HTTP 429 Too Many Requests"]
        end

        subgraph Asynchronous Background Worker
            LWM -->|"True (Async Trigger)"| BG["Async Prefetch Worker"]
            BG -->|"Batch Acquire (N=50)"| REDIS_CLI["Redis Async Client Pool"]
            REDIS_CLI -->|"Replenish +50 Tokens"| CAS
        end
    end

    subgraph Redis Cluster Layer
        REDIS_CLI -.->|"Async EVALSHA (2,000 QPS total)"| R_M1["Redis Master (redis-m1)"]
        R_M1 -->|"Atomic Global Decrement"| HASH_KEY["Key: {cust_ent_9942}"]
    end

    C1 --> REQ
    

5.3 SRE Emergency Triage Runbook & Circuit Breaking Playbook

6.1 The Definitive Decision Matrix & Architecture Selection Framework

6.2 Deep-Dive Technical FAQ: Advanced Systems Engineering Challenges

Q1: How do you handle multi-region active-active rate limiting across US-East and EU-West without incurring cross-Atlantic latency on every request?

Executing a synchronous Redis call across trans-Atlantic fiber introduces an unavoidable 70 ms – 100 ms network RTT penalty ($t_{\text{propagation}} \approx \frac{2 \times 6000\text{ km}}{200{,}000\text{ km/s}}$ in optic glass). Placing this round-trip on the synchronous path of an API request like /v1/payments/checkout completely destroys service latency SLAs. Production architectures resolve this via Dynamic Geo-Partitioned Token Leases paired with asynchronous Conflict-Free Replicated Data Types (PN-Counters):

flowchart LR
    subgraph US_East["Region: US-East (Virginia)"]
        ClientUS["US Clients"] --> GW_US["API Gateway (US)"]
        GW_US --> LocalRedis_US[("Local Redis US (Master)")]
        LocalRedis_US -.-> LeaseAlloc_US["Local Lease: 60% Capacity"]
    end

    subgraph EU_West["Region: EU-West (Frankfurt)"]
        ClientEU["EU Clients"] --> GW_EU["API Gateway (EU)"]
        GW_EU --> LocalRedis_EU[("Local Redis EU (Master)")]
        LocalRedis_EU -.-> LeaseAlloc_EU["Local Lease: 40% Capacity"]
    end

    LocalRedis_US <-->|"Async CRDT Delta Sync (Gossip / WAN Mesh)"| LocalRedis_EU
    

1. Static Capacity Partitioning with Dynamic Re-Weighting: For a global customer limit of $10{,}000\text{ QPS}$, quota is partitioned proportionally (e.g. $6{,}000\text{ QPS}$ US, $4{,}000\text{ QPS}$ EU). Requests are evaluated against regional Redis with < 1ms latency.
2. Asynchronous WAN Gossip Reconciliation: Every 200–500ms, background daemons exchange consumed token counters via PN-Counter CRDTs, rebalancing unused quotas across regions without blocking active traffic.
3. Partition Failure Invariant: If trans-oceanic fiber is severed, each region operates independently within its allocated static quota slice ($C_{\text{global}} = C_{\text{US}} + C_{\text{EU}}$), guaranteeing backend protection.

Q2: How do NTP clock step adjustments and leap seconds affect continuous-time rate limiters, and how do we guarantee monotonicity?

Continuous-time rate limiters compute replenishment via $\Delta t = t_{\text{current}} - t_{\text{last\_updated}}$. If host clocks step backwards via non-monotonic NTP updates, $\Delta t < 0$, destroying tokens and triggering false HTTP 429 rejections.

• Clamp Delta to Non-Negative Space: In Lua scripts, always enforce local elapsed_us = math.max(0, now_us - last_updated_us).
• OS-Level Slew Configuration: Configure chronyd -x to slew clock frequency gradually without backward jumps.
• Monotonic Clocks: For local in-memory buckets, sample monotonic clocks (CLOCK_MONOTONIC_RAW or System.nanoTime()), which are immune to NTP adjustments.

Q3: How do you rate-limit long-lived streaming connections like gRPC bi-directional streams and WebSockets?

Evaluating limits only during HTTP connection handshake is insufficient for streaming protocols that stay connected for days. Streaming limiters enforce dual-dimensional metering (Frame Frequency + Byte Volume) and apply Backpressure Flow Control:

sequenceDiagram
    autonumber
    actor Client as gRPC / WebSocket Client
    participant Proxy as Gateway (Envoy / Custom Proxy)
    participant Bucket as Local Token Bucket (Byte / Frame)

    Client->>Proxy: Stream Data Frame (Size: 64 KB)
    Proxy->>Bucket: Consume Tokens (Cost = 65,536 bytes)
    alt Bucket has sufficient tokens
        Bucket-->>Proxy: Approved (Remaining: 180 KB)
        Proxy->>Proxy: Forward frame to upstream backend
    else Bucket Exhausted (Negative balance)
        Bucket-->>Proxy: Rejected / Throttled
        Note over Proxy,Client: Trigger TCP / HTTP/2 Flow Control
        Proxy-->>Client: Stop sending HTTP/2 WINDOW_UPDATE frames
        Note over Client: Client TCP send buffer fills up;
client kernel stalls write() syscall
    end
    

Q4: How do you protect the Redis keyspace from hash collision attacks and memory exhaustion from spoofed random IP addresses?

Attackers cycling through 100M random IPs can inflate Redis memory by 8GB+. Mitigate by:

• Subnet Masking (CIDR Aggregation): Aggregate IPv4 into /24 subnets (256 IPs per key) and IPv6 into /64 routing prefixes.
• HMAC-SHA256 Truncated Key Hashing: Truncate HMAC-SHA256 digests to 16 hex characters (64-bit integer representation: rl:ip:{digest}).
• Aggressive Short TTLs with volatile-lfu Eviction: Set 60s TTLs with LFU cache eviction so Redis automatically sheds one-off spoofed IP keys under pressure.

Q5: How do compound rate limit keys work for tiered multi-dimensional quotas?

Enterprise APIs evaluate compound constraints (Platform Capacity + Tenant Tier + Endpoint Cost + Client IP). Production gateways construct composite keys $\text{Key}_{\text{composite}} = \text{"rl:"} \,\|\, \text{TenantID} \,\|\, \text{Tier} \,\|\, \text{EndpointHash} \,\|\, \text{ClientID}$ and evaluate all dimensions atomically in a single multi-key Lua script.

Q6: What happens during a Redis Master failover, and how do you prevent replica promotion from resetting counters or causing split-brain?