1Show the Level 1 solution
2**A.**
31. **False.** About N/(N + 1) move: 80% for 4 → 5.
42. **True.** Only keys in its new arc move, and they move to it.
53. **False.** Binary search over a few thousand points is still a handful of steps.
64. **False.** They spread across many servers; that's a key benefit.
75. **False.** It scores every server directly.
8
9**B.**
101. **Plain mod N** is fine if the shard count never changes (or fixed slots).
112. **Ring** (ketama-style) or rendezvous.
123. **Fixed slots** (16,384).
134. **Ring hash or Maglev** at the load balancer.
1Show the Level 2 solution
21. About 80% of 10 million = **8 million** pages move (become misses).
32. About 1/5 = **2 million**.
43. Mod N: about N/(N + 1); ring: about 1/(N + 1). For N = 9: **90%** vs **10%**.
54. 20 × 200 = **4,000** points; log₂(4,000) ≈ **12** steps.
65. Fair share is 100,000 ÷ 4 = 25,000 a second; 1.95× that is about **48,750**, well over 30,000: **overloaded**. With 100 vnodes (1.16×), about 29,000: just under.
1Show the Level 3 solution
2Tested solution (Python 3), the key parts:
3
4```python
5def h(s):
6 return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big") # stable across runs
7
8
9class Ring:
10 def __init__(self, servers=(), vnodes=1):
11 self.vnodes, self.points, self.owner = vnodes, [], {}
12 for s in servers:
13 self.add(s)
14
15 def add(self, server):
16 for v in range(self.vnodes):
17 p = h(f"{server}#{v}")
18 bisect.insort(self.points, p)
19 self.owner[p] = server
20
21 def lookup(self, key):
22 i = bisect.bisect_right(self.points, h(key)) % len(self.points)
23 return self.owner[self.points[i]]
24
25 def replicas(self, key, n):
26 out, i = [], bisect.bisect_right(self.points, h(key))
27 while len(out) < n:
28 s = self.owner[self.points[i % len(self.points)]]
29 if s not in out: # skip vnodes of servers already chosen
30 out.append(s)
31 i += 1
32 return out
33
34
35def rendezvous(key, servers):
36 return max(servers, key=lambda s: h(f"{key}|{s}"))
37```
38
39All checks pass: mod 4 → 5 moves 79.8% of 100,000 keys; the ring moves 22.9%, all to the new server; removing a server moves only its keys; the busiest server's share falls from 1.95× to 1.16× with 100 vnodes; replicas are 3 distinct servers; rendezvous moves about 20%, all to the new server; and the buggy replica walk duplicates servers for about half of keys. The full file is in `code/ch28_consistent_hashing.py`.
1Show the Level 4 solution
21. **What went wrong:** the code takes the next **3 points** on the ring, but with virtual nodes, neighbouring points often belong to the **same physical server**. For many keys, "3 replicas" were really 2 copies on one machine and 1 elsewhere, or even all 3 on one machine. When that machine's disk failed, those keys lost every copy. In the chapter's code, about **half** of keys get a duplicated server this way.
32. **The fix:** skip points of servers already chosen:
4
5```python
6def replicas(ring, key, n=3):
7 out, i = [], bisect.bisect_right(ring.points, h(key))
8 while len(out) < n:
9 server = ring.owner[ring.points[i % len(ring.points)]]
10 if server not in out:
11 out.append(server)
12 i += 1
13 return out
14```
15
16**Also:** skip servers in the same **rack or availability zone** as already-chosen replicas, so a single rack or zone failure can't take all copies. And run a background check that every key really has N distinct replicas (anti-entropy repair).
1Show the Level 5 (sketch) solution
21. **A hash ring with virtual nodes** (ketama-style) in the cache client library: the cluster changes size for sales, and the ring keeps movement small. (Rendezvous would also work at 4 to 8 servers.)
32. **About 160 vnodes per 16 GB server and 320 per 32 GB server**, so bigger servers get about twice the keys. Measure the spread and adjust.
43. **Membership:** server list in service discovery or a config store (Chapter 27); clients watch it and rebuild the ring on change; all clients use the same stable hash and vnode naming.
54. **Adding 4 to 4 at once** moves about half the keys: half the lookups miss and hit the database. Soften it by adding servers **one or two at a time** before the sale, **warming** new servers (read-through from the old owner for a transition period, or copy hot keys), request coalescing and stale-while-revalidate (Chapter 13), and rate-limiting database refills.
65. **Hot pages:** a short-lived **in-process cache** on app servers for the top few hundred pages; or **replicate** hot keys under suffixes (`page:42#0..#3`) and pick one at random per request; detect hot keys with a count-min sketch (Chapter 20).