[数据结构与算法]Dynamo分布式键值系统的一点理解

解决了什么问题

高可用的、可持续写入的存储服务。

P2P的系统，伸缩灵活。

几个关键问题和解决方案

数据分布

哈希环

将待存储的键值对中键的Hash值范围看成首尾相连成为一个环。环上的每个节点负责存储的数据为顺时针方向其前一个节点到当前节点的哈希值范围对应的数据。

为了数据分布的均匀一致，并且考虑到节点的异构性(节点性能、磁盘空间差异)，引入了虚拟节点。将哈希环进一步按照细粒度分割，最好等距分割(这样数据的归档、重新分布都很容易)，分割后的哈希环上的每一段，都视为一个虚拟节点，再按照每个物理节点的负载，为其与分配负载相当数量的虚拟节点。

数据备份

NWR是一种一致性和可用性的平衡策略。N代表数据的副本数量，W代表写请求成功的最少副本数量，R代表读请求成功的最少副本数量。举个例子，N=3表示副本数量是3；W=2表示两个副本数据写成功后这个写请求就是成功的，可以给客户返回成功；R=2表示成功读取到两个副本数据，就可以给客户返回了。这个NWR保证的是，当有1个节点失效后，集群还是可以正常工作的。当系统比较重视读的效率时，可以设置R=1；当系统比较注重写的效率时，可以设置W=1。

成员管理

交换mapping

集群初始化后，每个节点都记录了自己的哈希段(虚拟节点)、物理节点、副本的哈希段，称为mapping；节点间通过定期交换mapping，每个节点都知道了其他节点的mapping信息，这样就可以处理请求的转发了。

节点加入

当有新节点加入，新节点先与种子节点交换mapping，再与其他节点交换mapping, 直到所有节点的mapping一致。除此之外，新节点还会从其他节点接管过来属于自己的哈希段，类似于替其他节点分担压力，这就涉及到数据迁移，以及mapping的再同步。

节点退出

当已有节点出现故障且无法恢复时，这个节点被视为退出了，该节点负责的哈希段数据由顺时针方向该节点的下一个节点负责接管，这个接管节点先从mapping中找出故障节点的备份节点，通过Merkle树(后面具体讲)将不止一致的数据同步到本节点，并且更新本节点mapping。

短暂故障处理

当某个节点在短时间内无法响应请求，会由其他节点暂存新写入的数据，这些数据会存放在单独的数据库中，当节点恢复后，再由接管的节点将暂存的数据从本节点同步到恢复的节点，当同步成功后，再将暂存的数据从接管节点删除。这样的好处是不用重新进行数据分布和数据迁移，用来应对节点的临时故障十分快速有效。对于读请求，只要其他副本还正常工作且满足NWR策略，并不影响当前系统的读操作。

永久故障处理

当节点永久故障时，需要将故障节点的数据迁移到新接管的节点中，或者当多个副本进行数据一致性检测时，都需要进行数据同步。这里有两个重要的点，一个是快速的发现不一致，另一个是只同步不一致的数据。当数据量比较少的时候，我们可以遍历节点中的数据逐个对比，当海量数据的时候，我们不得不需要另辟蹊径。Merkle树是一种很理想的数据结构，它的每个叶子对应每个对象值的哈希值，每个非叶子都对应其子孙的哈希值，这样层层向上知道跟节点，对应的就是整个节点中存储对象的哈希值。到这里，已经很明显了，通过对比两个节点Merkle树的根节点就可以知道数据是否一致，这就解决了上述的第一个问题，快速发现是否一致；然后顺着根节点找出所有不一致的字节点、最后直到叶子节点，这些叶子就是不一致的数据，仅同步这些叶子节点的数据即可，这就解决了第二个问题，精准同步差异数据。