阅读笔记（十六）高可用KV数据存储Dynamo实现细节《Dynamo: Amazon’s Highly Available Key-value Store》

╰+哭是因爲堅強的太久メ 2023-07-02 05:23 25阅读 0赞

### 一. 简介 ###

Dynamo是亚马逊的一个高可用分布式存储系统，《Dynamo: Amazon’s Highly Available Key-value Store》一文详细描述了该系统的整个架构及思考。Dynamo作为亚马逊的数据存储系统，最关键的在于满足用户的需求，保持极高的可用性，因为哪怕几秒的无法使用也可能造成极大的经济损失。因此Dynamo的建立初衷为强可用性弱一致性（最终一致性）[AP模型][AP]。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70]  
  上图是一个Dynamo技术栈的大致分布图，Dynamo使用了众多技术，包括K-V映射，同步技术，冲突检测，异步复制，出错检测，分区还原等。本文对Dynamo的各层结构进行简单概括并记录，下图是Dynamo中采用的技术。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70 1]

### 二. 数据的定位Consistent Hashing ###

无论是读写，我们首先需要的是确认数据的位置，即K-V映射关系的建立。在Dynamo中，采用的是一致性哈希（Consistent Hashing）实现。其核心思想是一个Key可以映射到多个节点，即多个备份。这种做法有几个好处：

1.  对于客户端来说，可以就近查询数值而不需要多条请求远端数据
2.  方便数据丢失时恢复数据
3.  利于实现负载均衡

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70 2]  
  如上图所示为一致性哈希采取的环形存储，箭头表示key计算出的值得分布。A，B，C是三个不同的节点，策略1是随机计算T个值并存储，策略2是随机计算并等分存储，而策略3则是有规律的计算并存储。Dynamo通过测试发现策略3相对来说有着最佳的负载均衡率，而策略2最差。具体测试结果如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70 3]

### 三. 分区一致性Sloopy Quorum ###

当我们通过一致性哈希解决了数据存放位置的问题后，需要解决的问题就在于数据的同步性问题，即共识问题。类似于[Paxos][]，Raft等共识算法，Dynamo采取的是Sloopy Quorum而不是严格Quorum。这样做的原因显然也是为了高可用性考虑：严格Quorum需要大多数人投票同意才可达成共识，而Sloopy Quorum仅需要写和读部分节点并比较，核心思想为：

1.  用户选择一定数量的W/N个节点去写入
2.  用户从R/N个节点中读取数据

通常，我们需要保证R + W > N，从而实现至少有一个节点覆盖了读和写的操作。关于R和W的选值，其实反应了模型的不同要求：

*  R = 1, W = N：快速读，慢速写
 *  R = N, W = 1：快速写，慢速读
 *  R = N / 2, W = N / 2 + 1，适中选择

在实际中，很少使用N超过3的模型，因为多个备份会极大的增加系统的存储量，是极大的负担。因此，一般针对性的会选择N=3， R, W 在1和2之间变化的模型。比如

*  Basho’s Riak采用N = 3, R = 2, W = 2
 *  Linkedin’s Voldmort采用N = 2 或 3, R = 1, W = 1
 *  Apache’s Cassandra采用N = 3, R = 1, W = 1

### 四. 写入同步 Vector Clock ###

对于写入的冲突检测和融合，Dynamo采取类似vector clock的方式进行处理，在[vector clock][]一文中详细介绍实现细节和可能存在的问题。下图为一个简单的冲突融合过程。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70 4]

### 五. 错误检测Gossip算法以及数据恢复的Merkle Tree ###

gossip是一种用于错误检测的概率性算法，详细介绍可以见[该文][Link 1]。而Merkle Tree，即哈希树，是常用的统计、检测用的存储方式，在数据检测、下载检测等多出均有使用。基本原理是采用二分法将文件分为多个小块，然后依次求哈希。根节点根据叶子结点求哈希，依次求得。比较的适合，从根节点开始比较，从而避免整个文件全部拷贝，只需要针对性的恢复出错的一小部分即可。

### 六. 总结 ###

本文大致分析了Dynamo架构各个方面的实现细节和特点，但是论文原文中还有很多内容是本文没有涵盖的，比如其他公司的产品介绍、比如Dynamo开发中获得的经验教训、比如后续优化改进等等，有兴趣还是深入研究原文为佳。

[AP]: https://blog.csdn.net/u013354486/article/details/103831931
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200203162909794.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200203163027960.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200203171821898.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200203172205119.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY=,size_16,color_FFFFFF,t_70
[Paxos]: https://blog.csdn.net/u013354486/article/details/104081997
[vector clock]: https://blog.csdn.net/u013354486/article/details/104113744
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200203171601176.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY=,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/u013354486/article/details/104088402