Rate Limiter: A Token Bucket in Python

Another classic interview question: "Build a rate limiter that allows short bursts, but keeps a steady rate over time." The usual answer is a token bucket. Each client has a bucket that holds at most 5 tokens. A request spends one token, and tokens drip back at 1 per second. A full bucket lets 5 requests through at once; after that, about one per second gets through.

No timer adds the tokens. A bucket stores just two numbers, tokens and last (the time of its last request), and the refill is worked out when the next request arrives: the seconds since last times the rate, but never more than the bucket holds. For example, a bucket of 10 tokens refilled at 2 per second and emptied at second 50 holds 6 tokens at second 53, and 10 (not 40) at second 70.

When less than one whole token is left, the answer is 429 Too Many Requests with a Retry-After header: the seconds until one token is back, rounded up. Requests name their client in the X-Client-Id header, and the tests move a hidden clock that now() in the starting code returns. These requests from ana, in order, must get these answers:

GET /data   clock 1000  →  200  {"client": "ana", "tokens_left": 4}
GET /data   clock 1000  →  200  {"client": "ana", "tokens_left": 3}
GET /data   clock 1000  →  200  {"client": "ana", "tokens_left": 2}
GET /data   clock 1000  →  200  {"client": "ana", "tokens_left": 1}
GET /data   clock 1000  →  200  {"client": "ana", "tokens_left": 0}
GET /data   clock 1000  →  429  {"error": "Too many requests"}   Retry-After: 1
GET /data   clock 1001  →  200  {"client": "ana", "tokens_left": 0}
GET /data   clock 1001  →  429  {"error": "Too many requests"}   Retry-After: 1
GET /data   clock 1004  →  200  {"client": "ana", "tokens_left": 2}
GET /data   clock 1100  →  200  {"client": "ana", "tokens_left": 4}

Your task: the starting code finds the client's bucket (a new client starts with a full one), saves it and spends a token on every request. Refill the bucket from the seconds since its "last" request, never above CAPACITY, move "last" to now, and when less than one token is left answer 429 with the error "Too many requests" and a Retry-After header.

Assignment
Follow the Coding Tutorial to refill the bucket from the time that passed and refuse a request when it is empty.

Hint
The seconds since the last request are current - bucket["last"]. Use min(CAPACITY, …) so the bucket never overflows. An empty bucket is missing 1 - bucket["tokens"] of a token; divide by RATE and round up with math.ceil.