Rate Limiting: Protecting Systems from Themselves

TL;DR: Rate limiting caps how often a principal (user, API key, IP, tenant) can call an API within a time window and rejects the excess with HTTP 429. Token bucket is the default algorithm: it allows bursts up to a configured capacity and refills at a steady rate. Use centralized Redis with a Lua script for atomicity at moderate scale¹, sliding window counters at the edge for global scale², and adaptive concurrency limits (Netflix Vegas-style) when you cannot predict the safe rate in advance³. Always return Retry-After on 429. Separate rate limits (abuse prevention, per-second) from quotas (billing, per-month): they share infrastructure but have different reset semantics.

Learning Objectives

After this module, you will be able to:

• Implement token bucket, leaky bucket, fixed window, and sliding window rate limiters
• Choose a rate-limit key scheme (per-user, per-API-key, per-IP, per-tenant)
• Make a rate limiter distributed without turning Redis into a bottleneck
• Communicate limits to clients via standard HTTP headers and response codes
• Combine rate limiting with circuit breaking, load shedding, and quotas

Intuition

You are the bouncer at a nightclub with a fire-code capacity of 200. You let people in one at a time, counting heads. When the count hits 200, the rope goes up and nobody enters until someone leaves. That is a fixed-window rate limiter.

Now imagine a highway toll plaza. Cars arrive in bursts (rush hour) and trickles (3 AM). The toll booth does not care about bursts as long as the average throughput stays below the road’s capacity. It lets a cluster of cars through quickly, then slows the next batch. That is a token bucket: you accumulate tokens while idle, spend them during bursts, and once they are gone you wait for refills.

Both models solve the same problem: protecting a finite resource from unbounded demand. In software, the resource is your API server, your database connection pool, or your downstream dependency. The demand is every client, script, and bot on the internet. Without a limiter, one runaway script can saturate your entire fleet, and you cannot distinguish it from a DDoS attack until it is too late.

The rest of this chapter gives you the algorithms, the distributed infrastructure, and the production patterns to build that bouncer into your system.

Theory

Why rate limit

Rate limiting defends against three classes of failure that a backend cannot otherwise distinguish⁴:

1. Malicious abuse - credential stuffing, scraping, L7 DDoS.
2. Accidental abuse - a developer’s runaway loop, a retry storm from a broken client.
3. Cost runaway - one tenant’s batch job starving every other customer of shared capacity.

Beyond defense, rate limits enable monetization (free tier: 100 req/min, pro: 1,000 req/min) and SLO protection (if your database handles 50K QPS, you cannot let clients push 80K through the gateway).

Stripe draws a sharp distinction: a rate limiter shapes the rate of well-behaved traffic from a single actor, while a load shedder looks at the whole system and drops low-priority work when resources saturate⁴. Both live in the same request path but answer different questions.

Algorithms

Six algorithms dominate production. They differ in state per key, burst tolerance, and atomicity requirements.

Fixed window. Store one counter per (key, window start). INCR on arrival, reject if over limit. One integer per key. The fatal flaw: at the window boundary, a client can fire N requests at 11:00:59 and N more at 11:01:00, admitting 2N in one second⁵. Figma rejected it for exactly this reason⁶.

Sliding window log. Store a sorted set of every request timestamp. Count members within the window on each request. Exact, but memory is O(limit * keys). Figma calculated that 500 req/day/user over 10,000 users would require ~20 MB in Redis just for timestamps⁶. Use for security-critical, low-volume endpoints (login).

Sliding window counter. Keep counters for the current and previous bucket, then weight them: rate = prev_count * ((window - elapsed) / window) + curr_count². Two integers per key. Cloudflare measured this across 400 million requests and 270,000 distinct sources: 0.003% error rate, average 6% gap between true and observed rate, zero false positives². This is the production-proven choice at edge scale.

