1.2.1　负载均衡算法

在选定转发方式的情况下，采用哪种调度算法将决定整个负载均衡的性能表现，不同的算法适用于不同的应用场合，有时可能需要针对特殊场合，自行设计调度算法。每个负载均衡器都有自己独有的算法，下面给大家介绍一下LVS、HAProxy、Nginx常见的算法。

1.LVS的常见算法

（1）轮叫调度（Round Robin）

负载均衡器通过“轮叫”调度算法将外部请求按顺序轮流分配到集群中的真实服务器上，它均等地对待每一台服务器，而不管服务器上实际的连接数和系统负载。任何形式的负载均衡器（包括硬件或软件级别的）都带有基本的轮叫（也叫轮询功能）。

（2）加权轮叫（Weighted Round Robin）

负载均衡器通过“加权轮叫”调度算法根据真实服务器的不同处理能力来调度访问请求，这样可以保证处理能力强的服务器能处理更多的访问流量。负载均衡器可以自动问询真实服务器的负载情况，并动态地调整其权值。

（3）最少连接（Least Connections）

负载均衡器通过“最少连接”调度算法动态地将网络请求调度到已建立的连接数最少的服务器上。如果集群系统的真实服务器具有相近的系统性能，采用“最少连接”调度算法可以较好地实现负载均衡。

（4）加权最少连接（Weighted Least Connections）

在集群系统中的服务器性能差异较大的情况下，负载均衡器采用“加权最少连接”调度算法优化负载均衡性能，具有较高权值的服务器将承受较大比例的活动连接负载。负载均衡器可以自动问询真实服务器的负载情况，并动态地调整其权值。

（5）基于局部性的最少连接（Locality-Based Least Connections，LBLC）

“基于局部性的最少连接”调度算法是针对目标IP地址的负载均衡，目前主要用于Cache集群系统。该算法会根据请求的目标IP地址找出该目标IP地址最近使用的服务器，若该服务器是可用的且没有超载，则将请求发送到该服务器；若服务器不存在，或者该服务器超载且有服务器处于一半的工作负载状态，则用“最少连接”的原则选出一个可用的服务器，并将请求发送到该服务器。

（6）带复制的基于局部性最少连接（Locality-Based Least Connections with Replication）

“带复制的基于局部性最少连接”调度算法也是针对目标IP地址的负载均衡，目前主要用于Cache集群系统。它与LBLC算法的不同之处是它要维护从一个目标IP地址到一组服务器的映射，而LBLC算法维护的是从一个目标IP地址到一台服务器的映射。该算法会根据请求的目标IP地址找出该目标IP地址对应的服务器组，并按“最少连接”原则从服务器组中选出一台服务器，若服务器没有超载，将请求发送到该服务器；若服务器超载，则按“最少连接”原则从这个集群中选出一台服务器，将该服务器加入服务器组中，并将请求发送到该服务器。同时，如果该服务器组有一段时间没有被修改，则会将最忙的服务器从服务器组中删除，以降低复制的程度。

（7）目标地址散列（Destination IP Hashing）

“目标地址散列”调度算法会以请求的目标IP地址作为散列键（Hash Key）从静态分配的散列表找出对应的服务器，若该服务器是可用的且未超载，那么会将请求发送到该服务器，否则返回空。

（8）源地址散列（Source IP Hashing）

“源地址散列”调度算法会以请求的源IP地址作为散列键从静态分配的散列表找出对应的服务器，若该服务器是可用的且未超载，那么会将请求发送到该服务器，否则返回空。

（9）源IP和端口的Hash（Source IP and Source Port Hashing）

通过Hash函数将来自同一个源IP地址和源端口的请求映射到后端的同一台服务器上，该算法适用于需要保证来自同一用户同一业务的请求被分发到同一台服务器的场景。

（10）随机（Random）

随机地将请求分发到不同的服务器上，从统计学角度来看，调度的结果是为各台服务器平均分担用户的连接请求，该算法适用于集群中各机器性能相当，无明显优劣差异的场景。

2.HAProxy的常见算法

HAProxy的算法现在也越来越多了，具体有如下8种：

1）roundrobin，表示简单的轮询，这是负载均衡基本都具备的算法。

2）static-rr，每个服务器根据权重轮流使用，类似roundrobin，但它是静态的，意味着运行时修改权限是无效的。另外，它对服务器的数量没有限制。

3）leastconn，连接数最少的服务器优先接收连接。leastconn建议用于长会话服务，如LDAP、SQL、TSE等，而不适合短会话协议，如HTTP。该算法是动态的，对于实例启动慢的服务器权重会在运行中调整。

