Rate Limiting Algorithms: Token Bucket vs Sliding Window

TL;DR. Token bucket is the right default for public APIs: it allows legitimate bursts up to a defined capacity while capping sustained rate, and Stripe, GitHub, and AWS all use it for exactly this reason.¹²³ Switch to sliding window counter when boundary bursts are unacceptable and you need rolling-window accuracy at fixed-window cost. Use GCRA (a leaky-bucket variant storing one timestamp per key) when you want rolling accuracy with zero background processes.⁴⁵ The deciding dimension is burst tolerance: if downstream can absorb short spikes, pick token bucket; if it cannot, pick sliding window or GCRA.

Learning Objectives

• Compare token bucket, leaky bucket, fixed window, sliding window, and GCRA across burst tolerance, memory cost, and implementation complexity.
• Identify the workload characteristics that favor burst-tolerant algorithms over strict-rate algorithms.
• Justify a hybrid approach that layers local token bucket with a global sliding-window service.
• Evaluate Stripe’s and Cloudflare’s production choices and explain why each picked its algorithm.

The Core Trade-off

Rate limiting caps operations per time window. The fundamental tension is burst tolerance vs enforcement accuracy. Token bucket lets idle clients accumulate credit and fire a burst up to capacity C, which is what API consumers want (batch jobs, mobile app launches, retry storms after connectivity loss).¹ Sliding window enforces a strict rolling count, preventing the boundary-burst exploit where a client fires 2N requests in 200 ms across a fixed-window reset.⁶

A second tension hides underneath: state cost vs precision. Fixed window needs one integer per client. Sliding window log needs O(N) timestamps per client. Sliding window counter and GCRA achieve near-exact rolling accuracy with O(1) state, which is why they dominate modern production systems.⁶⁴

The algorithm choice is rarely the bottleneck at scale. The coordination pattern is. Cloudflare runs per-PoP counters because a centralized store would collapse under L7 attack traffic.⁶ Envoy layers a local token bucket before a global gRPC rate-limit service to cut central-store load.⁷

flowchart LR
    subgraph "Burst-tolerant"
        TB[Token Bucket]
        FW[Fixed Window]
    end
    subgraph "Strict-rate"
        LB[Leaky Bucket / GCRA]
        SWC[Sliding Window Counter]
        SWL[Sliding Window Log]
    end
    TB -->|"allows C burst"| Downstream
    LB -->|"smooth at rate R"| Downstream
    SWC -->|"rolling count"| Downstream

Side-by-Side Comparison

The table misleads on one dimension: token bucket’s “exact for sustained rate” hides the fact that a burst of C requests in 1 ms is legal. If your downstream cannot absorb C concurrent requests, token bucket is the wrong choice regardless of sustained-rate correctness.

GCRA’s single-timestamp state makes it the cheapest accurate algorithm, but its TAT math is less intuitive than explicit counters. Teams that need to debug rate-limit decisions in production often prefer sliding window counter for its inspectable two-counter state.⁵

When to Pick Token Bucket

• Public APIs with bursty clients. Stripe (100 parallel req/sec per account in live mode; 25 in test mode)¹⁰, GitHub (5,000 req/hour)², and AWS API Gateway (10,000 RPS sustained with a 5,000-request burst bucket in major regions)³ all use token bucket because normal API usage is inherently bursty.
• Mobile and batch workloads. A mobile app that wakes up after 30 minutes of idle should be allowed to sync immediately. Token bucket accumulates credit during idle periods up to capacity C.
• Per-user isolation where slight overage is acceptable. The downstream can absorb short spikes because it has its own capacity headroom or queuing.
• You need two intuitive knobs. Rate R (sustained) and capacity C (burst) map directly to product decisions: “100 requests per minute, bursts up to 50.”

When to Pick Sliding Window

• Fixed-window boundary bursts are unacceptable. Protecting expensive operations (payment processing, auth endpoints) where 2x burst in 200 ms could overwhelm a fragile downstream.⁶
• High-volume edge rate limiting. Cloudflare chose sliding window counter for billions of daily decisions because it achieves a 0.003% total error rate (requests wrongly allowed or wrongly limited) with two counters per key.⁶
• Anti-abuse and DDoS mitigation. Attackers deliberately exploit window boundaries. Sliding window closes that gap.
• You want GCRA’s accuracy without its clock-skew risk. GCRA’s absolute TAT is sensitive to clock skew (Brandur recommends using Redis TIME for synchronization⁵); sliding window counter’s relative offsets within the current window are typically less affected.
• Audit trail needed. Sliding window log (O(N) memory) stores every timestamp, enabling precise retry-after computation and forensic analysis of abuse patterns.⁹

The Hybrid Path

Most production systems layer algorithms rather than picking one. Envoy’s recommended pattern: a local in-process token bucket absorbs spikes before consulting a global gRPC rate-limit service that runs sliding-window or GCRA logic in Redis.¹¹⁷ The local bucket handles most over-limit traffic without a network round trip; the global service enforces cross-node accuracy.

