Token bucket rate limiter.
Refill by elapsed time, spend tokens per request, allow bursts up to capacity, and tell a rejected client when to retry.
Build the token bucket from Day 3, section 2.4: every key (a user, an API key) has a bucket that holds up to capacity tokens and refills at rate tokens per second. A request costs tokens_requested tokens. If the bucket has enough, spend them and allow the request; otherwise reject it.
Implement TokenBucketLimiter(rate, capacity, clock):
| Method | Returns |
|---|---|
is_allowed(key, tokens_requested=1) |
True and spends the tokens, or False and spends nothing |
tokens(key) |
tokens the key has right now, after refill (a float). Feeds X-RateLimit-Remaining |
retry_after(key, tokens_requested=1) |
seconds until that request would be allowed: 0.0 if it would be allowed now. Feeds Retry-After on a 429 |
Rules the tests check:
- A key you have never seen starts with a full bucket.
- Refill is lazy: there is no background timer. On each call, add
elapsed_seconds × ratetokens, capped atcapacity. Keep the fractional part: 0.25 s at 2 tokens/s is half a token. - A rejected request spends nothing.
- Keys are independent.
- Read time only through
clock.now()(seconds, a float). Tests pass aFakeClockthey move by hand, so they never sleep.
A limiter that calls time.time() directly can only be tested with real sleeps, which makes tests slow and flaky. Passing the clock in is the same move interviewers look for when they ask "how would you test this?" (Day 3, Question 7).
Write your code, then run 4 example tests and 9 hidden tests. Each run is limited to 8 seconds: an infinite loop gets stopped and Python restarts, your code stays.