Rate Limiting
Control ingress throughput and defend upstream services against resource exhaustion, DDoS, and cascading failure.
Overview
“Traffic is bursty. Servers are finite.”
Normal Operating Window
Unregulated ingress forces requests into unconstrained memory queues. When queue depth saturates thread pools, latency breaches timeouts and client retries trigger cascading outages.
Why It Exists
Black Friday Flash Sale: 50,000 RPS vs 500 Max Database Connections
Flash Sale Begins
Traffic spikes instantaneously from 800 req/s to 50,000 req/s.
Queue Saturation
Application threads lock waiting for Postgres connections. TCP accept backlog fills.
Upstream Timeouts
Clients hit their 300ms HTTP read timeout. Gateway drops waiting sockets.
The Retry Storm
50,000 failed clients simultaneously retry requests, doubling the load to 100k RPS.
Total Cascading Outage
PostgreSQL crash under connection exhaustion. Entire cluster health checks fail.
How It Works
Token Bucket
O(1) timeTokens refill into a bucket of capacity B at rate r. Each request consumes 1 token. When empty, requests are rejected. Allows short bursts up to capacity B.
- • Naturally absorbs sudden traffic bursts up to capacity
- • Extremely light memory footprint (2 numbers per key)
- • Industry standard: used by AWS, Stripe, Cloudflare
- • Can allow momentary spikes into downstream databases
- • Requires careful capacity sizing to avoid downstream overload
Prove It: Predict the System Behavior
Bucket Capacity = 100 tokens, Refill Rate = 20 tokens/sec. The bucket is currently full (100 tokens).
An instantaneous flash burst of 250 requests arrives in the exact same millisecond. What happens to the traffic?
All 250 requests are accepted because the system autoscales token generation.
Exactly 100 requests are admitted (HTTP 200) and 150 requests are immediately rejected (HTTP 429).
The first 100 requests pass, and the remaining 150 wait in an internal thread queue for 7.5 seconds.
All 250 requests are rejected because the burst size exceeded the bucket capacity.
Interactive Visualizer
Adjust capacity, refill rates, and packet arrival speeds. Trigger instant bursts or continuous streams to observe token consumption, bucket depletion, and HTTP 429 rejection branches.
Interactive Token Bucket Laboratory
Real-time packet arrival, leak/refill concurrency, and 429 rejection dynamics.
Build It Step-by-Step
The engineering blueprint. Expand each sequential milestone to examine requirements, architectural impacts, common pitfalls, and blueprint pseudocode.
Identify tenant identification key (API key vs IP) and bucket parameters (capacity B, refill rate r).
Determines state cardinality and whether storage fits entirely in L1 memory cache.
type Bucket struct {
capacity int64 // maximum token capacity
tokens int64 // current available tokens
refillRate int64 // tokens generated per unit time
lastRefill time.Time // monotonic timestamp of previous evaluation
mu sync.Mutex
}- Using client IP without proxy awareness (breaks for NAT/universities)
- Floating point token counts that cause precision drift
Code Implementation
Production-ready, idiomatic reference implementations across Go, TypeScript, Python, and Java with sticky language switching, copy-to-clipboard, and source download.
Core Architectural Design Decisions
Invariants & MechanicsUsed time.monotonic() instead of time.time() to protect against clock drift and leap seconds.
Used context manager with self._lock to ensure locks always release even on unexpected exceptions.
import time
import threading
from typing import Tuple
class TokenBucket:
"""Thread-safe Token Bucket Rate Limiter with lazy refill."""
def __init__(self, capacity: float, refill_rate_per_sec: float):
self.capacity = float(capacity)
self.refill_rate = float(refill_rate_per_sec)
self.tokens = float(capacity)
self.last_refill = time.monotonic()
self._lock = threading.Lock()
def allow(self, cost: float = 1.0) -> Tuple[bool, float, float]:
"""
Attempts to consume tokens.
Returns: (is_allowed, remaining_tokens, retry_after_seconds)
"""
with self._lock:
now = time.monotonic()
elapsed = now - self.last_refill
self.last_refill = now
# Replenish tokens
self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
if self.tokens >= cost:
self.tokens -= cost
return True, self.tokens, 0.0
deficit = cost - self.tokens
retry_after = deficit / self.refill_rate
return False, self.tokens, retry_afterEdge Cases & Failure Modes
Investigate real-world production incidents. Expand each failure mode to analyze symptoms, root causes, and defensive engineering mitigations.
Production Considerations
Production checklist covering observability metrics, horizontal sharding, reliability fail-open patterns, and client identity security.
Why it matters: Tracks total accepted vs throttled volume to calculate error budget burn rate.
Why it matters: Exposes real-time reservoir depth to detect systemic under-provisioning.
Why it matters: Ensures the limiter check itself does not introduce tail latency overhead.
Trade-offs
Select an algorithm below to dynamically compare memory footprints, burst tolerance, boundary precision, and distributed suitability.
| Primitive | Memory Footprint | Burst Tolerance | Distributed Readiness |
|---|---|---|---|
| Token Bucket | ~16 | High | Excellent |
| Leaky Bucket | ~64 | Zero | Moderate |
| Fixed Window | ~8 | Flawed | High |
| Sliding Window | ~32 | Moderate | High (weighted) / Low (sorted set ZADD overhead). |
General-purpose REST/GraphQL public APIs and user operations (AWS, Stripe).
High — Continuous monotonic time resolution without window quantization.
High — Gracefully accommodates bursts up to bucket capacity.
Excellent — Trivial to implement in atomic Redis Lua script.
Further Reading
Authoritative industry references, IETF RFC standards, and systems engineering papers.
Scaling your API with rate limiters
How Stripe protects its payment API using token buckets and tiered load shedders.
RFC 6585: Additional HTTP Status Codes (HTTP 429)
The canonical standard defining 429 Too Many Requests and Retry-After response semantics.
Token Bucket Algorithm and Traffic Policing
Original mathematical formalization of leaky and token bucket traffic shaping mechanisms.
Rate Limiting Architecture at Cloudflare
Techniques for globally distributed rate limiting across hundreds of edge data centers without central sync.