分布式集群如何实现高效的数据分布，一致性哈希、分布式哈希表

秒速五厘米 2022-10-30 11:19 137阅读 0赞

### 分布式集群如何实现高效的数据分布，一致性哈希、分布式哈希表 ###

*  一、前言
 *  二、技术背景
 *  三、传统 Hash
 *  四、一个简单的 DHT
 *  五、DHT 的改进
 *   *  1、虚拟节点
     *   *  （1）增加集群节点
         *  （2） 引入虚拟节点
     *  2、负载边界因子
 *  六、DHT 引发的思考

# 一、前言 #

随着互联网的发展，用户产生的数据越来越多，企业面临着庞大数据的存储问题，目前市面上主流的分布式大数据文件系统，都是对数据切片打散，通过离散方法将数据散列在集群的所有节点上，本文将带你了解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值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]  
如图所示，先将存储节点通过 Hash计算后添加到 DHT 环上，每个节点距离上一个节点间的这段区间，作为该节点的数据分区，Hash值落在这个分区的数据将存储到这个节点上；

然后将数据通过 Hash算法散列到DHT环上，数据落到DHT环上后，按照顺时针方向找到离自己最近的节点作为数据存储节点，如下所示，数据 ObjectA 落到节点 NodeA上，数据 ObjectB 落到节点 NodeB 上；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]  
初始化DHT的源码如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]  
首先定义了一个存放集群节点元数据的Map，用来存储接入到DHT环中的物理节点数据。然后定义了一个DHT环——vNodes，用来存储DHT环中的节点位置信息。这样我们就实现了一个简单的DHT环，通过addPhysicalNode方法可以模拟集群节点的加入。加入时会计算节点的Hash值并存放到vNodes中。  
![图片: https://uploader.shimo.im/f/9l8g7BCYTZrLsnQm.png][https_uploader.shimo.im_f_9l8g7BCYTZrLsnQm.png]  
初始化4个存储节点。  
![在这里插入图片描述][20210219102234288.png]  
通过countNodeValue方法插入100条数据，在写数据的过程中，根据数据的 Hash值找到DHT环上最近的一个节点，然后将数据写入该节点中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]  
插入100条数据后，各个节点的数据分布如下，可以看见4个节点的数据并不均匀，只有一个节点分配到了数据（这与写入的数据也有一定关系）。  
![在这里插入图片描述][20210219102304852.png]  
插入100万条数据后，各个节点的数据分布如下，虽然每个节点都分配到了数据，但仍然出现了较大的数据倾斜。这将导致99%的请求都会由Node3进行处理，出现一核有难三核围观的情况。  
![在这里插入图片描述][20210219102316707.png]

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

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

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

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

# 五、DHT 的改进 #

## 1、虚拟节点 ##

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

### （1）增加集群节点 ###

通过增加集群节点的方式最简单直接，目的是将更多的节点散列到DHT环上，使得环上所有节点分布更加均匀，节点间的区间间隔尽可能的均衡，以下是10个节点和20个节点集群的数据分布情况。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]  
可以发现，通过增加节点的方式，仍然无法从根本上解决数据倾斜的问题。并且增加节点会提高集群的设备成本和维护成本。同时，这种方案还引出了一个严重的问题，如果Node20故障了，那么Node20的数据会全数迁移到下一个节点上，最终导致集群出现数据倾斜，数据较多的节点还将处理更多的IO请求，容易形成数据热点，成为性能瓶颈，引发集群整体的性能下降。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 7]

### （2） 引入虚拟节点 ###

为了解决数据倾斜的问题，引入了虚拟节点的概念。虚拟节点也就是真实节点的一个逻辑副本，如图所示，对节点NodeA进行3次虚拟节点hash分布，形成了虚拟节点NodeA1、NodeA2、NodeA3。当NodeA故障后，指向NodeA的数据会指向NodeB、NodeC。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 9]  
当引入虚拟节点数量为100时，数据已经分散在各个节点上了，如果虚拟节点足够多，最终将达到数据均衡的状态。  
![在这里插入图片描述][20210219102605456.png]

