Linux服务器集群LVS

共计 13710 个字符，预计需要花费 35 分钟才能阅读完成。

本文主要介绍了 Linux 服务器集群系统–LVS（Linux Virtual Server）, 并简单描述下 LVS 集群的基本应用的体系结构以及 LVS 的三种 IP 负载均衡模型（VS/NAT、VS/DR 和 VS/TUN）的工作原理，以及它们的优缺点和 LVS 集群的 IP 负载均衡软件 IPVS 在内核中实现的各种连接调度算法。
参考文献 http://www.linuxvirtualserver.org/zh/index.html

前言

LVS(Linux Virtual Server)的简写，翻译为 Linux 虚拟服务器，即一个虚拟的服务器集群系统，是由我国章文嵩博士在 1998 年 5 月所研究成立，也是中国国内最早出现的自由软件项目之一。

宗旨

使用集群技术和 Linux 操作系统实现一个高性能、高可用的服务器.
- 提供很好的可伸缩性(Scalability)
- 提供很好的可靠性(Reliability)
- 提供很好的可管理性(Managerability)

实现负载均衡方式

硬件(Hardware)
- F5BIG-IP
- Citrix NetScaler(思杰)
- A10
软件(Software)
- 运行在 TCP/IP 四层协议上：
  - LVS(Linux Virtual Server)
- 运行在 TCP/IP 七层协议上：
  - nginx
  - haproxy

基本 LVS 体系架构

集群 LVS 架构描述

LVS 集群采用 IP 负载均衡技术和基于内容请求分发技术。调度器具有很好的吞吐率，将请求均衡地转移到不同的服务器上执行，且调度器自动屏蔽掉服务器的故障，从而将一组服务器构成一个高性能的、高可用的虚拟服务器。整个服务器集群的结构对客户是透明的，而且无需修改客户端和服务器端的程序。

架构基本构图

Linux 服务器集群 LVS

为此，在设计时需要考虑系统的透明性、可伸缩性、高可用性和易管理性。一般来说，LVS 集群采用三层结构，其体系结构如图 1 所示，三层主要组成部分为：
- 负载调度器（load balancer），它是整个集群对外面的前端机，负责将客户的请求发送到一组服务器上执行，而客户认为服务是来自一个 IP 地址（我们可称之为虚拟 IP 地址）上的。
- 服务器池（server pool），是一组真正执行客户请求的服务器，执行的服务有 WEB、MAIL、FTP 和 DNS 等。
- 共享存储（shared storage），它为服务器池提供一个共享的存储区，这样很容易使得服务器池拥有相同的内容，为用户提供相同的服务.

LVS 模型介绍

NAT：Network Address Translation(地址转换)
DR: Direct Routing(直接路由)
TUN：IP Tunneling(IP 隧道)

Virtual Server via Network Address Translation NAT(VS/NAT)

在一组 real_server 服务器前有一个 Director，它们是通过 Switch/HUB 相连接的。这些服务器提供相同的网络服务、相同的内容，即不管请求被发送到后台哪一台 RealServer，执行结果是一样的。服务的内容可以复制到每台 RealServer 的本地硬盘上，可以通过网络文件系统（如 NFS）共享，也可以通过一个分布式文件系统来提供。所有的 RealServer 只需要将自己的网关指向 Director 即可。客户端可以是任意操作系统，但此方式下，一个 Director 能够带动的 RealServer 比较有限。在 VS/NAT 的方式下，Director 也可以兼为一台 RealServer。

VS/NAT 的体系结构如图所示:

Linux 服务器集群 LVS
图 2：VS/NAT 的体系结构

