1.简述

1.1.哈希算法

哈希算法：将任意长度的输入通过散列算法转换成固定长度的输出。

哈希算法是一种映射算法，将任意个数的输入映射为固定个数的哈希值。

1.2.应用场景举例

分布式缓存

现有用户数据3000万，为提高访问速度，将用户基本信息保存在缓存中，其中：

• key=user:{uid}，其中uid为用户ID，由UUID生成。value为姓名、账号级别等构成的Json串。
• 为了分担单台服务器压力，将缓存数据分摊在3台服务器上。
• 为了能够快速定位某个用户所在的服务器，通过 key % 3的哈希算法分配图片的存储位置。
• 理想情况下，服务器node2有1000万用户信息，相当于1000万个key经过哈希都映射为哈希值2.

其他应用：

• 数据库分表

1.3.普通哈希算法的缺陷

正常情况下，上述哈希算法是没有问题的。

但是，因为一些原因，需要增减服务器，这是必然导致哈希算法的变化，例如变为 key % 5。

当哈希算法的模数发送变化时，原有的映射值几乎全部失效，需要重新映射几乎全部数据，这个工作量十分巨大。

缺陷总结：当增加或移除节点时，普通哈希算法几乎需要重新映射全部关键字。

一致性哈希算法能够在一定程度上解决上述缺陷。

2.一致性哈希算法

一致性哈希 是一种特殊的哈希算法。

在使用一致哈希算法后，节点的改变平均只需要对K/N 个关键字重新映射，其中K是关键字的数量，N是节点数量。

下面分表讲述一致性哈希的几个关键问题：算法步骤、节点增减、哈希偏斜、虚拟节点。

2.1.算法步骤

哈希算法也是一种取模算法，只是，模数固定为2^32，也就是说哈希值范围：0 ~ (2^31 - 1)，如下图所示：

一致性哈希环：

• 图中的圆环称之为一致性哈希环，由2^32个节点构成。。
• 节点按照顺时针排列，正上方节点为0，节点0的左侧相邻节点为2^31-1节点。

一致性哈希算法：

1. 对服务器进行ip % (2^32)哈希，结果如图中绿色的点所示。
2. 对key进行key % (2^32)哈希，结果如同种紫色的点所示。
3. 判断key所属服务器：从紫色点的位置开始，顺时针探索，遇到的第一个绿色的点，就是其所属的服务器。

2.2.增减节点

那么，一致性哈希算法，如何在一定程度上解决节点增减引起的问题呢？如下图所示：

节点增加：

• 图中节点D为新增节点。
• 此时，只需将节点D至节点B之间的key重新映射至节点D即可，图中只有1个key受此影响。

节点减少：

• 图中节点A为移除节点。
• 此时，只需将节点A至节点C之间的key重新映射至节点BB即可，图中只有3个key受此影响。

总结：(理想情况下)

• 假定共有K个key和N个节点，每个节点上存储K/N个key。
• 当新增节点时，只需将新增节点内至新增节点的上个节点之间的key重新映射至新增节点即可，共计(K/N)/2个key。
• 当移除节点时，只需将移除节点至移除节点的上个节点之间的key重新映射至移除节点的下个节点即可，共计(K/N)个key。
• 所以说，一致性哈希能够在一定程度上解决增减节点的问题，而不是完全解决。

2.3.哈希偏斜

讨论哈希问题，必然需要讨论哈希偏斜问题。下图就是一致性哈希偏斜的例子：

如图中所示：

• 节点A上映射了9个key，而节点C上只映射了1个key。
• 这种情况下，理论上，服务器A需要承受的压力是服务器C的9倍。

那么，一致性哈希如何解决哈希偏斜问题，这就需要进入虚拟节点的概念了。

2.4.虚拟节点

下图就是增加了虚拟节点的一致性哈希环：

如图所示：

• 深绿色节点为实际服务器的哈希结果，浅绿色节点为虚拟节点。
• 虚拟节点如何产生？很多种方法，如：ip+number % (2^32)。
• 如图，虚拟节点B1和B2都是服务器B的IP+顺序号进行一致性哈希算法生成的，所以映射到B1和B2的key其实还是映射到了节点B上。
• 增加虚拟节点之后，节点A、B、C上分别映射了3、4、5个节点，偏斜情况大大改观。

总结：

• 在一致性哈希算法中，可以通过虚拟节点解决哈希偏斜问题。
• 理论上，增加的虚拟节点越多，哈希值分布越平均。
• 当然，也要注意虚拟节点的生成算法是否合理，生成的虚拟节点是否分布平均。

---

3.参考

• https://blog.csdn.net/justloveyou_/article/details/78313649
• https://baike.baidu.com/item/%E4%B8%80%E8%87%B4%E6%80%A7%E5%93%88%E5%B8%8C/2460889?fr=aladdin

cs