Two replicas of Tiffin's order history each hold 400 million orders. They are supposed to be identical. But a replica was down for an hour last Tuesday, a hinted write got lost, and a disk silently flipped a bit. Somewhere, the two copies differ. Which orders?
Comparing them row by row means reading and shipping 400 million rows across the network to find maybe a few hundred differences. A Merkle tree lets the replicas find those differences by exchanging a handful of hashes instead.
The problem: finding a needle in two haystacks
You met leaderless replication and read repair in Module 13. Read repair only fixes keys that somebody reads. Rows that nobody reads (old orders, cold restaurants) can stay out of sync forever. Databases fix that with a background process called anti-entropy: replicas periodically compare their data and repair what differs.
The challenge is doing that comparison cheaply when almost everything is already the same. You want the cost to depend on how much is different, not on how much data there is.