客户通过 Virtual IP Address（虚拟服务的 IP 地址）访问网络服务时，请求报文到达调度器，调度器根据连接调度算法从一组真实服务器中选出一台服务器，将报文的目标地址 Virtual IP Address 改写成选定服务器的地址，报文的目标端口改写成选定服务器的相应端口，最后将修改后的报文发送给选出的服务器。同时，调度器在连接 Hash 表中记录这个连接，当这个连接的下一个报文到达时，从连接 Hash 表中可以得到原选定服务器的地址和端口，进行同样的改写操作，并将报文传给原选定的服务器。当来自真实服务器的响应报文经过调度器时，调度器将报文的源地址和源端口改为 Virtual IP Address 和相应的端口，再把报文发给用户。我们在连接上引入一个状态机，不同的报文会使得连接处于不同的状态，不同的状态有不同的超时值。在 TCP 连接中，根据标准的 TCP 有限状态机进行状态迁移，这里我们不一一叙述，请参见 W. Richard Stevens 的《TCP/IP Illustrated Volume I》；在 UDP 中，我们只设置一个 UDP 状态。不同状态的超时值是可以设置的，在缺省情况下，SYN 状态的超时为 1 分钟，ESTABLISHED 状态的超时为 15 分钟，FIN 状态的超时为 1 分钟；UDP 状态的超时为 5 分钟。当连接终止或超时，调度器将这个连接从连接 Hash 表中删除。

这样，客户所看到的只是在 Virtual IPAddress 上提供的服务，而服务器集群的结构对用户是透明的。对改写后的报文，应用增量调整 Checksum 的算法调整 TCP Checksum 的值，避免了扫描整个报文来计算 Checksum 的开销。

在一些网络服务中，它们将 IP 地址或者端口号在报文的数据中传送，若我们只对报文头的 IP 地址和端口号作转换，这样就会出现不一致性，服务会中断。所以，针对这些服务，需要编写相应的应用模块来转换报文数据中的 IP 地址或者端口号。我们所知道有这个问题的网络服务有 FTP、IRC、H.323、CUSeeMe、Real Audio、Real Video、Vxtreme / Vosiac、VDOLive、VIVOActive、True Speech、RSTP、PPTP、StreamWorks、NTT AudioLink、NTT SoftwareVision、Yamaha MIDPlug、iChat Pager、Quake 和 Diablo。

下面，举个例子来进一步说明 VS/NAT，如图 3 所示：

Linux 服务器集群 LVS
图 3：VS/NAT 的例子

VS/NAT 的配置如下表所示，所有到 IP 地址为 202.103.106.5 和端口为 80 的流量都被负载均衡地调度的真实服务器 172.16.0.2:80 和 172.16.0.3:8000 上。目标地址为 202.103.106.5:21 的报文被转移到 172.16.0.3:21 上。而到其他端口的报文将被拒绝。

Protocol	Virtual IP Address	Port	Real IP Address	Port	Weight
TCP	202.103.106.5	80	172.16.0.2	80	1
			172.16.0.3	8000	2
TCP	202.103.106.5	21	172.16.0.3	21	1

从以下的例子中，我们可以更详细地了解报文改写的流程。

访问 Web 服务的报文可能有以下的源地址和目标地址：

SOURCE

202.100.1.2:3456

DEST

202.103.106.5:80

调度器从调度列表中选出一台服务器，例如是 172.16.0.3:8000。该报文会被改写为如下地址，并将它发送给选出的服务器。

SOURCE

202.100.1.2:3456

DEST

172.16.0.3:8000

从服务器返回到调度器的响应报文如下：

SOURCE

172.16.0.3:8000

DEST

202.100.1.2:3456

响应报文的源地址会被改写为虚拟服务的地址，再将报文发送给客户：

SOURCE

202.103.106.5:80

DEST

202.100.1.2:3456

这样，客户认为是从 202.103.106.5:80 服务得到正确的响应，而不会知道该请求是服务器 172.16.0.2 还是服务器 172.16.0.3 处理的。

Virtual Server via Direct Routing(VS/DR)

VS/DR 利用大多数 Internet 服务的非对称特点，Director 中只负责调度请求，而后台 real_server 服务器直接将响应返回给客户，不再通过 Director 进行转发。

DR 方式是通过改写请求报文中的 MAC 地址部分来实现的。Director 和 RealServer 必需在物理上有一个网卡通过不间断的局域网相连, 如通过高速的交换机或者 HUB 相连。

