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. True or false? Explain in one line.

1. With hash mod N, adding one server moves about 1/N of keys.
2. On a hash ring, adding a server only moves keys to the new server.
3. Virtual nodes make lookups much slower.
4. With virtual nodes, a failed server's keys go to one neighbour.
5. Rendezvous hashing needs a ring.

B. Ring, fixed slots, or plain mod N? One line each.

1. A fixed set of 8 database shards that will never change.
2. A Memcached cluster that grows during sales.
3. A Redis Cluster.
4. A load balancer that should keep each user on the same backend as backends come and go.

Level 2: Calculate

1. 10 million cached pages across 4 servers with mod N. You add a 5th. About how many pages move?
2. Same with a hash ring (ideal case). About how many move?
3. Going from N to N + 1 servers: what fraction moves with mod N, and with a ring? Work it out for N = 9.
4. 20 servers, 200 virtual nodes each. How many points on the ring? About how many binary-search steps per lookup?
5. One server holds 1.95× its fair share of keys. If each server can handle 30,000 requests a second and the cluster gets 100,000 a second spread over 4 servers, is that server overloaded?

Level 3: Build

In Python:

1. moved_fraction(before, after) and show mod 4 → mod 5 moving about 80% of keys.
2. A Ring with add, remove and lookup using a stable hash and binary search.
3. Show that adding a server moves about 1/(N + 1) of keys, all to the new server, and removing one moves only its keys.
4. Add virtual nodes and measure the busiest server's share with 1 vs 100 vnodes.
5. replicas(key, n) returning the next n distinct servers, and rendezvous(key, servers).

Level 4: Debug

After a disk failure on one storage node, the team discovered that some keys had lost all their data, even though the system is configured to keep 3 replicas of everything. The replica code:

1. Explain how a key with "3 replicas" lost all its data when one node failed.
2. Fix it, and name one more improvement real systems make.

Level 5: Design

Design the key placement for the bookstore's cache cluster: 10 million cached pages, 4 servers normally, growing to 8 during the Big Book Sale, with servers of two sizes (16 GB and 32 GB). Some pages are very hot.

Deliver:

1. Ring, fixed slots or rendezvous, and why.
2. How many virtual nodes (or slots), and how bigger servers get more keys.
3. How clients learn about servers joining and leaving.
4. What happens to hit ratio and the database when you add 4 servers at once, and how to soften it.
5. How very hot pages are handled, since hashing alone puts each key on one server.