Token bucket. A bucket of capacity C refills at rate R tokens/sec. Each request takes one token; reject if empty. Allows bursts up to C and steady rate R. Stripe sets C = 5 * R so a user with a 100 req/sec limit can burst to 500¹. This is the industry default. Use it unless you have a specific reason not to.

Leaky bucket. A queue of capacity C drains at constant rate R. Requests enqueue on arrival; if full, reject. Output rate is constant. NGINX limit_req uses this with zero burst by default⁷. Harsher on clients than token bucket because it smooths rather than absorbs bursts.

GCRA (Generic Cell Rate Algorithm). The leaky bucket formalized as virtual scheduling. State is a single scalar: the Theoretical Arrival Time (TAT). On arrival at time t_now: allow if t_now >= TAT - tau, then set TAT = max(t_now, TAT) + T where T = period/limit⁸. Implemented in redis-cell as the CL.THROTTLE command, benchmarked at ~0.1 ms per command⁹. Reach for GCRA only when you need precise smoothing with minimal state.

flowchart TD
    subgraph Fixed Window
        FW1[Counter per window] --> FW2[INCR on arrival]
        FW2 --> FW3{count > limit?}
        FW3 -->|Yes| FW4[Reject 429]
        FW3 -->|No| FW5[Allow]
    end
    subgraph Token Bucket
        TB1[Bucket: capacity C, refill R/sec] --> TB2[Compute filled tokens]
        TB2 --> TB3{tokens >= 1?}
        TB3 -->|Yes| TB4[Decrement, Allow]
        TB3 -->|No| TB5[Reject 429]
    end
    subgraph Sliding Window Counter
        SW1[prev_count + curr_count weighted] --> SW2[rate = prev * weight + curr]
        SW2 --> SW3{rate >= limit?}
        SW3 -->|Yes| SW4[Reject 429]
        SW3 -->|No| SW5[Allow]
    end

Distributed rate limiting

A single-process counter is trivial. The hard problem is making the counter consistent across a fleet of servers that all see parts of the same user’s traffic.

Central Redis with Lua. The simplest correct design. A Lua script runs atomically inside Redis (single-threaded execution), collapsing read-modify-write into one round trip. Stripe’s production token-bucket Lua is about 26 lines: read tokens and last_refreshed, compute filled tokens, check requested, write back, return allowed/remaining¹⁰. Typical round-trip: 0.1 to 0.5 ms for a local cluster. Redis failure rate in Stripe’s production: 0.01%, and they fail open on those¹.

Dedicated rate-limit service. Envoy’s global rate limit filter calls a gRPC Rate Limit Service (RLS) over a long-lived stream; Lyft’s reference RLS uses Redis as the backend¹¹. Gubernator (Mailgun, open source) runs a cluster of stateless peers, consistent-hashes each key to an owning peer, holds counters in memory, and batches hits in 500-microsecond windows (up to 1,000 requests per batch at peak)¹². For hot global keys, Gubernator’s GLOBAL behavior answers from a local replica and asynchronously gossips hits to the owner, trading exact counts for scale.

Cell-based local counters. Cloudflare evaluates rate limits at 330+ PoPs. Inside each PoP, a Twemproxy/memcached cluster consistent-hashes counters across servers. Once a limiter trips, each server caches the “mitigation active” flag in process memory, so subsequent rejected requests short-circuit without a memcached round-trip. This is how a 400,000 req/sec attack does not crush their own counter layer².

sequenceDiagram
    participant Client
    participant API as API Gateway
    participant Redis
    Client->>API: POST /charges
    API->>Redis: EVALSHA token_bucket.lua user:123
    Note right of Redis: Atomic: read tokens/ts,<br/>compute filled, decrement,<br/>SETEX with TTL
    Redis-->>API: {allowed=1, remaining=99}
    API-->>Client: 200 OK + RateLimit r=99, t=30
    Client->>API: POST /charges (burst x100)
    API->>Redis: EVALSHA token_bucket.lua user:123
    Redis-->>API: {allowed=0, remaining=0}
    API-->>Client: 429 Too Many Requests + Retry-After: 5

