CSE Roadmap

Core tier · about 3 hours · 7 parts

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.