IPVS调度算法

IPVS内核代码支持以下调度算法（大量内容摘自LVS网站）。

轮转(Round Robin, rr)

轮转调度算法将每个传入请求发送到其列表中的下一个服务器。因此，在三服务器集群（服务器A,B和C）中，请求1将转到服务器A，请求2将转到服务器B，请求3将转到服务器C，请求4将转到服务器A，这样就完成了服务器的循环或“轮转”。它对所有真实服务器都一视同仁，而不管每个服务器所经历的传入连接数量或响应时间。与传统的轮转DNS相比，虚拟服务器具有一些优势。轮转DNS将单个域名解析为不同的IP地址，调度粒度是基于主机的，并且DNS查询的缓存阻碍了基本算法，这些因素导致真实服务器之间的动态负载严重失衡。

加权轮转(Weighted Round Robin, wrr)

加权轮转调度旨在更好地处理具有不同处理能力的服务器。可以为每个服务器分配一个权重，权重就是用来表示处理能力的整数值。具有较高权重的服务器优先获取新连接，并且会获得更多连接，相同权重的服务器获取的连接数相同。举个栗子，真实服务器A,B和C分别具有权重4,3,2，在调度周期（mod sum(Wi)）中，良好的调度序列将是 AABABCABC。在加权轮转调度的实现中，在修改虚拟服务器的规则之后，将根据服务器权重生成调度序列。

当真实服务器的处理能力不同时，加权轮转调度优于轮转调度。但是，如果请求的负载变化很大，则可能导致真实服务器之间的动态负载严重失衡。简而言之，大多数需要大量响应的请求可能会被引导到同一个真实服务器。

实际上，轮转调度是加权轮转调度的一个特殊实例，其中所有服务器的权重都相等。

最少连接(Least Connection, lc)

最少连接调度算法将网络连接定向到具有最少数量的已建立连接的服务器。这是动态调度算法之一，因为它需要动态计算每个服务器的实时连接。对于管理具有相似性能的服务器集群的虚拟服务器，且请求的负载变化很大时，最少连接调度可以进行平滑分发。虚拟服务器会将请求定向到具有最少活跃连接的真实服务器。

乍一看，即使存在各种计算能力的服务器，最少连接调度也可能表现良好，因为更快的服务器将获得更多的网络连接。事实上，由于TCP的 TIME_WAIT 状态，它无法很好地执行。TCP的TIME_WAIT通常是2分钟，在这2分钟，一个繁忙的网站经常收到数千个连接，例如，服务器A的计算能力是服务器B的2倍，服务器A处理数千个请求并使它们进入TCP的TIME_WAIT状态，但服务器B正在爬行以完成其数千个连接。因此，最少连接调度不能在具有各种处理能力的服务器之间很好地平衡负载。

加权最少连接(Weighted Least Connection, wlc)

加权最少连接调度是最少连接调度的超集，您可以在其中为每个真实服务器分配性能权重。具有较高权重值的服务器在任何时候都将获得更大比例的实时连接。虚拟服务器管理员可以为每个真实服务器分配权重，并且网络连接将被安排到每个服务器，其中每个服务器的当前活动连接数与其权重成正比。默认权重为1。

加权最少连接调度的工作原理如下：

假设有n个真实服务器，每个服务器i具有权重Wi(i=1,2,…,n)，和活动连接数Ci(i=1,2,…,n)，ALL_CONNECTIONS是Ci的总和(i=1,2,…,n)，下一个网络连接将被定向到服务器j，其中

(Cj/ALL_CONNECTIONS)/Wj = min { (Ci/ALL_CONNECTIONS)/Wi } (i=1,..,n)

由于ALL_CONNECTIONS在此查找中是常量，因此不需要将Ci除以ALL_CONNECTIONS，它可以被优化为

Cj/Wj = min { Ci/Wi } (i=1,..,n)

加权最少连接调度算法相比最少连接调度算法需要额外的除法。为了在服务器具有相同的处理能力时最小化调度的开销，最少连接调度和加权最少连接调度算法都需要被实现。

基于局部性的最少连接(Locality-Based Least Connection, lblc)

基于局部性的最少连接调度算法用于目标IP负载均衡。它通常用于缓存集群。如果服务器处于活动状态且负载不足，那么此算法通常会将发往IP地址的数据包定向到其所在服务器。如果服务器过载（其活动连接数大于其权重）并且有其他服务器处于半负载状态，则将加权最少连接服务器分配给此IP地址。

带复制的基于局部性最少连接(Locality-Based Least Connection with Replication, lblcr)

带复制的基于局部性最少连接调度算法也用于目标IP负载均衡。它通常用于缓存集群。它与 LBLC 调度的区别在于：负载均衡器需要维护从一个目标IP地址到一组服务器的映射，而LBLC调度维护从一个目标IP地址到一台服务器的映射。对目标IP的请求将分配给对应的服务器组中的最少连接节点。如果服务器组中的所有节点都过载，那么从集群中挑选出最少连接节点，并将其添加到服务器组中。如果服务器组在指定时间内都未修改，则从服务器组中删除负载最高的节点，以避免高度复制。

目标地址哈希(Destination Hashing, dh)

目标地址哈希调度算法根据请求的目标IP地址查找静态分配的哈希表来为服务器分配网络连接。

源地址哈希(Source Hashing, sh)

源地址哈希调度算法根据请求的源IP地址查找静态分配的哈希表来为服务器分配网络连接。

最短预期延迟(Shortest Expected Delay, seq)

最短预期延迟调度算法以最短的预期延迟将网络连接分配给服务器。如果发送到第i个服务器，作业将经历的预期延迟为 (Ci + 1)/ Ui，其中Ci是第i个服务器上的连接数，Ui是第i个服务器的固定服务速率（权重）。

永不排队(Never Queue, nq)

永不排队调度算法采用双速模型。当有空闲服务器可用时，作业将被发送到空闲服务器，而不是等待快速服务器。当没有空闲服务器时，作业将被发送到最短预期延迟的服务器（最短预期延迟调度算法）。

溢出连接(Overflow-Connection, ovf)

溢出连接调度算法根据活动连接数实现“溢出”负载均衡，将所有连接发送到具有最高权重的节点，并且如果连接数超过节点的权重，就溢出到下一个节点。请注意，此调度算法可能不适用于UDP，因为它仅使用活动连接。