Merkle Tree是Dynamo论文中用到的一个算法，读这篇论文前，我并不知道这个算法，所以找了相关资料了解了解，以便我对论文有更进一步的了解。
什么是Merkle Tree
Merkle Tree，是一种树（数据结构中所说的树），网上大都称为Merkle Hash Tree,这是因为 它所构造的Merkle Tree的所有节点都是Hash值。Merkle Tree具有以下特点：
1. 它是一种树，可以是二叉树，也可以多叉树，无论是几叉树，它都具有树结构的所有特点；
2. Merkle树的叶子节点上的value，是由你指定的，这主要看你的设计了，如Merkle Hash Tree会将数据的Hash值作为叶子节点的值；
3 非叶子节点的value是根据它下面所有的叶子节点值，然后按照一定的算法计算而得出的。如Merkle Hash Tree的非叶子节点value的计算方法是将该节点的所有子节点进行组合，然后对组合结果进行hash计算所得出的hash value。
例如，下图就是一个Merkle Hash Tree形状，如果它是Merkle Hash Tree，则节点7的hash value必须是通过节点15、16上的value计算而得到.
图一 Merkle Hash Tree
为什么要使用Merkle Tree
目前， 在计算机领域，Merkle Tree大多用来进行比对以及验证处理。在处理比对或验证的应用场景中时，特别是在分布式环境下进行比对或验证时，Merkle Tree会大大减少数据的传输量以及计算的复杂度。例如，就拿图一举例，假如是 15,16.......30是一个个数据块的hash值，我把这些数据从A传输到B，数据传输到B后，我想验证下传输到B上的数据的有效性型（验证数据是否在传输过程中发生变化），只需要验证A
和 B上所构造的Merkle Tree的root节点值是否一致即可，如果一致，表示数据是有效的，传输过程中没有发生改变。假如在传输过程中，15对应的数据被人篡改，通过Merkle Tree很容易定位找到（因为此时，节点0,1,3,7,15对应的hash值都发生了变化），定位的时间复杂度为O（log(n））.
和 B上所构造的Merkle Tree的root节点值是否一致即可，如果一致，表示数据是有效的，传输过程中没有发生改变。假如在传输过程中，15对应的数据被人篡改，通过Merkle Tree很容易定位找到（因为此时，节点0,1,3,7,15对应的hash值都发生了变化），定位的时间复杂度为O（log(n））.
Merkle Tree的应用场景
BitTorrent应用 [3,7]
在BT中, 通常种子文件中包含的信息是Root值, 此外还有文件长度、数据块长等重要信息. 当客户端下载数据块8时，在下载前，它将要求peer提供校验块8所需的全部路径哈希值：H24、H12、H6和H1.
下载完成后, 客户端就会开始校验, 它先计算它已经下载的数据块8的Hash值23, 记做H23′ ,
表示尚未验证. 随后会按照我在上一小节中给出的几个公式, 来依次求解 直到得到H0′ 并与H0 做比较,
校验通过则下载无误。
校验通过的这些路径哈希值会被缓存下来, 当一定数量的路径哈希值被缓存之后，后继数据块的校验过程将被极大简化。此时我们可以直接利用校验路径上层次最低的已知路径哈希值来对数据块进行部分校验，而无需每次都校验至根哈希值H0。
下载完成后, 客户端就会开始校验, 它先计算它已经下载的数据块8的Hash值23, 记做
表示尚未验证. 随后会按照我在上一小节中给出的几个公式, 来依次求解 直到得到
校验通过则下载无误。
校验通过的这些路径哈希值会被缓存下来, 当一定数量的路径哈希值被缓存之后，后继数据块的校验过程将被极大简化。此时我们可以直接利用校验路径上层次最低的已知路径哈希值来对数据块进行部分校验，而无需每次都校验至根哈希值H0。
Amazon Dynamo 副本同步 [4]
Amazon Dynamo 论文描述的副本同步技术是比较复杂的，在这，只是简单的描述下 Dynamo是怎样使用 Merkle Tree来对副本进行同步的。而至于为什么要同步、同步详细过程，容我在后面章节描述。
在Dynamo的数据划分算法的章节里，我们描述了，Dynamo 集群的所有机器都分布在一致性Hash环上，每台机器保存了Hash到机器区间（hash环上，两个机器节点之间，称机器区间）里的所有数据，同时，为了保证数据存储的持久性，一台机器上的数据会在其它机器上有备份，也就是所谓的副本。由于某些原因，副本需要同步，保持一致，既然要同步，就先要对副本数据进行比对，找出不一致的地方，然后合并成统一的一个副本。而目前，我们所关心的是比对，需要牵涉到跨网络传输，如果对机器上所有数据都进行比对的话，数据传输量就会很大，从而造成“网络拥挤”。为了解决这个问题，可以在每台机器上针对每个区间里的数据构造一棵Merkle
Tree，这样，在两台机器间进行数据比对时，从Merkle Tree的根节点开始进行比对，如果根节点一样，则表示两个副本目前是一致的，不再需要任何处理；如果不一样，则遍历Merkle Tree，定位到不一致的节点也非常快速，大大节省了比对时间以及数据的传输量。
Tree，这样，在两台机器间进行数据比对时，从Merkle Tree的根节点开始进行比对，如果根节点一样，则表示两个副本目前是一致的，不再需要任何处理；如果不一样，则遍历Merkle Tree，定位到不一致的节点也非常快速，大大节省了比对时间以及数据的传输量。
在Git中的使用
Git的作用类似于SVN和CVS，但功能比它们都要强大，是个分布式处理资源协同使用的工具，具体我也不是很熟悉。但据说，在Git里对集群里的机器间的文件同步也是采用Merkle Tree来进行比对的。具体技术细节，我猜可能是这样： 为Git 工作目录下的所有文件构造一个Merkle Tree，因为文件的层次结构天生就适合构造一棵树， 机器间文件的同步也是采用Merkle
Tree的比对原理来实现的，和在Dynamo中使用的一样，只是叶子节点的值有点差异，一个是文件，一个键值对(key-value)。 注意，这个只是我个人猜测啊，如果我设计的话，就这么搞，应该不是胡搞瞎搞吧， 呵呵！
Tree的比对原理来实现的，和在Dynamo中使用的一样，只是叶子节点的值有点差异，一个是文件，一个键值对(key-value)。 注意，这个只是我个人猜测啊，如果我设计的话，就这么搞，应该不是胡搞瞎搞吧， 呵呵！
Reference
- http://en.wikipedia.org/wiki/Hash_tree
- http://en.wikipedia.org/wiki/Lamport_signature
- http://blog.csdn.net/starxu85/article/details/3859011
- http://ultimatearchitecture.net/index.php/2010/09/12/merkle-tree/
- http://www.public.asu.edu/~rzhang46/
- http://yishanhe.net/wiki/Secure-topk-query.html
- http://www.bittorrent.org/beps/bep_0030.html
- https://www.usenix.org/conference/osdi12/secure-offline-data-access-using-commodity-trusted-hardware