马上要写开题报告了，初步打算会做分布式计算方面（或是某些人口中的云计算）的一些研究。之前也看了不少相关的论文，但基本上都是浑沦吞枣，不求甚解。之后在某搜索引擎公司呆了一段时间，对这方面又有了新的认识，所以结合公司遇到的问题，在细细研读一遍这个领域的一些重要的论文。今天看的是Amazon公开的一个分布式KV数据库Dynamo。

互联网公司的大规模分布式计算系统都有一些相同的特点，其中之一就是为了节省成本，一般都将集群搭建在廉价的PC服务器上。这样的话，随着集群规模的增大，发生机器故障的情况就屡见不鲜了。所以此时在设计系统时，应该将机器故障视为一种常态。而Dynamo就是在这种前提下，Amazon的一个解决方案。

综合来看，Dynamo有如下特点：
0）简单的存取模式，只支持KV模式的数据存取，同时特定于小于1M的数据；
1）高可用性，即便在集群中部分机器故障，网络中断，甚至是整个机房下线，仍能保证用户对数据的读写；
2）高可扩展性，除了能够跨机房部署外，动态增加，删除集群节点，同时对正常集群影响很小。
3）数据的高可用性大于数据的一致性，短时间的数据不一致是可以容忍的，采用最终一致性¹来保证数据的高可用。
4）服务于内网，数据间没有隔离。
5）服务保证条约，在Amazon一切皆服务²的原则下，每个模块都要为其使用者提供服务时间保证，比如在每秒500个请求的压力下，99.9%的请求要在300ms内返回。接下来详细介绍为了完成上述目标，Dynamo中所采用的技术方案。

数据划分(Partition)

Dynamo作为一个分布式的存储，必须能够将用户输入的数据划分到集群中的不同机器中存储。传统的划分方式都是类Hash的，即按照数据中的某些特征值做Hash（一般都是取模），使数据映射到下边的机器中。但是这种方式有个很大的缺点，那就是当集群中机器增加的时候，之前的Hash全部都是失效了，再Hash的成本很大，也就制约了集群的扩展。

Dynamo中采用的是“一致性Hash”来解决这个问题。基本思想是每一个Dynamo节点都有一个Token，可以将Dynamo想象成一个环，拥有不同Token值的节点处于环的不同位置。当一个GET(key)请求到来时，应用路由层或是Dynamo会将这个key做一个Hash，将这个Key同样映射到环上，然后在环上按照固定顺序往下寻找，找到的第一个Dynamo节点即为对这个Key服务的节点。当要向集群中增加机器时，首先为这个新节点分配一个Token，然后将他下游机器上原来的数据复制到本机上就算完成了。这样的好处是每当增加一个新节点，只会影响一小部分现有节点，不必像以前那样全部数据重新Hash，相比较而言，数据迁移的成本要小得多。

上述只是一个简单的一致性Hash原理的解释，实际并不是按照这种最简单的方式使用的。首先为了应对节点Token在环中分布不均的状况，以及考虑不同机器性能有差异的情况，Dynamo采用了“虚节点”技术，即为每个实际节点分配多个Token，此时一个机器在环中不仅有一个地址而是多个地址。另外考虑到数据的可用性问题，每份数据不是仅存在一个节点中，而是分别复制到下游的多个机器上，复制个数是可以配置的。这样当一个节点失效时，可以继续沿环寻找下一个节点。

副本技术与节点发现机制

上边已经说了Dynamo为了保证数据不丢失，采用了副本技术。Dynamo节点启动的时候会为他配置一个参数N，表示数据的副本数。当一条数据写到Hash环中对应的节点的时候，同样会发送给下游的N-1个节点（这些节点都是实际节点，而非虚节点）。这N个节点在系统中称为“Preference List”，同时为了应对出错的状况，“Preference List”中的节点数往往大于N。这里有个问题，就是当前节点是如何知道他的下游节点的呢？这就是节点发现机制。

由于各种各样的原因，暂时性的节点掉线是时有发生的。如果因为一个节点暂时性的掉线，而导致副本迁移等代价高昂的操作显然是不合适的。所以Dynamo提供了一组命令行接口和HTTP接口供管理员手工添加，删除节点。一旦一个节点的角色发生改变（上线或下线等），它都会将这个改变和放生的时间存储到一个持久的数据库中，这些数据构成了一个节点的状态变迁历史。然后通过一个Gossip-Based Protocol将这个消息传递出去。节点在收到其它节点的消息时，会将收到的消息与自己本地存储的消息进行合并，最终每个节点都会得到整个集群的信息。为了应对可能出现的“Local
Partition”现象，某些Dynamo节点作为“种子”节点，种子节点可以通过全局的方式被其它所有节点发现，最终所有的节点自己存储的状态信息都与种子节点的状态信息合并。

