1. 一致性哈希⚓

1.1 负载均衡问题⚓

负载均衡问题。不同的负载均衡算法，对应的就是不同的分配策略，适应的业务场景也不同。

最简单的方式，引入一个中间的负载均衡层，让它将外界的请求「轮流」的转发给内部的集群。

考虑到每个节点的硬件配置有所区别，我们可以引入权重值，将硬件配置更好的节点的权重值设高，这种算法叫做加权轮询。

但是，加权轮询算法无法应对「分布式系统（数据分片的系统）」，因为分布式系统中，每个节点存储的数据是不同的。

一个分布式 KV（key-valu）缓存系统，某个 key 应该到哪个或者哪些节点上获得，应该是确定的。一致性哈希算法就是一个能应对分布式系统的负载均衡算法。

哈希算法。因为对同一个关键字进行哈希计算，每次计算都是相同的值，这样就可以将某个 key 确定到一个节点了，可以满足分布式系统的负载均衡需求。

哈希算法最简单的做法就是进行取模运算。但是有一个很致命的问题，如果节点数量发生了变化，也就是在对系统做扩容或者缩容时，必须迁移改变了映射关系的数据，否则会出现查询不到数据的问题。

假设总数据条数为 M，哈希算法在面对节点数量变化时，最坏情况下所有数据都需要迁移，所以它的数据迁移规模是 O(M)，这样数据的迁移成本太高了。

一致性哈希算法很好地解决了分布式系统在扩容或者缩容时，发生过多的数据迁移的问题。

一致哈希算法也用了取模运算，但与哈希算法不同的是，哈希算法是对节点的数量进行取模运算，而一致哈希算法是对 2^32 进行取模运算，是一个固定的值。

一致哈希算法是对 2^32 进行取模运算的结果值组织成一个圆环，这个圆环被称为哈希环。

一致性哈希要进行两步哈希：

所以，一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的哈希环上。

「数据」进行哈希映射得到映射的结果值往顺时针的方向的找到第一个节点，就是存储该数据的节点。

所以，当需要对指定 key 的值进行读写的时候，要通过 2 步进行寻址。

增加节点或者减少节点的情况：

在一致哈希算法中，如果增加或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。

一致性哈希算法并不保证节点能够在哈希环上分布均匀，这样就会有大量的请求集中在一个节点上。在这种节点分布不均匀的情况下，进行容灾与扩容时，哈希环上的相邻节点容易受到过大影响，容易发生雪崩式的连锁反应。

所以，一致性哈希算法虽然减少了数据迁移量，但是存在节点分布不均匀的问题。

要想解决节点能在哈希环上分配不均匀的问题，就是要有大量的节点，节点数越多，哈希环上的节点分布的就越均匀。

具体做法是，不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有「两层」映射关系。

下图中均为虚拟节点：

在实际的工程中，虚拟节点的数量会大很多，比如 Nginx 的一致性哈希算法，每个权重为 1 的真实节点就含有160 个虚拟节点。

虚拟节点除了会提高节点的均衡度，还会提高系统的稳定性。当节点变化时，会有不同的节点共同分担系统的变化，因此稳定性更高。

有了虚拟节点后，还可以为硬件配置更好的节点增加权重，比如对权重更高的节点增加更多的虚拟机节点即可。

因此，带虚拟节点的一致性哈希方法不仅适合硬件配置不同的节点的场景，而且适合节点规模会发生变化的场景。