VIP 地址为 Director 和 RealServer 组共享，RealServer 上绑定的 VIP 配置在各自 Non-ARP 的网络设备上(如 eth0 或 lo),Director 的 VIP 地址对外可见，而 RealServer 的 VIP 对外是不可见的, 只是用于处理目标地址为 VIP 的网络请求,RealServer 的地址即可以是内部地址，也可以是真实地址。

VS/DR 的体系结构如图所示:

Linux 服务器集群 LVS
图 4：VS/DR 的体系结构

VS/DR 的工作流程如图 5 所示：它的连接调度和管理与 VS/NAT 和 VS/TUN 中的一样，它的报文转发方法又有不同，将报文直接路由给目标服务器。在 VS/DR 中，调度器根据各个服务器的负载情况，动态地选择一台服务器，不修改也不封装 IP 报文，而是将数据帧的 MAC 地址改为选出服务器的 MAC 地址，再将修改后的数据帧在与服务器组的局域网上发送。因为数据帧的 MAC 地址是选出的服务器，所以服务器肯定可以收到这个数据帧，从中可以获得该 IP 报文。当服务器发现报文的目标地址 VIP 是在本地的网络设备上，服务器处理这个报文，然后根据路由表将响应报文直接返回给客户。

Linux 服务器集群 LVS
图 5：VS/DR 的工作流程

在 VS/DR 中，根据缺省的 TCP/IP 协议栈处理，请求报文的目标地址为 VIP，响应报文的源地址肯定也为 VIP，所以响应报文不需要作任何修改，可以直接返回给客户，客户认为得到正常的服务，而不会知道是哪一台服务器处理的。
VS/DR 负载调度器跟 VS/TUN 一样只处于从客户到服务器的半连接中，按照半连接的 TCP 有限状态机进行状态迁移。

Virtual Server via IP Tunneling(VS/TUN)

IP 隧道 (IP tunneling) 是将一个 IP 报文封装在另一个 IP 报文的技术，这可以使得目标为一个 IP 地址的数据报文能被封装和转发到另一个 IP 地址。

IP 隧��技术亦称为 IP 封装技术(IP encapsulation)。IP 隧道主要用于移动主机和虚拟私有网络(Virtual Private Network)，在其中隧道都是静态建立的，隧道一端有一个 IP 地址，另一端也有唯一的 IP 地址。它的连接调度和管理与 VS/NAT 中的一样，只是它的报文转发方法不同。

Director 根据各个服务器的负载情况，动态地选择一台 RealServer，将请求报文封装在另一个 IP 报文中，再将封装后的 IP 报文转发给选出的 RealServer;RealServer 收到报文后，先将报文解封获得原来目标地址为 VIP 的报文，RealServer 发现 VIP 地址被配置在本地的 IP 隧道设备上，所以就处理这个请求，然后根据路由表将响应报文直接返回给客户。

VS/TUN 的体系结构如图所示:

Linux 服务器集群 LVS
图 6：VS/TUN 的体系结构

VS/TUN 的工作流程如图 7 所示：它的连接调度和管理与 VS/NAT 中的一样，只是它的报文转发方法不同。调度器根据各个服务器的负载情况，动态地选择一台服务器，将请求报文封装在另一个 IP 报文中，再将封装后的 IP 报文转发给选出的服务器；服务器收到报文后，先将报文解封获得原来目标地址为 VIP 的报文，服务器发现 VIP 地址被配置在本地的 IP 隧道设备上，所以就处理这个请求，然后根据路由表将响应报文直接返回给客户。

Linux 服务器集群 LVS
图 7：VS/TUN 的工作流程

在这里需要指出，根据缺省的 TCP/IP 协议栈处理，请求报文的目标地址为 VIP，响应报文的源地址肯定也为 VIP，所以响应报文不需要作任何修改，可以直接返回给客户，客户认为得到正常的服务，而不会知道究竟是哪一台服务器处理的。

Linux 服务器集群 LVS
图 8：半连接的 TCP 有限状态机

三种负载模型比较

Virtual Server via NAT