与正常节点发现类似，对错误节点的发现机制也是使用的Gossip-Based Protocol，每个节点都记录自己与其它节点的连通状态。在论文中有关于去中心化的分布式系统中错误发现机制详细介绍的参考。

写操作高可用

Dynamo中，最重要的是要保证写操作的高可用性，即“Always Writeable”，这样就不可避免的牺牲掉数据的一致性。如上所述，Dynamo中并没有对数据做强一致性要求，而是采用的最终一致性。结合上述的数据副本技术，可以看出，若不保证各个副本的强一致性，则用户在读取数据的时候很可能读到的不是最新的数据。Dynamo中将数据的增加或删除这种操作都视为一种增加操作，即每一次操作的结果都作为一份全新的数据保存，这样也就造成了一份数据会存在多个版本，分布在不同的节点上。这种情况类似于版本管理中的多份副本同时有多人在修改。多数情况下，系统会自动合并这些版本，一旦合并尝试失败，那么冲突的解决就交给应用层来解决。这是系统表现出来的现象就是，一个GET(KEY)操作，返回的不是单一的数据，而是一个多版本的数据列表，由用户决定如何合并。这其中的关键技术就是Vector
Clock。

一个Vector Clock可以理解为一个<节点编号，计数器>对的列表。每一个版本的数据都会带上一个Vector Clock。通过对比两份不同数据的Vector Clock就能发现他们的关系。所以应用层在读取数据的时候，系统会连带这Vector Clock一同返回；在操作数据的时候也需要带上数据的Vector Clock一同提交。大致流程如图。

一个正常的GET和SET流程

之前也说过，Amazon在设计组件的时候采用的是“一切皆服务”的原则。Dynamo也不例外，应用可以通过两种方式使用Dynamo：1）通过一个应用路由层转发请求到对应Dynamo节点。2）通过连接Dynamo的API到自己程序中使用。两种方式各有优劣。负责处理读写请求的Dynamo节点在系统中称为“Coordinator”，一般是之前提到的“Preference List”中的第一台节点。如果不再这个List中的机器收到了读写请求，它会将这个请求转发到在List中的机器上。

Dynamo中一共涉及三个重要的参数，其中N，代表数据的副本数，之前已经说过了。另外还有W和R，分别表示：一次写操作，最小必须写成功节点数；和一次读操作，最小读成功节点数。另外要求W + R > N。设计这两个参数主要是出于性能考虑，不然可以直接令 W = R = N。读数据时，只要有除了Coodinator之外的R-1个节点返回了数据，就算是读成功（此时可能返回多个版本的数据）。同理，写数据时，只要有除了Coordinator之外的W-1个节点写入成功，就算数据写入成功。

故障处理

故障检测和处理往往都是分布式系统的重点和难点，尤其是对于像Dynamo这种对可用性要求很高的系统。上边说了，通过设定N，W，R参数来保证读写的正确。一旦出现读写失败的情况，都会触发故障处理机制。Dynamo中将故障分为两类，一类是临时性的故障，另一类是持久的故障。分别对应两种不同的处理方式。

以N=3为例，如果在一次写操作时发现节点A挂了，那么本应该存在A上的副本就会发送到D上，同时在D中会记录这个副本的元信息（MetaData）。其中有个标示，表明这份数据是本应该存在A上的，一旦节点D之后检测到A从故障中恢复了，D就会将这个本属于A的副本回传给A，之后删除这份数据。Dynamo中称这种技术为“Hinted
Handoff”。另外为了应对整个机房掉线的故障，Dynamo中应用了一个很巧妙的方案。之前说过“Preference List”，每次读写都会从这个列表中取出R或W个节点。那么只要在这个列表生成的时候，让其中的节点是分布于不同机房的，自然数据就写到了不同机房的节点上。

“Hinted Handoff”的方式在少量的或是短暂的机器故障中表现很好，但是在某些情况下仍然会导致数据丢失。如上所说，如果节点D发现A重新上线了，会将本应该属于A的副本回传过去，这期间D发生故障就会导致副本丢失。为了应对这种情况，Dynamo中用了基于 Merkle Tree的Anti-Entrpy系统（不知道中文怎么翻译），关于Merkle Tree的资料，参考Dynamol中链接。