跳至主要內容

分布式存储 - 一致性Hash算法


概述

一致性hash多用于分布式数据存储场景,在集群节点数量发生变化时,提升集群适应变化的能力。

大多数网站背后肯定不是只有一台服务器提供服务,因为单机的并发量和数据量都是有限的,所以都会用多台服务器构成集群来对外提供服务。那么这些服务器需要如何分配客户端的请求呢,这个其实就是负载均衡。但是一般的负载均衡算法是针对所有服务器上的数据都是一样的,也就是无法应对分布式存储的场景。

当想要提高系统的容量,就会将数据水平切分到不同的节点来存储,也就是将数据分布到了不同的节点。比如一个分布式 KV(key-valu) 缓存系统,某个 key 应该到哪个或者哪些节点上获得,应该是确定的,不是说任意访问一个节点都可以得到缓存结果的。而hash算法就可以很好的完成k-v对的存储,因为对同一个关键字进行哈希计算,每次计算都是相同的值,这样就可以将某个 key 确定到一个节点了,可以满足分布式系统的负载均衡需求。

而一致性 hash 是传统 hash 算法的增强版。

传统hash存在的问题

hash算法最简单的做法就是进行取模运算,比如分布式系统中有 3 个节点,就可以基于 hash(key) % 3 公式对数据进行映射。

但是这样,如果节点数量发生了变化(比如当前节点不能满足要求了,需要新增一个节点增加容量),也就是在对系统做扩容或者缩容时,必须迁移改变了映射关系的数据,否则会出现查询不到数据的问题。

显然,要解决这个问题,就需要进行数据迁移,比如节点的数量从 3 变化为 4 时,需要基于新的计算公式 hash(key) % 4 ,重新对数据和节点做映射。

假设总数据条数为 M,哈希算法在面对节点数量变化时,最坏情况下所有数据都需要迁移,所以它的数据迁移规模是 O(M),这样数据的迁移成本太高了。

而一致性 hash 算法则是将这种因节点数量变化所需要花费的调整成本,降至最低

一致性hash

一致性 hash 引入了哈希环的概念,核心思路:

  • 规定了一个哈希环,环的元素由 [0, 2^32 -1] 范围的整数组成
  • 将 key,服务节点通过计算映射到哈希环上
  • 顺时针方向为 key 寻找相邻的第一台服务节点,完成 key -> node 的关系映射

比如,下图中的 key-1 映射的位置,往顺时针的方向找到第一个节点就是节点 A。

另外两个节点对应关系为:

  • Key1 -> Node-A
  • Key2 -> Node-B
  • Key3 -> Node-C

假设当前新增一个节点,比如节点数量从3增加到了4,新的节点 D 经过哈希计算后映射到了下图中的位置:

也就是说,key-1、key-3 都不受影响,只有 key-2的数据 需要被迁移节点 D。

因此,在一致哈希算法中,如果增加或者移除一个节点,仅影响该节点在哈希环上顺时针相邻的后继节点,其它数据也不会受到影响。这就可以解决传统hash算法中大量数据迁移的问题。

数据倾斜问题

但是一致性哈希算法并不保证节点能够在哈希环上分布均匀,这样就会带来一个问题,会有大量的请求集中在一个节点上。

这样所有的数据都会请求到节点A上,这就没有了负载均衡。
并且假设节点A故障被移除了,那么所有的数据也都需要迁移到节点B上

因此,一致性 hash 确实能够降低节点数量变化对集群整体造成的影响,但存在数据倾斜问题。

引入虚拟节点

虚拟节点的核心:

  • 将一个物理节点分化成多个虚拟节点
  • 将虚拟节点映射到哈希环上
  • 当 key 命中虚拟节点后,通过虚拟节点找到其所属的物理节点

也就是说,不再将真实节点映射到哈希环上,而是将虚拟节点映射到哈希环上,并将虚拟节点映射到实际节点,所以这里有两层的映射关系。

比如:

  • 对节点 A 加上编号来作为虚拟节点:A-01、A-02、A-03
  • 对节点 B 加上编号来作为虚拟节点:B-01、B-02、B-03
  • 对节点 C 加上编号来作为虚拟节点:C-01、C-02、C-03

可以看到这样使得数据分布更加平衡。另外如果移除了一个节点C,也不会发生大量的数据迁移情况,并且能有不同的节点共同分担系统的变化,因此稳定性更高:

  • 比如,当某个节点被移除时,对应该节点的多个虚拟节点均会移除,而这些虚拟节点按顺时针方向的下一个虚拟节点,可能会对应不同的真实节点,即这些不同的真实节点共同分担了节点变化导致的压力。

上图是为了方便理解,每个真实节点仅包含 3 个虚拟节点,这样能起到的均衡效果其实很有限。而在实际的工程中,虚拟节点的数量会大很多,比如 Nginx 的一致性哈希算法,每个权重为 1 的真实节点就含有160 个虚拟节点。

并且,有了虚拟节点后,还可以为硬件配置更好的节点增加权重,比如对权重更高的节点增加更多的虚拟机节点即可。

总结

首先,hash算法可以用来解决分布式存储的问题,但如果节点数量发生变化,也将会发生大量的数据迁移。

而一致性hash算法就是通过一个首尾相连的hash环解决传统hash算法中大量的数据迁移的问题的,如果增加或者移除一个节点,仅影响该节点在哈希环上顺时针相邻的后继节点,其它数据也不会受到影响。

但是一致性哈希算法并不保证节点能够在哈希环上分布均匀,存在数据倾斜问题。

因此就引入了虚拟节点,将一个真实节点映射为多个虚拟节点。不再将真实节点映射到哈希环上,而是将虚拟节点映射到哈希环上,从而提高节点的负载均衡度,和系统的稳定性。

seven97官方微信公众号
seven97官方微信公众号