浅谈一致性哈希

引言

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

名词简写

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

描述

引用维基百科的介绍

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

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

作用

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

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

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

优化

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