关于后端:漫谈负载均衡算法

负载平衡是个大话题，咱们能够谈谈：

• slow start 给新退出的节点调配较低权重，防止过载
• priority 不同的可用区（AZ）有不同的优先级，非以后可用区的节点只有在以后可用区节点不可用时才作为备份退出
• subset 分组负载平衡，会先通过负载平衡算法抉择一个组，再通过负载平衡算法在组里抉择具体的节点
• retry 当负载平衡碰上重试时，须要思考一些额定的状况。在重试时，通常咱们须要选中另一个节点，而不是从新选中以后节点。此外，在重试完所有节点后，个别状况下咱们不会再重试多一轮。

本文会关注以上各性能的基石局部 —— 负载平衡算法。

Random

随机负载平衡即随机选取一个节点。因为该形式是无状态的，所以是最容易实现的负载平衡。不过这是对于开发者的长处，不是使用者的。随机负载平衡只保障了数学冀望上的平衡，并不保障宏观尺度上是平衡的。有可能间断几个申请都命中同一个节点，正如运气不佳的人总会洪水猛兽一样。黑天鹅事件是随机负载平衡抹不去的暗影。我惟一举荐采纳随机负载平衡的场景，就是只有随机负载平衡作为惟一的选项。

RoundRobin

RoundRobin 指每个节点都会轮流被选中。对于所有节点权重都一样的场景，实现 RoundRobin 并不难。只需记录以后被选中的节点，而后下次选中它的下个节点即可。

对于权重不一样的场景，则须要思考如何让选中的节点足够平衡。假如有两个节点 A、B，权重别离是 5、2。如果只是使用权重统一时简略的 RoundRobin 实现，会失去上面的后果：

A B
A B
A
A
A

节点 A 最多会被间断选中 4 次（以后轮结尾时的 3 次加上下一轮时的 1 次）。思考到 A、B 节点的权重比例是 2.5:1，这种间断选中 A 节点达 4 次的行为跟两节点的权重比是不相称的。

所以针对该场景，咱们须要超过简略的逐节点轮询，让不同权重的节点间尽可能在宏观层面上平衡。以后面的 A、B 节点为例，一个宏观层面上的平衡调配会是这样的：

A
A B
A
A
A B

节点 A 最多被间断选中 3 次，跟权重比例 2.5:1 相差不大。

在实现带权重的 RoundRobin 算法的时候，请尽可能不要本人创造一套新算法。带权重的 RoundRobin 实现较为容易犯错。可能会呈现这样的状况：在本地开发测试下没问题，在线上跑一段时间也 OK，直到业务方输出了一组非凡的值，而后不平衡就产生了。该当参考支流的实现，如果须要在支流实现上做调整，最好提供数学上的证实。

接下来让咱们看下支流的实现 —— Nginx 和 Envoy 是如何做的。

Nginx 的实现大体上是这样子的：

1. 每个节点有本人的一个以后得分。每次抉择时遍历各个节点，给得分加上一个跟节点权重相干的值。
2. 每次抉择分数最高的节点。
3. 节点被选中时分数减去所有权重的和。

权重越高的节点，在减去分数后复原得越快，也就越有可能被持续选中。而且这里存在一个复原过程，所有保障了在下一次不太可能选中同一个节点。

因为这块代码耦合了被动健康检查的性能（存在多个 weight；effect_weight 须要依据 max_fails 做调整），所以较为简单。因为 Nginx 的具体实现代码并非本文重点，感兴趣的读者能够自行查阅。

Envoy 的实现绝对清晰些。它是基于 EDF 算法 的简化版原本做节点抉择。简略来说，它采纳了优先队列来抉择以后最佳节点。对于每个节点，咱们会记录两个值：

• deadline 下一次须要取出节点的机会
• last_popped_time 上一次取出此节点的机会

（Envoy 的具体实现代码与此有些出入。这里采纳 last_popped_time 而非 Envoy 中的 offset_order 是出于容易了解的目标）

再次以咱们的 A、B 节点为例。

A、B 两节点以 1/ 权重 作为各自的得分。算法运行形式如下：

