一致性哈希算法

今天我们继续来聊一聊一种分布式算法:一致性哈希算法。

在具体看其是什么算法之前,我们先来看看是什么背景需要这个算法的横空出世。

一致性哈希算法解决什么问题?

我们都知道单节点的存储能力和访问能力都是有上限的,尽管我们可以通过升级硬件配置等方式来纵向扩展节点的能力,但终究解不了渴。

所以很多时候我们会采用横向扩展的方式,也就是增加机器来提升服务整体的存储能力和访问能力。

但是横向扩展有个需要解决的问题。

在分布式系统中,如何将数据有效地分配到各个节点上。还要保证多个节点的数据分布的均匀程度,避免出现数据倾斜的问题。

对于这个问题,我们可以这么解决:

  1. 对数据执行增删改查的时候,都先将数据的唯一标识(通常是 id),通过哈希函数转换成一个哈希值,记为 h
  2. 如果有 N 台机器,则计算 h % N 的值,这个值就是该数据所在的机器编号,对该数据的增删改查操作,都只在这台机器上进行。

一个好的哈希函数足以保证数据分布的均匀,这个实现看起来有效且实现简单,但是在节点频繁增减的场景下,所有数据都需要根据 id 重新进行 hash,这个数据迁移的成本是很大的,无法保证数据的平衡和稳定。

因此,一种称为一致性哈希(Consistent Hashing)的算法应运而生,来解决这个问题。

什么是一致性哈希算法

一致性哈希算法是一种用于分布式系统中的负载均衡算法。它的主要目标是尽可能减少节点变动(例如,节点的增加或删除)时所需重新分配的数据量。该算法通过将所有可能的数据分片和节点映射到一个逻辑环上,从而实现数据的均匀分布和高效查找。

概念没看懂,我们来看看他的实现原理,你就懂了。

我们通过以下步骤来理解一致性哈希算法的核心原理:

  1. 构造哈希环:将整个哈希空间组织成一个环。例如,我们假设数据的 id 通过哈希函数转换成的哈希值范围是 0 ~ 。把这个数字空间首尾相连,形成一个环。如下图:

  1. 节点映射:利用每个机器节点的唯一标识(如机器 id),通过哈希函数映射到环上的某个点。例如,节点 A 通过哈希函数映射到位置 150,节点 B 映射到位置 250,依此类推。如下图:

  1. 数据映射:我们的每一条数据都能通过 id 哈希到这个环上的某个点上。例如,id 为 1 通过哈希函数映射到位置 130,id 为 2 映射到位置 220,依此类推。如下图:

  1. 数据存储:数据会存储在环上的 顺时针方向 遇到的第一个节点上。例如,id = 1 映射到 130,而最接近的节点是位置 150 的节点 A,因此 id=1 存储在节点 A 上。同理,id = 2 映射到 220,而最接近的节点是位置 250 的节点 B,因此 id = 2 存储在节点 B 上。如下图:

看完这个过程,相信你已经能够理解一致性哈希算法的核心流程,下面我们来看下这种算法是如何解决我们上文提到的,在增删节点的场景下需要大量数据迁移的问题。

如何处理增删机器后的数据迁移

先来看看增加机器。

为了方便描述,假设我们现在有两台机器 m1 和 m2,同时有数据 data1,data2,data3,他们经过哈希算法后的分布情况如下图,同时由于一致性哈希算法的数据映射的性质,我们很清楚的知道 data1 和 data2 在机器 m2 上,data3 在机器 m1 上。

假设现在我们新增加了一台机器 m3,其经过哈希之后落在了下图所示的位置:

这时候我们要做的,只需要把原本属于机器 m2 的数据重新哈希到机器 m3 上,其他机器的数据是不用动的。这个数据迁移的成本就小很多。

删除机器也很简单,假设在上图中,我们要把机器 m2 删掉,只需要把机器 m2 上的数据迁移到机器 m1 上即可。

细心的同学可能发现了,如果当机器数量比较少的时候,可能还是会导致数据分布不均匀,出现数据倾斜的问题。例如下图中的情况:

总结

一致性哈希算法作为在分布式系统用于实现负载均衡的算法,主要目标是减少因节点的增减所带来的数据迁移的成本。

发表回复

后才能评论