写点什么

一致性哈希算法

作者:乐只
  • 2024-02-06
    重庆
  • 本文字数:2086 字

    阅读完需:约 7 分钟

一致性哈希算法

在分布式领域中各技术组件都有实现 KV 形式的存储,在实现各类工作能力的同时还简化了算法实现。以 Raft 分布式协议为例,它通过在领导者采用 KV 存储来简化算法实现和共识协商,但同时也限制所有写请求只能在领导者节点上进行处理,从而导致集群退化为单机模式。

没有什么是加一个中间层解决不了的问题,那么有那就再加一层。为实现既要又要的目的,可以通过分集群来突破单集群的性能限制,然后再各集群节点和客户端之间加一个哈希代理层进行路由。

简单的哈希算法

公式:m = hash(o) mod n

o:需要被哈希函数作用的对象值

n:集群中节点的个数


假设集群中有 A、B 和 C 三个节点、对象值为 1 到 10 十个数据,经过简单哈希函数公式 m = hash(o) mod n 计算后得:

如果增加一个 D 节点,那么此时公式中的 n 就由 3 变成了 4。上述十个数据就得重新代入哈希函数计算一个新值,计算后得:

对比两组数据发现只有 1 和 2 经过哈希函数重新计算后没有被移动,当前还只有十个数据,如果当集群中数据量很大是,那么每次扩容和缩容带来的数据迁移成本可谓是相当巨大,更有甚者会导致宕机,由此可以使用一致性哈希来解决数据迁移成本高的问题。

一致性哈希算法

一致性哈希算法是 1997 年发布的《Consistent Hashing and Random Trees》论文中提出的,使用此算法可以大幅度减少数据迁移量,它可以保证在进行扩容和缩容时,节点之间的数据迁移只限于两个节点之间,不会像上述简单的哈希函数那样造成大规模的数据迁移。

哈希环

一致性哈希算法也用了取模运算,与普通哈希算法直接对节点的数量进行取模运算有所不同,一致性哈希算法是对 232 进行取模运算。即将数据映射到 0~(232-1)的数字空间,将这些数字头尾相连可以组织成一个虚拟的圆环,也就是哈希环:



上图所示哈希环的空间是按顺时针方向组织的,圆环的正上方的点代表原点 0,0 点右侧的第一个点代表 1,以此类推,2、3、4、5、6……直到 232-1,即 0 点左侧的第一个点代表 232-1。

映射节点到哈希环

在一致性哈希算法中,可以通过执行自定义的哈希算法将节点映射到哈希环上,那么每个节点就能确定其在哈希环上的位置了:


映射数据到哈希环

同理执行自定义的哈希算法计算出每个数据对应的 key 值,然后散列到哈希环上,hash(o1) = key1、hash(o2) = key2、hash(o3) = key3、hash(o4) = key4:


存储数据到节点

将节点和数据都映射到同一个哈希环上之后,然后以原点 0 为起点顺时针转动,在转动过程中数据遇到的第一个节点就是该数据的归属,然后读写数据的时候就可以按照此到对应的节点上去寻找。

扩容和缩容

扩容

扩容即向集群中增加一个节点 D,节点 D 经过上述同样自定义的哈希函数后计算后,然后将其映射到哈希环上,如下图所示。



此时再根据顺时针存储的规则进行数据迁移:

扩容之后发现只有 key4 从之前的节点 A 迁移到了节点 D 上,数据的移动仅发生在节点 A 和节点 D 之间,其他节点上的数据并未受到影响。

缩容

缩容即向集群中减少一个节点 C,先将节点 C 从哈希环上移除,然后再根据顺时针存储的规则进行数据的迁移:



缩容之后发现只是将节点 C 的所属的数据迁移到了节点 A 上,其他数据并未受到影响。

总的来说,使用了一致性哈希算法后,扩容或缩容的时候,都只需要重定位哈希环中的一小部分数据。也就是说,一致性哈希算法具有较好的容错性和可扩展性。

复杂度

假设总数据条数是 M,节点个数是 N。

哈希函数时间复杂度

  • 传统哈希算法,以 N 为基数执行取模运算,时间复杂度为 O(1)。

  • 一致性哈希算法,首先将关键字先转换为 32 位整型,然后采用二分法(所有节点在哈希环上是有序排列的)确定节点在哈希环上的处理范围,综合时间复杂度为 O(logN) 。

数据迁移规模

  • 传统哈希算法,因为节点变化需要迁移的数据规模是不可控的,所以综合数据迁移规模为 O(M)。

  • 一致性哈希算法,哈希环中各节点均匀分布的情况下,数据迁移规模为 O(M/N)。

综上数据条数 M 远大于主机节点数 N,而且数据迁移的成本很大,所以一致性哈希算法更划算。

数据倾斜

一致性哈希算法虽然降低了数据的迁移量,但是也存在两个数据倾斜的问题

  1. 如果映射后哈希环中的数字分布不均匀,就会导致各节点处理的数据不均衡、各节点的负载不均衡。

  2. 容灾和扩容时哈希环上相邻节点会受到极大影响,极端情况下,假如节点 A 出现故障,存储在 A 上的数据要全部转移到 B 上,大量的数据导可能会导致节点 B 的崩溃,之后 A 和 B 上所有的数据向节点 C 迁移,导致节点 C 也崩溃,由此导致整个集群宕机,产生雪崩效应。

虚拟节点

想要解决数据倾斜的问题,一来可以让集群中的节点尽可能的多,从而让各个节点均匀的分布在哈希空间中。但是在生产环境中机器的数量往往都是固定的,所以我们只能在物理节点和哈希环之间再加一层虚拟节点层。假如集群中有 4 个节点,首先不是直接将哈希环分为 4 份,而是将均分地分为 32 份,每份对应一个虚拟节点共 32 个虚拟节点;然后再将这 32 个虚拟节点映射到 4 个物理节点上。



设置虚拟节点层后,为异构的服务器节点设置权重也更方便。只需要为权重高的真实节点,赋予更多的虚拟节点即可。虽然虚拟节点增多可以提升均衡性,但是也会消耗更多的内存与计算力。


发布于: 刚刚阅读数: 3
用户头像

乐只

关注

知其白,守其黑 2018-03-30 加入

还未添加个人简介

评论

发布
暂无评论
一致性哈希算法_一致性Hash算法_乐只_InfoQ写作社区