Rate limiting: one token per request

An API's servers can handle about 1,000 requests a second, shared by thousands of customers. One customer ships a bug: a script that retries in a tight loop, 2,000 times a second. Now more work arrives than the servers can do, and the queueing lesson showed what a line does once the load passes 100%: it grows without end, until everyone times out.

A rate limiter at the door turns away each client's requests over its agreed rate at once, with a short reply that costs almost nothing. The buggy script gets errors; everyone else gets fast answers. This lesson takes apart the token bucket the queueing lesson met in passing, then its rivals, and what a client should do when told no.

rate limit

An agreed rate for one client, such as 100 requests a minute per API key. A rate limiter turns away the requests over it.

token bucket

Holds up to capacity tokens and refills at rate tokens a second. A request spends one token, or is rejected if the bucket holds less than one, so a burst of up to capacity requests passes at once.

fixed and sliding windows

Limiters that count requests per window of time. A fixed window resets on the clock, say each minute; a sliding window looks back one window from now.

leaky bucket

A queue that drains at a fixed rate. Requests wait their turn, and are rejected only when the queue is full.

429 Too Many Requests

The HTTP status for a rejected request, often with a Retry-After header saying when to try again.

A token bucket remembers two numbers per client: its tokens, and the time, last, when it counted them. No timer drips tokens in; when a request arrives at time t, the bucket works out what a drip would have added since:

tokens = min(capacity, tokens + rate × (t − last)), then last = t.

With at least one token, the request spends it and goes through; otherwise it is rejected. The min stops a quiet client saving up: however long it waits, it comes back to at most a full bucket.

That is O(1) work per request, and a million clients' buckets fit in tens of megabytes. A bucket idle for capacity ÷ rate seconds is full again, so a limiter can forget idle clients and hand them a full bucket when they return.

The same spike against a smaller bucket: 3 tokens, refilling at 1 a second, so the sums are easy. The player stops at each close call: take the tokens left after the last request, add the seconds since, cap at 3, and ask whether that makes one token.

8 of the 10 got through. The two turned away came mid-spike, with 0.88 tokens at 4.01 s and 0.53 at 4.66 s: at 1 token a second, the bucket can't keep up with 3 requests a second.

Here it is in code: capacity 2, a refill of 1 token a second, and three requests at time 0, then three at time 3, each answered ok or 429.

def limit(times, capacity, rate):
    tokens = capacity
    last = 0
    replies = []
    for t in times:
        tokens = min(capacity, tokens + rate * (t - last))
        last = t
        if tokens >= 1:
            tokens -= 1
            replies.append('ok')
        else:
            replies.append('429')
    return replies

result = limit([0, 0, 0, 3, 3, 3], 2, 1)
print(' '.join(result))

Choosing the numbers. The rate is the load you will pass on for good: a client's fair share, and for a bucket guarding a whole service, comfortably below what it can sustain, since latency explodes near full load. The capacity is the burst you will absorb at once. Real clients are bursty (one page load can fire a dozen calls), so a capacity of 1 turns honest users away, while a huge one lets a flood through before the rate bites.

Other ways to count. The rivals differ in what they remember:

• A fixed-window counter keeps one count per client per minute on the clock, reset when the minute turns. The cheapest, but the reset is a cliff, as the first mistake below shows.
• A sliding-window log keeps the time of each request it let through in the last window, and allows a new one only if fewer than the limit are there. Exact, but a limit of 1,000 an hour for a million clients can mean a billion timestamps.
• A sliding-window counter keeps this minute's count and the last one's, weighting the old one by how much of it still lies in the past 60 seconds: 15 seconds into a minute, three quarters. Two numbers, and close when traffic is fairly even.
• A leaky bucket sends queued requests on at a fixed rate: perfectly smooth output, but requests wait, where a token bucket passes a burst at once.

Many servers, one limit. A limiter usually runs in the API gateway, keyed by API key, user or IP address (the crudest: many users share an address, and an attacker can use many). A big service runs many gateways, and a key's limit must hold across them all. Keep the buckets in a shared store, refilling, checking and spending in one atomic step, since a separate read and write is a race (the concurrency lesson); let each machine enforce its share, with no extra round trip; or send each key to the one limiter that owns it, picked by consistent hashing.

What the client sees. A rejected request gets a 429, cheap to send and clear about why. A well-behaved client waits as long as its Retry-After header says. With no header it backs off exponentially, waiting about 1 s, then 2, then 4, up to a cap, so a struggling service gets more room each time. And it adds jitter, a random part of each wait, because clients rejected together would otherwise all retry together.

• A rate limiter turns away requests over a client's agreed rate at once, with a 429, so no one client can push a service to where its queues explode.
• A token bucket keeps two numbers per client and refills lazily from the time since it last counted: O(1) per request.
• In any t seconds it passes at most capacity + rate × t. Set the rate comfortably below what the service sustains, and the capacity to the bursts you will absorb.
• A fixed window can pass twice its limit across a boundary, a sliding log is exact but stores every request, a sliding counter estimates, and a leaky bucket smooths traffic by making it wait.
• Across machines, share one atomic count, split the limit, or route each key to one limiter. Clients honour Retry-After and back off exponentially, with jitter.
• Next: system design and An API that survives a spike put a limiter in front of a whole service. Practise keeping state per key and spacing out work with Least Recently Used Cache and Schedule Tasks with a Cooldown.