Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Token bucket by hand (20 minutes)
A bucket has capacity 3 and refills 1 token per second. It starts full. Requests arrive: 4 at 0 s, 1 at 1 s, 2 at 2 s, 5 at 6 s. Mark each as pass or refuse.
Done when: a table with tokens before and after each event and a verdict for all 12 requests.
Hint
Add tokens first (up to the capacity), then spend them.
Easy 2: Leaky bucket by hand (20 minutes)
A queue holds 4 and drains 2 per second. 7 requests arrive at 0 s. Which are queued, which are refused, and when is each processed?
Done when: a list of queued and refused requests with processing times.
Hint
Queue holds 4, so 3 requests are refused. Processing is 2 per second.
Easy 3: Pick the algorithm (20 minutes)
Choose an algorithm for each: a public API that tolerates bursts, a payment service that needs an even flow, a login endpoint where exactness matters, a service with 50 million users and little memory.
Done when: four choices, each with a reason and a weakness.
Hint
Think "bursts", "even flow", "exact" and "small memory".
Medium
Medium 1: The window edge (30 minutes)
A fixed window allows 60 requests per minute. A client sends 60 at 10:00:55 and 60 at 10:01:05. Count the requests in the 10 seconds from 10:00:55 to 10:01:05. Then run the same requests through a sliding window log and count how many pass.
Done when: two counts and a statement of the excess in the fixed case.
Hint
A log counts requests in the last 60 seconds from each new request.
Medium 2: Sliding window counter (30 minutes)
The limit is 20 per minute. The previous minute had 18 requests, the current minute has 6 so far, and 25 percent of the current minute has passed. Compute the estimate and give the verdict. Then redo it when 75 percent has passed.
Done when: two estimates with working and two verdicts.
Hint
Estimate = current + previous × (1 − share of the current minute passed).
Medium 3: Memory for counters (30 minutes)
A service has 20 million users. Compare the memory of a token bucket (two numbers of 8 bytes), a fixed window counter (16 bytes) and a sliding window log with a limit of 200 per minute at 8 bytes per time stamp.
Done when: three figures in MB or GB and a note about which fits in one machine with 16 GB.
Hint
Users × bytes per user, then convert to MB or GB.
Hard
Hard 1: Spot the race (45 minutes)
Write the steps of a limiter that reads a counter, checks it and writes it back. Show a timeline with two overlapping requests that both pass with the limit set at 10 and the counter at 9. Give two fixes and the trade-off of each.
Done when: a timeline table, two fixes and a trade-off for each.
Hint
Both requests read before either writes.
Hard 2: Design the limit rules (45 minutes)
A photo app has endpoints for login, upload, view and comment. Write a rule for each: who is counted (user, IP, API key), what limit, which algorithm and what the caller sees when refused. Add one rule for the whole system.
Done when: a table of five rules with the four columns and one sentence defending the login rule.
Hint
Choose a different key for each rule. Logins by IP, uploads by user.
Hard 3: Fail open or closed (50 minutes)
The counter store goes down for 3 minutes at peak, 30,000 requests per second. Describe what happens with fail open and with fail closed on a public read API, and on a payment API. Estimate the number of requests affected in each case and propose a safer middle path.
Done when: four outcomes with request counts, and a middle path such as a local fallback limit.
Hint
Requests affected = rate × seconds. A local limit per server holds a part of the line.