VS/NAT 的优点是服务器可以运行任何支持 TCP/IP 的操作系统，它只需要一个 IP 地址配置在调度器上，服务器组可以用私有的 IP 地址。缺点是它的伸缩能力有限，当服务器结点数目升到 20 时，调度器本身有可能成为系统的新瓶颈，因为在 VS/NAT 中请求和响应报文都需要通过负载调度器。我们在 Pentium166 处理器的主机上测得重写报文的平均延时为 60us，性能更高的处理器上延时会短一些。假设 TCP 报文的平均长度为 536Bytes，则调度器的最大吞吐量为 8.93MBytes/s. 我们再假设每台服务器的吞吐量为 800KBytes/s，这样一个调度器可以带动 10 台服务器。（注：这是很早以前测得的数据）

基于 VS/NAT 的的集群系统可以适合许多服务器的性能要求。如果负载调度器成为系统新的瓶颈，可以有三种方法解决这个问题：混合方法、VS/TUN 和 VS/DR。

在 DNS 混合集群系统中，有若干个 VS/NAT 负载调度器，每个负载调度器带自己的服务器集群，同时这些负载调度器又通过 RR-DNS 组成简单的域名。
但 VS/TUN 和 VS/DR 是提高系统吞吐量的更好方法。

对于那些将 IP 地址或者端口号在报文数据中传送的网络服务，需要编写相应的应用模块来转换报文数据中的 IP 地址或者端口号。
这会带来实现的工作量，同时应用模块检查报文的开销会降低系统的吞吐率。

Virtual Server via Direct Routing

跟 VS/TUN 方法一样，VS/DR 调度器只处理客户到服务器端的连接，响应数据可以直接从独立的网络路由返回给客户。这可以极大地提高 LVS 集群系统的伸缩性。

跟 VS/TUN 相比，这种方法没有 IP 隧道的开销，但是要求负载调度器与实际服务器都有一块网卡连在同一物理网段上，服务器网络设备（或者设备别名）不作 ARP 响应，或者能将报文重定向（Redirect）到本地的 Socket 端口上。

Virtual Server via IP Tunneling

在 VS/TUN 的集群系统中，负载调度器只将请求调度到不同的后端服务器，后端服务器将应答的数据直接返回给用户。这样，负载调度器就可以处理大量的请求，它甚至可以调度百台以上的服务器（同等规模的服务器），而它不会成为系统的瓶颈。即使负载调度器只有 100Mbps 的全双工网卡，整个系统的最大吞吐量可超过 1Gbps。所以，VS/TUN 可以极大地增加负载调度器调度的服务器数量。VS/TUN 调度器可以调度上百台服务器，而它本身不会成为系统的瓶颈，可以用来构建高性能的超级服务器。

VS/TUN 技术对服务器有要求，即所有的服务器必须支持“IP Tunneling”或者“IP Encapsulation”协议。目前，VS/TUN 的后端服务器主要运行 Linux 操作系统，我们没对其他操作系统进行测试。因为“IP Tunneling”正成为各个操作系统的标准协议，所以 VS/TUN 应该会适用运行其他操作系统的后端服务器。

三种模型的优缺点比较

三种 IP 负载均衡技术的优缺点归纳在下表中：

	VS/NAT	VS/TUN	VS/DR
Server	any	Tunneling	Non-arp device
server_network	private	LAN/WAN	LAN
server_number	low (10~20)	High (100)	High (100)
server_gateway	load balancer	own router	Own router

内核中负载均衡调度算法

IPVS 在内核中的负载均衡调度是以连接为粒度的。在 HTTP 协议（非持久）中，每个对象从 WEB 服务器上获取都需要建立一个 TCP 连接，同一用户的不同请求会被调度到不同的服务器上，所以这种细粒度的调度在一定程度上可以避免单个用户访问的突发性引起服务器间的负载不平衡在内核中的连接调度算法上，IPVS 已实现了以下八种调度算法：

固定调度算法：

RR : 轮叫调度（Round-Robin Scheduling）
WRR : 加权轮叫调度（Weighted Round-Robin Scheduling）
DH : 目标地址散列调度（Destination Hashing Scheduling）
SH : 源地址散列调度（Source Hashing Scheduling）

