Conduit 08: Edge Rate Limiting using Distributed Token Bucket Algorithms

1. Production Incident Context: Distributed L7 DDoS Bypassing In-Memory Limits

Standard Nginx rate limiting directives (e.g. limit_req_zone) store client request counters inside host-local shared memory zones. In globally distributed multi-region deployments using BGP Anycast, traffic routes across dozens of edge proxy nodes.

During a distributed Layer-7 DDoS attack, a botnet distributed 100,000 requests/sec across 20 distinct edge proxies. Because each proxy node only observed 5,000 QPS (below local host limits), the attack bypassed local rate limiters completely and overwhelmed the backend database cluster.

# Local Nginx shared memory counters fail to detect distributed botnet
Edge Node US-East:  5,000 QPS -> PASS (Local limit: 10,000 QPS)
Edge Node EU-West:  5,000 QPS -> PASS (Local limit: 10,000 QPS)
Edge Node AP-South: 5,000 QPS -> PASS (Local limit: 10,000 QPS)
----------------------------------------------------------------------
Backend Aggregated Load: 100,000 QPS -> DATABASE CPU 100% (MELTDOWN!)

2. Deep Architecture Mechanics: Atomic Token Bucket via Redis & Lua

To enforce global rate caps across distributed edge nodes, we implement the Token Bucket Algorithm backed by an atomic Redis Cluster.

[ Edge Proxy US-East ] ──┐
[ Edge Proxy EU-West ] ──┼──> [ Atomic Redis Lua EVAL ] ──> Global Token Bucket State
[ Edge Proxy AP-East ] ──┘     (Calculates delta_t refill & decrements in single thread)
            

Token Bucket Math Formula

Instead of running background cron tasks to refill tokens every millisecond, the algorithm calculates available tokens dynamically based on the time elapsed since the last request ($\Delta t$):

$\text{New Tokens} = \min\left(\text{Capacity}, \text{Current Tokens} + \Delta t \times \text{Refill Rate}\right)$

3. Production OpenResty Atomic Redis/Lua Rate Limiter Code

Deploy this atomic Lua rate-limiting module inside your OpenResty edge proxy location block:

-- /usr/local/openresty/nginx/lua/rate_limiter.lua
-- Atomic Token Bucket Rate Limiter in Lua

local redis = require "resty.redis"
local red = redis:new()

red:set_timeout(1000) -- 1s timeout

local ok, err = red:connect("10.0.20.15", 6379)
if not ok then
    ngx.log(ngx.ERR, "Failed to connect to Redis: ", err)
    return -- Fail open to prevent blocking legitimate traffic
end

-- Atomic Token Bucket Lua Script
local lua_script = [[
    local key = KEYS[1]
    local limit = 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 not tokens then
        tokens = limit
        last_updated = now
    else
        local delta = math.max(0, now - last_updated)
        tokens = math.min(limit, tokens + delta * 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, 60)
        return 1 -- ALLOW REQUEST
    else
        return 0 -- REJECT REQUEST (HTTP 429)
    end
]]

local client_ip = ngx.var.remote_addr
local key = "rate_limit:" .. client_ip
local now = ngx.now()

-- Execute atomic script (Limit: 20 tokens, Refill: 5 tokens/sec)
local res, err = red:eval(lua_script, 1, key, 20, 5, now, 1)

if res == 0 then
    ngx.status = 429
    ngx.header.content_type = "application/json"
    ngx.say('{"error": "Too Many Requests", "retry_after_seconds": 2}')
    ngx.exit(429)
end

4. Real-World SRE Live Diagnostic Toolkit

Monitor Redis rate-limiting latency and HTTP 429 block rates during L7 DDoS attacks:

1. Inspect Redis Rate Limiter Key State

# Query active token bucket state for a specific client IP
redis-cli -h 10.0.20.15 HGETALL "rate_limit:198.51.100.44"

# Output:
# 1) "tokens"       2) "3.421"
# 3) "last_updated" 4) "1785940120.102"

5. Redis Fail-Open Strategy & Local Memory Fallback

In high-throughput edge environments, network partitions between proxies and the central Redis cluster must not cause global outage.

• Fail-Open Policy: If Redis returns a connection timeout or error, log an alert and let the request pass through rather than returning HTTP 500/503 to users.
• Local Shared Memory Circuit Breaker: Automatically fall back to local limit_req_zone shared memory counters whenever Redis connection errors exceed 1% over a 10-second window.

6. Verified Benchmark Results: Local Memory vs. Atomic Distributed Limiter

We simulated a 100,000 QPS distributed L7 flood across 20 edge nodes:

7. Prometheus Observability (PromQL Queries)

• HTTP 429 Rejection Rate: rate(nginx_http_requests_total{status="429"}[1m])
• Redis Rate Limit Lua Latency: redis_command_call_duration_seconds_bucket{cmd="eval"}