一致性hash

前言

大多数网站背后并不是只有1台服务器，经常是以集群的形式来对外提供服务，那如何分配客户端的请求？其实这就是一个负载均衡的问题，其中之一应对负载均衡问题的算法就是：哈希算法。

哈希算法

hash的特点是散列，普通的hash算法group = key % N 来实现负载均衡。但是当分区节点扩容或缩容的时候（只要集群数量N发生变化），之前计算的hash映射就会失效。如果集群中每个节点提供的服务无差别，倒不会产生什么影响。但是对于 分布式缓存系统而言，意味着所有的缓存都失效，这是灾难性的。

一致性hash

一致性hash是通过构建环形的hash空间来代替线性的hash空间，整个hash空间被构建成一个首尾相连的环，他需要进行2次hash映射。
第一次，给集群的每个节点计算hash，然后记录hash值，这就是他们在环上的位置。
第二次，对key计算hash，然后在环上顺时针找到的第1个节点，就是存储该key的集群节点。

如上图的hash空间，集群有3个节点：group0、group1、group2。有6个key，落在环上位置后，顺时针找到相邻的第1个节点，所以group0存储（key3和key6），group1存储（key1和key4），group2存储（key2和key5）。
当集群节点增加和删除时对负载均衡的影响，如下图：

优点：group0节点挂掉后，对其他分区节点的key没影响，只是group0上的key会顺延落入group1节点。
缺点：
缓存雪崩：增加group1节点的压力，当group1抗不住也会雪崩，滚雪球般全部滚到group2节点。
数据倾斜：

引入虚拟节点

解决上述问题最好的办法是扩充整个环上的节点数量，所以引入了虚拟节点的概念。一个实际节点将会对应多个虚拟节点，且这几个虚拟节点是均匀分摊在环上，并不是聚凑一起的，这样当其中一个实际节点宕机，那对应的虚拟节点也会下线宕机，每个节点上的数据，会顺延到下一个节点，这样可以分摊原来只有1个实际节点的数据，而且是整个环的节点一起分摊，减轻了影响下个节点雪崩的可能性。