Part 6 of 6 · 3 min read
Exercises
Easy
Easy 1: Trace the bucket (20 minutes)
A bucket holds 3 tokens and refills 1 token per second. Requests arrive at 0, 0, 0, 0, 1, 1, 2.5 seconds. Mark each Y or n.
Done when: seven letters are written (YYYn then Y n Y) with the token count after each step.
Hint
Count tokens as a decimal. The refill at 2.5 seconds is 1.5 tokens since 1 second.
Easy 2: Run the four limiters (20 minutes)
Type the interface, clock and four classes. Reproduce the first three rows of the run table.
Done when: you print YYYYnn, YYn and YYYYnn.
Hint
The fake clock has a set and an advance method.
Easy 3: Choose (20 minutes)
For each need, pick an algorithm and give one reason: a login form that must never allow more than 5 tries in any minute, a public API that tolerates short bursts, a billing job that must run at a steady speed.
Done when: three answers name sliding window, token bucket and leaking bucket, with reasons.
Hint
Think about burst tolerance and steady output.
Medium
Medium 1: Decision result (45 minutes)
Change tryAcquire to return a Decision with the fields allowed, remaining and retryAfterMs, for the token bucket and the fixed window.
Done when: a refused call tells the client how long to wait and a test checks the number.
Hint
Time to wait is the missing share of a token divided by the rate.
Medium 2: Rules table (45 minutes)
Write a Rules class that maps an endpoint and a user tier to a limiter factory. Test two endpoints with different limits for the same user.
Done when: one endpoint refuses on the third call and the other on the sixth.
Hint
A key such as "endpoint:tier" works for the map.
Medium 3: Idle clean-up (45 minutes)
Make Limiters remove limiters that have been idle for ten minutes, using the fake clock.
Done when: after ten idle minutes the map is empty, and a new call creates a fresh limiter.
Hint
Store the last use time with each limiter.
Hard
Hard 1: Leaking bucket (90 minutes)
Build a leaking bucket with a bounded queue and a worker that takes one request per interval. Define the interface it needs.
Done when: a test fills the queue, sees the extra request dropped, and sees requests handled at the fixed rate.
Hint
A ScheduledExecutorService with a fixed rate drains the queue.
Hard 2: Shared store (90 minutes)
Define a CounterStore interface with an atomic incrementWithExpiry. Write an in-memory version and a fixed window limiter that uses it. Show that two limiter instances share one count.
Done when: two instances on one store together allow exactly the limit, and a thread test confirms it.
Hint
ConcurrentHashMap.merge is atomic.
Hard 3: Compare under load (90 minutes)
Run 100,000 requests with a skewed timing pattern through all four limiters. Report the number allowed in each, and the memory used by the log version.
Done when: a table shows allowed counts and memory, and a sentence explains the differences using the algorithm descriptions.
Hint
A log of timestamps is a deque of longs, so memory grows with the limit.