数据分布的方式

前言

在分布式集群中,会把数据分散存储到不同节点。

常见的数据分布方式有两种,分别是顺序分布和哈希分布。

 

顺序分布

顺序分布就是把一整块数据按照顺序,分散到很多机器中。

比如有数据 1- 100,那么划分数据时,可能 1 到 50 分布到机器1,51 到 100 分布到机器 2

 

哈希分布

1、节点取余

使用特定的数据(比如用户ID),根据节点数量 N,使用公式:hash(key) % N 计算出一个 0~(N-1)值,决定数据映射到哪一个节点上。

缺点:当节点数量 N 变化时(扩容或者收缩),数据和节点之间的映射关系需要重新计算,这样的话,按照新的规则映射,要么之前存储的数据找不到,要么之前数据被重新映射到新的节点。

实践:常用于数据库的分库分表规则,一般采用预分区的方式,提前根据数据量规划好分区数,比如划分为 512 或 1024 张表,保证可支撑未来一段时间的数据量,再根据负载情况将表迁移到其他数据库中。

 
2、一致性哈希

一致性哈希分区(Distributed Hash Table)实现思路是为系统中每个节点分配一个 token,范围一般在 0~232 ,这些 token 构成一个哈希环。

数据读写,执行节点查找操作时,先根据 key 计算 hash 值,然后顺时针找到第一个大于等于该哈希值的 token 节点

如图,n1 ~ n4 是 4 个节点。

图中的黄点代表数据,根据 key 计算哈希值,现在四个黄点都位于 n2 和 n3 之间,找到顺时针最近的节点 n3。(现在,还没有添加蓝色的 n5 节点)

这时,如果我们在 n2 和 n3 之间增加一个节点 n5,就会有两个黄点写到 n5,另外的两个黄点还是写入 n3。

数据虽然还是会发生漂移,但是这个时候你是否注意到,其实只有 n2 ~ n3 这部分的数据被漂移,其他的数据都是不会变的。

这种方式相比节点取余最大的好处在于加入和删除节点只影响哈希环中相邻的节点,对其他节点无影响

缺点:

每个节点的负载不相同,因为每个节点的hash是根据 key 计算出来的,换句话说就是假设 key 足够多,被 hash 算法打散得就将非常均匀;但是如果 key 过少,导致每个节点处理的 key 个数不太一样,甚至相差很大,这就会导致某些节点压力将会很大。

 
3、虚拟槽分区

虚拟槽分区巧妙地使用了哈希空间,使用分散度良好的哈希函数把所有数据映射到一个固定范围的整数集合中,整数定义为槽(slot)。这个范围一般远远大于节点数,比如 Redis Cluster 槽范围是0~16383。槽是集群内数据管理和迁移的基本单位。采用大范围槽的主要目的是为了方便数据拆分和集群扩展。每个节点会负责一定数量的槽,下图所示。

当前集群有5个节点,每个节点平均大约负责3276个槽。由于采用高质量的哈希算法,每个槽所映射的数据通常比较均匀,将数据平均划分到5个节点进行数据分区。Redis Cluster 就是采用虚拟槽分区,下面就介绍 Redis 数据分区方法。

每当 key 访问过来,Redis Cluster 会计算哈希值是否在这个区间里。它们彼此都知道对应的槽在哪台机器上,这样就能做到平均分配了。

 

 



Top