LVS调度算法

内核中的连接调度算法

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

在内核中的连接调度算法上，IPVS已实现了以下八种调度算法：

• 轮叫调度（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）

1、轮叫调度

该算法是以轮叫的方式依次将请求调度不同的服务器，即每次调度执行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、加权轮叫调度

该算法可以解决服务器间性能不一的情况，它是相应的权值表示服务器的处理性能，服务器的缺省值为1。假设服务器A的权值为1，B的权值为2，则表示服务器的处理性能是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，则在一个调度周期内，顺序为AABABCABC.次方法也比较简单，高效。当请求的服务时间变化很大，单独的加权轮叫调度算法依然会导致服务器之间负载不平衡

3、最小连接调度

该算法是将新的连接请求分配到当前连接数最小的服务器，最小调度是一种动态调度算法，它通过服务器当前所活跃的连接数来估计服务器的负载情况。调度器需要记录各个服务器已连接的数目，当一个请求被调度到某台服务器时，其连接数加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;

4、加权最小连接调度

该算法是最小连接调度的超集，各个服务器用相应的权值表示其处理能力。服务器的缺省值为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;

　　参考：http://www.linuxvirtualserver.org/zh/lvs4.html