5.1.3　容错

Dynamo把异常分为两种类型：临时性的异常和永久性异常。有一些异常是临时性的，比如机器假死；其他异常，如硬盘报修或机器报废等，由于其持续时间太长，称为永久性的。下面解释Dynamo的容错机制：

●数据回传　在Dynamo设计中，一份数据被写到K，K+1，……，K+N-1这N台机器上，如果机器K+i（0≤i≤N-1）宕机，原本写入该机器的数据转移到机器K+N，如果在指定的时间T内K+i重新提供服务，机器K+N将通过Gossip协议发现，并将启动传输任务将暂存的数据回传给机器K+i。

●Merkle树同步　如果超过了时间T机器K+i还是处于宕机状态，这种异常被认为是永久性的。这时需要借助Merkle树机制从其他副本进行数据同步。Merkle树同步的原理很简单，每个非叶子节点对应多个文件，为其所有子节点值组合以后的哈希值；叶子节点对应单个数据文件，为文件内容的哈希值。这样，任何一个数据文件不匹配都将导致从该文件对应的叶子节点到根节点的所有节点值不同。每台机器对每一段范围的数据维护一颗Merkle树，机器同步时首先传输Merkle树信息，并且只需要同步从根到叶子的所有节点值均不相同的文件。

●读取修复　假设N=3，W=2，R=2，机器K宕机，可能有部分写操作已经返回客户端成功了但是没有完全同步到所有的副本，如果机器K出现永久性异常，比如磁盘故障，三个副本之间的数据一直都不一致。客户端的读取操作如果发现了某些副本版本太老，则启动异步的读取修复任务。该任务会合并多个副本的数据，并使用合并后的结果更新过期的副本，从而使得副本之间保持一致。