CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 8 of 8 · 3 min read

Exercises

Easy

Easy 1: Find the owner (20 minutes)

A ring of 0 to 99 has servers at 15, 40, 65 and 90. Give the owner of keys at 3, 15, 16, 70 and 95.

Done when: five owners.

Hint

Go clockwise from the key to the first server at or after it.

Easy 2: Add a server (20 minutes)

On the same ring, add a server at 55. Say which keys of the five in Easy 1 move, and the share of the ring that changes owner.

Done when: a list of moved keys and a share.

Hint

The new server takes the range from the previous server (40) up to 55.

Easy 3: Mod N or ring (20 minutes)

Hashes 5, 9, 14, 18, 22, 27, 33, 40. Compute how many change server under mod N when N goes from 4 to 5, and the minimum that would have to move to give the new server a fair share.

Done when: two counts.

Hint

Minimum = keys ÷ 5 for a fair share.

Medium

Medium 1: Remove a server (30 minutes)

On the ring with servers at 15, 40, 65 and 90, remove the server at 40. Give the affected range, the new owner and the share moved. Then compute the load of each remaining server as a share of the ring.

Done when: a range, an owner, a share and three load shares.

Hint

Server 40's keys go to server 65.

Medium 2: Virtual nodes (30 minutes)

Three servers have 100, 100 and 200 virtual nodes. Compute their ring shares. One of the 100-node servers fails. Compute the new shares assuming its points are spread evenly.

Done when: two sets of shares.

Hint

Share = virtual nodes ÷ total.

Medium 3: Replica placement (30 minutes)

A ring has servers A, B, C, D at 10, 30, 50 and 70 (range 0 to 79). Place N = 3 copies for keys at 5, 33 and 75. A and B are in data centre 1, and C and D in data centre 2. Adjust to put copies in both data centres.

Done when: three copy sets and an adjusted rule.

Hint

Walk clockwise for 3 distinct servers, then swap to cover both centres.

Hard

Hard 1: Failure spike (45 minutes)

A cache cluster of 10 servers carries 100,000 requests a second at a 96 percent hit ratio. One server fails. Compute the database load just after the failure with a ring and with hash mod N. State the time the ring spike lasts if each moved key refills on its first miss and each key is read about once a second.

Done when: two database loads and a duration estimate.

Hint

Ring: 10 percent of keys miss. Mod N: about 90 percent miss.

Hard 2: Cluster growth (45 minutes)

A ring of 8 servers with 150 virtual nodes each grows to 12. Compute the share of keys that move, the number of virtual nodes added, and the data moved for 6 TB. Compare with fixed partitions of 1,200 partitions.

Done when: three numbers and a comparison.

Hint

Adding 4 servers to 8 moves about 4 ÷ 12.

Hard 3: Design a sticky chat router (50 minutes)

A chat service routes each user to a chat server by consistent hashing on the user id. Design the ring, the number of virtual nodes, what happens when a server restarts (connections lost, users reconnect), the load on the new owner, and the way to limit the reconnect storm.

Done when: a design with numbers and a reconnect plan.

Hint

Reconnects can be spread with random delays.