System Design HLD-12.03
Rate limiting algorithms
Token bucket, leaky bucket, fixed window, sliding log and sliding window counter compared, plus distributed limits in Redis, 429s and headers.
The big idea
Your public API serves thousands of customers. One of them deploys a buggy script that calls you 5,000 times a second. Without limits, that single customer uses most of your capacity and everyone else's requests slow down or fail. A rate limiterA mechanism that caps how many requests a client (user, API key, IP address) may make in a period, rejecting or delaying the excess. caps each client's request rate, so one client's mistake or abuse cannot become everybody's outage. It also protects against credential stuffing, scraping and runaway retries, and turns pricing tiers ("1,000 calls a minute on the free plan") into something enforceable.
The interesting part is how you count. "10 requests per second" sounds precise, but should a client that was quiet for a minute be allowed a quick burst of 20? Is it per calendar second, or any one-second span? Must the count be exact, or is close enough fine if it uses far less memory? Each algorithm answers these questions differently.
Think of a ticket barrier at a station. A token bucket is a turnstile that lets you through if there is a token waiting, with tokens added at a steady rate and a few allowed to pile up for a rush. A leaky bucket is a queue in front of a single gate that opens at a fixed pace, however big the crowd.
How it works
Step 1: Token bucket
A token bucketA rate limiter that adds tokens to a bucket at a fixed rate up to a maximum; each request spends a token, so short bursts up to the bucket size are allowed while the long-run rate is capped. has two settings: a refill rate (the sustained limit, 10 per second) and a capacity (the largest burst, 20). Each request spends one token; no token, no service. It needs only two numbers per client, the token count and the last refill time, and it matches how real clients behave: idle for a while, then a burst of page loads. It is the most widely used algorithm, and the one in the case studies below.
Step 2: Leaky bucket
A leaky bucketA rate limiter that queues requests and releases them at a fixed rate; requests that do not fit in the queue are rejected, so output is perfectly smooth. puts requests in a queue that drains at a fixed rate. Output is perfectly smooth, which is ideal for protecting something that hates bursts, such as a legacy system or a hardware device, but bursts are delayed rather than served quickly, and a full queue rejects new arrivals. Many implementations use the "leaky bucket as a meter" form, which behaves much like a token bucket without actually queuing.
Step 3: Window counters
- Fixed window: count requests per calendar interval, such as per second or per minute. One counter per client per window: trivially cheap, often a Redis
INCRplusEXPIRE. The flaw is the boundary: 10 requests at 0.9 s and 10 more at 1.1 s are both allowed, so 20 pass in 0.2 seconds. - Sliding log: keep the timestamp of every accepted request and count those in the last second. Exact, but memory grows with the limit: a limit of 10,000 per hour means storing up to 10,000 timestamps per client.
- Sliding window counter: keep fixed-window counts but estimate the sliding window by weighting the previous window by how much of it still overlaps. With 42 requests in the previous minute and 18 so far in the current one, 15 seconds in: 42 x (45/60) + 18 = 49.5. Two counters per client, and close to exact.
Try it
Try this:
- With the token bucket, find the sudden burst at 8 s: up to 20 are accepted at once, then the rest are rejected. Lower the bucket size to 5 and compare.
- Switch to fixed window and look at the peak near 20 s, where the burst straddles a window boundary. The peak in any one-second span is well above 10.
- Compare sliding log and sliding window counter. They behave almost identically, but one stores a timestamp per request and the other two counters.
Going deeper
What to limit by
Limits are applied per key: user id or API key for authenticated traffic, IP address for anonymous traffic (careful: many users can share one IP behind a corporate network or carrier NAT), and sometimes per endpoint, because a search costs far more than a profile read. Layer them: a generous global limit at the edge against floods, tighter per-customer limits in the API, and a cap on concurrent requests for expensive endpoints.
Distributed rate limiting
With 50 API servers behind a load balancer, each server's local counter sees only 1/50 of a client's traffic. Options:
- Central store: keep counters in Redis and update them atomically, usually with a small Lua script that reads, refills and decrements in one step. Accurate, but adds a network hop to every request, and Redis becomes a dependency to protect.
- Local limits with a share of the budget: each of N servers allows limit / N. No coordination, but uneven load balancing makes it inaccurate.
- Approximate and eventually synchronized: count locally, sync periodically. Cheap and fast, slightly permissive.
Decide what happens when the limiter's store is down: usually fail open (allow traffic) rather than turning a Redis outage into a full API outage.
Telling clients
Rejected requests should get HTTP 429 Too Many Requests, ideally with a Retry-After header, and successful ones can carry headers describing the limit and how much is left (commonly X-RateLimit-Limit, X-RateLimit-Remaining and a reset time). Well-behaved clients then back off with jitter ( Timeouts, retries, backoff and jitter ) instead of hammering.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Token bucket | APIs that should allow short bursts and cap the sustained rate | Bursts can still hit a backend all at once |
| Leaky bucket (queue) | Protecting systems that need perfectly smooth input | Adds latency; bursts wait instead of being served |
| Fixed window | Simplicity and minimal memory, coarse quotas per day or month | Up to twice the limit across a window boundary |
| Sliding log | Exact limits with low request counts | Memory per request; expensive at high limits |
| Sliding window counter | Near-exact limits at scale with two counters | Approximation; assumes even spread within the previous window |
Common mistakes
- Limiting only by IP and blocking whole offices or mobile carriers behind shared addresses.
- Per-server local counters behind a load balancer, giving each client N times the intended limit.
- Rejecting with 500 or 503 instead of 429, so clients cannot tell they should slow down.
- Failing closed when the limiter's store is down, turning a Redis blip into a full outage.
- Treating every endpoint the same when some cost a hundred times more than others.
In the wild
Stripe
Scaling your API with rate limiters (opens in a new tab)Stripe describes four kinds of limiters in production. A request rate limiter restricts each user to N requests per second; a concurrent requests limiter caps how many requests can be in progress at once (for example 20), which helps with resource-intensive endpoints whose impatient users retry; a fleet usage load shedder keeps a share of the fleet available for the most important requests; and a worker utilization load shedder sheds lower-priority traffic as a last line of defense. The post implements these with the token bucket algorithm in Redis.
Cloudflare
How we built rate limiting capable of scaling to millions of domains (opens in a new tab)Cloudflare needed rate limits across a huge anycast network, where a central data store would add too much latency. It uses the sliding window approximation, weighting the previous window by its overlap, and its post works an example: 42 x ((60 - 15) / 60) + 18 = 49.5 requests. Counters live in a memcache cluster inside each data center. In its analysis of real traffic, only 0.003 percent of requests were wrongly allowed or rate limited, with an average 6 percent difference between the real and approximate rate.
Check yourself
-
A token bucket has capacity 20 and refills at 10 per second. A client idle for a minute sends 30 requests at once. Roughly how many are accepted immediately?
Show answer
B. 20 The bucket holds at most 20 tokens no matter how long the client was idle.
-
Why can a fixed window limiter of 10 per second let 20 requests through in 0.2 seconds?
Show answer
B. 10 can arrive at the end of one window and 10 at the start of the next Counts reset at the boundary, so a burst straddling it gets two full allowances.
-
Your API runs on 40 servers and each keeps its own local counter set to the per-client limit. What is the effective limit?
Show answer
B. Up to 40 times the intended limit Each server sees only part of the traffic and allows a full limit, so totals multiply.
-
What should a rate limited client receive?
Show answer
B. HTTP 429 with a Retry-After hint 429 tells clients they are being limited and when it is reasonable to retry.
Recap
- Rate limits cap each client's requests so one client cannot degrade everyone.
- Token bucket allows bursts up to its capacity and caps the sustained rate; leaky bucket smooths output.
- Fixed windows are cheap but leak at boundaries; sliding logs are exact but costly; sliding window counters approximate well with two counters.
- Distributed limits need shared counters (often Redis) or accepted approximation, and should usually fail open.
- Return 429 with Retry-After and limit headers so clients can back off.
Next up
- Crack the system design round learning path