Where to enforce

Most production stacks layer limits at multiple points, trading context for reach:

flowchart LR
    Client --> Edge[Edge / CDN<br/>IP + ASN limits<br/>Cloudflare 81M+ req/s]
    Edge --> GW[API Gateway<br/>Token bucket per API key<br/>Redis Lua]
    GW --> Svc[Service<br/>Adaptive concurrency<br/>Envoy filter]
    Svc --> DB[(Database<br/>Per-role connection limit<br/>statement_timeout)]

The edge has the best blast-radius (rejects before your infrastructure even sees the traffic) but the least context about the user’s tier or session. The gateway has auth context but adds a hop. The service has the most context but protects only itself. Database-level throttles (Postgres statement_timeout, per-role connection limits) are the last line and most correct but the latest to fire¹³.

Client behaviors

RFC 6585 defines HTTP 429 Too Many Requests and permits (via “MAY include”) a Retry-After header; the RFC’s SHOULD applies to explanatory details, not Retry-After itself¹⁴. The IETF draft-ietf-httpapi-ratelimit-headers-10 (2025) standardizes two structured fields: RateLimit-Policy (quota and window) and RateLimit (remaining and reset)¹⁵.

Legacy headers are widespread: GitHub returns x-ratelimit-limit, x-ratelimit-remaining, x-ratelimit-used, x-ratelimit-reset (UTC epoch seconds)¹⁶. Slack returns 429 with a Retry-After header (e.g., 30 seconds)¹⁷.

Well-behaved clients implement capped exponential backoff with full jitter: sleep = random(0, min(cap, base * 2^attempt)). Marc Brooker’s 2015 AWS simulation showed full jitter reduced total call count by more than half versus un-jittered backoff across 100 competing clients¹⁸. Most AWS SDKs ship this today.

Sustained 429 should trip a client-side circuit breaker, not just sustained 5xx. Tight-looping through 429 is just as load-inducing as tight-looping through 503.

Adaptive and concurrency limits

Static rate limits become stale as topology changes (auto-scaling, partial outages, code pushes that change latency). Netflix Concurrency Limits (2018) infers the safe operating point from measured latency using a TCP-Vegas-style gradient³:

gradient = minRTT / sampleRTT

A gradient of 1 means no queuing. Less than 1 means a queue has formed. The limit updates as newLimit = currentLimit * gradient + sqrt(limit). After convergence, the algorithm holds the limit where p99 latency just starts to rise. Netflix reports it stops retry storms from cascading and rejects excess load in sub-millisecond time³.

Envoy ships the same idea as the adaptive_concurrency HTTP filter with a Gradient Controller: measures minRTT every 60 seconds (with 0 to 10% jitter to avoid cluster-wide synchronization), then adjusts the concurrency limit each sample window¹³.

stateDiagram-v2
    [*] --> Probing
    Probing --> Probing: gradient ~= 1, limit += 1
    Probing --> MeasuringMinRTT: every 60s +/- jitter
    MeasuringMinRTT --> Probing: new minRTT sampled
    Probing --> Backoff: gradient < 1 (queue detected)
    Backoff --> Probing: limit = gradient * old + sqrt(limit)

Real-World Example

Stripe’s four-layer rate limiting architecture is the most thoroughly documented production system in this space¹¹⁰.

Layer 1: Request Rate Limiter. Token bucket, capacity = 5x replenish rate, keyed per user. Implemented as a ~26-line Lua script against Redis (ElastiCache). The script reads tokens and last_refreshed, computes filled tokens based on elapsed time, checks if the request fits, decrements, and writes back with a TTL of 2x fill_time. The entire read-modify-write is atomic because Redis runs Lua single-threaded.

Layer 2: Concurrent Request Limiter. A Redis sorted set of in-flight request IDs per user. ZCARD to check count, ZADD to enter, ZREM on completion, ZREMRANGEBYSCORE to reap crashed requests whose timestamps exceed a timeout. This catches users who open thousands of slow connections rather than sending fast bursts.

