Rate Limiting Algorithms
ReliabilityHow to throttle API requests fairly and efficiently to protect backends from overload.
A nightclub bouncer only lets in 100 people per hour. Algorithm 1 (Fixed Window): exactly 100 from 8pm-9pm, 100 from 9pm-10pm - but 99 arrive at 8:59pm and 99 at 9:01pm, so 198 rush in around 9pm. Algorithm 2 (Sliding Window): always count last 60 minutes, no such burst. Algorithm 3 (Token Bucket): a bucket fills at 100 tokens/hour, each entry costs 1 token. Early arrivals can have a brief burst if tokens accumulated overnight.
Fixed Window Counter: Divide time into fixed windows (e.g., 1 minute). Count requests per user in each window. Simple to implement with `INCR key EXPIRE 60`. Problem: boundary attack - a user can send 100 requests at 00:59 and 100 at 01:01 (a burst of 200 in 2 seconds).
Sliding Window Log: Store timestamps of each request for the user. On each request, evict timestamps older than the window. Count remaining. 100% accurate, no boundary burst. Problem: memory-intensive (must store all timestamps for active users).
Sliding Window Counter: Hybrid: count requests in the CURRENT window + (fraction of previous window × count in previous window). Very close to sliding window accuracy with fixed-window storage efficiency. Used by Cloudflare.
Token Bucket: Each user has a bucket that fills at N tokens/second (up to a max burst). Each request consumes 1 token. If the bucket is empty, reject. Allows legitimate burst traffic (if a user hasn't used the API for 10 minutes, they have accumulated tokens). Best for APIs with natural bursty usage patterns (user submitting a form, not polling every second).
Leaky Bucket: Requests enter a queue (the "bucket") and are processed at a fixed steady rate. Smooths out bursty traffic into a constant stream. Ideal for protecting downstream services that cannot handle bursts. The downside: requests in queue have unpredictable latency.
- Rate limits are per-user (auth token or IP), not global.
- Always return 429 Too Many Requests with Retry-After header.
- Rate limit at the API Gateway/Load Balancer level to protect all services uniformly.
- Distributed rate limiting needs shared state (Redis INCR + TTL is the standard).
- Implement client-side exponential backoff - do not retry immediately on 429.
Curated Curation & Deep Insights
ScaleDojo CertifiedOur system architects are vetting high-quality, authorized video guides for Rate Limiting Algorithms with zero third-party platform links.
We are preparing premium, zero-competitor deep-dives for Rate Limiting Algorithms. Authorized reading references will appear automatically.