一、前言

随着互联网的发展，用户产生的数据越来越多，企业面临着庞大数据的存储问题，目前市面上主流的分布式大数据文件系统，都是对数据切片打散，通过离散方法将数据散列在集群的所有节点上，本文将带你了解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值。

01.png

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

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

02.png

初始化DHT的源码如下：

03.png

首先定义了一个存放集群节点元数据的Map，用来存储接入到DHT环中的物理节点数据。然后定义了一个DHT环——vNodes，用来存储DHT环中的节点位置信息。这样我们就实现了一个简单的DHT环，通过addPhysicalNode方法可以模拟集群节点的加入。加入时会计算节点的Hash值并存放到vNodes中。

04.png

初始化4个存储节点。

05.png

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

06.png

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

07.png

插入100万条数据后，各个节点的数据分布如下，虽然每个节点都分配到了数据，但仍然出现了较大的数据倾斜。这将导致99%的请求都会由Node3进行处理，出现一核有难三核围观的情况。

08.png

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

09.png
10.png

说了一个简单DHT环的基本原理后，再来思考一个问题：简单的DHT环数据离散，但仍然存在数据倾斜的情况，还不如用传统的hash方式分配数据。

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

我们还是用之前分配好的100万条数据，模拟节点4故障，如下图所示，Node4上的数据只迁移到了Node1，对Node2和Node3不产生数据迁移，从而降低了节点故障导致每个节点都需要进行数据迁移带来的影响。

11.png

五、DHT 的改进

1、虚拟节点

大家思考一下，解决数据倾斜的问题可以如何解决？

通过增加集群节点的方式最简单直接，目的是将更多的节点散列到DHT环上，使得环上所有节点分布更加均匀，节点间的区间间隔尽可能的均衡，以下是10个节点和20个节点集群的数据分布情况。

12.png
13.png

可以发现，通过增加节点的方式，仍然无法从根本上解决数据倾斜的问题。并且增加节点会提高集群的设备成本和维护成本。同时，这种方案还引出了一个严重的问题，如果Node20故障了，那么Node20的数据会全数迁移到下一个节点上，最终导致集群出现数据倾斜，数据较多的节点还将处理更多的IO请求，容易形成数据热点，成为性能瓶颈，引发集群整体的性能下降。

14.png

（2） 引入虚拟节点

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

image image

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

17.png

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

18.png

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

19.png

当Node3故障后，Node3上的数据被均匀的分散到其他节点上，不会出现数据倾斜的情况。

20.png

2、负载边界因子

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

[图片上传失败...(image-42435a-1605674270363)]

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

image image

打开负载边界因子开关的情况：

[图片上传失败...(image-3b3239-1605674270363)]

在打开负载边界因子开关后，数据得到了较好的均衡。

六、DHT 引发的思考

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

可以看到，DHT提供了一种负载均衡的思路。利用hash算法的特性，将数据或业务请求分散到集群中的各个节点上，提高系统容错性。

vivo 用户运营开发团队