System Design & Architecture Interview Question 7: Token Bucket Rate Limit
System Design & Architecture Interview Questions · Test 1 · question 7 of 10
A public API limits each API key to 100 requests per minute using a fixed-window counter that resets at the start of every clock minute. An abusive client sends 100 requests at 12:00:59 and another 100 at 12:01:00. All 200 are accepted within two seconds, and the backend is overwhelmed.
The replacement limiter must let a client send a short burst of up to 20 requests at once, keep each key's long-run average at 100 requests per minute, never allow the double burst at a window boundary, and keep only a small, fixed amount of state per key. What should the team use?
Show answer and explanation
Answer:
A token bucket has two parameters that map directly onto the requirements. The bucket size caps the burst: at most 20 requests can go through back to back. The refill rate fixes the long-run average: tokens return at 100 per minute. Each request spends a token, and requests are rejected when the bucket is empty. Nothing resets at a clock boundary, so a client can never get two full allowances in two seconds. The state per key is just a token count and a last-refill timestamp.
Option B keeps the boundary flaw. A client can still send 50 at the end of one window and 50 at the start of the next. It also halves the throughput allowed for legitimate clients.
Option C does remove the boundary problem, but it stores one timestamp per request (up to 100 per key). That breaks the small, fixed-state requirement, and it still allows all 100 requests in a single burst.
Option D limits concurrency, not rate. Fast requests that finish quickly are never throttled, so a client could send thousands per minute as long as fewer than 100 are in flight at once.
Reference: RFC 2697 - A Single Rate Three Color Marker (token bucket rate and burst size)