Rate Limiting: Token Bucket, Leaky Bucket & Sliding Window

Overview

Rate limiting is the controlled rejection (or delay) of excess traffic so a system stays available, fair, and affordable under load.

Abuse and security. Brute-force login, credential stuffing, scraping, and DoS amplification all look like "too many requests from an identity." Edge/WAF limits stop cheap attacks before origin. Per-route limits on /login, /password-reset, /otp are often tighter than global API quotas.

Fairness and multi-tenancy. One noisy tenant can starve everyone else. Product tiers map cleanly to limits (free = 10 RPS, pro = 100 RPS, enterprise = negotiated). Fairness keys (user_id, API key, tenant_id) matter more than IP alone (NAT, mobile carriers, corporate proxies).

Cost control. Every admitted request costs compute, egress, third-party API dollars, LLM tokens, or DB IOPS. Stripe's public guidance: treat limits as maximums, not targets. Client-side token buckets reduce 429 storms before they start.

Cascading failure prevention. When a dependency slows, retries amplify traffic → retry storms → total outage. Rate limits + circuit breakers + backoff with jitter are a layered defense. Leaky-bucket / outbound shaping protects fragile downstreams (SMS gateways, bank APIs, payment processors).

By the end you should be able to:

1. Show why a fixed window admits up to 2× at the boundary.
2. Contrast sliding log (exact, O(n) memory) vs sliding counter (O(1), approximate).
3. Separate token bucket (burst + sustained) from leaky bucket (smooth egress; police vs shape).
4. Place Redis + Lua for distributed atomicity, and design keys that survive Cluster hash slots.
5. Return 429 + Retry-After (and Limit / Remaining / Reset) — not 401 and not 503.

1. 1

   INCR + EXPIRE → 2× at the seam

   Fixed window only

   Cheap daily/hourly caps. Wrong as the only limiter on a public API — the boundary burst is the interview.

2. 2

   pick burst vs fairness → O(1) per key

   Winner for interactive APIs: token bucket or sliding counter

   Token bucket when legitimate spikes are a feature. Sliding counter when you want recent-history fairness without log memory. Drill: algorithms.

3. ?

   Atomic + layered + honest HTTP

   Redis Lua for the global debit (atomic limiters). Local shed + regional store (gateways). Speak 429, not 503 (headers). Per-tenant quotas so one noisy neighbor cannot eat the fleet (fairness).

Algorithms compared

Fixed window counter

Partition time into aligned buckets (each minute, each hour). Count requests in the current bucket; reset when the clock crosses the boundary.

Pros: O(1) memory, trivial Redis INCR + EXPIRE, easy quotas ("1000/day").

Cons — the boundary burst: a client can send limit requests at 11:59:59 and another limit at 12:00:00 → up to 2× the intended rate in about two seconds. Downstream that cannot absorb 2× will melt.

Use for internal quotas, coarse caps, or layered with a finer limiter (per-second + per-minute).

Sliding window log

Store a timestamp (or unique id + score) for every request in the window. On each request: prune entries older than now - window, count remaining; admit if count < limit.

Pros: exact fairness; no boundary exploit.

Cons: memory O(requests in window). At 10k RPS per key this is expensive. Redis typically uses a sorted set (ZADD / ZREMRANGEBYSCORE / ZCARD) inside a Lua script for atomicity.

Sorted-set members must be unique (timestamp + sequence). Using only the timestamp as member silently drops same-ms requests.

Use for low-volume, high-value paths where exactness matters.

Sliding window counter (approximate / hybrid)

Keep two fixed-window counters — previous and current. Estimate:

estimated = prev_count * (1 - elapsed_in_current / window) + curr_count

Admit if estimated + 1 <= limit, then increment current.

Pros: O(1) memory, near-exact, smooths boundary bursts. Cloudflare published about a 0.003% wrong-decision rate across hundreds of millions of requests with this class of approach.

