Linux集群调度算法及技术研究

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）。

（一）轮叫调度

轮叫调度（Round Robin Scheduling）算法是以轮叫的方式依次将请求调度到不同的服务器，即每次调度执行i=（i+1）modn，并选出第i台服务器。该算法的优点是简洁，无须记录当前所有连接的状态，所以是一种无状态调度。在系统实现时，它引入了一个额外条件；当服务器的权值为零时，表示该服务器不可用而不被调度。这样做的目的是将服务器切出服务（如屏蔽服务器故障和系统维护），同时与其他加权算法保持一致。

轮叫调度算法假设所有服务器处理性能均相同，无论服务器的当前连接数和响应速度怎样。该算法相对简单，不适用于服务器组中处理性能不一的情况，而且当请求服务时间变化比较大时，轮叫调度算法容易导致服务器间的负载不平衡。虽然Round-Robin DNS方法也是以轮叫调度的方式将一个域名解析到多个IP地址，但轮叫DNS方法的调度粒度是基于每个域名服务器的，域名服务器对域名解析的缓存会妨碍轮叫解析域名生效，这会导致服务器间负载的严重不平衡。这里，IPVS轮叫调度算法的粒度是基于每个连接的，同一用户的不同连接都会被调度到不同的服务器上，所以这种细粒度的轮叫调度要比DNS的轮叫调度优越很多。

（二）加权轮叫调度

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

（三）最小连接调度

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

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

（四）加权最小连接调度(www.xing528.com)

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

（五）基于局部性的最小连接调度与带复制的基于局部性最小连接调度

基于局部性的最小连接调度（Locality-Based Least Connections Scheduling，LBLC）算法与带复制的基于局部性最小连接调度（Locality-Based Least Connections with Replication Scheduling，LBLCR）算法都是针对请求报文的目标IP地址的负载均衡调度，目前主要用于Cache集群系统。因与讨论的邮件系统集群的关联不大，这里不做进一步阐述。

（六）目标地址散列调度

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

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

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

（七）源地址散列调度

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