分布式集群如何实现高效的数据分布

用户头像
vivo互联网技术
关注
发布于: 2020 年 11 月 16 日
分布式集群如何实现高效的数据分布

一、前言



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

发布于: 2020 年 11 月 16 日 阅读数: 1172
用户头像

官方公众号:vivo互联网技术,ID:vivoVMIC 2020.07.10 加入

分享 vivo 互联网技术干货与沙龙活动,推荐最新行业动态与热门会议。

评论 (3 条评论)

发布
用户头像
2020 年 11 月 19 日 18:09
回复
用户头像
LAXCUS大数据集群操作系统的分布处理架构做得很好!采用了轮循+散列+分支预测多种手段。
2020 年 11 月 19 日 18:08
回复
用户头像
一致性哈希的多机版?
2020 年 11 月 18 日 19:21
回复
没有更多了
分布式集群如何实现高效的数据分布