Cons: approximate; the formula assumes a roughly uniform distribution inside the previous window.

Use as the default for most public APIs at scale.

Token bucket

A bucket holds up to capacity tokens. Tokens refill at rate r (tokens/sec). Each request costs cost tokens (usually 1). If enough tokens → admit and subtract; else reject (or wait).

• Burst = capacity (empty → full instantaneously if idle long enough).
• Sustained rate = refill rate r.
• Idle clients accumulate burst; busy clients are capped at r.

Pros: explicit burst vs sustained knobs; natural fit for developer APIs and SDKs. AWS API Gateway uses token bucket for throttling: rate = refill RPS, burst = bucket size.

Cons: a full-bucket burst can still overwhelm a fragile downstream even if average rate is fine.

Use for user-facing APIs that should tolerate legitimate spikes (page loads firing N parallel calls).

Leaky bucket

Requests enter a queue (bucket). The queue leaks (processes) at a constant rate. If the queue is full → drop (police) or block/wait (shape).

Pros: smooth, constant egress — ideal traffic shaping for SMS, payment batching, fragile partners.

Cons: adds latency under burst (queueing). Not ideal for interactive low-latency APIs if you shape rather than reject.

Where to enforce

Production pattern: layer them. Edge blocks obvious abuse; gateway enforces global / API-key quotas; the service enforces expensive-route costs (search costs 10 tokens).

Local vs global. In-process is fast and needs no Redis; undercounts across replicas (N pods × limit = N× effective). Use for coarse protection. Global (Redis / DynamoDB) is shared truth across the fleet — you need atomic check-and-update (Lua / transactions).

Request path: Client → Edge (cheap IP/path rules) → Gateway (auth, extract key, EVAL Lua against Redis) → Service if allowed; else 429 with standard headers.

Diagrams - step by step

Three small diagrams for rate limiting. Step numbers in the labels give the animation order. The lesson map under Diagram 1 plays those steps.

Diagram 1 - Happy path: edge, gateway, Redis, service

The edge drops cheap abuse. The gateway builds the key and asks Redis to refill and debit in one script. Allowed traffic is forwarded. A deny is 429 with Retry-After. If Redis is down, fail open to a local limiter and alert, except on money paths, which fail closed.

flowchart TB
  A["Step 1 Client request Ready"]
  B["Step 2 Edge WAF applies cheap IP and path rules Ready"]
  C["Step 3 Gateway authenticates and builds the key rl:env:limit:identity:route Ready"]
  D["Step 4 EVALSHA Lua on Redis - refill and debit atomically Ready"]
  E["Step 5 Allowed? Ready"]
  F["Step 6a Forward to the service Ready"]
  G["Step 6b 429 with Retry-After and RateLimit headers Ready"]
  X["Failure path - fail-open to a local limiter plus alert, money paths fail-closed Ready"]
  A -->|continues| B
  B -->|continues| C
  C -->|continues| D
  D -->|continues| E
  E -->|yes| F
  E -->|no| G
  D -->|Redis down| X

Diagram 2 - Failure path: fixed window boundary burst

A fixed window looks empty on both sides of the minute. The client sends the full limit at 11:59:59 and again at 12:00:00, so the service sees about 200 requests in two seconds. A sliding window, a token bucket, or a layered per-second limit removes that seam.

Diagram 3 - Decision: pick the algorithm

Allow bursts and cap the sustained rate with a token bucket. Shape egress to a fragile partner with a leaky bucket. When fairness over recent history matters, use a sliding log at low volume and a sliding counter at high volume. A fixed window is only a coarse daily quota: as the only per-second gate it admits up to 2x at the boundary. A full token bucket still floods a partner that needed a smooth rate.

Redis + Lua for distributed atomicity

