Practice: five levels

Assignments

Five levels. Do them in order. Answers are in "Solutions" at the end, so try first.

Level 1: Think (no code)

A. Which algorithm? One line each.

1. A public API where a page load fires 20 calls at once, then goes quiet.
2. Calls to an old inventory system that falls over above 50 requests a second, even briefly.
3. "5 login attempts per 15 minutes per account", exact.
4. A daily quota of 10,000 calls per API key.
5. High-volume per-key limits where fixed windows let through too much at boundaries.

B. Which key (IP, account, API key, phone number, or a combination)? One line each.

1. Stopping credential stuffing against one account from many IPs.
2. Free vs paid plans for partner apps.
3. Stopping a script from requesting 1,000 OTPs to one phone number.
4. Blunting a flood from a few IP addresses before it reaches your servers.

Level 2: Calculate

1. A token bucket holds 100 tokens and refills at 100 per minute. How often does a token arrive? After it's emptied, how long until it's full again?
2. With a fixed window of 100 per minute, what's the most requests a client can get through in one second, and how?
3. A sliding log keeps one 8-byte timestamp per request. With 1 million API keys at 100 per minute, how much memory for timestamps? And for a sliding window counter with two 8-byte counters per key?
4. The API handles 1 million requests a minute, each needing one Redis operation for rate limiting. How many Redis operations a second?
5. One client sends 100 requests a minute across 10 servers that each enforce a local limit of 10. The load balancer sends it 30, 25, 20, 10, 5, 4, 3, 2, 1 and 0 requests. How many get through?
6. An attacker makes 10,000 login guesses against one account from 1,000 IPs. How many get through a per-IP limit of 10? A per-account limit of 5?

Level 3: Build

In Python:

1. A TokenBucket(capacity, refill_per_s) with allow(now, cost=1), storing only tokens and last time.
2. A LeakyBucket(capacity, leak_per_s) with offer(now) returning the delay or None.
3. FixedWindow, SlidingLog and SlidingWindowCounter with allow(now), and a boundary_burst test that shows fixed window allowing 200 while the others allow 100.
4. A fake Redis and two shared-counter functions: read-then-write, and atomic INCR. Show the race.
5. headers(limit, used, reset_in) returning RateLimit-* headers, with Retry-After when exhausted.

Level 4: Debug

During a partner's traffic spike, monitoring shows one API key making about 160 requests a minute against a limit of 100. The limiter, running on 20 API servers:

1. Explain exactly how the key gets past its limit.
2. Fix it. Then name the other weakness this limiter still has, even after the fix.

Level 5: Design

Design rate limiting for the bookstore: a public partner API (free plan 100 a minute, paid 1,000 a minute, with bursts allowed), a login endpoint, an OTP endpoint, and the search endpoint (expensive). Traffic: about 1 million API requests a minute across 30 servers.

Deliver:

1. The algorithm and key for each limit, with numbers.
2. Where each limit is enforced (edge, gateway, service).
3. How the shared state works, and what happens if Redis is unavailable.
4. What clients see when limited (status, headers, body).
5. How you'd spot and handle a credential-stuffing attack.