虚拟节点数据1万时的数据分布：  
![在这里插入图片描述][20210219102620101.png]  
虚拟节点数量为100万时的数据分布：  
![在这里插入图片描述][20210219102659499.png]  
当Node3故障后，Node3上的数据被均匀的分散到其他节点上，不会出现数据倾斜的情况。  
![在这里插入图片描述][20210219102703610.png]

## 2、负载边界因子 ##

这样就完美了吗？我们初始化一个4个节点的DHT环，虚拟节点设置为100，然后插入100条数据，并打印DHT环的元数据信息如下：  
![在这里插入图片描述][20210219102719505.png]  
可以发现，虽然设置的虚拟节点，但是仍然无法均衡的将节点散列到DHT环上，导致Node2过载，Node1空闲。我们再思考一种极端场景，当我们的数据恰好计算hash值后都在区间A，而这个区间只有NodeA，那么仍然出现了数据倾斜。如何解决这个问题呢，这里我们引入一个叫负载边界因子的概念。DHT环部署了4个节点，总共有100条数据要插入，那么平均下来每个节点的权重就是100/4+1=26，当数据映射过程中达到了该节点的权重，则映射到下一个节点，下面是代码实现。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][20210219102741586.png]  
打开负载边界因子开关的情况：  
![在这里插入图片描述][20210219102755201.png]  
在打开负载边界因子开关后，数据得到了较好的均衡。

# 六、DHT 引发的思考 #

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221024/43585f50c9504524ac6add7f3ba0dcb1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]: /images/20221024/ff29a301d96443a9be1a6cec3cc4831a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]: /images/20221024/98d1b927edfc49bd9312ea1801966d49.png
[https_uploader.shimo.im_f_9l8g7BCYTZrLsnQm.png]: /images/20221024/d346b46fc248443f9f196ac205250d33.png
[20210219102234288.png]: /images/20221024/e8e0d0a1d1a34779814ad64ef26ac85f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]: /images/20221024/31a3348eb88942ab900094b2df89a384.png
[20210219102304852.png]: /images/20221024/3f494e7c548c4f1882de736176a73d7f.png
[20210219102316707.png]: /images/20221024/3da54a10fc284e34a09817ae2214c0d2.png
[20210219102324920.png]: /images/20221024/3e34ece3d42440168f8af7a2622e8dae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 4]: /images/20221024/8eaf170efb8b48d2ab4d19054b7e079e.png
[20210219102401518.png]: /images/20221024/36cbf92e3aeb40a4b894efc752b3e6cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]: /images/20221024/d1654a26c119487ca4673f6910b6447d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]: /images/20221024/70f6a9b9594749ab98204c475224208e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 7]: /images/20221024/2f1db9ff10db4d3bb86eb85c473f1d27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 8]: /images/20221024/0c7e3d7054a043eb9cfeb591da48f760.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 9]: /images/20221024/94cb691302dd475b9eab6e959f25034d.png
[20210219102605456.png]: /images/20221024/6da8ee21c1ee40a2844c4fc7ce190f54.png
[20210219102620101.png]: /images/20221024/fd6f7ad27d9348e3bc855d8b80f8434e.png
[20210219102659499.png]: /images/20221024/47e015482f514d72bbdddf25a31827de.png
[20210219102703610.png]: /images/20221024/211c1fdf4a71492c81ef47bcc0edaf57.png
[20210219102719505.png]: /images/20221024/0166eafe49aa4c0b8bacd263978df190.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 10]: /images/20221024/ca0cd1ceee4d452d99772966408831e7.png
[20210219102741586.png]: /images/20221024/a23caef7ce8c43d9a2127c03b4538506.png
[20210219102755201.png]: /images/20221024/6fedca5a1cc94686a0b402982544e990.png