Naive GET → decide → INCR is a TOCTOU race: two concurrent requests both see "under limit" and both pass. Redis EVAL runs Lua atomically — no other command interleaves. Prefer Lua over MULTI/EXEC when you need branching on values just read. MULTI/EXEC queues commands but cannot conditionally skip based on intermediate reads without WATCH / retry loops. Full script walk, hash tags, EVALSHA, and fail-open vs fail-closed: Redis + Lua atomic rate limiters. Local vs global vs edge: distributed rate limits across gateways.

Key design

Compose keys from stable identity + scope:

rl:{env}:{limit_name}:{identity}:{route_or_resource}
rl:prod:api:user:42:/v1/search
rl:prod:login:ip:203.0.113.10
rl:prod:stripe_proxy:apikey:<hashed>   # hash secrets; never log raw keys

On Redis Cluster, wrap the identity in hash-tag braces so prev/curr window keys share a slot:

rl:{user:42}:swc

Identity hierarchy: authenticated user > API key > device id > IP. IP alone fails behind CGNAT and shared egress.

HTTP headers and 429

429 Too Many Requests means "slow down" — not auth failure (401/403) and not server error (5xx). Returning 503 trains clients to treat this as capacity failure and fail over, which is the wrong behavior. Header names, Retry-After vs Reset, and client jitter: HTTP 429, RateLimit headers & Retry-After. Per-tenant quotas vs raw RPS: fairness, quotas & noisy neighbors.

Body should be machine-readable, for example:

{ "error": "rate_limited", "retry_after_seconds": 12 }

Clients: exponential backoff with jitter; honor Retry-After when present.

Idempotency interaction. Rate limiters often run before idempotency caches. A 429 may not reserve the idempotency key the same way a processed request does — clients must understand retry semantics for their platform.

Worked examples

Sandboxes below are in-memory. Redis stays in teaching fences (no network in the playground).

Press Run. Snippets must be self-contained — no network, files, or native modules.

Press Run. Snippets must be self-contained — no network, files, or native modules.

Redis sliding window counter (teaching fence — needs Redis)

Hash-tag the base key so both window keys share a Cluster slot. Run as one EVAL so GET/INCR cannot race across pods.

"""
estimated = prev * (1 - t/W) + curr
Admit if estimated < limit, then INCR current window key.
"""
SLIDING_COUNTER_LUA = """
-- KEYS[1] = base key with hash tag, e.g. rl:{user:42}
-- ARGV[1] = window_ms, ARGV[2] = limit, ARGV[3] = now_ms
local base = KEYS[1]
local window = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local curr_id = math.floor(now / window)
local prev_id = curr_id - 1
local curr_key = base .. ':' .. curr_id
local prev_key = base .. ':' .. prev_id
local curr = tonumber(redis.call('GET', curr_key) or '0')
local prev = tonumber(redis.call('GET', prev_key) or '0')
local elapsed = now % window
local weight = 1.0 - (elapsed / window)
local estimated = prev * weight + curr
if estimated >= limit then
  local retry = math.ceil((estimated - limit + 1) / math.max(prev, 1) * window)
  return {0, 0, retry}
end
curr = redis.call('INCR', curr_key)
redis.call('PEXPIRE', curr_key, window * 2)
local remaining = math.max(0, math.floor(limit - (prev * weight + curr)))
return {1, remaining, 0}
"""

def allow_sliding_counter(redis, user_id: str, limit: int, window_ms: int = 60_000) -> dict:
    import time
    base = f"rl:{{{user_id}}}:swc"
    now_ms = int(time.time() * 1000)
    allowed, remaining, retry = redis.eval(
        SLIDING_COUNTER_LUA, 1, base, window_ms, limit, now_ms
    )
    return {
        "allowed": bool(allowed),
        "remaining": int(remaining),
        "retry_after_ms": int(retry),
    }

import Redis from "ioredis";

