一、前言

随着互联网的倒退，用户产生的数据越来越多，企业面临着宏大数据的存储问题，目前市面上支流的分布式大数据文件系统，都是对数据切片打散，通过离散办法将数据散列在集群的所有节点上，本文将带你理解DHT（Distributed Hash Table）：分布式哈希表是如何实现数据的分布式离散存储的。

DHT（Distributed Hash Table）：分布式哈希表

二、技术背景

互联网倒退晚期，数据通常存储在单个服务器上，初期数据增长较为迟缓，能够通过晋升单机的存储能力满足数据的增长需要；随着互联网遍及水平的推动，用户数、用户产生和拜访的数据呈指数增长；单机已无奈存储用户须要的数据。为此，迫切需要多个服务器独特合作，存储量级更大的数据。

三、传统 Hash

传统 Hash 通过算法 hash()=X mod S 来对数据进行扩散，在元数据比拟扩散的状况下，数据可能很好的散列在集群节点中。因为S代表了集群的节点数，当进行集群的扩容缩容时，S的变动会影响到历史数据的命中问题，因而为了进步数据命中率，会产生大量测数据迁徙，性能较差。

四、一个简略的 DHT

分布式 Hash 通过结构一个长度为2的32次方（ipv4地址的数量）的环，将节点散列在 Hash环上，依据不同的 Hash算法计算出来的 Hash值有所不同，本文采纳FNV Hash算法来计算 Hash值。

如图所示，先将存储节点通过 Hash计算后增加到 DHT 环上，每个节点间隔上一个节点间的这段区间，作为该节点的数据分区，Hash值落在这个分区的数据将存储到这个节点上；

而后将数据通过 Hash算法散列到DHT环上，数据落到DHT环上后，依照顺时针方向找到离本人最近的节点作为数据存储节点，如下所示，数据 ObjectA 落到节点 NodeA上，数据 ObjectB 落到节点 NodeB 上；

初始化DHT的源码如下：

首先定义了一个寄存集群节点元数据的Map，用来存储接入到DHT环中的物理节点数据。而后定义了一个DHT环——vNodes，用来存储DHT环中的节点地位信息。这样咱们就实现了一个简略的DHT环，通过addPhysicalNode办法能够模仿集群节点的退出。退出时会计算节点的Hash值并存放到vNodes中。

初始化4个存储节点。

通过countNodeValue办法插入100条数据，在写数据的过程中，依据数据的 Hash值找到DHT环上最近的一个节点，而后将数据写入该节点中。

插入100条数据后，各个节点的数据分布如下，能够看见4个节点的数据并不平均，只有一个节点调配到了数据（这与写入的数据也有肯定关系）。

插入100万条数据后，各个节点的数据分布如下，尽管每个节点都调配到了数据，但依然呈现了较大的数据歪斜。这将导致99%的申请都会由Node3进行解决，呈现一核有难三核围观的状况。

呈现如上问题是什么起因呢？通过查看DHT环上各节点的hash值不难看出，各节点间距不平均，插入的数据按顺时针查找节点时都找到了Node3，因而数据都写到了Node3外面，所以节点区间不平均会使某些节点能笼罩更多的数据，导致数据不平衡。

说了一个简略DHT环的基本原理后，再来思考一个问题：简略的DHT环数据离散，但依然存在数据歪斜的状况，还不如用传统的hash形式调配数据。

后面提到传统的hash形式在过后在节点故障后，整个集群的数据会进行大量的迁徙，影响集群性能，那么DHT能解决这一问题吗？

咱们还是用之前调配好的100万条数据，模仿节点4故障，如下图所示，Node4上的数据只迁徙到了Node1，对Node2和Node3不产生数据迁徙，从而升高了节点故障导致每个节点都须要进行数据迁徙带来的影响。

五、DHT 的改良

1、虚构节点

大家思考一下，解决数据歪斜的问题能够如何解决？

通过减少集群节点的形式最简略间接，目标是将更多的节点散列到DHT环上，使得环上所有节点散布更加平均，节点间的区间距离尽可能的平衡，以下是10个节点和20个节点集群的数据分布状况。

能够发现，通过减少节点的形式，依然无奈从根本上解决数据歪斜的问题。并且减少节点会进步集群的设施老本和保护老本。同时，这种计划还引出了一个重大的问题，如果Node20故障了，那么Node20的数据会全数迁徙到下一个节点上，最终导致集群呈现数据歪斜，数据较多的节点还将解决更多的IO申请，容易造成数据热点，成为性能瓶颈，引发集群整体的性能降落。

（2） 引入虚构节点

为了解决数据歪斜的问题，引入了虚构节点的概念。虚构节点也就是实在节点的一个逻辑正本，如图所示，对节点NodeA进行3次虚构节点hash散布，造成了虚构节点NodeA1、NodeA2、NodeA3。当NodeA故障后，指向NodeA的数据会指向NodeB、NodeC。

当引入虚构节点数量为100时，数据曾经扩散在各个节点上了，如果虚构节点足够多，最终将达到数据平衡的状态。

虚构节点数据1万时的数据分布：

虚构节点数量为100万时的数据分布：

当Node3故障后，Node3上的数据被平均的扩散到其余节点上，不会呈现数据歪斜的状况。

2、负载边界因子

这样就完满了吗？咱们初始化一个4个节点的DHT环，虚构节点设置为100，而后插入100条数据，并打印DHT环的元数据信息如下：

能够发现，尽管设置的虚构节点，然而依然无奈平衡的将节点散列到DHT环上，导致Node2过载，Node闲暇。咱们再思考一种极其场景，当咱们的数据恰好计算hash值后都在区间A，而这个区间只有NodeA，那么依然呈现了数据歪斜。如何解决这个问题呢，这里咱们引入一个叫负载边界因子的概念。DHT环部署了4个节点，总共有100条数据要插入，那么均匀下来每个节点的权重就是100/4+1=26，当数据映射过程中达到了该节点的权重，则映射到下一个节点，上面是代码实现。

关上负载边界因子开关的状况：

在关上负载边界因子开关后，数据失去了较好的平衡。

六、DHT 引发的思考

上述的只是一个简略的DHT，数据也做了简化，数据的存储和读取都须要查问DHT环，如何晋升DHT的读写性能？如何晋升DHT的高牢靠？当节点故障后，如何将故障节点的数据迁徙到新的节点？如何做好数据备份？如何保障正本数据不集中在一个节点上？也是须要去思考的，本文只是抛砖引玉简略的介绍了DHT根本的思维，更多生产环境面临的挑战，在此不做开展。

能够看到，DHT提供了一种负载平衡的思路。利用hash算法的个性，将数据或业务申请扩散到集群中的各个节点上，进步零碎容错性。

vivo  用户经营开发团队