动态调度算法:

LC : 最小连接调度（Least-Connection Scheduling）
WLC : 加权最小连接调度（Weighted Least-Connection Scheduling）
LBLC : 基于局部性的最少链接（Locality-Based Least Connections Scheduling）
LBLCR : 带复制的基于局部性最少链接（Locality-Based Least Connections with Replication Scheduling）
SED : 最短预期延时调度（Shortest Expected Delay Scheduling）
NQ : 不排队调度（Never Queue Scheduling）

轮叫调度(RR)

轮叫调度（Round Robin Scheduling）算法就是以轮叫的方式依次将请求调度不同的服务器，即每次调度执行 i = (i +1) mod n，并选出第 i 台服务器。算法的优点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无状态调度。

在系统实现时，我们引入了一个额外条件，当服务器的权值为零时，表示该服务器不可用而不被调度。这样做的目的是将服务器切出服务（如屏蔽服务器故障和系统维护），同时与其他加权算法保持一致。所以，算法要作相应的改动，它的算法流程如下：

轮叫调度算法流程：

假设有一组服务器 S = {S0, S1, …, Sn-1}，一个指示变量 i 表示上一次选择的
服务器，W(Si)表示服务器 Si 的权值。变量 i 被初始化为 n -1，其中 n > 0。j = i;
do {j = (j + 1) mod n;
    if (W(Sj) > 0) {
        i = j;
        return Si;
    }
} while (j != i);
return NULL;

轮叫调度算法假设所有服务器处理性能均相同，不管服务器的当前连接数和响应速度。该算法相对简单，不适用于服务器组中处理性能不一的情况，而且当请求服务时间变化比较大时，轮叫调度算法容易导致服务器间的负载不平衡。

虽然 Round-Robin DNS 方法也是以轮叫调度的方式将一个域名解析到多个 IP 地址，但轮叫 DNS 方法的调度粒度是基于每个域名服务器的，域名服务器对域名解析的缓存会妨碍轮叫解析域名生效，这会导致服务器间负载的严重不平衡。这里，IPVS 轮叫调度算法的粒度是基于每个连接的，同一用户的不同连接都会被调度到不同的服务器上，所以这种细粒度的轮叫调度要比 DNS 的轮叫调度优越很多。

加权轮叫调度(WRR)

加权轮叫调度（Weighted Round-Robin Scheduling）算法可以解决服务器间性能不一的情况，它用相应的权值表示服务器的处理性能，服务器的缺省权值为 1。假设服务器 A 的权值为 1，B 的权值为 2，则表示服务器 B 的处理性能是 A 的两倍。加权轮叫调度算法是按权值的高低和轮叫方式分配请求到各服务器。权值高的服务器先收到的连接，权值高的服务器比权值低的服务器处理更多的连接，相同权值的服务器处理相同数目的连接数。加权轮叫调度算法流程如下：

加权轮叫调度算法流程:

假设有一组服务器 S = {S0, S1, …, Sn-1}，W(Si)表示服务器 Si 的权值，一个
指示变量 i 表示上一次选择的服务器，指示变量 cw 表示当前调度的权值，max(S)
表示集合 S 中所有服务器的最大权值，gcd(S)表示集合 S 中所有服务器权值的最大
公约数。变量 i 初始化为 -1，cw 初始化为零。while (true) {i = (i + 1) mod n;
if (i == 0) {cw = cw - gcd(S); 
     if (cw <= 0) {cw = max(S);
       if (cw == 0)
         return NULL;
     }
  } 
  if (W(Si) >= cw) 
    return Si;
}

例如，有三个服务器 A、B 和 C 分别有权值 4、3 和 2，则在一个调度周期内 (mod sum(W(Si))) 调度序列为 AABABCABC。加权轮叫调度算法还是比较简单和高效。当请求的服务时间变化很大，单独的加权轮叫调度算法依然会导致服务器间的负载不平衡。

从上面的算法流程中，我们可以看出当服务器的权值为零时，该服务器不被被调度；当所有服务器的权值为零，即对于任意 i 有 W(Si)=0，则没有任何服务器可用，算法返回 NULL，所有的新连接都会被丢掉。加权轮叫调度也无需记录当前所有连接的状态，所以它也是一种无状态调度。

