CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 5 of 8 · 4 min read

Rate limiting

Give each client a quota.

Rate limiting (or throttling) rejects a request when a quota is exceeded. A service can have several quotas: requests seen, or bytes received, in a time interval. Quotas are usually per user, API key or IP address. A worked example (made up): each API key may send 10 requests per second. A key that sends 12 per second has about 2 per second refused.

The rejection should say why. For HTTP the answer is status 429 (Too Many Requests). The response can name the quota and carry a Retry-After header that says how many seconds to wait, as in Retry-After: 60. A client that plays by the rules stops for that time. This protects the service from non-malicious clients, for example a buggy client stuck in a loop. It is also used to enforce pricing tiers: users who want more resources pay for a higher quota.

UDS adds two cautions. Rate limiting only partly protects against a DDoS attack. Nothing forces a throttled client to stop, and rejecting is not free, since the service still has to open a connection and read part of the request. The only true protection, says the book, is scale: put many services behind one large front service that can reject traffic upstream, with its cost shared among all of them.

And rate limiting differs from load shedding. Shedding uses the local state of one process (its concurrent requests). Rate limiting uses the global state, such as all requests for one API key across all instances.

Rate limiting

Rate limiting rejects a client's requests once the client has used its quota in a period of time.

Example: each API key may make 100 requests a minute. The 101st gets a 429 and a Retry-After header.

Algorithms. Xu lists five, each with a trade-off.

Algorithm How it works Good Weak
Token bucket A bucket holds tokens up to a size. Tokens are added at a steady rate. Each request takes a token or is dropped Simple, memory-light, allows short bursts. Used by Amazon and Stripe Two settings (size and refill rate) are hard to tune
Leaking bucket Requests join a first-in-first-out queue and are processed at a fixed rate. A full queue drops new requests Steady output rate. Used by Shopify A burst fills the queue with old requests and new ones are dropped
Fixed window counter One counter per fixed time window. Drop requests over the limit until the next window Simple, light A burst at the window edges can let through up to twice the quota
Sliding window log Keep a log of request timestamps and drop old ones Exact Uses a lot of memory
Sliding window counter Combine the counts of the current and previous windows, weighted by overlap Smooth and light An approximation

Worked examples (made up unless from the book).

Token bucket. Size 4, refill 2 tokens per second. Six requests arrive together: 4 pass, 2 are dropped. One second later the bucket has 2 tokens again, so 2 more pass.

Fixed window edge. Xu's example: a limit of 5 per minute, reset at each round minute. Five requests arrive just before 2:01:00 and five just after. Both windows are within quota, yet in the minute from 2:00:30 to 2:01:30 ten requests passed, twice the limit.

Sliding window counter. The limit is 100 per minute. Last minute had 80 requests, the current minute has 30 so far, and the minute is 25 percent over, so the current minute. The window overlaps 75 percent of last minute: 80 × 0.75 + 30 = 90. This is under 100, so the next request passes. UDS describes this weighted sum with two counters per API key, which is far lighter than a list of timestamps.

Many servers. With several instances, the counts must be shared. UDS says to use a shared data store, and to use one atomic get-and-increment (or compare-and-swap) instead of a transaction per request, which would be far too slow. Instances can also batch their bucket updates in memory and flush them to the store from time to time. This trades a little accuracy for speed. Xu adds that the rate limiter should not take the whole system down: if its cache fails, requests should still flow (high fault tolerance).

Check yourself: 1. What does Retry-After tell the client? 2. In the token bucket example, why do exactly 4 of 6 requests pass? 3. Why is the fixed window counter unfair at window edges?