Rate Limiting

Algorithms, distributed implementations, and production patterns.

Why Rate Limiting

Algorithms

Every rate-limiting algorithm answers the same question — "has this client used up its budget?" — but they disagree on how much memory that costs and how a burst is treated. The first three count requests against a window in time; the last two model a bucket instead of a counter. Fixed Window, Sliding Window, Token Bucket, and Leaky Bucket are the four shapes you'll actually reach for in production — sliding window log and sliding window counter are the accuracy/memory tradeoff inside "sliding window" itself.

graph LR
    subgraph W1["Window 1 — 00:00 to 01:00 — 100 requests, limit not exceeded"]
        R1["100 requests, spread across the window"]:::window
    end
    subgraph W2["Window 2 — 01:00 to 02:00 — 100 requests, limit not exceeded"]
        R2["100 requests, spread across the window"]:::window
    end
    B["200 requests inside a 2-second span straddling 01:00 — each window resets independently, so neither one alone looks like a violation"]:::burst
    R1 -->|"last 100 requests of window 1, sent right before 01:00"| B
    R2 -->|"first 100 requests of window 2, sent right after 01:00"| B
    classDef window fill:#3498db,stroke:#2471a3,color:#fff;
    classDef burst fill:#e74c3c,stroke:#c0392b,color:#fff;

key = "ratelimit:{user}:{minute}"
INCR key
EXPIRE key 60

prev_window_count = 80
curr_window_count = 30
elapsed_in_current = 0.4  # 40% into current window
estimated = curr_window_count + prev_window_count * (1 - elapsed_in_current)
= 30 + 80 * 0.6
= 78

Algorithm Comparison

graph TD
    classDef risky fill:#e74c3c,stroke:#c0392b,color:#fff
    classDef caution fill:#f39c12,stroke:#ba6018,color:#fff
    classDef safe fill:#27ae60,stroke:#1e8449,color:#fff
    classDef entry fill:#34495e,stroke:#212f3c,color:#fff

    T["Burst traffic arrives<br/>(same client, same instant)"]:::entry

    subgraph WINDOW["Window-based counters"]
        FW["Fixed Window<br/>O(1) memory"]
        SWL["Sliding Window Log<br/>O(n) memory — one entry per request"]
        SWC["Sliding Window Counter<br/>O(1) memory — two counters + interpolation"]
    end

    subgraph BUCKET["Bucket-based shaping"]
        TB["Token Bucket<br/>O(1) memory"]
        LB["Leaky Bucket<br/>O(queue) memory"]
    end

    T --> FW & SWL & SWC & TB & LB

    FW --> FW1["Boundary burst: up to 2x the limit<br/>can pass around the window edge"]:::risky
    SWL --> SWL1["Exact block at the true limit —<br/>but memory cost scales with request volume"]:::caution
    SWC --> SWC1["~99.9% accurate block —<br/>small interpolation error, constant memory"]:::safe
    TB --> TB1["Lets the burst through up to capacity,<br/>then throttles to the refill rate"]:::caution
    LB --> LB1["Queues the burst, drains it at a<br/>fixed rate — output is always smooth"]:::safe

Redis Implementations

Sliding Window Counter (Lua)

Atomic read-update-expiry in a single script — no race conditions, because the entire script runs as one indivisible operation on Redis's single-threaded execution.

-- KEYS[1] = current window key, KEYS[2] = prev window key
-- ARGV[1] = limit, ARGV[2] = elapsed_fraction (0.0–1.0), ARGV[3] = window_seconds

local curr = tonumber(redis.call('GET', KEYS[1])) or 0
local prev = tonumber(redis.call('GET', KEYS[2])) or 0
local limit = tonumber(ARGV[1])
local weight = 1 - tonumber(ARGV[2])
local estimated = curr + prev * weight

if estimated >= limit then
    return 0  -- rejected
end

redis.call('INCR', KEYS[1])
redis.call('EXPIRE', KEYS[1], tonumber(ARGV[3]) * 2)
return 1  -- allowed

