Load shedding turns requests away when the servers are full, whoever sent them. A rate limiter decides in advance how much each caller may send, so one caller's flood can't take the system away from everyone else.
One caller can take everything
When traffic is more than the servers can take, every caller suffers the overload together. It doesn't matter that one caller sends four times its share and the others behave: their requests wait in the same queues and fail in the same timeouts.
Try one limit for everyone and one limit per client, on a noisy client and a quiet one. Watch which of the two gets refused.
What a rate limit is
A rate limit says: this caller may send at most this many requests per second (or minute, or day). The limiter counts each caller's requests, by a key such as an API key, a user id or an IP address, and refuses the ones over the limit straight away, with HTTP 429 Too Many Requests and usually a Retry-After header saying when to try again.
| Limit by | Fair to | Weak against |
|---|---|---|
| API key | each partner or app | one key shared by many users |
| User id | each signed-in person | traffic before login |
| IP address | anonymous traffic | many users behind one office or phone network |
A refused request costs the limiter a fraction of a millisecond, and the app servers nothing. Callers that retry a 429 right away just send more traffic to refuse, so good clients honour Retry-After and back off.
Token bucket
The most common algorithm. Each caller has a bucket that holds up to burst tokens and refills at limit tokens a second. Each request takes a token; with none left, it's refused.
| Bucket of 50, refilling at 100 a second | |
|---|---|
| A caller idle for a while | can send 50 at once, then 100 a second |
| A caller sending 100 a second, steadily | is always let through |
| A caller sending 300 a second | gets 100 a second through, and 200 refused |
The burst lets normal, bursty callers through without trouble while the long-run rate stays capped. It needs two numbers per caller: the tokens left and when they were last refilled.
Bursts of 60 requests arrive below, against a limit of 100 a second. The bucket size decides how much of each burst gets through.
A leaky bucket is the token bucket's mirror. Requests join a queue of the same size, and leave it at a fixed rate. Nothing is refused until the queue is full, and what comes out the other end is steady however bursty what went in was. The price is the wait in the queue.
Fixed and sliding windows
A fixed window counts requests per calendar second (or minute) and resets the count when the next one starts. It's the simplest to build: one counter per caller per window. Its flaw is at the boundary: a caller can send the whole limit at the end of one window and again at the start of the next, twice the limit in a moment.
A sliding window counts the requests in the last full window, wherever it ends, so no span of that length ever holds more than the limit. Keeping every request's time (a log) is exact but costs memory; a weighted mix of the current and previous window's counts is a close, cheap approximation.
The limit is 100 a second below, and a client sends 100 requests just before a second ends and 100 just after.
| Algorithm | Allows bursts | Memory per caller | At the boundary |
|---|---|---|---|
| Token bucket | up to the bucket size | two numbers | no boundary; up to the limit plus the bucket in any second |
| Fixed window | the whole limit at once | one counter | up to twice the limit |
| Sliding window (log) | the whole limit at once | one time per request | exact |
| Sliding window (counter) | the whole limit at once | three numbers | a little over (up to about 19% in the labs) |
Limits on many machines
A limiter usually runs on every load balancer or API gateway node (the front door that checks and routes API calls), and a caller's requests are spread over all of them. If each of 4 nodes allows 1 000 a second on its own, the caller really gets 4 000.
| Approach | How | Cost |
|---|---|---|
| Split the limit | each of 4 nodes allows 250 | uneven spreading refuses some requests early |
| Shared counter | every node counts in one store, such as Redis | an extra network call per request, and a store that must stay up |
| Local, synced now and then | count locally, share totals every few hundred ms | callers can briefly go over |
A shared counter also needs a plan for when its store is down: fail open (let everything through, with no limits) or fail closed (refuse everything). Most limiters fail open, since a short spell without limits hurts less than refusing every caller.
Four nodes share one client's traffic below, with most of it landing on one node, as real traffic often does.
Rate limiting or load shedding
The two work together. A rate limit is a promise per caller, set ahead of time, and enforced even when the servers have room. Load shedding is the last line, for when the servers are full whatever the callers are doing.
| Rate limiting | Load shedding | |
|---|---|---|
| Decides by | who is asking | whether there's room right now |
| Protects | other callers, and the bill | the servers |
| Refuses with | 429 Too Many Requests | 503 Service Unavailable |
In the wild
The ideas in this chapter, and where you'll meet them in real systems and interviews:
| Idea | Where you'll meet it |
|---|---|
| API rate limits | GitHub (5 000 requests an hour per token), Stripe, Twitter's API, all answering 429 |
| Limiters in front of servers | AWS API Gateway throttling, NGINX limit_req, Envoy's local and global rate limits, Kong |
| Shared counters | Redis INCR with EXPIRE for fixed windows, Redis sorted sets for sliding logs |
| A classic interview question | "Design a rate limiter": the algorithms, the key, and where the counts live |
Your practice
Inkwell's partners build on its public API, and every contract allows 1 000 requests a second. One partner shipped a bug that calls the API in a loop at more than twice that, and every partner's requests are failing. Put a limiter in front of the API so the well-behaved partner never notices, and the buggy one gets exactly what its contract allows.