Token Bucket

The industry default. Your gateway will now allow a burst and then hold the client to a steady rate, and it will charge the expensive /export endpoint more than a cheap read. The 429 it sends back can say, to the second, when the request would have been admitted.

The mechanism

Each client owns a bucket that holds at most capacity tokens. Tokens drip in at refill_rate per second; every request spends cost tokens, and a request that cannot pay is refused. An idle client accumulates tokens, up to the cap, and may spend them all at once. A busy client is held to the refill rate. That gives two independent knobs: capacity is the burst you tolerate, refill_rate is the sustained rate. Fixed and sliding windows cannot separate the two.

Lazy refill: math instead of a timer

Nothing tops buckets up in the background. Each bucket stores two numbers, tokens and last (the time they were computed). When a request arrives:

tokens = min(capacity, tokens + (now - last) * refill_rate)
last   = now
if tokens >= cost: tokens = tokens - cost, allow
else:              refuse

A bucket first seen at time t starts full with last = t. Idle clients cost nothing; there is no timer to run. This is why a token bucket is O(1) in time and memory per client.

A worked trace with capacity 3 and refill 0.5 per second, cost 1, requests at 0, 0, 0, 0, 1, 2, 3, 4 (different from your exercise):

An instant burst of 3, then one request every 2 seconds. The half token at time 1 stays in the bucket, which is exactly why time 2 succeeds.

Telling the client the truth

Cost matters for the last one. A client refused a 5-token request with 2.25 tokens needs (5 - 2.25) / 0.5 = 5.5 seconds, so Retry-After is 6. Quoting the cost-1 wait would send it back too early, to be refused again.

Who runs this

AWS API Gateway documents its throttling as a token bucket (a rate plus a burst). Stripe's engineering writeups describe a token-bucket request limiter backed by Redis. Envoy's local rate limit is configured literally as max_tokens, tokens_per_fill and fill_interval. Whenever an API documents both a rate and a burst, it is a token bucket.

Common mistakes

• Dropping the cap. A client idle over a weekend would bank hundreds of thousands of tokens and legally flood you on Monday. The min is the algorithm.
• Integer tokens. At 0.5 tokens a second, a client polling every second gains int(0.5) = 0 tokens per visit and is locked out forever. Keep the fraction.
• Refilling but not moving last when you refuse. Counting the same elapsed time again on the next request mints tokens from nothing.
• Starting empty, or starting a late-arriving client with a bucket refilled since time zero.
• One cost for everything. Real APIs charge by work; GitHub's GraphQL API charges points per query for exactly this reason.

Your exercise

Capacity 10, refill 0.5 tokens per second, every request costs 1 token except /export, which costs 5. Answer with the four headers as defined above.