浅谈一致性哈希

引言

上一篇文章我们讲到负载均衡算法的几种常规实现,今天我们来谈一下另一种实现,也是大多数组件用到的一致性哈希算法。

名词简写

  • n :节点数量
  • m :图片名称
  • vn : 虚拟节点数量

描述

引用维基百科的介绍

一致哈希 是一种特殊的哈希算法。在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n 个关键字重新映射,其中 K 是关键字的数量,n 是槽位数量。然而在传统的哈希表中,添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

如果不是涉及基础服务建设的开发者,几乎是感受不到它的存在,但是它却和我们的日常息息相关,像经常使用的第三方组件 Nginxkafka 都不同程度上用到了这门技术。

作用

解决槽位变动带来的大面积地址重新映射

传统的哈希算法采用 hash(m) % n 映射 m 的地址,当添加新节点或者有节点出现故障的时候, n 将产生变化,随即 hash(m) % n 的结果值将发生变化,几乎所有的地址映射都会受到影响:

哈希

一致性哈希则不同于传统方法,本质是构造一个定长的哈希环,将每个节点 hash 后放置在环中的某处位置上,计算 m 的哈希值后 顺时针 寻找最近的节点位置。添加新节点后,只需计算新节点的 hash 放置在环中,影响的只是顺时针临近的映射地址,其他均不受影响:

一致性哈希

优化

当哈希环上的节点分布不均匀时,节点的管辖范围有概率性的不同,大量的 m 哈希后产生了数据倾斜。参考 加权轮询法(Weight Round Robin) 的加权特性,不够分配就加权来补,在哈希环中补加虚拟节点 vn 个,使整个哈希环中的节点分布达到理论性的均衡:

虚拟节点