1Show the Level 1 solution
2**A.**
31. **Token bucket**: bursts allowed.
42. **Leaky bucket**: smooth, steady output.
53. **Sliding log**: exact, and tiny at 5 entries per account.
64. **Fixed window** (per day): simple, and a boundary burst over a day matters little.
75. **Sliding window counter.**
89**B.**
101. **Account** (or account + IP).
112. **API key**, with the limit set by its plan.
123. **Phone number** (plus IP and account).
134. **IP**, at the edge.
1Show the Level 2 solution
21. 60 ÷ 100 = one token every **0.6 seconds**; from empty to full: **60 seconds**.
32. **200**: 100 in the last moments of one window and 100 at the start of the next (the chapter's code lets 200 through in about 0.2 s).
43. Log: 1,000,000 × 100 × 8 bytes = **0.8 GB**. Counter: 1,000,000 × 2 × 8 bytes = **16 MB**.
54. 1,000,000 ÷ 60 ≈ **16,700** operations a second.
65. min(10, each): 10 + 10 + 10 + 10 + 5 + 4 + 3 + 2 + 1 + 0 = **55**. The client is under its limit of 100 but loses 45 requests.
76. Per IP: each IP makes 10 guesses, all within its limit of 10, so **10,000** get through. Per account: **5**.
1Show the Level 3 solution
2Tested solution (Python 3), the key parts:
34```python
5class TokenBucket:
6 def __init__(self, capacity, refill_per_s):
7 self.capacity, self.rate = capacity, refill_per_s
8 self.tokens, self.last = capacity, 0.0
910 def allow(self, now, cost=1):
11 self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
12 self.last = now
13 if self.tokens >= cost:
14 self.tokens -= cost
15 return True
16 return False
171819class SlidingWindowCounter:
20 def __init__(self, limit, window):
21 self.limit, self.window, self.counts = limit, window, {}
2223 def estimate(self, now):
24 w = int(now // self.window)
25 elapsed = (now % self.window) / self.window
26 return self.counts.get(w - 1, 0) * (1 - elapsed) + self.counts.get(w, 0)
2728 def allow(self, now):
29 if self.estimate(now) + 1 > self.limit:
30 return False
31 w = int(now // self.window)
32 self.counts[w] = self.counts.get(w, 0) + 1
33 return True
343536def atomic_allow_many(r, key, limit, concurrent):
37 return sum(1 for _ in range(concurrent) if r.incr(key) <= limit) # INCR is atomic
38```
3940All checks pass: the token bucket allows 100 of 150 instant requests and the next one 0.6 s later; the leaky bucket delays 0, 0.5, 1 s and drops the overflow; at the minute boundary, fixed window allows 200 while sliding log, sliding window counter and token bucket allow 100; the sliding estimate is 70; read-then-write allows 20 where INCR allows 5; uneven local limits pass 55 of 100; per-IP limits let all 10,000 stuffing guesses through while per-account allows 5. The full file is in `code/ch25_rate_limiting.py`.
1Show the Level 4 solution
2**How it leaks:** `GET`, compare, then `SET` is **not atomic**. Under a spike, many of the 20 servers read the same count (say 95) at nearly the same moment; each sees "under 100", each allows its request, and each writes **96**. The counter rises far more slowly than the real number of requests, so the key gets well past 100. (In the chapter's code, 20 concurrent requests with 95 used all pass instead of 5.) The `ex=60` on every `SET` also keeps pushing the expiry forward, which is a second, smaller bug.
34**The fix:** increment and check in **one atomic operation**, and set the expiry only when the key is created:
56```python
7def allow(redis, api_key):
8 key = f"rl:{api_key}:{int(time.time() // 60)}"
9 count = redis.incr(key) # atomic: every request gets a unique count
10 if count == 1:
11 redis.expire(key, 60) # first request in this window sets the expiry
12 return count <= 100
13```
1415(Use a Lua script, or `SET key 0 EX 60 NX` before `INCR`, so a crash between `INCR` and `EXPIRE` can't leave a key with no expiry.)
1617**The weakness that remains:** it's still a **fixed window**, so a client can send 100 at 10:15:59 and 100 at 10:16:00: **200 in about a second**. For accuracy, switch to a sliding window counter or a token bucket in a Lua script.
1Show the Level 5 (sketch) solution
21. **Limits:**
3 - Partner API: **token bucket per API key**, capacity = 1 minute's worth (100 free, 1,000 paid), refill 100 or 1,000 a minute. Search costs **5 tokens**.
4 - Login: **sliding log per account** (5 per 15 minutes) plus a per-IP limit (say 50 per 15 minutes), with progressive delays and CAPTCHA.
5 - OTP: **per phone number** (3 sends per hour, 5 verify attempts per OTP) and per IP.
6 - Edge: a generous **per-IP** limit (say 1,000 a minute) to drop floods.
72. **Placement:** per-IP at the CDN/WAF; per-key token buckets at the API gateway; login and OTP limits inside the auth service; an outbound leaky bucket in front of the SMS gateway.
83. **Shared state:** a Redis cluster sharded by key, token buckets updated by a Lua script; about 16,700 operations a second at 1 million requests a minute. Limiter calls have a 5 ms timeout. If Redis is down: the partner API **fails open** with a local per-server backstop (limit ÷ 30, with slack); login and OTP **fail closed** to a strict local limit.
94. **Client view:** `429` with `Retry-After`, `RateLimit-Limit`, `RateLimit-Remaining`, `RateLimit-Reset` (the last three on every response), and a Problem Details body naming the plan and limit.
105. **Credential stuffing:** alert on a spike in failed logins **across** accounts or IPs, many accounts failing from many IPs, or a high failure ratio. Respond with per-account delays, CAPTCHA for suspicious traffic, checks against breached-password lists, edge bot management, and forced resets for accounts with confirmed compromise.