4）source，对请求源IP地址进行散列，用可用服务器的权重总数除以散列值，根据结果进行分配。只要服务器正常，同一个客户端IP地址总是访问同一个服务器。如果散列的结果随可用服务器的数量变化而变化，那么客户端会定向到不同的服务器。该算法一般用于不能插入cookie的TCP模式。它还可以在广域网上为拒绝使用会话cookie的客户端提供最有效的粘连。该算法默认是静态的，所以运行时修改服务器的权重是无效的，但是算法会根据“hash-type”的变化做调整。

5）URI，表示根据请求的URI地址进行散列，用可用服务器的权重总数除以散列值，根据结果进行分配。只要服务器正常，同一个URI地址总是会访问同一个服务器。一般用于缓存代理，以最大限度提高缓存的命中率。该算法只能用于HTTP后端，默认是静态的，所以运行时修改服务器的权重是无效的，但是算法会根据“hash-type”的变化做调整。

6）url_param，表示请求的URL参数。在HTTP GET请求的查询串中查找<param>中指定的URL参数，基本上可以锁定使用特定规则的URL到特定负载均衡器节点的要求，该算法一般用于将同一个用户的信息发送到同一个后端服务器上。该算法默认是静态的，所以运行时修改服务器的权重是无效的，但是算法会根据“hash-type”的变化做调整。

7）hdr(<name>)，对于每个HTTP请求，此处由<name>指定的HTTP首部将会被取出做Hash计算，并由服务器总权重相除以后将HTTP请求发至某个被挑选的服务器，没有有效值的会被轮询调度。此算法的目的是使用同一浏览器，请求被发送到同一后端主机。

8）rdp-cookie(name)，根据cookie(name)来锁定并散列每一次TCP请求，该机制用于退化的持久模式，可以使同一个用户或者同一个会话ID总是发送给同一台服务器。如果没有cookie，则使用roundrobin算法代替。该算法默认是静态的，所以运行时修改服务器的权重是无效的，但是算法会根据“hash-type”的变化做调整。

3.Nginx的常见算法

（1）roundrobin（默认）

每个请求按时间顺序逐一分配到不同的后端服务器，如果后端服务器宕掉，则会跳过该服务器分配至下一个监控的服务器。并且它无须记录当前所有连接的状态，所以它是一种无状态调度。

（2）weight

指定在轮询的基础上加上权重，权重和访问比率成正比，即用于表明后端服务器的性能好坏，这种情况特别适合后端服务器性能不一致的工作场景。

（3）ip_hash

每个请求按访问IP的散列结果分配，当新的请求到达时，先将其客户端IP通过散列算法进行散列计算，得出一个值，在随后的请求中，只要客户端IP的散列值相同，就会被分配至同一个后端服务器，该调度算法可以解决Session的问题，但有时会导致分配不均即无法保证负载均衡。

（4）fair（第三方）

按后端服务器的响应时间来分配请求，响应时间短的优先分配。

（5）url_hash（第三方）

按访问URL的散列结果来分配请求，使每个URL定向到同一个后端服务器，后端服务器为缓存时比较有效。

在upstream中加入Hash语句，server语句中不能写入weight等其他的参数，hash_method使用的是Hash算法，示例如下：

---

upstream web_pool {
server squid1:3128;
server squid2:3128;
hash $request_uri;
hash_method crc32;
}

---

（6）一致性Hash算法

应该是借鉴了目前最流行的一致性Hash算法思路。它的具体做法是：将每个服务器虚拟成N个节点，均匀分布到Hash环上，每次请求根据配置的参数计算出一个Hash值，在Hash环上查找离这个Hash最近的虚拟节点，对应的服务器作为该次请求的后端机器，这样做的好处是，如果是动态地增加了机器或者某台Web机器宕机，对整个集群的影响最小，其工作原理如图1-3所示。

图1-3　一致性Hash算法工作原理图

当后端是缓存服务器时，经常使用一致性Hash算法来进行负载均衡。

使用一致性Hash的好处在于，增减集群的缓存服务器时，只有少量的缓存会失效，回源量较小。在CDN集群架构中，Nginx或者自研的缓存软件系统所使用的负载均衡推荐算法便是一致性Hash。

事实上，负载均衡算法也可以分成静态算法和动态算法。那么我们如何分类上述算法呢？

静态调度算法，即负载均衡会根据自身设定的规则进行分配，不需要考虑节点服务器的情况，如rr、wrr及ip_hash等。

动态调度算法，即负载均衡会根据后端节点的当前状态来决定是否分发请求，如连接数少的优先获取请求、响应时间短的优先获取请求等。

了解了这些负载均衡算法的原理后，我们能够在特定的应用场合选择最合适的调度算法，从而尽可能地保持后端服务器的最佳利用性。当然也可以自行开发算法，不过这已超出本文范围，请参考有关算法原理的资料。