1. 结构一个优先队列，排序办法为先比拟 deadline，前者雷同时比拟 last_popped_time。每个节点的初始值为各自的得分。
2. 每次抉择，会从优先队列中 pop 最新的值。
3. 每次选中一个节点后，更新它的 last_popped_time 为选中时的 deadline，并往 deadline 中减少对应的得分，从新插入到队列中。

每次抉择如下：

能够看出，在 EDF 算法下，节点 A 最多被间断选中 3 次（以后循环结尾时的 1 次加上下一循环时的 2 次），跟权重比例 2.5:1 相差不大。另外与 Nginx 的算法相比，在 EDF 下，抉择节点的工夫复杂度次要是从新插入时的 O(logn)，存在大量节点时会比一一节点比拟分数更快些。

Least Request

起码申请算法通常又称之为最小连接数算法，这一别名来源于晚期每个申请往往对应一个连贯，且该算法经常用于长连贯的负载平衡当中。RoundRobin 算法可能保障发给各个节点的申请是平衡的，然而它并不保障以后节点上的申请数是平衡的，因为它不晓得每个申请什么时候完结。如果服务的负载与以后申请数严密相干，比方在推送服务中心愿每个节点治理的连接数要平衡，那么一个现实的抉择就是应用起码申请算法。另外如果申请耗时较长且长短不一，应用起码申请算法也能保障每个节点上要筹备解决的申请数平衡，防止长时间排队。对于这种状况，也适宜采纳后文提到的 EWMA 算法。

要想实现起码申请算法，咱们须要记录每个节点的以后申请数。一个申请进来时加一，申请完结时减一。对于所有节点权重都一样的状况，靠 O(n) 的遍历能够找出起码申请的节点。咱们还能够再优化下。通过 P2C 算法，咱们能够每次随机抉择两个节点，以 O(1) 的工夫复杂度来达到近似于 O(n) 的遍历的成果。事实上，满足上面条件的状况，都能用 P2C 算法来优化工夫复杂度：

1. 每个节点有一个分数
2. 所有节点权重统一

所以有些框架会间接形象出一个 p2c 的中间件作为通用能力。