目标地址散列调度(DH)

目标地址散列调度（Destination Hashing Scheduling）算法也是针对目标 IP 地址的负载均衡，但它是一种静态映射算法，通过一个散列（Hash）函数将一个目标 IP 地址映射到一台服务器。

目标地址散列调度算法先根据请求的目标 IP 地址，作为散列键（Hash Key）从静态分配的散列表找出对应的服务器，若该服务器是可用的且未超载，将请求发送到该服务器，否则返回空。该算法的流程如下：

目标地址散列调度算法流程:

假设有一组服务器 S = {S0, S1, ..., Sn-1}，W(Si)表示服务器 Si 的权值，C(Si)表示服务器 Si 的当前连接数。ServerNode[]是一个有 256 个桶（Bucket）的
Hash 表，一般来说服务器的数目会运小于256，当然表的大小也是可以调整的。算法的初始化是将所有服务器顺序、循环地放置到 ServerNode 表中。若服务器的
连接数目大于 2 倍的权值，则表示服务器已超载。n = ServerNode[hashkey(dest_ip)];
if ((n is dead) OR
    (W(n) == 0) OR
    (C(n) > 2*W(n))) then
    return NULL;
return n;

在实现时，我们采用素数乘法 Hash 函数，通过乘以素数使得散列键值尽可能地达到较均匀的分布。所采用的素数乘法 Hash 函数如下：

素数乘法 Hash 函数

static inline unsigned hashkey(unsigned int dest_ip)
{return (dest_ip* 2654435761UL) & HASH_TAB_MASK;
}
其中，2654435761U L 是 2 到2^32 (4294967296)间接近于黄金分割的素数，(sqrt(5) - 1) / 2 =  0.618033989
  2654435761 / 4294967296 = 0.618033987

源地址散列调度(SH)

源地址散列调度（Source Hashing Scheduling）算法正好与目标地址散列调度算法相反，它根据请求的源 IP 地址，作为散列键（Hash Key）从静态分配的散列表找出对应的服务器，若该服务器是可用的且未超载，将请求发送到该服务器，否则返回��。它采用的散列函数与目标地址散列调度算法的相同。它的算法流程与目标地址散列调度算法的基本相似，除了将请求的目标 IP 地址换成请求的源 IP 地址，所以这里不一一叙述。

在实际应用中，源地址散列调度和目标地址散列调度可以结合使用在防火墙集群中，它们可以保证整个系统的唯一出入口。

最小连接调度(LC)

最小连接调度（Least-Connection Scheduling）算法是把新的连接请求分配到当前连接数最小的服务器。最小连接调度是一种动态调度算法，它通过服务器当前所活跃的连接数来估计服务器的负载情况。调度器需要记录各个服务器已建立连接的数目，当一个请求被调度到某台服务器，其连接数加 1；当连接中止或超时，其连接数减一。

在系统实现时，我们也引入当服务器的权值为零时，表示该服务器不可用而不被调度，它的算法流程如下：

最小连接调度算法流程:

假设有一组服务器 S = {S0, S1, ..., Sn-1}，W(Si)表示服务器 Si 的权值，C(Si)表示服务器 Si 的当前连接数。for (m = 0; m < n; m++) {if (W(Sm) > 0) {for (i = m+1; i < n; i++) {if (W(Si) <= 0)
                continue;
            if (C(Si) < C(Sm))
                m = i;
        }
        return Sm;
    }
}
return NULL;

当各个服务器有相同的处理性能时，最小连接调度算法能把负载变化大的请求分布平滑到各个服务器上，所有处理时间比较长的请求不可能被发送到同一台服务器上。但是，当各个服务器的处理能力不同时，该算法并不理想，因为 TCP 连接处理请求后会进入 TIME_WAIT 状态，TCP 的 TIME_WAIT 一般为 2 分钟，此时连接还占用服务器的资源，所以会出现这样情形，性能高的服务器已处理所收到的连接，连接处于 TIME_WAIT 状态，而性能低的服务器已经忙于处理所收到的连接，还不断地收到新的连接请求。

