如何分配请求

为什么要对请求做分配？因为单机的并发量和数据量都是有限制的，对于高并发场景来说，单机的并发量是远远达不到要求的。所以大多数网站都不仅仅是使用一个节点(服务器)来对外提供服务。这个时候，面对节点，如何做请求的分配(负载均衡)就十分的重要了。

负载均衡中，最简单的方式就是轮询。比如集群有 3 个节点，外界请求有 3 个，那么每个节点都会处理 1 个请求，达到了分配请求的目的。

轮询他有一个缺点：每个节点可能性能不相同，所以在单位时间内能提供的服务次数也不相同。但是轮询他是做了个比较”平均“的分配，这可能使某些节点不能完全发挥性能的同时，某些节点不堪重负。

为了克服这个缺点，我们又引入了加权轮询的方式，让请求按照一定比重分配在不同的节点上。

不过轮询方式的使用有一个前提：每个节点存储的数据都是相同的。如果，我们使用的是”数据分片的系统“，则不能使用这种方法分配请求。

这种不能使用加权轮询的场景很常见，有很多分布式系统提高系统容量的方法就是做数据切片并且在不同分区(partition)中进行处理存储。比如一个分布式KV缓存系统(Redis：这不就是我嘛)，某个key应该到哪一个节点获取，应该是确定的，不能任意访问节点就能获得缓存结果的。

因此，对于上述情况，我们必须找到一个能够应对的负载均衡算法。

使用哈希算法的问题

提到这种场景，可能很多人第一时间会想到”哈希算法“。因为对同一个key进行哈希计算，得到的结果是固定的，这样就能够完美解决我们提出的问题，可以满足分布式系统的负载均衡需求。

是的，一般来说，这样是正确的。但是哈希算法计算存储到哪个节点是进行取余操作，如果对整个系统进行扩容或者缩容呢？是不是整个系统的缓存的存储的节点可能就不同了，就需要进行数据迁移？假设总数据条数为 M，哈希算法在面对节点数量变化时，最坏情况下所有数据都需要迁移，所以它的数据迁移规模是 O(M)，这样数据的迁移成本太高了。也可能有些人会说，整个系统没必要进行扩缩容。那对于分布式来说，是不是需要考虑到某个节点宕机的问题？

所以这种负载均衡的方法并不能使用在这种场景下。我们应该要重新想一个新的算法，来避免分布式系统在扩容或者缩容时，发生过多的数据迁移。

什么是一致性哈希算法

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

我们可以把一致哈希算法是对 2^32 进行取模运算的结果值组织成一个由 2^32 个点组成的圆环。称为哈希环。

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

• 第一步：对存储节点进行哈希计算，也就是对存储节点做哈希映射，比如根据节点的 IP 地址进行哈希；
• 第二步：当对数据进行存储或访问时，对数据进行哈希映射；

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

不过，是否有可能数据进行哈希映射之后的位置没有节点？是的，这不仅仅是有可能，而是一致性哈希算法必然会发生的。

那数据是如何通过哈希映射后找到存储该数据的节点呢？只要找到映射的结果值往顺时针方式的第一个节点，这个节点就是应该存储数据的节点。

并且在一致哈希算法中，如果增加或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，这样大大减少了需要数据迁移的数量。

那一致性哈希算法有没有什么问题呢？

一致性哈希算法的问题

有的，一致性哈希算法不保证节点能够在哈希环上分布均匀，这样就会带来一个问题，会有大量的请求集中在一个节点上。

如图，如果节点经过一致性哈希算法分布后，为这样密集的分布，则会导致大部分请求都会打到节点A上。导致节点A的压力非常的大，节点B和C的压力很小(节点A内心：”说好的负载均衡呢？我好累“)。

另外，在这种节点分布不均匀的情况下，进行容灾与扩容时，哈希环上的相邻节点容易受到过大影响，容易发生雪崩式的连锁反应。

我们试想一下，如果节点A被移除了，将会把数据都迁移到节点B。节点B的访问量和数据量会迅速增大，一旦压力超过了节点B所能负载的，可能会出现宕机的风险。继而影响到节点C······，形成雪崩式的连锁反应。

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

如何通过虚拟节点提高负载均衡度

解决节点分布不均匀，有一个非常暴力的方法，只要节点越多，分布就会越均匀。

但是实际上，我们并不可能在一个服务上有如此多的节点数量。所以我们可以加入虚拟节点，也就是对一个真实节点做多个副本。

具体做法是，不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点。

比如对每个节点分别设置 3 个虚拟节点：

• 对节点 A 加上编号来作为虚拟节点：A-01、A-02、A-03
• 对节点 B 加上编号来作为虚拟节点：B-01、B-02、B-03
• 对节点 C 加上编号来作为虚拟节点：C-01、C-02、C-03

引入虚拟节点后，原本哈希环上只有 3 个节点的情况，就会变成有 9 个虚拟节点映射到哈希环上，哈希环上的节点数量多了 3 倍。

可以看出来，分布明显比之前更加均匀。

上面为了方便你理解，每个真实节点仅包含 3 个虚拟节点，这样能起到的均衡效果其实很有限。而在实际的工程中，虚拟节点的数量会大很多，比如 Nginx 的一致性哈希算法，每个权重为 1 的真实节点就含有160个虚拟节点。

另外，虚拟节点除了会提高节点的均衡度，还会提高系统的稳定性。当节点变化时，会有不同的节点共同分担系统的变化，因此稳定性更高。并且我们还能给节点设置权重，性能更好的节点有更多的虚拟节点，这样也能满足每台机器性能不同的情况。

总结

所以带虚拟节点的一致性哈希算法不仅适合硬件配置不同的节点的场景，而且适合节点规模会发生变化的场景。对于我们上述提到的场景中，使用带有虚拟节点的一致性哈希算法是最为合适的。

除了 Nginx 之外，你还知道哪些分布式系统使用了一致性哈希算法呢？