Building Distributed Rate Limiters: Token Bucket, Leaky Bucket, and Sliding Window Logs

Why You Need This in Real Life

At 09:00 AM on ticket launch day, a botnet launches a Denial of Service (DoS) attack, sending 250,000 requests per second to your public /api/v1/checkout endpoint.

Without a rate limiter, incoming requests swamp your application worker threads, flood database connection pools, and crash your backend infrastructure for genuine paying customers.

Rate limiting is an essential defense layer designed to:

Prevent resource starvation caused by DoS attacks or runaway client scripts.
Enforce API monetization tiers (e.g., Free Tier: 100 req/min; Pro Tier: 10,000 req/min).
Protect downstream third-party APIs (e.g., Stripe, Twilio) from exceeding rate quotas.

To build distributed rate limiters that scale across multi-region API gateways, you must master the Token Bucket, Leaky Bucket, Fixed Window, Sliding Window Counter, and Redis Lua Scripting mechanics.

Part 1: Deconstructing Rate Limiting Algorithms

1. Token Bucket Algorithm

Concept: A bucket with capacity $B$ holds tokens. A refiller adds tokens to the bucket at a constant rate $R$ tokens/sec.
Request Processing: Each incoming request consumes 1 token. If tokens $\ge 1$ , the request proceeds. If tokens $< 1$ , the request is dropped with HTTP 429 Too Many Requests.
Strengths: Allows short burst traffic up to capacity $B$ . Memory-efficient ( $\mathcal{O}(1)$ memory per user).

  Refiller (+R tokens/sec)
           |
           v
    +--------------+
    |  [T] [T] [T] |  (Bucket Capacity B = 3)
    +------+-------+
           |
    Incoming Request ---> Consumes 1 Token [T] ---> ALLOWED (HTTP 200)

2. Leaky Bucket Algorithm

Concept: Requests enter a FIFO queue (the bucket). The queue leaks requests to downstream handlers at a smooth, constant output rate $R$ .
Strengths: Smooths out traffic bursts into a steady flow.
Drawbacks: Burst traffic is delayed in the queue rather than processed immediately.

3. Fixed Window Counter Algorithm

Concept: Time is divided into fixed windows (e.g., 60-second intervals). A counter tracks requests per window.
Weakness (The Boundary Burst Trap): If a client sends 100 requests at 00:59 and another 100 requests at 01:01, 200 requests pass in a 2-second window, double the intended rate limit!

4. Sliding Window Counter Algorithm

Combines the low memory overhead of Fixed Window with boundary accuracy by calculating a weighted average of the current and previous windows:

$\text{Weight} = \frac{\text{Time Remaining in Current Window}}{\text{Window Length}}$ $\text{Estimated Count} = (\text{Previous Window Count} \times \text{Weight}) + \text{Current Window Count}$

Part 2: Rate Limiter Algorithm Comparison

Algorithm	Burst Capacity	Memory Overhead	Time Boundary Accuracy
Token Bucket	Excellent	Very Low ( $\mathcal{O}(1)$ )	High
Leaky Bucket	None (Smooths flow)	Low (Queue size)	High
Fixed Window	High (Boundary flaw)	Very Low ( $\mathcal{O}(1)$ )	Low (Boundary bursts)
Sliding Window Log	Excellent	High ( $\mathcal{O}(N)$ timestamps)	Perfect
Sliding Window Counter	Moderate	Very Low ( $\mathcal{O}(1)$ )	Excellent ( $99.9\%$ accurate)

Part 3: Distributed Rate Limiting with Redis & Lua Scripts

In a distributed environment with 10 API gateway nodes, storing rate limit counters in local node memory fails because a client can hit 10 different gateways, effectively multiplying their rate limit by 10x.

Rate limit counters must be stored in a centralized, high-speed cache like Redis.

The Concurrent Race Condition

Reading a counter from Redis, incrementing it in Java, and writing it back to Redis creates a race condition under high concurrency. Two parallel requests will read the same counter value, causing under-counting.

The Solution: Atomic Redis Lua Scripts

Redis executes Lua scripts atomically. No other Redis command can execute while a Lua script is running, eliminating race conditions.

-- Redis Lua Script for Atomic Token Bucket Rate Limiter
-- KEYS[1]: Rate limit key (e.g., "rate:user_42")
-- ARGV[1]: Bucket capacity (B)
-- ARGV[2]: Refill rate per millisecond (R)
-- ARGV[3]: Current timestamp (milliseconds)

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

-- Fetch current state from Redis Hash
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
    -- Calculate refilled tokens based on elapsed time
    local delta = math.max(0, now - last_updated)
    tokens = math.min(capacity, tokens + delta * refill_rate)
    last_updated = now
end

if tokens >= 1 then
    tokens = tokens - 1
    redis.call("HMSET", key, "tokens", tokens, "last_updated", last_updated)
    redis.call("EXPIRE", key, 60) -- Auto cleanup after 60s idle
    return {1, math.floor(tokens)} -- Allowed (1)
else
    redis.call("HMSET", key, "tokens", tokens, "last_updated", last_updated)
    return {0, math.floor(tokens)} -- Rejected (0)
end

Part 4: Proper HTTP Header Response Standards

When an API client is rate-limited, the API gateway must return standardized HTTP response headers so clients can back off gracefully:

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1704067260
Retry-After: 35

{
  "error": "Too Many Requests",
  "message": "API rate limit exceeded. Please retry after 35 seconds."
}

Next Steps

Now that we understand distributed rate limiting algorithms and atomic Redis Lua scripts, we will explore the Circuit Breaker pattern in Part 11: protecting services from cascading failures.

References & Further Reading

Vattani, C., et al. (2015). Optimal Probabilistic Cache Expiration (XFetch Algorithm). VLDB Endowment.
Redis Ltd. Redis Caching Strategies, Eviction Policies (LRU/LFU), and Memory Optimization. Redis Docs.
Kleppmann, M. (2017). Designing Data-Intensive Applications (Chapter 3: Storage and Retrieval). O’Reilly Media.