分布式数据分区算法之一致性哈希算法
分布式系统特点
分布式系统
分布式系统主要是为了解决了单机限制,通过把计算和数据分布在不同的节点,当客户端查询时,查询负载也随之分布到不同节点上。
分布式数据系统
当今许多应用属于数据密集型(data-intensive
),而不是计算密集型(compute-intensive
)。对于数据密集性应用,CPU的处理能力往往不是第一限制,关键在于数据量、数据复杂度以及数据多变情况下如果对数据进行存储。
分布式数据系统特点
我们常见一些中间件如kafka
就是一个典型的分布式数据系统。一个典型kafka架构包含分区(Partition)、副本(Replicas)等术语。
数据分区
Kafka Partition也就是数据分区,采用数据分区的主要目的是提高可扩展性。通过把不同数据放到不同节点磁盘上,提高了单机磁盘存储上限。
数据复制
通常数据分区主要和数据复制结果使用。既每个分区在多个节点上都有副本。kakfa保存数据副本目的主要是为了提高系统的容错性,避免某一节点出现故障数据丢失。
如何让数据存储在不同分区
假设面临海量数据,现在需要切分他们,那么该如何决定哪些记录放在哪些节点上呢?
数据分区主要目标是将数据和查询负载均衡分布在所有节点上。如果节点平均分摊负载,那么理论上10个节点应该能够处理10倍的数据量和10倍于单个节点的吞吐量(忽略复制)。而如果分区不均匀,则会出现某些分区节点比其他分区承担更多的数据量或查询负载,也就是我们常说的数据倾斜。数据倾斜会导致分区效率严重下降,在极端情况下,所有负载可能会集中在一个分区节点上。
那么如何保证数据是平均分摊到不同节点?
最简单方式是将记录随机分配给所有节点。这种方法可以比较均匀分布数据,但有一个很大缺点,当试图读取特定数据时,没有办法做到数据存储在哪个节点上,所以不得不并行查询所有节点。
那么如果保证数据能查询到同时又尽量满足平均分摊呢?
现在假设数据是简单的键-值数据模型,某个键(key)应该在哪个节点上存储及获得应该是确定的,不管访问任意一个节点都可以得到缓存结果。
一个好的哈希算法就能满足上述诉求。例如处理一个字符串的32位哈希,当输入某一个字符串,它会返回一个0和2^32~1之间近似随机分布的数值,每次计算结果都是相同的。
哈希算法
使用哈希算法
哈希算法最简单的做法就是进行取模运算,比如分布式系统中有 3 个节点
如果客户端要获取指定 key 的数据,通过下面的公式可以定位节点:
hash(key) % 3
现在有 3 个查询 key 的请求,分别查询 key-01,key-02,key-03 的数据,这三个 key 分别经过 hash() 函数计算后的值为 hash( key-01) = 6、hash( key-02) = 7、hash(key-03) = 8,然后再对这些值进行取模运算。
通过这样的哈希算法,每个 key 都可以定位到对应的节点。
看到上面例子,是不是觉得so easy,通过key就可以轻而易举找到对应节点。但是哈希算法有一个致命的缺点。
使用哈希算法有什么问题
分布式数据系统因为节点故障或者数据量增多,需要我们提升集群可扩展性,也就是对系统做扩缩容。
如下图,集群从3个节点扩展为4个节点集群。之前hash(key-01) % 3 = 0
变成了hash(key-01) % 4 = 2
。查询数据时请求到节点C,但是数据是存在在节点A上。
所以在需要变更节点时,大部分数据都需要迁移,重新映射。但是数据的迁移成本是非常高的。比如,我们常用的中间件redis,就存在这种问题。新增节点时需要执行reshard进行重新分片,同时把数据迁移到新分片上。
针对这种问题,还有一个更好的方案,也就是一致性哈希算法(Consistent Hashing
)。
一致性哈希算法
什么是一致性哈希算法
一致性哈希算法(Consistent Hashing
)也是用取模运算,但与哈希算法不同的时候,哈希算法是对节点的数据进行取模,而一致性哈希算法是对2^ 32进行取模运行。
我们可以把一致哈希算法是对 2^32 进行取模运算的结果值组织成一个圆环,就像钟表一样,钟表的圆可以理解成由 60 个点组成的圆,而此处我们把这个圆想象成由 2^32 个点组成的圆,这个圆环被称为哈希环。圆环的正上方的点代表 0,0 点右侧的第一个点代表 1,以此类推,2、3、4、5、6……直到 2^32-1,也就是说 0 点左侧的第一个点代表 2^32-1。如下图:
使用一致性哈希实现哈希寻址?
使用一致性哈希要进行两步哈希:
-
第一步:对存储节点进行哈希计算,也就是对存储节点做哈希映射;比如,下图中根据节点的主机名进行哈希计算
-
第二步:当对数据进行存储或访问时,对数据进行哈希映射,然后从这个位置沿着哈希环顺时针“行走”,遇到第一个节点就是key对于节点;比如,下图中对要查询的key-2进行哈希计算,确定此key-2映射在哈希环的位置,然后从这个位置往顺时针方向找到第一个节点,也就是节点B
数据迁移
了解一致性哈希算法原理后,很多人会问一致性哈希算法在增加一个节点或者减少一个节点是如何处理数据迁移的?
新增节点
假设节点数量从3增加到4,新的节点D经过哈希计算后映射到了下图的位置:
你可以看到,key-1、key-3 都不受影响,只有 key-2 需要被迁移节点 D。
减少节点
假设节点数量从3减少到2,比如将节点A移除:
你可以看到,key-2和key-3不会受到影响,只有key-1需要迁移到节点B
因此,在一致性哈希算法中,如果增加或者移除一个节点,仅影响该节点在哈希环上顺时针相邻的后继节点,其他数据也不会受到影响(一般采用一致性哈希算法需要迁移的数据仅为使用比哈希算法时的1/3)
使用一致性哈希算法有什么问题
使用一致性哈希算法如果节点太少,很容易出现节点分布不均匀。这样会带来一个问题,也就是数据倾斜问题。会有大量请求集中在一个节点上。
比如,下图中 3 个节点的映射位置都在哈希环的右半边:
在这种节点分布不均匀的情况下,进行容灾与扩容时,哈希环上的相邻节点容易受到过大影响,容易发生雪崩式的连锁反应。
比如,上图中如果节点 A 被移除了,当节点 A 宕机后,根据一致性哈希算法的规则,其上数据应该全部迁移到相邻的节点 B 上,这样,节点 B 的数据量、访问量都会迅速增加很多倍,一旦新增的压力超过了节点 B 的处理能力上限,就会导致节点 B 崩溃,进而形成雪崩式的连锁反应。
所以,一致性哈希算法虽然减少了数据迁移量,但是存在节点分布不均匀的问题。
如何通过虚拟节点提高均衡度
要想解决节点能在哈希环上分配不均匀的问题,一种方法是新增大量的节点,节点数越多,分布在哈希环也就越均匀。但真实应用场景,我们不可能分配哪么多的节点,那样会造成资源浪费。所以这个时候,我们加入虚拟节点。
虚拟节点指不再将真实节点映射到哈希环上,而是在哈希环上映射一些虚拟节点,然后将虚拟节点映射到实际节点,所以这里【两层】映射关系
比如对每个节点分别设置 3 个虚拟节点:
- 对节点 A 加上编号来作为虚拟节点:A-01、A-02、A-03
- 对节点 B 加上编号来作为虚拟节点:B-01、B-02、B-03
- 对节点 C 加上编号来作为虚拟节点:C-01、C-02、C-03
引入虚拟节点后,原本哈希环上只有 3 个节点的情况,就会变成有 9 个虚拟节点映射到哈希环上,哈希环上的节点数量多了 3 倍。
你可以看到,节点数量多了后,节点在哈希环上的分布就相对均匀了。这时候,如果有访问请求寻址到「A-01」这个虚拟节点,接着再通过「A-01」虚拟节点找到真实节点 A,这样请求就能访问到真实节点 A 了。
上面为了方便你理解,每个真实节点仅包含 3 个虚拟节点,这样能起到的均衡效果其实很有限。而在实际的工程中,虚拟节点的数量会大很多,比如 Nginx 的一致性哈希算法,每个权重为 1 的真实节点就含有160 个虚拟节点。
另外,虚拟节点除了会提高节点的均衡度,还会提高系统的稳定性。当节点变化时,会有不同的节点共同分担系统的变化,因此稳定性更高。
比如,当某个节点被移除时,对应该节点的多个虚拟节点均会移除,而这些虚拟节点按顺时针方向的下一个虚拟节点,可能会对应不同的真实节点,即这些不同的真实节点共同分担了节点变化导致的压力。
而且,有了虚拟节点后,还可以为硬件配置更好的节点增加权重,比如对权重更高的节点增加更多的虚拟机节点即可。
因此,带虚拟节点的一致性哈希方法不仅适合硬件配置不同的节点的场景,而且适合节点规模会发生变化的场景。
内容小结
基于键-值数据模型的分布式数据系统,通过哈希算法,客户端每一次相同key请求都能访问到固定节点。同时,哈希算法会返回一个0和2^32~1之间近似随机分布的数值。让数据能尽可能落均匀落到集群所有节点上。
但是,哈希算法存在一个问题。哈希算法是通过hash(key) % 集群数
计算得到的,集群扩缩都会导致哈希值出现变化,所以集群在扩缩容时需要对大量的数据进行迁移。
为了解决这个问题,引入了一致性哈希算法,不直接对集群数取模,而是先对构建一个2^32-1
哈希环。首先把【节点】映射到哈希环上,然后把【数据】计算哈希后,顺时针方向找到第一个在哈希环上的节点。通过这种方式,很好的解决了数据迁移的问题。
但是按下葫芦浮起瓢,如果节点数很少情况下通过一致性哈希算法会出现数据倾斜问题。会出现大量请求集中在一个节点上。
为了解决这个问题,引入了虚拟节点。在哈希环上映射了大量虚拟节点,同时再将多个虚拟节点映射到一个真实节点。这样既解决了数据迁移的问题,同时也解决了数据倾斜的问题。