Distributed systems · 13 min

Merkle tree

Two copies of a million rows find the few that differ by comparing about 41 short fingerprints, not a million rows.

Your ramen delivery app keeps its orders in two databases, one in Tokyo and one in Osaka, so either can serve customers if the other goes down. Last night the link between them dropped for 30 seconds.

A few changes reached Tokyo but never reached Osaka: an order marked delivered, a quantity corrected. This morning each copy holds just over a million orders, and a handful don’t match. Which ones, and how do you find them without shipping the whole table across the country?

Attempt one: ship every order across

Osaka sends all of its orders to Tokyo, and Tokyo checks them one by one. To keep the numbers round, say there are exactly 1,048,576 orders (that is 2²⁰, “about a million”) of about 1 KB each.

That is about 1 GB over the network to find perhaps five bad rows. Every night. This is the wrong way; it is just the number to beat.

Attempt two: send a fingerprint instead

Each side reads its own orders, sorted by order ID, and feeds them all, one after another, into a single hash: one fingerprint for the whole table. With SHA-256 that is 32 bytes. Osaka sends those 32 bytes to Tokyo.

If the two fingerprints match, the tables match. One tiny message and you are done. But last night they won’t match, and a mismatch tells you only “something, somewhere, is different”. To find what, you are back to sending a gigabyte.

Attempt three: one fingerprint per chunk

Cut the sorted orders into 1,024 chunks of 1,024 orders each, and fingerprint each chunk. Osaka sends 1,024 fingerprints, which is 32 KB. Tokyo finds the chunks whose fingerprints differ (five bad orders touch at most five chunks), and only those chunks come across: about 1 MB each.

1 GB has become a few MB. But look at what you sent first: a list of 1,024 fingerprints that are almost all equal. That list is just more data to compare, so you can fingerprint it too.

Fingerprints of fingerprints

Take that idea all the way down to single orders and all the way up to one code. Here it is with 8 orders, like the demo below:

1. Hash each order on its own. These 8 codes are the leaves.
2. Pair up neighbours, stick each pair’s two codes together, and hash that. You get 4 parents.
3. Pair those up and hash again: 2 boxes.
4. Once more: 1 box. That is the root.

With 1,048,576 orders you halve 20 times to get down to one box, so the tree has the leaves plus 20 levels above them. Just as log₂ 1,024 = 10, log₂ 1,048,576 = 20.

Count the boxes and each level has half as many as the one below: 8 + 4 + 2 + 1 = 15 for 8 orders. For a million it is 1,048,576 + 524,288 + … + 1, which comes to just under 2 million: always one less than twice the number of orders.

The demo calls orders “blocks” and calls Tokyo and Osaka “Replica A” and “Replica B”. It uses a short 8-character hash so it fits on screen. The box at its top lets you hash any text: change “3 ramen” to “4 ramen” and the whole code changes.

Walking down only the branch that differs

Tokyo and Osaka each build their tree locally. That reads every order once, on its own server, but sends nothing. Then they talk, starting at the top. Each comparison is Osaka sending one 32-byte code and Tokyo checking it against its own box in the same place. Osaka sends all the codes Tokyo asks for on one level in a single message, so it is one round trip per level:

1. Compare the two roots. If they match, every order matches. Stop.
2. If they differ, compare the two children of that box.
3. A child that matches is skipped, along with everything under it.
4. A child that differs gets its own two children compared, and so on.
5. A leaf that differs is a bad order. Osaka sends just that one.

With one bad order in a million, every level below the root costs exactly 2 comparisons: one child matches, one doesn’t. That is 1 for the root plus 2 × 20 levels = 41 comparisons, in 21 round trips.

That “exactly 2 per level” holds for one bad order. With several, it becomes an upper limit, because bad orders that share boxes share comparisons. The general rule: with n orders and k bad ones, the walk takes at most 1 + 2 × k × log₂ n comparisons. For last night’s five bad orders among a million: 1 + 2 × 5 × 20 = 201 comparisons, about 6 KB of fingerprints, then five orders. Compare that with 1 GB.

Here is the walk as code. Notice that a matching pair returns straight away; that early return is where all the saving comes from.

diff(a, b, level, i):              # start at the root: diff(a, b, top, 0)
    if a[level][i] == b[level][i]:
        return []                      # same: skip everything below
    if level == 0:
        return [i]                     # a leaf: this order differs
    return diff(a, b, level - 1, 2*i) + diff(a, b, level - 1, 2*i + 1)

When the tree stops helping

So bad orders that sit close together are cheaper than scattered ones. And if most orders differ, the walk opens nearly every one of the 2 million boxes and then copies most of the orders anyway, which costs more than just copying the table. A Merkle tree is for the common case: two copies that are almost the same.

Keeping the tree current is cheap too. When one order changes, only the 21 boxes on its path to the root need new hashes, not the whole tree.

A bonus: proving one order is in there

The same tree answers a second question. Say the shop publishes its root every night, and an auditor wants to check that order #2 is really in the data without downloading a million orders.

You send order #2 plus one sibling code per level: the box next to its path at each step up. The auditor hashes the order, then joins it with each sibling in turn and hashes again. The proof says, for each sibling, whether it goes on the left or the right. Finally the auditor checks that the result equals the root. A shop can’t fake this with made-up siblings: landing on the published root with a changed order would mean finding two different texts with the same hash, which SHA-256 makes practically impossible. That is 3 codes for 8 orders, 20 for a million and 30 for a billion. Change the order by one letter and the result won’t match the root.

Who keeps a tree like this

• Cassandra runs a “repair” job that brings replicas back in line. It builds a Merkle tree on each, compares them, and sends only the rows under leaves that differ. Each leaf covers a range of rows, as in the note above.
• Amazon’s Dynamo paper (2007) describes the same idea for keeping replicas in sync in the background.
• Git names every file, folder and commit by the hash of its contents, and a folder’s hash covers the hashes inside it. That is why any change to any file gives a new commit ID.
• Certificate Transparency logs (public lists of every HTTPS certificate issued) and Bitcoin publish roots, so anyone can check that one certificate or one transaction is included with a short proof, like the auditor above.

Back to Tokyo and Osaka. Each night they compare 32-byte roots. Most nights that is one comparison and done. After a blip, a couple of hundred comparisons point straight at the handful of orders that need copying.