负载均衡之轮的计算方法

㈠ 计算机的负载均衡算法

计算机的负载均衡算法主要有以下几种：

1、静态负载均衡算法包括：轮询，比率，优先权。

2、动态负载均衡算法包括：最少连接数，最快响应速郑模轮度，喊信观察方法，预测法，动态性能分配，动态服务器补充，服务质量，服务类型，规则模式。

负载均衡算法的种类有很多种，常见的负载均衡算法包括轮询法、随机法、源地址哈希法、加权轮询法、加权随机法、最小连接法等，应根据具体的使用场景选取对应的算法。

(1)负载均衡之轮的计算方法扩展阅读：

在计算机的世界，这就是大家耳熟能详的负载均衡（load balancing），所谓负载均衡，就是说如果一组计算机节点（或者一组进程）提供相同的（同质的）服务，那么对服务的请求就应该均匀的分摊到这些节点上。

负载均衡的意义在于，让所有节点以最小的代价、最好的状态对外提供服务，这样系统吞吐量最大，性能更高，对于用户而言请求的时间也更小。而且，负载均衡增强了系统的可靠性，最大化降低了单个节点过载、甚至crash的概率。不难想象，如果一个系统绝大部分请求都落在同一个节点上，那么这些请求响应时间都很慢，而且万一节码没点降级或者崩溃，那么所有请求又会转移到下一个节点，造成雪崩。

㈡ 负载均衡算法 — 轮询

在分布式系统中，为了实现负载均衡，必然会涉及到负载调度算法，如 Nginx 和 RPC 服务发现等场景。常见的负载均衡算法有 轮询 、 源地址 Hash 、 最少连接数 ，而 轮询 是最简单且应用最广的算法。

3 种常见的唤晌轮询调度算法，分别为 简单轮询 、 加权轮询 、 平滑加权轮询 。本文将用如下 4 个服务，来详细说明轮询调度过程。

简单轮询是轮询算法中最简单的一种，但扒桥由于它不支持配置负载，所以应用较少。

假设有 N 台实例 S = {S1, S2, …, Sn}，指示变量 currentPos 表示当前选择的实例 ID，初始化为 -1。算法可以描述为：
1、调度到下一个实例；
2、若所有实例已被 调度 过一次，则从头开始调度；
3、每次调度重复步骤 1、2；

调度过程，如下：

这里使用 PHP 来实现，源码见 fan-hao/load-balance 部分。

首先，定义一个统一的操作接口，主要有 init() 和 next() 这 2 个方法。

然后，根据简单轮询算法思路，实现上述接口：

其中， total 为总实例数量，春链猛 services 为服务实例列表。由于简单轮询不需要配置权重，因此可简单配置为：

在实际应用中，同一个服务会部署到不同的硬件环境，会出现性能不同的情况。若直接使用简单轮询调度算法，给每个服务实例相同的负载，那么，必然会出现资源浪费的情况。因此为了避免这种情况，一些人就提出了下面的 加权轮询 算法。

加权轮询算法引入了“权”值，改进了简单轮询算法，可以根据硬件性能配置实例负载的权重，从而达到资源的合理利用。

假设有 N 台实例 S = {S1, S2, …, Sn}，权重 W = {W1, W2, ..., Wn}，指示变量 currentPos 表示当前选择的实例 ID，初始化为 -1；变量 currentWeight 表示当前权重，初始值为 max(S)；max(S) 表示 N 台实例的最大权重值，gcd(S) 表示 N 台实例权重的最大公约数。

算法可以描述为：
1、从上一次调度实例起，遍历后面的每个实例；
2、若所有实例已被遍历过一次，则减小 currentWeight 为 currentWeight - gcd(S)，并从头开始遍历；若 currentWeight 小于等于 0，则重置为 max(S)；
3、 直到 遍历的实例的权重大于等于 currentWeight 时结束，此时实例为需调度的实例；
4、每次调度重复步骤 1、2、3；

例如，上述 4 个服务，最大权重 max(S) 为 4，最大公约数 gcd(S) 为 1。其调度过程如下：

这里使用 PHP 来实现，源码见 fan-hao/load-balance 部分。

其中， getMaxWeight() 为所有实例的最大权重值； getGcd() 为所有实例权重的最大公约数，主要是通过 gcd() 方法（可用 gmp_gcd() 函数）求得 2 个数的最大公约数，然后求每一个实例的权重与当前最大公约数的最大公约数。实现如下：

需要注意的是，在配置 services 服务列表时，需要指定其权重：

加权轮询 算法虽然通过配置实例权重，解决了 简单轮询 的资源利用问题，但是它还是存在一个比较明显的 缺陷 。例如：

服务实例 S = {a, b, c}，权重 W = {5, 1, 1}，使用加权轮询调度生成的实例序列为 {a, a, a, a, a, b, c}，那么就会存在连续 5 个请求都被调度到实例 a。而实际中，这种不均匀的负载是不被允许的，因为连续请求会突然加重实例 a 的负载，可能会导致严重的事故。

为了解决加权轮询调度不均匀的缺陷，一些人提出了 平滑加权轮询 调度算法，它会生成的更均匀的调度序列 {a, a, b, a, c, a, a}。对于神秘的平滑加权轮询算法，我将在后续文章中详细介绍它的原理和实现。

轮询算法是最简单的调度算法，因为它无需记录当前所有连接的状态，所以它是一种 无状态 的调度算法，这些特性使得它应用较广。

轮询调度算法并不能动态感知每个实例的负载，它完全依赖于我们的工程经验，人为配置权重来实现基本的负载均衡，并不能保证服务的高可用性。若服务的某些实例因其他原因负载突然加重，轮询调度还是会一如既往地分配请求给这个实例，因此可能会形成小面积的宕机，导致服务的局部不可用。

相关文章 »