CSE Roadmap

Core tier · about 5 hours · 8 parts

Part 6 of 8 · 2 min read

Failures

Detect, cover, repair.

At scale, failures are common, so handling them is part of the main design.

Detecting a failure. One server saying another is down is not enough. At least two independent views should agree. Having every node tell every other node (all-to-all) works but does not scale. The book recommends gossip:

  • Each node keeps a list of members with a heartbeat counter for each.
  • It raises its own counter every so often.
  • It sends its list to a few random nodes, who pass it on.
  • If a member's counter has not risen for a set time, the node is marked down, and that news spreads.

Covering a short failure. A strict quorum would block reads and writes when copies are down. A sloppy quorum picks the first W healthy servers for a write and the first R healthy servers for a read, skipping the ones that are down. If s2 is down, s3 takes its writes for a while. When s2 returns, s3 hands the data back. This is hinted handoff.

Repairing a long failure. If a copy is gone for good, or has missed many writes, the system uses anti-entropy: compare the copies and bring the older one up to date. Comparing every key would be slow. A Merkle tree makes it cheap. Keys are grouped into buckets. A hash is taken of each bucket's keys, and then hashes of hashes, up to a single root. Two nodes compare roots. If equal, the data is the same, with one small check. If different, they compare the children, and so on down, until only the buckets that differ remain, and only those are copied. The data moved is proportional to the difference, and not to the total. The book gives a sizing: 1 million buckets for 1 billion keys, so 1,000 keys per bucket.

A whole data centre down. Copy data to several data centres. Even if one is offline, users can read through another.

Check yourself: 1. Why not trust a single report that a server is down? 2. What does hinted handoff do? 3. Why is a Merkle tree cheaper than comparing all keys?