Rate Limiting

A balancer is the one place that sees every client, which makes it the natural place to stop any one of them from monopolising the fleet: a scraper in a tight loop, a buggy retry storm, a password-guessing script. In this lesson your balancer starts counting requests per client and answers the surplus with a real 429.

The token bucket

The most common algorithm is the token bucket, the one behind nginx's limit_req, Envoy's local rate limit and most API gateways. Each client owns a bucket.

• The bucket holds at most capacity tokens (the allowed burst).
• Tokens flow in at a steady rate (the long-run average allowed).
• Each request takes one token. With no token to take, the request is rejected.

A new client starts with a full bucket, so a quiet client may burst up to capacity requests at once and is then held to the refill rate. A client that goes idle simply refills, but never above capacity.

No timers: refill when asked

Nobody runs a thread that adds tokens every millisecond. The bucket stores two numbers, its token count and the time it was last topped up, and computes the refill lazily whenever it is touched:

elapsed = max(0, now - last)                 # a clock that steps backwards adds nothing
tokens  = min(capacity, tokens + elapsed * rate)
last    = max(last, now)

Integers, not floats

Rates are written per minute (30r/m in nginx), and a token arrives every 60000 / rate milliseconds, which is rarely a whole number. Floating point drifts, and different languages print it differently, so use a unit in which everything is an integer. Count in ticks, where one token is 60000 ticks. Then a rate of R tokens per minute adds exactly R ticks per elapsed millisecond: 60 tokens per minute is one token per second, which is 60000 ticks per 1000 ms, or 60 per millisecond. Keep ticks in a 64-bit integer: 46 days of milliseconds times 60 is already beyond 32 bits.

capacity 3, rate 60 per minute (R = 60 ticks per ms), one token = 60000 ticks

now(ms)   event            ticks     tokens
   0      first seen       180000    3.000
   0      request          120000    2.000    allowed, 2 remaining
   0      request x2        0        0.000    allowed
 400      request           24000    0.400    denied
1000      request           60000    1.000    allowed, bucket empty again

The 429 on the wire

A rejected request gets a response that tells a well-behaved client when to come back:

HTTP/1.1 429 Too Many Requests\r\n
Retry-After: 2\r\n
\r\n

Retry-After is a whole number of seconds, rounded up: promising 1 second when 400 ms remain is fine, promising 0 sends the client straight back to be refused again. To compute it, take the shortfall 60000 - ticks, divide by the rate (rounding up) to get milliseconds, then round those up to seconds. Allowed responses commonly carry X-RateLimit-Remaining, the number of whole tokens left.

Other shapes

A leaky bucket drains at a fixed speed and smooths output, a sliding window counts the last N seconds exactly at a higher memory cost, and a fixed window is cheap but lets a client send two full bursts straddling a boundary. With several balancers the counters must be shared (Redis INCR), synced periodically, or divided statistically.

Common mistakes

• Float tokens, or truncating a partial refill to zero: at 1 token per minute the bucket gains a tick every millisecond and must not lose it.
• Refilling past capacity after a long idle gap.
• Negative elapsed time when the clock steps back: it must add nothing and must not move last backwards.
• Rounding Retry-After down, or reporting 0.

Your exercise

The starter reads the commands and prints. You write the refill and the request decision. LIMIT <capacity> <per_minute> sets the policy for everyone and forgets all buckets (defaults: 10 and 60). NOW <ms> sets the clock. REQUEST <client> prints 200 X-RateLimit-Remaining: <n> or 429 Retry-After: <s>. STATUS <client> prints the tokens as <whole>.<three digits> without taking one.