title: Explain Merkle Trees for use in Eventual Consistency
body: <p><a href="http://en.wikipedia.org/wiki/Hash_tree" rel="noreferrer">Merkle Trees</a> are used as an anti-entropy mechanism in several distributed, replicated key/value stores:</p>
  
  <ul>
  <li><a href="http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf" rel="noreferrer">Dynamo</a></li>
  <li><a href="http://doc.erlagner.org/riak_core/merkerl.html" rel="noreferrer">Riak</a></li>
  <li><a href="http://wiki.apache.org/cassandra/AntiEntropy" rel="noreferrer">Cassandra</a></li>
  </ul>
  
  <p>No doubt an anti-entropy mechanism is A Good Thing - transient failures just happen, in production.
  I'm just not sure I understand why Merkle <em>Trees</em> are the popular approach.</p>
  
  <ul>
  <li><p>Sending a complete Merkle tree to a peer involves sending the local key-space to that peer, along with
  hashes of each key value, stored in the lowest levels of the tree.</p></li>
  <li><p>Diffing a Merkle tree sent from a peer requires having a Merkle tree of your own.</p></li>
  </ul>
  
  <p>Since both peers must already have a sorted key / value-hash space on hand, why not do a linear merge to detect discrepancies?</p>
  
  <p>I'm just not convinced that the tree structure provides any kind of savings when you factor in upkeep costs, and the fact
  that <em>linear passes over the tree leaves are already being done just to serialize the representation over the wire</em>.</p>
  
  <p>To ground this out, a straw-man alternative might be to have nodes exchange arrays of hash digests,
  which are incrementally updated and bucketed by modulo ring-position.</p>
  
  <p>What am I missing?</p>