5.1.2　一致性与复制

为了处理节点失效的情况（DHT环中删除节点），需要对节点的数据进行复制。思路如下：假设数据存储N份，DHT定位到的数据所属节点为K，则数据存储在节点K，K+1，……，K+N-1上。如果第K+i（0≤i≤N-1）台机器宕机，则往后找一台机器K+N临时替代。如果第K+i台机器重启，临时替代的机器K+N能够通过Gossip协议发现，它会将这些临时数据归还K+i，这个过程在Dynamo中叫做数据回传（Hinted Handoff）。机器K+i宕机的这段时间内，所有的读写均落入到机器[K，K+i-1]和[K+i+1，K+N]中。如果机器K+i永久失效，机器K+N需要进行数据同步操作。一般来说，从机器K+i宕机开始到被认定为永久失效的时间不会太长，积累的写操作也不会太多，可以利用Merkle树对机器的数据文件进行快速同步（参见下一小节）。

NWR是Dynamo中的一个亮点，其中N表示复制的备份数，R指成功读操作的最少节点数，W指成功写操作的最少节点数。只要满足W+R＞N，就可以保证当存在不超过一台机器故障的时候，至少能够读到一份有效的数据。如果应用重视读效率，可以设置W=N，R=1；如果应用需要在读/写之间权衡，一般可设置N=3，W=2，R=2；当然，如果丢失最后的一些更新也不会有影响的话，也可以选择W=1，R=1，N=3。

NWR看似很完美，其实不然。在Dynamo这样的P2P集群中，由于每个节点存储的集群信息有所不同，可能出现同一条记录被多个节点同时更新的情况，无法保证多个节点之间的更新顺序。为此Dynamo引入向量时钟（Vector Clock）的技术手段来尝试解决冲突，如图5-2所示。

图　5-2　向量时钟

Dynamo中的向量时钟用一个[nodes,counter]对表示。其中，nodes表示节点，counter是一个计数器，初始为0，节点每次更新操作加1。首先，Sx对某个对象进行一次写操作，产生一个对象版本D1（[Sx，1]），接着Sx再次操作，counter值更新为2，产生第二个版本D2（[Sx，2]）；之后，Sy和Sz同时对该对象进行写操作，Sy将自身的信息加入向量时钟产生了新的版本D3（[Sx，2]，[Sy，1]），Sz同样产生了新的版本信息D4（[Sx，2]，[Sz，1]），这时系统中就有了两个冲突的版本。最常见的冲突解决方法有两种：一种是通过客户端逻辑来解决，比如购物车应用；另外一种常见的策略是"last write wins"，即选择时间戳最新的副本，然而，这个策略依赖集群内节点之间的时钟同步算法，不能完全保证准确性。

向量时钟不能完美解决冲突，即使N+W＞R,Dynamo也只能保证每个读取操作能读到所有的更新版本，这些版本可能冲突，需要进行版本合并。Dynamo只保证最终一致性，如果多个节点之间的更新顺序不一致，客户端可能读取不到期望的结果。这个不一致问题需要注意，因为影响到了应用程序的设计和对整个系统的测试工作。