const SLIDING_COUNTER_LUA = `
local base = KEYS[1]
local window = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local curr_id = math.floor(now / window)
local prev_id = curr_id - 1
local curr_key = base .. ':' .. curr_id
local prev_key = base .. ':' .. prev_id
local curr = tonumber(redis.call('GET', curr_key) or '0')
local prev = tonumber(redis.call('GET', prev_key) or '0')
local elapsed = now % window
local weight = 1.0 - (elapsed / window)
local estimated = prev * weight + curr
if estimated >= limit then
  local retry = math.ceil((estimated - limit + 1) / math.max(prev, 1) * window)
  return {0, 0, retry}
end
curr = redis.call('INCR', curr_key)
redis.call('PEXPIRE', curr_key, window * 2)
local remaining = math.max(0, math.floor(limit - (prev * weight + curr)))
return {1, remaining, 0}
`;

export async function allowSlidingCounter(
  redis: Redis,
  userId: string,
  limit: number,
  windowMs = 60_000,
): Promise<{ allowed: boolean; remaining: number; retryAfterMs: number }> {
  const base = `rl:{${userId}}:swc`;
  const nowMs = Date.now();
  const [allowed, remaining, retry] = (await redis.eval(
    SLIDING_COUNTER_LUA,
    1,
    base,
    windowMs,
    limit,
    nowMs,
  )) as [number, number, number];
  return { allowed: allowed === 1, remaining, retryAfterMs: retry };
}

Redis token bucket Lua (sketch)

-- KEYS[1]=bucket hash; ARGV: capacity, refill_per_ms, now_ms, cost
local capacity = tonumber(ARGV[1])
local refill = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])
local tokens = tonumber(redis.call('HGET', KEYS[1], 'tokens') or capacity)
local last = tonumber(redis.call('HGET', KEYS[1], 'ts') or now)
tokens = math.min(capacity, tokens + (now - last) * refill)
if tokens < cost then
  return {0, tokens, math.ceil((cost - tokens) / refill)}
end
tokens = tokens - cost
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], 3600000)
return {1, tokens, 0}

Distributed pitfalls

Clock skew. App-supplied timestamps across pods disagree → under/over counting. Prefer Redis TIME inside Lua for sorted-set sliding logs, or accept that window IDs from app clocks are approximate. NTP drift of tens of ms is usually fine for second-scale windows; sub-second windows are harder.

TOCTOU races. Separate read/decide/write commands allow concurrent admits past the limit. Fix: single Lua EVAL (or Redis transactions with careful WATCH — Lua is simpler).

Hot keys. One celebrity user / viral endpoint → all traffic hits one Redis key → CPU hot spot. Mitigations: local token bucket in front of Redis (absorb micro-bursts), key sharding with probabilistic admission, Redis Cluster + careful hash tags, tiered limits (coarse local + fine global).

Multi-region. Global Redis cross-region adds latency and split-brain risk. Common pattern: regional limits (strong) + async global quotas (eventual), or sticky users to a region. Edge rate limits (Cloudflare colo-local) are intentionally local unless you design otherwise — document the semantics.

Fail-open vs fail-closed. If Redis is down: fail-open preserves availability (risk: overload); fail-closed preserves safety (risk: total outage). Senior answer: fail-open with local fallback limits + alert; critical money paths may fail-closed.

Costed requests. Not all requests cost 1: search = 10, upload = 50. Token bucket with variable cost models this; fixed window counters need weighted increments. GraphQL: parse query complexity/depth, charge N tokens per field — simple request-count limits are trivial to bypass with nested queries.

Interview Q&A

Pitfalls

Cheat sheet

Go Deeper

• AWS API Gateway throttling (token bucket rate + burst)
• Cloudflare WAF rate limiting rules
• Stripe rate limits (429, concurrency, Retry guidance)
• Stripe Engineering — Scaling your API with rate limiters
• Redis — Build 5 rate limiters with Lua
• Kong Gateway rate limiting plugin
• NGINX — limiting access to proxied HTTP resources (limit_req)
• Arcjet — algorithms compared (fixed, sliding, token, leaky)

Cluster: algorithms · Redis + Lua · gateways · 429 headers · fairness