Consistent Hashing 如何实现高效负载均衡
今天我们来聊聊 Consistent Hashing（一致性哈希）。分布式系统相较于单机的很大区别在于，我们需要一组机器相互配合来体现共同的业务价值。哪怕某个实例挂掉，只要分布式系统作为一个整体能兜住底，从外界看来，整个系统就是正常的。
而在数据规模，请求规模日益放大的今天，各种原因导致的机器故障并不罕见，在设计系统的时候我们就需要假设单机来看一定有可能挂掉，如何让我们整个集群在局部节点宕机的情况还能快速恢复，快速扩缩容，让这一组机器看起来就好像是一台机器一样，规避掉多机协同可能带来的问题。
这一点，对于传统的哈希算法是个挑战。
事实上，早在 1997年，互联网们就意识到了这个问题，并提出了我们今天要聊的解决方案。建议有余力的同学好好阅读一下 25 年前的这篇经典论文：Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web
哈希是什么
Hashing is the process of mapping one piece of data — typically an arbitrary size object to another piece of data of fixed size, typically an integer, known as hash code or simply hash. A function is usually used for mapping objects to hash code known as a hash function.
哈希的本质在于将一个任意大小的对象，映射到固定大小的对象，这个映射的方法，就叫做【哈希函数】。
设想一下，现在高铁站希望针对所有出站旅客做【落地核酸检查】，开辟了 9 个检测窗口，我们希望对所有旅客进行划分，保证 9 个窗口流量均匀，这个时候旅客的数量可能是随机的，有的车次人多，有的人少。但我们需要一个统一的标准，快速判断怎样来做划分，使得来一个旅客，我们就能快速引导他到某个窗口做检测。窗口的数量是固定的，旅客数量是不定的，而划分规则也是确定的。这三者就分别对应到我们上面的概念。
任你人多人少，总之，我们提供了 9 个窗口来服务。在分布式系统看来，就是 9 个有工作能力的节点。
经过哈希函数处理后，每个对象被分配到一个固定的槽，但碰撞是难以避免的，这个时候可以考虑直接在后面加上链表。就像大家在各个窗口排队。
传统哈希的问题
Typical hashing based schemes do a good job of spreading load through a known, fixed collection of servers. The Internet, however, does not have a fixed collection of machines. Instead, machines come and go as they crash or are brought into the network. Even worse, the information about what machines are functional propagates slowly through the network, so that clients may have incompatible “views” of which machines are available to replicate data. This makes stan- dard hashing useless since it relies on clients agreeing on which caches are responsible for serving a particular page.
这里我们引用论文里的经典论述：
- 传统哈希算法针对数量确定的 server 做负载均衡时非常有效。
- 但可惜的是，互联网并没有一个定死的机器数量。我们可能会随着负载增加而加机器，也可能因为宕机而下掉某个机器。事实上，如果某台机器由于一些原因无法继续工作，等到整个系统反应过来，可能已经过去了很久。
- 所以，上层的 proxy 或者 client 可能无法感知到到底哪些机器还能正常 work。
这三点推论指向了一个无奈的结果，即传统哈希的策略在分布式系统中很难奏效，因为它强依赖上层的 clients 明确到底请求要发给哪个节点。
假设我们有 5 个节点，需要根据租户ID （假设是个 int64）将不同租户的请求路由到 5 个节点其中的一个。按照传统哈希的做法，通常我们会取模，即：tenantID % 5 获取一个数，当然只能是 0,1,2,3,4 中的一个。这就分别对应了我们的每个节点。
如果仅仅是无状态的请求，其实是不影响的，但怕就怕很多时候，我们要分配的不是【无状态的请求】，而是【有状态的数据】。一旦节点增加或减少，分配结果就大不相同。
试想一下，现在加了一个节点，取模结果就完全不一样了，那原来在 0,1,2,3,4 五个节点的数据要怎么办，触发一次迁移么？这几乎相当于把整个系统数据做调整，由此带来的网络 IO 成本是很高的，而且也会影响系统稳定性。
有没有一个比较轻量级的解决方案呢？
一致性哈希
一致性哈希就是要解决上面提到的 rehashing 的问题，在扩缩容的时候也能使得分配的变化最小。
要做到这一点，关键是设计出来一种分配方案，不直接依赖提供服务的节点数量。不能你有 9 个节点，我就对 9 取模，这样显然每次都要大变。
怎么办？
加一层！一次 hashing 不够，我就做两次。
原有经典哈希体系中，我们对【请求】做了哈希，就直接对应到【服务节点】了。现在我们不希望它们直接沟通，而是有一个中间层。想象一下我们有一个 hash ring，环形的结构，存储了哈希之后的结果。
- 这个环形结构 hash ring 上包含了所有【请求】和【服务节点】；
- 可以认为这个环可以包含任意多个点，并且【服务节点】可以被放到环上任意一个位置（同样需要经过一次哈希来计算出）；
- 【请求】哈希之后不再唯一对应一个【服务节点】，而是同样被放在这个环形结构上，经过同样的哈希函数计算。
我们假定这个 hash ring 是有序的，那么顺时针遍历各个节点，每个【请求】将被分配给距离它最近的那个【服务节点上。如图所示：
这样一来，每个【服务节点】都拥有一个区域，两个节点之间的环形区域，归顺时针更大的那个节点。所有进入这个区域的请求都会被这个节点所处理。
如图，John 被 Node 1 处理，Deyan 和 Africa 被 Node 2 处理。每个【请求】去顺时针寻找第一个可用的【服务节点】即可。
缩容
一旦某个节点因为某种原因宕机，需要移除，那么直接移除即可，原先寻找这个节点的【请求】，会直接归属到下一个【服务节点】，如图所示：
类似的，我们也可以通过分配的弧长，来调整不同节点的权重。假设某个【服务节点】机器配置特别好，我们就让它管辖的区间更广即可。
如图，这里有节点 0,1,2。但分配弧长时，节点 0 占的区间比 1 和 2 都大，这样就调节了权重。
扩容
假设我们需要加机器，也是类似的原理。需要将原来的弧长分配给新的节点，让这个区间内的【请求】能够找到新节点即可：
注意，此时节点1 和 节点 2 服务的请求是完全没动的，只是原来节点0的一些请求分配给了节点 3。
成本对比
时间复杂度
假设总数据条数为 M，而节点个数为 N：
- 传统的哈希算法以 N 为基数执行取模运算，时间复杂度为 O(1)；
- 一致性哈希算法需要将关键字先转换为 32 位整型（这 1 步的时间复杂度也是 O(1)），再根据哈希环中各节点的处理范围，找到所属的节点。由于所有节点是有序排列的，所以采用二分法，可以在 O(logN) 时间复杂度内，完成关键字到节点位置的映射。
数据迁移规模
- 传统哈希算法中，节点变化会导致映射结果不可控，最坏情况下所有数据都需要迁移，所以它的数据迁移规模是 O(M)；
- 对于一致性哈希算法，我们可以通过调整节点位置，任意设定迁移规模。在环中各节点均匀分布的情况下，数据迁移规模是 O(M/N)。
所以，一致性哈希算法的缺点是将映射函数的时间复杂度从 O(1) 提高到了 O(logN)，它的优点是将数据迁移规模从 O(M) 降低至 O(M/N)。
但注意，在真实的线上场景中，我们根本不在乎哈希这点时间消耗，事实上【请求】这个 M 是远大于【服务节点】数量 N 的，而且数据迁移是一个很重的操作。这就是一致性哈希的好用之处。
虚拟节点
为了提高均衡性，防止某个节点一旦挂了，下个节点要处理的请求量翻倍，我们常常会把 hash ring 分配更均匀，而不是直接划出一大块区间给某个节点。即在真实的数据节点与哈希环之间引入一个虚拟节点层。
例如下图中的集群含有 4 个节点，但我们并不直接将哈希环分为 4 份，而是将它均匀地分为 32 份并赋予 32 个虚拟节点，因此每个虚拟节点会处理 227 个哈希值，再将 32 个虚拟节点通过某个哈希函数（比如 CRC32）映射到 4 个真实节点上（比如图中 8 个绿色虚拟节点皆由同色的主机节点 0 处理）：
扩容和缩容都是类似的，这里的本质在于，为了维护虚拟节点和真实节点之间的映射关系，我们需要再加一层哈希映射，打散处理。事实上生产环境中虚拟节点个数可能非常多。这样能提升均衡性，但随之而来的性能消耗也会更多。
虚拟节点带来的最大优点，是宕机时由所有节点共同分担流量缺口，这避免了可能产生的雪崩效应。同时，扩容的新节点也会分流所有节点的压力，这也提升了系统整体资源的利用率。
结语
有位同学的总结说的很好，其实从传统哈希到一致性哈希，再到虚拟节点。本质是从一次哈希，变成了两次，最后三次哈希，提升数据分布均匀性。
- 传统哈希：分配一次就知道是哪个节点；
- 一致性哈希基础版：分配一次后，继续根据二分法找到请求所属的【服务节点】；
- 一致性哈希 + 虚拟节点：分配一次后，二分法找到【虚拟节点】，再重新映射，找到【真实节点】
把【分配】这一步成本提高，换回来数据分布的稳定性。扩缩容时不必大动干戈。