Back to System design

Rate Limiting: Token Bucket, Leaky Bucket, Sliding Window

medium
Scale: O(1) per check (Redis Lua); ~1M checks/s at scale Storage: O(active keys) — one counter per (identity, window) Cloudflare, Stripe, Twitter
FundamentalsAPI DesignReliability

Rate limiting protects services from being overwhelmed by enforcing a maximum request rate per identity. The difference between graceful degradation and cascading failure under load is usually whether you had a working limiter.

ScaleO(1) per check (Redis Lua); ~1M checks/s at scale
StorageO(active keys) — one counter per (identity, window)

Key Concepts

1
1. What you're protecting against. Accidental abuse (buggy retry loops), intentional abuse (credential stuffing, scraping), capacity exhaustion, and noisy neighbors in multi-tenant systems. Good rate limiting shapes traffic, allocates fair capacity, and stays invisible to legitimate users.
1. What you're protecting against.
2
2. Five algorithms. Token bucket: bucket of capacity C refills at rate R; each request takes 1 token. Allows bursts up to C. Most flexible default. Leaky bucket: queue with constant drain — smooths bursts, no peak. Fixed window: count in [t, t+window]; simple but 2x at boundary. Sliding window log: per-request timestamps in sorted set — accurate, O(N) memory. Sliding window counter: weighted blend of current + previous fixed-window — close to true sliding, O(1). Production default.
2. Five algorithms.
3
3. Distributed correctness. Single-node limiter is trivial. Distributed: each pod's local counter sums above the global limit (over-allowance). Strict global: every request hits Redis — adds latency, makes Redis a SPOF. Hybrid: each pod gets a local lease from the global counter and syncs periodically. Slightly imprecise, linearly scalable. Use Redis + Lua for atomic INCR + EXPIRE.
3. Distributed correctness.
4
4. UX matters. Return 429 Too Many Requests with Retry-After. Headers: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset. Apply at multiple layers — edge (cheap bot defense), gateway (per-API quotas), service (logic-aware). Differentiate authenticated vs anonymous; pre-auth limits on login endpoints prevent credential stuffing.
4. UX matters.429 Too Many RequestsRetry-AfterX-RateLimit-LimitX-RateLimit-Remaining
5
5. In production. Stripe publishes their multi-tier design (load shedding > per-route > per-user). Cloudflare: edge with bounded-load global state. GitHub: per-token limits with helpful 429s. Twitter: per-app and per-user windows with reset times. AWS API Gateway: usage plans with token bucket per API key.
5. In production.

Related Problems

CAP Theorem and PACELCeasyLoad Balancing: L4 vs L7, Algorithms, Health CheckseasyCaching Strategies: Cache-aside, Write-through, Write-backeasySQL vs NoSQL: When to Pick WhicheasySharding Strategies: Range, Hash, Directory, Geomedium

Approach

  1. Define the identity dimensions: user_id, api_key, ip, tenant_id, endpoint. Pick the right combination per limit.
  2. Pick the algorithm. Sliding window counter is the practical default.
  3. Pick the storage. Redis cluster for shared state; local in-pod for hot paths with periodic sync.
  4. Use Lua scripts for atomicity. INCR + EXPIRE in one round-trip avoids the time-of-check-vs-time-of-use race.
  5. Return 429 Too Many Requests with Retry-After, X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset.
  6. Apply at multiple layers: edge (cheap bot defense), gateway (per-API quotas), service (logic-aware).
  7. Tier-aware limits: free tier strict, pro tier generous; config-driven.
  8. Pre-auth limits on login / signup endpoints to defend against credential stuffing.
  9. Emergency override: global circuit breaker that drops low-priority traffic when the system is overloaded.

Algorithms in depth

Token bucket: capacity C, refill R/sec. Each request consumes 1 token. Allows bursts up to C. Most flexible.

Leaky bucket: queue with constant outflow R. Surplus dropped or queued. Hard cap on rate; no bursts.

Fixed window: count in [t, t+window]. Easy to implement, O(1). Boundary problem: 2x rate at window edges.

Sliding window log: per-request timestamps in a sorted set. Accurate, O(N) memory per key. Use for low-volume + high-precision needs.

Sliding window counter: weighted blend of current + previous fixed-window counts. O(1), close to true sliding. Standard default.

Components

  • Limiter middleware in the API gateway or sidecar.
  • Redis cluster (or local cache + periodic global sync).
  • Config service for per-route, per-tier quotas (dynamic, hot-reloadable).
  • 429 response builder with Retry-After / RateLimit headers.
  • Metrics: rejections per route, per tenant; hot-tenant alerts.
  • Bypass / allowlist for internal services.
  • Audit log for rejected requests (for support triage).

Distributed correctness

Naive: each pod maintains its own counter. Sum of pod counters > global limit ⇒ over-allowance.

Strict global: every request hits Redis. Adds latency and Redis becomes a SPOF.

Pragmatic hybrid: each pod gets a local 'lease' from the global counter (e.g. 1/Npods of the budget every second), enforces local quota, syncs slowly. Slightly imprecise but linearly scalable.

Cell-based: shard tenants across cells; each cell enforces independently. Bounded blast radius.

Trade-offs

Token bucket: best human-feel (bursts feel natural).

Leaky bucket: hard cap, no bursts. Good for downstream-rate-limited APIs.

Sliding log: best accuracy, worst memory.

Sliding counter: best practical default.

Edge limiting: cheap and absorbs garbage early; can't see user identity until later.

Service-level limiting: logic-aware, more expensive.

Real-world references

  • Stripe: published rate-limiting design; multi-tier (load shedding > per-route > per-user).
  • Cloudflare: edge rate-limiting with bounded-load global state.
  • GitHub: documented per-token rate limits, generous burst, helpful 429 responses.
  • Twitter: per-app and per-user limits with reset windows.
  • AWS API Gateway: usage plans with token bucket per API key.