加权最小连接调度(WLC)

加权最小连接调度（Weighted Least-Connection Scheduling）算法是最小连接调度的超集，各个服务器用相应的权值表示其处理性能。服务器的缺省权值为 1，系统管理员可以动态地设置服务器的权值。加权最小连接调度在调度新连接时尽可能使服务器的已建立连接数和其权值成比例。加权最小连接调度的算法流程如下：

加权最小连接调度的算法流程:

假设有一组服务器 S = {S0, S1, ..., Sn-1}，W(Si)表示服务器 Si 的权值，C(Si)表示服务器 Si 的当前连接数。所有服务器当前连接数的总和为
CSUM = ΣC(Si)  (i=0, 1, .. , n-1)。当前的新连接请求会被发送服务器 Sm，当且仅当服务器 Sm 满足以下条件
  (C(Sm) / CSUM)/ W(Sm) = min {(C(Si) / CSUM) / W(Si)}  (i=0, 1, . , n-1)
  其中 W(Si)不为零
因为 CSUM 在这一轮查找中是个常数，所以判断条件可以简化为
  C(Sm) / W(Sm) = min {C(Si) / W(Si)}  (i=0, 1, . , n-1)
  其中 W(Si)不为零

因为除法所需的 CPU 周期比乘法多，且在 Linux 内核中不允许浮点除法，服务器的
权值都大于零，所以判断条件 C(Sm) / W(Sm) > C(Si) / W(Si) 可以进一步优化
为 C(Sm)*W(Si) > C(Si)* W(Sm)。同时保证服务器的权值为零时，服务器不被调
度。所以，算法只要执行以下流程。for (m = 0; m < n; m++) {if (W(Sm) > 0) {for (i = m+1; i < n; i++) {if (C(Sm)*W(Si) > C(Si)*W(Sm))
                m = i;
        }
        return Sm;
    }
}
return NULL;

基于局部性的最少链接调度(LBLC)

基于局部性的最少链接调度（Locality-Based Least Connections Scheduling，以下简称为 LBLC）算法是针对请求报文的目标 IP 地址的负载均衡调度，目前主要用于 Cache 集群系统，因为在 Cache 集群中客户请求报文的目标 IP 地址是变化的。这里假设任何后端服务器都可以处理任一请求，算法的设计目标是在服务器的负载基本平衡情况下，将相同目标 IP 地址的请求调度到同一台服务器，来提高各台服务器的访问局部性和主存 Cache 命中率，从而整个集群系统的处理能力。

LBLC 调度算法先根据请求的目标 IP 地址找出该目标 IP 地址最近使用的服务器，若该服务器是可用的且没有超载，将请求发送到该服务器；若服务器不存在，或者该服务器超载且有服务器处于其一半的工作负载，则用“最少链接”的原则选出一个可用的服务器，将请求发送到该服务器。该算法的详细流程如下：

LBLC 调度算法流程:

假设有一组服务器 S = {S0, S1, ..., Sn-1}，W(Si)表示服务器 Si 的权值，C(Si)表示服务器 Si 的当前连接数。ServerNode[dest_ip]是一个关联变量，表示
目标 IP 地址所对应的服务器结点，一般来说它是通过 Hash 表实现的。WLC(S)表示
在集合 S 中的加权最小连接服务器，即前面的加权最小连接调度。Now为当前系统
时间。if (ServerNode[dest_ip] is NULL) then {n = WLC(S);
    if (n is NULL) then return NULL;
    ServerNode[dest_ip].server = n;
} else {n = ServerNode[dest_ip].server;
    if ((n is dead) OR
        (C(n) > W(n) AND
         there is a node m with C(m) < W(m)/2))) then {n = WLC(S);
        if (n is NULL) then return NULL;
        ServerNode[dest_ip].server = n;
    }
}
ServerNode[dest_ip].lastuse = Now;
return n;

