Part 5 of 6 · 3 min read
Edge cases and changes
Settings, memory and many servers.
Step 5: edge cases, tests and change requests
Edge cases:
| Case | Behaviour |
|---|---|
| Limit or window of zero or less | Refused by the constructor |
| Time goes backwards (a clock change) | The token bucket would add negative tokens. Clamp the elapsed time to zero |
| A request exactly on a window boundary | Belongs to the new window, by floorDiv |
| A huge number of client keys | The map grows without bound. Remove idle limiters, or expire them |
| A refused request | Counts nothing |
| A client that retries immediately | Refused again, so say how long to wait |
On the second row, the code shown does not guard against a backwards clock. Say so and add the clamp. Real systems use a monotonic clock for exactly this reason.
On the answer to the caller: the book says that a refused HTTP request returns status 429, and that headers should tell the client how many requests remain, what the limit is, and how many seconds to wait before retrying. A boolean is not enough for that, so a richer result such as Decision(allowed, remaining, retryAfterMs) is a natural extension. The token bucket can compute the wait directly from the missing fraction of a token.
Tests to write first: each row of the run table; zero and negative settings; two keys that do not interfere; the boundary at exactly the window length; and the thread test with a total check.
Change requests and the part that changes:
- "Different limits per endpoint and per user tier." A
Rulesclass that maps a key to a limiter factory. The book's rules examples, such as 5 marketing messages per day or login attempts per minute, are exactly such a table. Each rule becomes a small value, andLimiterslooks one up. - "Return the wait time." A
Decisionresult, as above. - "Use the leaking bucket." A new class that holds a bounded queue and a worker that drains it at a fixed rate. It does not fit the
tryAcquireshape exactly, since it delays requests, so it may need a second interface. - "Shared across many servers." The counters must live in a shared store. The book uses Redis and its atomic
INCRandEXPIREcommands, and warns about two problems: race conditions when two servers read and write the counter at once, and the need to synchronize counters across several limiter servers. The fix for the race is an atomic operation in the store, such as a script or a sorted set, and not a read followed by a write. The interface does not change. A newRateLimiterimplementation talks to the store. - "Monitor how many requests are refused." Count refusals in a decorator around any limiter (Level 4, module 5), and report them.
- "Soft limits that warn first." A second threshold and a result with a warning value.
Common mistake
Reading the counter, comparing, and then writing it back in separate steps. Two threads read the same count, and both write the same new value. Make the check and the update one atomic step, as the synchronized methods do.
Interview angle
Answer in your head first, then open it.
Which algorithm would you choose?
Token bucket if short bursts are fine. Sliding window if the limit must hold in any rolling window. Say what each costs.
What is wrong with the fixed window?
A burst at the boundary of two windows can pass twice the limit.
How do you make it thread-safe?
One lock per limiter, around the whole check-and-update, and an atomic computeIfAbsent for the registry.
How does it work across servers?
Counters move to a shared store with atomic updates, and the limiter classes talk to it.
Check yourself: 1. What must a result tell a refused HTTP client? 2. What is the danger of an unlimited map of keys? 3. Which part changes to share counters across servers?
Words you will meet
| Word | Meaning |
|---|---|
| Token | A unit of permission, taken by each request |
| Window | A span of time in which requests are counted |
| Burst | Many requests arriving close together |
| Throttle | To refuse or delay requests above a limit |
| Monotonic clock | A clock that never goes backwards |