波及到各节点权重不一的状况，就没方法用 P2C 算法了。咱们能够把权重依据以后申请数做一下调整，变成 weight / (1 + 申请数）。一个节点失去申请数越多，那么以后权重就会绝对应地缩小。比方一个权重为 2 的节点，以后有 3 个申请，那么调整之后的权重为 1/2。如果又来了一个新的申请，那么权重就变成了 2/5。通过动静调整权重，咱们就能让带权重的起码申请变成带权重的 RoundRobin，进而应用遍历或优先队列来解决它。

Hash

有些时候，须要保障客户端拜访到固定的服务端。比方要求代理同一个 Session 的客户端的申请到同一个节点，或者依据客户端 IP 路由到固定节点。这时候咱们须要采纳 Hash 算法来把客户端的特色映射到某个节点上来。不过简略的 Hash 会有一个问题，如果节点数扭转了，会放大影响到的申请数目。

假如这个简略的 Hash 就是以节点数来取余，申请是 1 到 10 这几个数。节点数一开始为 4，随后变成 3。那么后果是：

1: 0 1 2 3 0 1 2 3 0 1
2: 0 1 2 0 1 2 0 1 2 0

咱们能够看到，70% 的申请对应的节点都变动了，远大于 25% 的节点数变动。

所以实际中咱们更多的是采纳 Consistent Hash，如果没有才会思考个别的 Hash 算法。

Consistent Hash

一致性 Hash 是专门为缩小从新 Hash 时后果产生大幅扭转而设计的算法。在后面的 Hash 算法中，因为 Hash 的后果与节点数强相干，所以一旦节点数产生扭转，Hash 后果就会激烈变动。那么咱们能不能让 Hash 后果与节点数无关呢？一致性 Hash 为咱们提供了新的思路。

最常见的一致性 Hash 算法是 ring hash。也即把整个 Hash 空间看作一个环，而后每个节点通过 Hash 算法映射到环上的一个点，每个申请会算出一个 Hash 值，依据 Hash 值找顺时针方向最近的一个节点。这样一来，申请的 Hash 值和节点的数量就没有关系了。环上节点变更时，申请的 Hash 值不会变，变的只是离它最近的节点可能不一样。

读者兴许会提出这样的问题，如果节点的地位取决于 Hash 的值，那么如何保障它是平衡调配呢？我在之前的文章《漫谈非加密哈希算法》提到过，Hash 算法在设计时会思考到升高碰撞的可能性。一个高质量的算法，该当尽可能扩散 Hash 映射后的后果。当然，如果只是对无限的几个节点做 Hash，那么难免会呈现后果分得不够开的状况。所以一致性 Hash 中引入了虚构节点的概念。每个实在的节点会对应 N 个虚构节点，比如说 100 个。每个虚构节点的 Hash 值由相似于 Hash(node + "_" + virtual_node_id) 这样的算法失去。这样一个实在节点，就会对应 Hash 环上 N 个虚构节点。从统计学的角度上看，咱们能够认为只有 N 的值足够大，节点间间隔的标准差就越小，节点在环上的散布就越平衡。

然而 N 并不能有限变大。即便是环上的虚构节点，也须要实在的内存地址来记录其地位。N 获得越大，节点就越平衡，但耗费的内存就越多。Maglev 算法是另外一种一致性 Hash 算法，旨在优化内存占用。该算法因为采纳了别的数据结构，可能在保障同样的均衡性时应用更少的内存。（抑或在应用同样的内存时提供更好的均衡性，取决于你固定那一个变量）。

EWMA

EWMA（Exponential Weighted Moving Average）算法是一种利用响应工夫进行负载平衡的算法。正如其名，它的计算过程就是“指数加权挪动均匀”。

假如以后响应工夫为 R，间隔上次访问的工夫为 delta_time，上次访问时的得分为 S1，那么以后得分 S2 为：
S2 = S1 * weight + R * (1.0 - weight)，其中 weight = e ^ -delta_time/k。k 是算法中当时固定的常量。

它是指数加权的：上次访问间隔当初的工夫越长，对以后得分的影响越小。
它是挪动的：以后得分从上次得分调整过去。
它是均匀的：如果 delta_time 足够大，weight 就足够小，得分靠近以后响应工夫；如果 delta_time 足够小，weight 就足够大，得分靠近上次得分。总体来说，得分是历次响应工夫通过调整得来的。

仔细的读者会问，既然 weight 是由 delta_time 算进去的，那么用户在配置时指定的权重该放到哪个地位呢？EWMA 是一种自适应的算法，可能依照上游的状态动静调整。如果你发现你须要配置权重，那么你的场景就不适用于应用 EWMA。事实上，因为 EWMA 算法不必操心权重，许多人会思考把它作为不足 slow start 性能时的替代品。

然而 EWMA 并非万灵药。因为 EWMA 是基于响应工夫的算法，如果上游响应工夫和上游状态没多大关系时，就不实用 EWMA。比方后面介绍起码申请算法时提到的推送场景，响应工夫取决于推送的策略，这时采纳 EWMA 就不般配了。

另外 EWMA 算法有个固有缺点 —— 响应工夫不肯定反映了问题的全貌。构想一个场景，上游有个节点一直疾速抛出 500 谬误。在 EWMA 算法看来，这个节点反而是个优良节点，毕竟它有着无可比拟的响应工夫。后果大部分流量就会打到这个节点上。所以当你采纳 EWMA 时，务必同时开启健康检查，及时摘掉有问题的节点。不过有些时候，一个看上去不属于节点问题的状态码也可能导致流量不平衡。举个例子，某次灰度降级时，新版本减少了一个谬误的校验，会把生产环境上局部正确的申请给回绝掉（返回 400 状态码）。因为 EWMA 会偏向于响应更快的节点，会导致更多的申请落入这个有问题的版本上。

除了 EWMA 之外，也有其余基于响应工夫的算法，比方 Dubbo 的加权最短响应优先。