此外，对关联变量 ServerNode[dest_ip]要进行周期性的垃圾回收（Garbage
Collection），将过期的目标 IP 地址到服务器关联项进行回收。过期的关联项是指哪些当前时间（实现时采用系统时钟节拍数 jiffies）减去最
近使用时间超过设定过期时间的关联项，系统缺省的设定过期时间为 24 小时。

带复制的基于局部性最少链接调度(LBLCR)

带复制的基于局部性最少链接调度（Locality-Based Least Connections with Replication Scheduling，以下简称为 LBLCR）算法也是针对目标 IP 地址的负载均衡，目前主要用于 Cache 集群系统。它与 LBLC 算法的不同之处是它要维护从一个目标 IP 地址到一组服务器的映射，而 LBLC 算法维护从一个目标 IP 地址到一台服务器的映射。对于一个“热门”站点的服务请求，一台 Cache 服务器可能会忙不过来处理这些请求。这时，LBLC 调度算法会从所有的 Cache 服务器中按“最小连接”原则选出一台 Cache 服务器，映射该“热门”站点到这台 Cache 服务器，很快这台 Cache 服务器也会超载，就会重复上述过程选出新的 Cache 服务器。这样，可能会导致该“热门”站点的映像会出现在所有的 Cache 服务器上，降低了 Cache 服务器的使用效率。LBLCR 调度算法将“热门”站点映射到一组 Cache 服务器（服务器集合），当该“热门”站点的请求负载增加时，会增加集合里的 Cache 服务器，来处理不断增长的负载；当该“热门”站点的请求负载降低时，会减少集合里的 Cache 服务器数目。这样，该“热门”站点的映像不太可能出现在所有的 Cache 服务器上，从而提供 Cache 集群系统的使用效率。

LBLCR 算法先根据请求的目标 IP 地址找出该目标 IP 地址对应的服务器组；按“最小连接”原则从该服务器组中选出一台服务器，若服务器没有超载，将请求发送到该服务器；若服务器超载；则按“最小连接”原则从整个集群中选出一台服务器，将该服务器加入到服务器组中，将请求发送到该服务器。同时，当该服务器组有一段时间没有被修改，将最忙的服务器从服务器组中删除，以降低复制的程度。LBLCR 调度算法的流程如下：

LBLCR 调度算法流程:

假设有一组服务器 S = {S0, S1, ..., Sn-1}，W(Si)表示服务器 Si 的权值，C(Si)表示服务器 Si 的当前连接数。ServerSet[dest_ip]是一个关联变量，表示
目标 IP 地址所对应的服务器集合，一般来说它是通过 Hash 表实现的。WLC(S)表示
在集合 S 中的加权最小连接服务器，即前面的加权最小连接调度；WGC(S)表示在
集合 S 中的加权最大连接服务器。Now为当前系统时间，lastmod 表示集合的最近
修改时间，T 为对集合进行调整的设定时间。if (ServerSet[dest_ip] is NULL) then {n = WLC(S);
    if (n is NULL) then return NULL;
    add n into ServerSet[dest_ip];
} else {n = WLC(ServerSet[dest_ip]);
    if ((n is NULL) OR
        (n is dead) OR
        (C(n) > W(n) AND
         there is a node m with C(m) < W(m)/2))) then {n = WLC(S);
        if (n is NULL) then return NULL;
        add n into ServerSet[dest_ip];
    } else
    if (|ServerSet[dest_ip]| > 1 AND
        Now - ServerSet[dest_ip].lastmod > T) then {m = WGC(ServerSet[dest_ip]);
        remove m from ServerSet[dest_ip];
    }
}
ServerSet[dest_ip].lastuse = Now;
if (ServerSet[dest_ip] changed) then
    ServerSet[dest_ip].lastmod = Now;
return n;

此外，对关联变量 ServerSet[dest_ip]也要进行周期性的垃圾回收（Garbage Collection），将过期的目标 IP 地址到服务器关联项进行回收。过期的关联项是指哪些当前时间（实现时采用系统时钟节拍数 jiffies）减去最近使用时间（lastuse）超过设定过期时间的关联项，系统缺省的设定过期时间为 24 小时。