分布式存储引擎大厂实战——一致性哈希大厂应用背景数据如何存储的DHT优化
背景
作为k-v存储的创始人，Dynamo从亚马逊开发出来后，在存储领域引起了广泛的关注。 理论上，Dynamo可以无限扩展，性能无限线性增加。 为什么理论上无限地线性增加，将在后面叙述。 Dynamo的动态伸缩使系统的缩放输出能力非常高。 Dynamo将dynamoDB作为nosql领域的代表性DB进行了扩展。 要防止Dynamo无限扩展系统和降低性能，关键是整个存储群集中没有中心节点，并且所有扩展的节点都可以与群集中的其他节点平衡负载。 为了实现这种能力，必须依赖数据均匀分布的算法，该算法足够随机，且节点变动时，不能引起数据的大面积破坏(大部分数据会发生集群的可伸缩性) 这时，分布式哈希表(DHT )应运而生。
在讨论数据是如何存储的之前，请先讨论分布式群集中的数据是如何存储的。 既然是分布式群集，数据就以分布式方式存储，只存在于一个节点上。 必然需要存储逻辑来控制数据以分布式方式存储在群集中。 例如，假设群集中有4个节点node 1、node 2、node 3、node 4，要保存的数据将保存1~20这20个数字。 那么，怎么做数据呢？ ”节点的存储关系？ 比较常用的是节点数取模算法，该算法产生的数据分布如下。
该映射的关系是，数据n(1=n=20 )根据m=n%4) 1被存储在m的node中。 如果此时添加了集群中的一个节点，成为了node5，数据将如何分布？
同样，根据m=n%5 1的原则，数据分布如下，比较从4个节点到5个节点的数据分布可知，实际上只有4个数据留在原来的节点上，其他的数据分布完全改变为1-4/20=80% 可以看出，添加新桶后，80%发生了变化。 这意味着每次扩展和收缩此哈希表时都会重新计算条目的分布。 某些场景不能接受这个特性。 如下图所示
在分布式存储系统中，图中的每个桶相当于一台机器，文件分布在哪个机器上由散列算法决定，该系统由添加一台机器的散列算法决定，该系统由一台机器所有数据访问路径都出现了问题，尽管在一台机器停机时仅删除了部分数据，但整个服务仍将无法顺利扩展，从而成为一个有状态的服务那么，如何实现无状态化呢？ 今天的主角DHT算法出现了。 DHT全名(分布式hash table，分布式哈希表)。 根据前述的仿真算法，数据分布发生变动的理由是，数据分布逻辑随着节点的变化，规则完全发生了变化，不能使分布的数据的继承性变好(也就是说，数据依然大部分分布在原来的节点上)
典型的DHT模型具有环形结构，用于将所有输入key的哈希值映射到一个环形空间。 请看上面的例子。 数据1-20必须存储在四个节点上。 环形空间用0-63(2的n次方-1，在此为n=6)表示。 这里，在散列[密钥]范围属于0-15]时映射到节点1，在散列[密钥]范围属于[ 15，31 ]时映射到节点2，散列[密钥]范围为[ 31，47 ]
此时，增加1个节点node5变为5个，散列范围保持0-63的话，映射规则会发生变化，新增加的节点也将分配部分空间的映射。 作为可能的空间分配之一，节点node5被添加在node4和node 1之间，此时的空间分配可能如下。 如果范围为0-15]，则映射到节点1；如果散列[密钥]范围为[ 15，31 ]，则映射到节点2；如果散列[密钥]范围为[ 15，31 ]，则映射到节点2
相反，假设此时一个节点退出集群，一个节点减少。 例如node3结束后，数据如何分布？ 如果根据数据用hash值顺时针寻找并存储离自己最近的节点，则如果范围属于0-15]，则映射到节点1，如果hash[key]范围属于[ 15，31 ]，则映射到节点2，如果hash[key]
显然，对于新添加的节点，如果已分配了足够的映射空间，则1-8/64=87.5%的数据分布在原节点上，如果减少了一个节点，则1-16/64=75%的数据分布在原节点上数据的变动范围大幅减少。 比较前后两种模式，可以感受到DHT算法进行分布式数据分布的好处。 第二种方法有什么问题吗？ 施工中是这样直接使用的吗？ 对工程中的使用方法进行优化。
DHT优化的最初问题是，最初4个节点平均分配空间，但是添加新节点后，node4和node5的分配空间与其他节点相比明显减少了一半，减少1个节点node3后，node4的分配空间是其他节点的2倍由此，各节点的负载能力不同，各节点
的能力无法均衡。所以首先这里有一个问题，分摊空间的节点最好是不变的，不变那怎么增加节点或者删除节点呢？所以真正的工程应用上引申出logic节点的概念，又叫partition。 空间一开始就按partition分配好，如把空间 2 32 ^{{2^{32}}} 232 映射到partition（每个partition用p表示）。见上图把空间分成了8份。这8个逻辑空间是不会再变化的，然后就有一层逻辑节点到物理节点的映射关系，再以前4个物理节点为例，那么partition到node的映射关系如下图：
这时候如果新增一个节点node5，则映射关心将会变化，会从node2、node3上把partition迁移到node5上。这种叫做数据均衡算法，它是节点在出现变化时系统保持各节点负载均衡的一种机制，这个算法会对系统可靠性以及性能影响很大。
从上图的增加节点数据重新迁移分配可以看出，partition必须足够多，不然各个物理节点负载能力还是会有比较大的差异（比如上图，迁移后，node2和node3的负载不其它节点少了一半）。
一般在工程应用里面增加或者退出节点的时候，系统是会对业务IO做降级处理的，优先保障数据的均衡完成。因为存储产品的工程应用里面选择了CAP的AP两个点，从而实现最终一致性。
本章对一致性哈希进行了讲解，后续将介绍在分布式存储系统中，数据是如何保证可靠性以及一致性的。