Rate Limiting — Not Just "100 Requests Per Second"Token Bucket vs Leaky Bucket vs Sliding Window · Distributed Counters · The 429 Contract

Scenario & Constraints

Design the rate-limiting system for a public API platform (think Stripe / GitHub). 100k+ third-party integrations, peak 1M QPS, per-key limit 100 req/s, total platform capacity 500k QPS. One runaway script can saturate every worker and starve out paying-customer charge requests — which is why rate limiting is a survival baseline, not an anti-scraper add-on.

• Fairness: a misbehaving key must not drag down the others; high-priority calls (create charge) must not be starved by low-priority ones (export report).
• Precision: a 100 req/s limit cannot legally allow 200 requests crammed into the millisecond around a second boundary.
• Low overhead: the limiter latency must be far below the business latency — target p99 < 1 ms.
• Multi-dimensional: limit per user / IP / endpoint / org separately, and compose them (the tightest layer wins).
• Caller-friendly: 429 must be machine-retriable — Retry-After must be present and accurate.
• Limiter failure cannot become business failure: when Redis is down, letting traffic through (fail-open) beats taking down the whole site.

Today: algorithm choice, distributed implementation, accuracy vs performance, and the 429 contract.

High-Level Architecture

graph LR
    C["Client / 3rd-party app"]
    GW["API Gateway
(Envoy / Kong / homegrown)"]
    L1["Local token bucket
(per worker)"]
    L2["Central counter
Redis + Lua"]
    SHED["Load Shedder
(priority drop)"]
    APP["Business service"]

    C -->|"req + API key"| GW
    GW -->|"① fast path: 90% deny/allow"| L1
    L1 -->|"② slow path: periodic sync"| L2
    GW -.overload.-> SHED
    GW -->|✓| APP
    GW -.->|"✗ 429 + Retry-After"| C

    classDef edge fill:#0e2030,stroke:#64c8ff,color:#e8eef5
    classDef store fill:#1a1a30,stroke:#ffb450,color:#e8eef5
    classDef origin fill:#2a1530,stroke:#ff7ab6,color:#e8eef5
    class GW,L1 edge
    class L2 store
    class APP,SHED origin

Gateway uses local token bucket for the fast path; Redis is the central source of truth. Decisions return in under 1 ms.

Key Technical Points

1. Algorithm choice: Token Bucket vs Leaky Bucket vs Sliding Window vs GCRA

Principle: the four algorithms answer different questions — are bursts allowed? is output smoothed? how does the window roll?

# Token bucket core (Python pseudo-code)
def allow(key, capacity, refill_rate):
    now = time.time()
    tokens, last = state.get(key, (capacity, now))
    # lazy refill: top up by elapsed time when we look
    tokens = min(capacity, tokens + (now - last) * refill_rate)
    if tokens >= 1:
        state[key] = (tokens - 1, now)
        return True
    state[key] = (tokens, now)
    return False   # deny, retry_after = (1 - tokens) / refill_rate

2. Distributed limiting: central Redis vs local share vs async aggregation

Principle: a token bucket on one machine is trivial. The hard problem is coordinating a global quota shared across the fleet.

-- Atomic token bucket in Redis (Lua, Stripe-style)
-- KEYS[1]=bucket key  ARGV={capacity, refill_rate, now, cost}
local cap, rate, now, cost = tonumber(ARGV[1]), tonumber(ARGV[2]),
                              tonumber(ARGV[3]), tonumber(ARGV[4])
local data = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(data[1]) or cap
local last = tonumber(data[2]) or now
tokens = math.min(cap, tokens + (now - last) * rate)
local allowed = tokens >= cost and 1 or 0
if allowed == 1 then tokens = tokens - cost end
redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(cap / rate) * 2)
return {allowed, tokens}     -- atomic, no race

3. Multi-dimensional limiting and priority shedding

Principle: a single dimension cannot contain real traffic. One key may be fine, but the sum of all keys saturates an endpoint; an endpoint may be fine, but its downstream DB is dying. Check multiple dimensions independently, tightest wins.

# Multi-dimensional composition (pseudo-code)
def admit(req):
    keys = [
        ("key", req.api_key, 100, 1),
        ("ip", req.ip, 10, 1),
        ("ep", f"{req.api_key}:{req.path}", endpoint_limit(req.path), 1),
    ]
    for kind, k, cap, cost in keys:
        if not bucket_allow(f"{kind}:{k}", cap, refill_for(cap), cost):
            return reject(retry_after_from(cap, k), reason=kind)
    if global_inflight() > SHED_THRESHOLD and priority(req) < HIGH:
        return reject(retry_after=30, reason="overload")
    return ALLOW

4. The 429 contract: let callers back off gracefully

Principle: a limiter is not just a "deny" — it is a machine-readable backoff instruction for the caller. Without it, clients spin in a tight retry loop and pile on a second time.

Extensions & Optimization

• Hot key beyond a single Redis node: shard one high-traffic key across multiple Redis shards (key:0..15), each with a fractional quota, client hashes to shard. Cost: precision loss (local over-admit).
• From hard limits to adaptive limiting: drive the limit from downstream latency / error rate (Netflix concurrency-limits, Google SRE adaptive throttling) — "let more through when healthy, fewer when sick".
• Cross-region global quota: per-region local quota plus per-second async cross-region reconciliation. A strongly-consistent global quota costs too much and rarely earns its keep.
• Cost-weighted requests: not every request is "one token" — weight by endpoint CPU cost (GraphQL query complexity = points charged, CPU-heavy endpoints charge 10).
• Fail-open vs fail-close: when the limiter itself dies, let traffic through (a limiter failure should not become a business failure), but downstream is suddenly exposed — pair with a circuit breaker.

Common Pitfalls / Interview Follow-ups

1. "Why not sliding window log?" — Memory. 1M users × 100 reqs = 100M timestamps, several GB. Counter approximations get to < 5% error.
2. "What if Redis goes down?" — Fail-open and circuit-break; Stripe states this as an iron rule.
3. "Same user, multiple processes — how do they share a local token bucket?" — Per-process buckets don't; you need Redis, or "local sub-quota + async reconciliation".
4. "429 vs 503 — when each?" — 429 = caller over its quota (the caller's problem); 503 = service overloaded (your problem). Confusing them breaks the caller's retry strategy.
5. "How do you compute Retry-After?" — With a token bucket: (1 - tokens) / refill_rate. With a sliding window: milliseconds until the next second tick. And the server must add jitter.
6. "Why is token bucket more popular than leaky bucket?" — Public-API callers naturally arrive in bursts (a cron firing 50 requests at once); token bucket allows that legitimate burst. Strict leaky-bucket smoothing punishes normal users.

Deep Resources

• Stripe Engineering Blog — "Scaling your API with rate limiters" (Paul Tarjan): four limiter classes, Redis Lua, the fail-open principle. The companion GitHub gist has runnable Ruby code.
• Cloudflare Engineering Blog — "How we built rate limiting capable of scaling to millions of domains": distributed limiting at the edge — local decision plus async aggregation.
• Brandur Leach — "Rate Limiting, Cells, and GCRA" (brandur.org): the clearest explainer of GCRA, with a Redis implementation.
• Google SRE Book — Ch 21 "Handling Overload": adaptive throttling, priority shedding, client-side retry budgets.
• Marc Brooker's distributed systems essays: the right intuition for fail-open and backpressure as system properties.

Deeper Questions (click to expand)