Stripe runs four limiters in concert: (1) token bucket for per-account request rate, (2) concurrent-request limiter capping in-flight requests at ~20, (3) fleet-usage load shedder reserving capacity for critical methods, and (4) worker-utilization load shedder as last-line defense.¹ No single algorithm covers all four concerns.

flowchart TD
    Req[Incoming request] --> Local[Local token bucket]
    Local -->|over limit| R1[429 immediately]
    Local -->|under limit| Global[Global rate-limit service]
    Global --> Redis[(Redis: GCRA or sliding window)]
    Redis -->|OVER_LIMIT| R2[429 with Retry-After]
    Redis -->|OK| Backend[Forward to backend]

Real-World Examples

Stripe (2017). Token bucket via the Throttled library (Go, GCRA internally) against Redis.¹⁴ Default live-mode limit: 100 parallel requests per second per account (25 in test mode); individual endpoints have a default limit of 25 req/sec.¹⁰ The concurrent-request limiter is triggered much less often than the rate limiter (the 2017 blog cites ~12,000 rejections in a single month) and targets CPU-intensive endpoints.¹ All limiters are behind feature flags, dark-launched before enforcement, and fail open on Redis outage.¹

Cloudflare (2017). Sliding window counter at the edge, processing billions of rate-limit decisions daily.⁶ Mitigated a 400,000 req/sec single-domain attack without degrading service. Counters live in per-PoP Twemcache (not Redis) because the infrastructure already existed for SSL session IDs. Async increment keeps p99 below Redis round-trip time; once a key is known over-limit, edge servers cache the deny verdict locally.⁶

Envoy/Lyft (2017-present). Global gRPC rate-limit service with Redis backend, supporting nested descriptor hierarchies and shadow mode for safe rollout.¹¹ Local token bucket filter recommended as first stage. Two-Redis topology splits per-second limits from per-hour limits to isolate hot-key contention.¹¹

Common Mistakes

Decision Checklist

• Are bursts legitimate (token bucket) or abusive (sliding window / GCRA)?
• Can your downstream absorb C concurrent requests, or must output be strictly smooth?
• What is the memory budget per key? Sliding-window-log’s O(N) is expensive at high limits.
• Do you need cross-node accuracy? If yes, Redis + Lua or a global rate-limit service.
• Is the rate-limiter on the critical path? If yes, fail open on store outage.
• Have you dark-launched (shadow mode) before enforcing?¹¹
• Are you using the store’s clock (Redis TIME) to avoid clock-skew issues with GCRA?⁵

Key Takeaways

• Token bucket is the default for public APIs: it matches how real clients behave (bursty) and how most teams think about limits (rate + burst capacity).
• Sliding window counter gives rolling-window accuracy at fixed-window cost and is Cloudflare’s choice for billions of daily decisions.⁶
• GCRA stores one timestamp per key, needs no background process, and is the modern replacement for classic leaky bucket.⁴⁵
• The coordination pattern (local vs global, Redis vs in-process) matters more than the algorithm at scale.
• Always use Lua EVAL for atomic rate-limit decisions in Redis; never WATCH/MULTI/EXEC under contention.⁹

Further Reading

• Scaling your API with rate limiters (Stripe, 2017) - the canonical 4-limiter production pattern; explains why one algorithm is never enough.
• How we built rate limiting capable of scaling to millions of domains (Cloudflare, 2017) - sliding-window-counter design with accuracy measurements on 400M real requests.
• Rate Limiting, Cells, and GCRA (Brandur, 2015) - the single best GCRA explainer; authored by the Throttled maintainer.
• How Pingora keeps count (Cloudflare, 2023) - count-min sketch for per-key limits at 20M req/sec; 1000x memory savings vs naive HashMap.
• Build 5 Rate Limiters with Redis (Redis) - side-by-side Lua scripts for all five algorithms; explains why EVAL beats WATCH.
• envoyproxy/ratelimit (GitHub) - production reference implementation with descriptor hierarchy, shadow mode, and two-Redis topology.

Flashcards

flowchart TD
    Start[What are you rate-limiting?] --> Q1{Legitimate bursts OK?}
    Q1 -->|Yes| Q2{Need exact rolling window?}
    Q1 -->|No, strict output| Q3{Can caller tolerate delay?}
    Q2 -->|No, simplicity wins| FW[Fixed window]
    Q2 -->|Yes, low volume| SWL[Sliding window log]
    Q2 -->|Yes, high volume| GCRA[GCRA or sliding window counter]
    Q2 -->|Burst up to C| TB[Token bucket]
    Q3 -->|Yes, smooth output| LBS[Leaky bucket shaping]
    Q3 -->|No, drop immediately| LBP[Leaky bucket policing]

References