Rate Limiting Algorithms: Token Bucket, Leaky Bucket, & Sliding Window

Rate limiting controls the rate at which incoming requests are processed by a network or backend service. Without rate limiting, distributed systems are vulnerable to:

1. Denial-of-Service (DDoS) & Traffic Spikes: A surge of requests can exhaust database connection pools, saturate CPU, and trigger cascading service outages.
2. Brute-Force & Credential Stuffing Attacks: Attackers submitting thousands of password attempts per second against login endpoints.
3. Cost Overruns & Fair Resource Allocation: Preventing rogue clients from starving other tenants in multi-tenant SaaS platforms and limiting expensive downstream API calls (e.g., LLM inference).

Standard Rate Limiting Response Headers:

When rate limiting is enforced at an API Gateway or Reverse Proxy, the response should return HTTP 429 Too Many Requests along with informative tracking headers:

http
Copy
HTTP/1.1 429 Too Many Requests
Content-Type: application/problem+json
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1714000060

{
  "title": "Too Many Requests",
  "status": 429,
  "detail": "Rate limit of 100 requests per minute exceeded. Retry after 30 seconds."
}

The Token Bucket algorithm is the most popular rate limiter in modern API gateways because it allows controlled bursts of traffic while enforcing a strict long-term average rate:

How It Works:

1. A bucket has a maximum capacity of C tokens.
2. Tokens are added to the bucket at a constant refill rate of r tokens per second.
3. When the bucket reaches capacity C, newly added tokens overflow and are discarded.
4. When an API request arrives:
   • If at least 1 token is in the bucket: 1 token is consumed, and the request is allowed (200 OK).
   • If the bucket is empty: The request is immediately rejected (429 Too Many Requests).

Lazy Calculation (Zero Background Timers):

Instead of running a background cron ticker to add tokens every second (which wastes CPU across millions of users), the server calculates token replenishment lazily upon request arrival:

tokens_{now} = \min\Big(C,\; tokens_{stored} + (now - last\_refill\_time) × r\Big)

Storage Cost: Only two values per user/IP in Redis: tokens (float) and last_refill_timestamp (integer).

While the Token Bucket allows bursts, the Leaky Bucket algorithm enforces a strictly constant, smoothed output rate:

How It Works:

1. Incoming requests enter a FIFO queue (the bucket) of maximum capacity B.
2. The server pulls requests from the queue and processes them at a strictly constant leak rate (e.g., exactly 10 requests per second).
3. If requests arrive faster than the leak rate, the queue fills up.
4. If the queue is full, new incoming requests overflow and are immediately rejected (429 Too Many Requests).

Token Bucket vs. Leaky Bucket:

• Token Bucket: Allows instantaneous bursts of up to C requests as long as tokens are present. Great for user-facing APIs where rapid page navigation is normal.
• Leaky Bucket: Completely smooths traffic spikes into a continuous, stable stream. Ideal for egress traffic shaping, webhook dispatching, and feeding message queues to prevent downstream database saturation.

1. Fixed Window Counter (Simple but Flawed)

Divides time into fixed intervals (e.g., 1 minute). A Redis key (ratelimit:user123:2026-04-12-14:00) increments on every request.

[!WARNING] The Boundary Spike Flaw: If a user sends 100 requests at second 00:59 (end of window 1) and another 100 requests at second 01:01 (start of window 2), 200 requests are allowed in a 2-second interval, completely bypassing the intended 100 req/min rate limit.

2. Sliding Window Log (High Precision, High Memory)

Stores every request timestamp in a Redis Sorted Set (ZSET):

1. Remove all timestamps older than now - window_size using ZREMRANGEBYSCORE.
2. Count elements in the set using ZCARD.
3. If count < limit, add current timestamp via ZADD and allow request.

• Flaw: High memory usage (O(M) where M is the number of requests). Storing 1,000 timestamps per active user consumes hundreds of megabytes of Redis RAM.

3. Sliding Window Counter (Cloudflare / Redis Standard)

Combines the previous window count and current window count to approximate the sliding rate with minimal memory:

Estimated Requests = Count_{prev} × ≤ft(1 - \frac{time into current window}{window size}\right) + Count_{curr}

Memory Cost: Only 2 integer keys per user in Redis, offering 99.9% accuracy with virtually zero memory overhead!

In distributed environments with multiple API Gateway instances, executing separate GET and SET commands against Redis causes Check-Then-Act Race Conditions. Two concurrent requests could both see 99 requests in Redis and both increment to 100, exceeding the limit.

Atomic Token Bucket Lua Script:

lua
Copy
-- KEYS[1]: user rate limit key (e.g. "ratelimit:user_481")
-- ARGV[1]: capacity (e.g. 100)
-- ARGV[2]: refill_rate_per_sec (e.g. 10)
-- ARGV[3]: current_timestamp (e.g. 1714000000)
-- ARGV[4]: tokens_to_consume (e.g. 1)

local key = KEYS[1]
local capacity = 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 tokens == nil then
  tokens = capacity
  last_updated = now
else
  local delta = math.max(0, now - last_updated)
  tokens = math.min(capacity, 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, math.ceil(capacity / refill_rate) * 2)
  return { 1, math.floor(tokens) } -- Allowed: 1, Remaining tokens
else
  return { 0, math.floor(tokens) } -- Denied: 0, Remaining tokens
end