window = int(time.time() // 60)
curr_key = f"ratelimit:{user_id}:{window}"
prev_key = f"ratelimit:{user_id}:{window - 1}"
elapsed  = (time.time() % 60) / 60  # fraction into current window

allowed = redis.evalsha(sha, 2, curr_key, prev_key, LIMIT, elapsed, 60)

sequenceDiagram
    participant APP as Application
    participant REDIS as Redis (single-threaded execution)

    APP->>REDIS: EVALSHA sliding_window_script<br/>KEYS: curr_key, prev_key — ARGV: limit, elapsed, window
    Note over REDIS: the whole script runs atomically —<br/>no other client's script can interleave mid-way
    REDIS->>REDIS: GET curr, GET prev
    REDIS->>REDIS: estimated = curr + prev * (1 - elapsed)
    alt estimated >= limit
        REDIS-->>APP: return 0 (rejected)
    else estimated < limit
        REDIS->>REDIS: INCR curr, EXPIRE curr
        REDIS-->>APP: return 1 (allowed)
    end

Token Bucket (MULTI/EXEC)

def is_allowed(redis, user_id, capacity, rate):
    key = f"tokenbucket:{user_id}"
    now = time.time()

    with redis.pipeline() as pipe:
        while True:
            try:
                pipe.watch(key)
                data = pipe.hgetall(key)
                tokens   = float(data.get(b'tokens', capacity))
                last_ref = float(data.get(b'last',   now))

                # refill
                elapsed = now - last_ref
                tokens  = min(capacity, tokens + elapsed * rate)

                if tokens < 1:
                    pipe.unwatch()
                    return False

                pipe.multi()
                pipe.hset(key, mapping={'tokens': tokens - 1, 'last': now})
                pipe.expire(key, int(capacity / rate) + 10)
                pipe.execute()
                return True
            except redis.WatchError:
                continue  # retry on concurrent modification

WATCH/MULTI/EXEC is optimistic concurrency, not a lock: any client is free to read and compute against the key at the same time, and EXEC only fails if some other client's write actually landed on the watched key first.

sequenceDiagram
    participant APP as Application
    participant REDIS as Redis

    loop until EXEC succeeds
        APP->>REDIS: WATCH tokenbucket:{user}
        APP->>REDIS: HGETALL tokenbucket:{user}
        REDIS-->>APP: tokens, last_refill_time
        APP->>APP: refill: tokens = min(capacity, tokens + elapsed * rate)
        alt tokens < 1
            APP->>REDIS: UNWATCH
            APP-->>APP: return False (rejected)
        else tokens >= 1
            APP->>REDIS: MULTI / HSET tokens-1, last=now / EXEC
            alt another client wrote to the key first
                REDIS-->>APP: EXEC aborts (WatchError)
                Note over APP: loop retries — re-reads fresh state, recomputes from scratch
            else no interleaving write happened
                REDIS-->>APP: EXEC succeeds
                APP-->>APP: return True (allowed)
            end
        end
    end

Distributed Rate Limiting

Every API server needs to agree on the same count for the same client — otherwise the limit isn't actually a limit.

graph TD
    classDef bad fill:#e74c3c,stroke:#c0392b,color:#fff
    classDef good fill:#27ae60,stroke:#1e8449,color:#fff
    classDef client fill:#34495e,stroke:#212f3c,color:#fff
    classDef server fill:#3498db,stroke:#2471a3,color:#fff

    CLIENT["Client traffic"]:::client

    subgraph PROBLEM["Without coordination — each server counts alone"]
        S1P["API Server 1<br/>local counter: 100/100"]:::server
        S2P["API Server 2<br/>local counter: 100/100"]:::server
        S3P["API Server 3<br/>local counter: 100/100"]:::server
        RESULT_BAD["Up to 300 requests pass —<br/>3x the intended limit"]:::bad
        S1P & S2P & S3P --> RESULT_BAD
    end

    subgraph SOLUTION["With a central Redis counter"]
        S1S["API Server 1"]:::server
        S2S["API Server 2"]:::server
        S3S["API Server 3"]:::server
        REDIS_C["Redis Cluster<br/>one shared counter per rate-limit key"]:::good
        S1S & S2S & S3S -->|"every check hits<br/>the same counter"| REDIS_C
        REDIS_C --> RESULT_GOOD["Exactly 100 requests pass —<br/>limit enforced globally"]:::good
    end

    CLIENT -.-> S1P
    CLIENT -.-> S1S

Distributed Rate-Limit Check, Step by Step

What Breaks Without Atomicity

sequenceDiagram
    participant S1 as API Server 1
    participant S2 as API Server 2
    participant R as Redis

    Note over S1,R: Non-atomic GET-then-SET — the race
    S1->>R: GET tokens
    R-->>S1: 1
    S2->>R: GET tokens
    R-->>S2: 1
    Note over S1,S2: both saw 1 token available — both decide to allow
    S1->>R: SET tokens 0
    S2->>R: SET tokens 0
    Note over R: 2 requests admitted from a bucket<br/>that only ever had 1 token

Fix: use Lua scripts (atomic, as in the stepper above) or Redis's INCR + TTL pattern — anything that turns "read, decide, write" into one operation Redis executes without interruption, instead of two separate round trips a second server can slip in between.

Redis Cluster Sharding

Route each rate limit key to a consistent shard:

hash_slot = CRC16("ratelimit:{user_id}") % 16384

{} in the key forces Redis Cluster to hash only the bracketed part — all keys for a user land on the same slot, enabling Lua scripts across those keys.

Rate Limit Headers

HTTP/1.1 200 OK
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 42
X-RateLimit-Reset: 1719640800

HTTP/1.1 429 Too Many Requests
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1719640800

nginx Rate Limiting

http {
    # define shared memory zone: 10MB stores ~160k IPs
    limit_req_zone $binary_remote_addr zone=api:10m rate=10r/s;

    server {
        location /api/ {
            # burst=20: allow queue of 20 extra requests
            # nodelay: serve burst immediately (no artificial delay)
            limit_req zone=api burst=20 nodelay;
            limit_req_status 429;
        }
    }
}

AWS API Gateway Throttling

graph TD
    classDef acct fill:#8e44ad,stroke:#6c3483,color:#fff
    classDef stage fill:#3498db,stroke:#2471a3,color:#fff
    classDef method fill:#27ae60,stroke:#1e8449,color:#fff

    subgraph ACCT["AWS account — hard ceiling"]
        A["10,000 req/s<br/>shared across every API in the account"]:::acct
        subgraph STAGE["Deployment stage"]
            ST["1,000 req/s<br/>shared across every route in this stage"]:::stage
            subgraph METHOD["Route / method override"]
                M["100 req/s<br/>this specific route only"]:::method
            end
        end
    end

    A -.->|"stage limit can only be<br/>tighter than the account limit"| ST
    ST -.->|"method limit can only be<br/>tighter than the stage limit"| M

Usage Plans — attach to API keys for per-customer limits:

Usage Plan "free-tier":
  rate:  10 req/s
  burst: 50          # token bucket capacity
  quota: 10,000/day

• rate = token refill rate
• burst = bucket capacity (short spike allowed)
• quota = daily hard limit

Exceeds rate/burst → 429 Too Many Requests Exceeds quota → 429 Limit Exceeded

Rate Limiting Strategies

Combine: per-IP at edge (nginx/CDN) + per-user in app layer + per-endpoint for expensive routes.

Graceful Degradation

Reject vs Queue

Priority Queues for Premium Users

graph LR
    classDef premium fill:#f39c12,stroke:#ba6018,color:#fff
    classDef standard fill:#3498db,stroke:#2471a3,color:#fff
    classDef worker fill:#27ae60,stroke:#1e8449,color:#fff

    IN["Incoming requests"] -->|"plan == premium"| PQ["Premium queue<br/>capacity: 500"]:::premium
    IN -->|"plan == standard"| SQ["Standard queue<br/>capacity: 100"]:::standard
    PQ -->|"drained first"| W["Workers"]:::worker
    SQ -->|"drained only once the<br/>premium queue is empty"| W

def enqueue(request):
    plan = get_user_plan(request.user_id)
    queue = "queue:premium" if plan == "premium" else "queue:standard"

    if redis.llen(queue) >= QUEUE_LIMITS[plan]:
        return 429  # queue full, reject

    redis.rpush(queue, serialize(request))
    return 202  # accepted

Workers drain premium queue first; fall through to standard when idle.

Shedding Strategy

Quick Reference