1. 前言
三种IP负载均衡技术解决了系统的可伸缩性和透明性。如何通过负载调度器将请求高 效地分发到不同的服务器执行，使得由多台独立计算机组成的集群系统成为一台虚拟服务器；客户端应用程序与集群系统交互时，就像与一台高性能的服务器交互一 样。
负载调度器上的负载调度策略和算法，解决如何将请求流调度到各台服务器，使得各台服务器尽可能地保持负载均衡。
以下主要由两个部分组 成。第一部分描述IP负载均衡软件IPVS在内核中所实现的各种连接调度算法；第二部分给出一个动态反馈负载均衡算法（Dynamic-feedback load balancing），它结合内核中的加权连接调度算法，根据动态反馈回来的负载信息来调整服务器的权值，来进一步避免服务器间的负载不平衡。
2.1 内核中的连接调度算法
IPVS在内核中的负载均衡调度是以连接为粒度的。在HTTP协议（非持久）中，每个对象从WEB服务器上获取都需要建立一个TCP连接，同一用户 的不同请求会被调度到不同的服务器上，所以这种细粒度的调度在一定程度上可以避免单个用户访问的突发性引起服务器间的负载不平衡。
内核中的连接调度算法，IPVS实现了8种：
- 轮叫调度（Round-Robin Scheduling）
- 加权轮叫调度（Weighted Round-Robin Scheduling）
- 最小连接调度（Least-Connection Scheduling）
- 加权最小连接调度（Weighted Least-Connection Scheduling）
- 基于局部性的最少链接（Locality-Based Least Connections Scheduling）
- 带复制的基于局部性最少链接（Locality-Based Least Connections with Replication Scheduling）
- 目标地址散列调度（Destination Hashing Scheduling）
- 源地址散列调度（Source Hashing Scheduling）
2.1 轮询调度
轮叫调度（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;
- 算法假设所有服务器处理性能均相同，不管服务器的当前连接数和响应速度。不适用于服务器组中处理性能不一的情况，而且当请求服务时间变化比较大时，轮叫调度算法容易导致服务器间的负载不平衡。
2.2 加权轮询调度
加权轮询调度（Weighted Round-Robin Scheduling）算法可以解决服务器间性能不一的情况，用相应的权值表示服务器的性能，缺省值为1。
加权轮询调度算法
/*
假设有一组服务器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;
}
当请求的时间变化很大，单独的加权轮询算法也会导致服务器间的负载不平衡。
加权轮询调度无需记录当前所有连接的状态，是一种无状态调度。
2.3 最小连接调度
最小连接调度（Least-Connection Scheduling），把新的连接请求分配到当前链接数量最小的服务器。最小连接调度是一种动态算法，通过服务器当前活跃的连接数来估计服务器的负载情况。
需要记录各个服务器已经建立的连接数目。
权值为零时，表示该服务器不可用而不被调度：
/*
假设有一组服务器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;
当服务器性能相同时，最小连接调度可以把负载变化大的请求分布平滑到各个服务器上。
当服务器性能不同时，算法不理想。
2.4 加权最小连接调度
加权最小连接调度（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;
2.5 基于局部性的最小连接调度
基于局部性的最小连接调度（Locality-Based Least Connection Scheduling，简称LBLC）算法针对请求报文的目标IP地址的负载均衡调度。
因为在Cache集群中客户请求报文的目标IP地址是变化的，因此目前主要用于Cache集群系统，
算法的目标是在服务器负载基本平衡的情况下，将相同目标的IP请求调度到同一台服务器，来提高各个服务器的访问局限性和Cache命中率。
LBLC调度算法先根据请求的目标IP地址找出该目标IP地址最近使用的服务器，若服务器可用且未超载，将请求发送到该服务器，如果服务器不存在，或者服务器超载且有服务器处在一半的工作负载，则用“最小链接”原则选出可用服务器，发送请求到该服务器。
/*
假设有一组服务器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;
2.6 带复制的基于局部性最小链接调度
带复制的基于局部性最小链接调度（Locality-Based Least Connections with Replication Scheduling，简称为LBLCR）是针对目标IP地址的算法，用于Cache系统。
它和LBLC算法不同的是维护一个目标IP地址到一组服务器的映射，而LBLC算法维护一个目标IP地址到一台服务器的映射。
如果一个站点过于“热门”，LBLC算法会导致该站点映像出现在所有的Cache服务器上，降低了Cache服务器的使用效率。
LBLCR算法将“热门”站点映射到一组Cache服务器（服务器集合），根据对站点的请求调解集合中的服务器数量。提高了Cache集群系统的使用效率。
LBLCR算法先根据请求的目标IP地址找出该目标IP地址对应的服务器组；按“最小连接”原则从该服务器组中选出一台服务器，若服务器没有超载， 将请求发送到该服务器；若服务器超载；则按“最小连接”原则从整个集群中选出一台服务器，将该服务器加入到服务器组中，将请求发送到该服务器。同时，当该 服务器组有一段时间没有被修改，将最忙的服务器从服务器组中删除，以降低复制的程度。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小时。
2.7 目标地址散列调度
目标地址散列调度（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函数如下：
static inline unsigned hashkey(unsigned int dest_ip)
{
return (dest_ip* 2654435761UL) & HASH_TAB_MASK;
}
/*
其中，2654435761UL是2到2^32 (4294967296)间接近于黄金分割的素数，
(sqrt(5) - 1) / 2 = 0.618033989
2654435761 / 4294967296 = 0.618033987
*/
2.8 源地址散列调度
源地址散列调度（Source Hashing Scheduling）算法和目标地址散列调度算法相反，根据请求的源IP地址，作为散列键（Hash Key）从静态分配的散列表中找出对应的服务器，若该服务器是可用的且未超载，将请求发送到该服务器，否则返回空。它采用的散列函数与目标地址散列调度算法 的相同。它的算法流程与目标地址散列调度算法的基本相似，除了将请求的目标IP地址换成请求的源IP地址。
在实际应用中，源地址散列调度和目标地址散列调度可以结合使用在防火墙集群中，它们可以保证整个系统的唯一出入口。
3. 动态反馈负载均衡算法
动态反馈负载均衡算法考虑服务器的实时负载和响应情况，不断调整服务器间处理请求的比例，来避免有些服务器超载时依然收到大量请求，从而提 高整个系统的吞吐率。
有点难，以后有一定积累了再学。
