18 — A rate limiter, end to end

A rate limiter protects an API from abuse and traffic spikes. It’s a good example because it’s small, and it still needs high-level and low-level thinking. The setup: 20 stateless gateways, 50,000 requests a second, and a limit of 100 requests a minute per user.

The algorithms

A test sent 150 requests at 59.9 s and 150 at 60.1 s, with a limit of 100 a minute. The fixed window allowed 200, and the token bucket allowed 100. The fixed window’s problem is its boundary: each minute’s counter starts fresh.

High-level decisions

Where does state live? If each gateway counts alone, a user spread across all 20 gets up to 2,000 a minute. So the counters go in a shared store, usually Redis.

What identifies a client? API key, user ID or IP address. IP addresses are shared behind NAT, so they punish innocent users.

Where does it run? At the gateway, so that rejected traffic costs little.

What does a client see? An HTTP 429 with a Retry-After header.

What if Redis is down? This is a real policy choice.

• Fail open lets requests through, protecting availability.
• Fail closed rejects them, which suits sensitive endpoints such as login.

A common compromise is a local in-memory limiter as a fallback.

Does the check add latency? Every request now makes a Redis call. Options are to batch decisions locally, allowing small errors in exchange for fewer calls.

The token bucket

A timer refilling every user’s bucket would be wasteful with millions of users. Tokens can be worked out lazily, when a request arrives:

tokens = min(capacity, tokens + elapsed * refill_rate)

import threading
import time
from dataclasses import dataclass

@dataclass
class _BucketState:
    tokens: float
    last_refill: float

class TokenBucketRateLimiter:
    # Thread-safe Token Bucket rate limiter using O(1) lazy token refill calculation
    # and fine-grained per-key locking to minimize contention across users.
    def __init__(self, capacity: int, refill_rate_per_sec: float):
        self.capacity = float(capacity)
        self.refill_rate = float(refill_rate_per_sec)
        self._buckets: dict[str, _BucketState] = {}
        self._locks: dict[str, threading.Lock] = {}
        self._global_lock = threading.Lock()

    def _get_user_lock(self, key: str) -> threading.Lock:
        # Returns a dedicated lock per user key so User A never blocks User B.
        with self._global_lock:
            if key not in self._locks:
                self._locks[key] = threading.Lock()
            return self._locks[key]

    def allow_request(self, key: str, tokens_requested: int = 1) -> bool:
        user_lock = self._get_user_lock(key)
        
        with user_lock:
            now = time.monotonic()
            state = self._buckets.get(key)
            
            if state is None:
                # First request for this user: initialize full bucket
                state = _BucketState(tokens=self.capacity, last_refill=now)
                self._buckets[key] = state
            else:
                # Lazy refill: calculate tokens accrued since last request
                elapsed = max(0.0, now - state.last_refill)
                accrued = elapsed * self.refill_rate
                state.tokens = min(self.capacity, state.tokens + accrued)
                state.last_refill = now

            if state.tokens >= tokens_requested:
                state.tokens -= tokens_requested
                return True
            
            return False

if __name__ == "__main__":
    # Allow burst of 5 requests, refilling at 2 tokens per second
    limiter = TokenBucketRateLimiter(capacity=5, refill_rate_per_sec=2.0)
    
    print("Simulating burst of 7 immediate requests for user_42:")
    for i in range(1, 8):
        allowed = limiter.allow_request("user_42")
        print(f"  Request #{i}: {'ALLOWED' if allowed else 'THROTTLED (429)'}")
        
    print("\nWaiting 1.1 seconds for lazy refill (+2.2 tokens)...")
    time.sleep(1.1)
    for i in range(8, 11):
        allowed = limiter.allow_request("user_42")
        print(f"  Request #{i}: {'ALLOWED' if allowed else 'THROTTLED (429)'}")

Output:

Simulating burst of 7 immediate requests for user_42:
  Request #1: ALLOWED
  Request #2: ALLOWED
  Request #3: ALLOWED
  Request #4: ALLOWED
  Request #5: ALLOWED
  Request #6: THROTTLED (429)
  Request #7: THROTTLED (429)

Waiting 1.1 seconds for lazy refill (+2.2 tokens)...
  Request #8: ALLOWED
  Request #9: ALLOWED
  Request #10: THROTTLED (429)

Five pass, two are throttled, and 1.1 seconds earns 2.2 tokens, so two more pass.

_buckets and _locks never shrink, so this leaks memory as users accumulate. It needs eviction before real use.

The distributed race

Moving this to Redis naively creates a race. Two gateways read tokens = 1 at once, both subtract 1, and both write 0, so two requests pass on one token. A lock inside each gateway can’t help, because the race is between machines.

This is the same lost update as in chapter 5. The fix is the same too: do the read and the write as one atomic step. A Redis Lua script executes without other commands in between:

-- Atomic Distributed Token Bucket in Redis Lua
-- KEYS[1]: rate limit bucket key (e.g., "rl:user_42")
-- ARGV[1]: capacity, ARGV[2]: refill_rate_per_ms, ARGV[3]: now_ms, ARGV[4]: requested_tokens

local data = redis.call("HMGET", KEYS[1], "tokens", "last_refill")
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

local tokens = tonumber(data[1])
local last_refill = tonumber(data[2])

if tokens == nil then
    tokens = capacity
    last_refill = now
else
    local elapsed = math.max(0, now - last_refill)
    tokens = math.min(capacity, tokens + (elapsed * refill_rate))
    last_refill = now
end

if tokens >= requested then
    tokens = tokens - requested
    redis.call("HSET", KEYS[1], "tokens", tokens, "last_refill", last_refill)
    redis.call("PEXPIRE", KEYS[1], math.ceil((capacity / refill_rate) * 2))
    return 1 -- Allowed
else
    redis.call("HSET", KEYS[1], "tokens", tokens, "last_refill", last_refill)
    return 0 -- Throttled (429 Too Many Requests)
end

Some details matter here.

• The gateway supplies now_ms, so clock skew between gateways matters. Redis’s own TIME command is an alternative.
• “Atomic” means uninterrupted, not rollback: if a script fails midway, earlier writes stay.
• In a Redis cluster, all keys in a script have to be on the same shard.
• PEXPIRE cleans up idle users, which avoids the memory leak in the Python version.

How it fits together

[Client] -> [Gateway] -> rate limit script -> [Redis]
               |  allowed
               v
           [Service]

Each chapter’s ideas show up here: statelessness, percentiles on the Redis call, a timeout and a circuit breaker around Redis, a fallback when it fails, and metrics on how many requests get rejected.

The takeaway

The high-level decision was where the state lives, and the low-level one was how to update it atomically. A race that a mutex fixes in one process needs an atomic operation at the store once several machines are involved.