共计 2656 个字符，预计需要花费 7 分钟才能阅读完成。
一、前言
随着互联网的倒退，用户产生的数据越来越多，企业面临着宏大数据的存储问题，目前市面上支流的分布式大数据文件系统，都是对数据切片打散，通过离散办法将数据散列在集群的所有节点上，本文将带你理解 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 用户经营开发团队