Layer 3: Fleet Usage Load Shedder. Identical to the concurrent limiter but with a global key. Reserves a fraction of workers for critical requests (creating charges) when the fleet is under pressure.

Layer 4: Worker Utilization Load Shedder. Local per-process. When worker utilization exceeds 0.8, linearly sheds traffic (test-mode first, then GETs, then POSTs, critical last), ramping over 120 seconds to avoid flapping¹⁹.

Key engineering decisions:

• Fail open on Redis errors. The limiter must not take down the API. Redis failure rate: 0.01%¹.
• Dark launch every new limiter. Measure what it would have blocked, tune thresholds, then enforce.
• Kill switch per limiter (feature flag) so ops can disable any tier during an incident.
• Lua over MULTI/WATCH. Optimistic concurrency collapses under contention; Lua is always atomic.

Per their blog post, Stripe reports rejecting “millions of requests this month” of test-mode traffic alone through Layer 1, and 12,000 requests/month through the concurrent limiter¹.

Trade-offs

Algorithm

Enforcement point

Common Pitfalls

Exercise

Design a rate limiter for a public API with the following requirements: 1,000 requests/minute per API key, burst allowance of 200 requests, 100 million active keys, two regions, and a 30-second SLO for limit changes taking effect. Specify: algorithm, key scheme, storage, where it runs, and what headers you return on throttle.

HTTP/1.1 429 Too Many Requests
Retry-After: 4
RateLimit: "default";r=0;t=4
RateLimit-Policy: "default";q=1000;w=60

Key Takeaways

• Token bucket is the default rate-limit algorithm. Start there and rarely regret it. Set capacity to 3 to 5x the refill rate for burst tolerance.
• Per-key Redis counters with Lua scripts work until Redis becomes the bottleneck (~100K req/s per primary); then cell-based or sharded approaches take over.
• Always return Retry-After on 429. Without it, clients retry in tight loops and amplify the overload.
• Separate rate limits (abuse prevention, per-second reset) from quotas (billing, monthly reset) even if they share infrastructure. They have different reset semantics and audit needs.
• Layer your defenses: coarse at the edge, precise at the gateway, adaptive at the service. No single layer is sufficient.
• Adaptive concurrency limits (Netflix Vegas-style) self-tune and eliminate the need to guess a service’s RPS ceiling. Use them for service-to-service calls under auto-scaling.
• The algorithm is a two-week project. The policy (per-user, per-endpoint, per-tenant, tiered) is forever. Invest in the policy framework.

Further Reading

• Stripe: Scaling your API with rate limiters - The canonical production writeup covering token bucket, concurrent-request limiter, load shedder, and worker utilization; includes fail-open posture and dark-launch methodology.
• Cloudflare: How we built rate limiting capable of scaling to millions of domains - Sliding-window accuracy math (0.003% error on 400M requests), PoP-local architecture, and why CAS was rejected under attack load.
• Figma: An alternative approach to rate limiting - Sliding window counter derivation, memory calculations, and the shadow-ban technique for persistent attackers.
• AWS Architecture Blog: Exponential Backoff and Jitter - Marc Brooker’s 2015 post establishing full jitter as the industry standard; includes simulations showing >50% retry-load reduction.
• Netflix: Performance Under Load - Adaptive concurrency limits, the gradient algorithm, and why static RPS limits become stale under auto-scaling.
• Brandur Leach: Rate Limiting, Cells, and GCRA - The definitive GCRA explainer; one scalar per key, no drip process, rolling window inherent.
• IETF draft-ietf-httpapi-ratelimit-headers-10 - The modern standard for RateLimit and RateLimit-Policy header fields, replacing the X-RateLimit-* chaos.
• GitHub REST rate limits docs - Tiered primary + secondary limits, the full header contract, and how GitHub layers 5+ different limit dimensions on one API.

Flashcards

References