Rate Limiting Algorithms
You'll learn to
- -Compare token bucket, leaky bucket, and sliding window
A fast, well-cached system is still vulnerable to one thing: a single client (malicious or just buggy) sending far more requests than any reasonable user would. Rate limiting is how you protect the system you've built so far from being overwhelmed by any one source.
The rate limiter sits at the edge, rejecting excess requests before they ever reach application servers.
Imagine a water faucet with a governor that only lets through 10 drops per second, no matter how hard you turn the handle. A rate limiter does the same for API requests. It counts how many requests a user (or IP address, or API key) has made in a time window, and once they hit the limit (say, 100 requests per minute), it blocks any additional requests with a '429 Too Many Requests' error until the window resets. This protects your servers from being overwhelmed by a single abusive user, a bot scraping your site, or a DDoS attack flooding you with millions of fake requests. Without rate limiting, one bad actor can bring down your entire service for everyone.
Examples: Token Bucket algorithm in Redis, AWS WAF rate rules, Cloudflare rate limiting, Stripe's tiered rate limits, Nginx limit_req module
How 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.
Where should rate limiting live: in each application server, or in a shared, central place?
"In each application server, so it doesn't add an extra network hop."
"Centrally: usually at the gateway or a dedicated service backed by a shared store like Redis. If every server tracks its own counters independently, a client can get N times the intended limit just by having its requests spread across N servers by the load balancer. The limiter needs a shared view of a client's request count, not a per-server one."