LVS负载均衡（调度）算法-内核中的连接调度算法

 

此次主题主要讲述LVS 负载均衡策略和算法，这里面完全是罗列了章博士里面的blog，属于总结和转发性质。

 

如何将请求流调度到各台服务器，使得各台服务器尽可能地保持负载均衡。文章主要由两个部分组成。第一 部分描述IP 负载均衡软件IPVS 在内核中所实现的各种连接调度算法；第二部分给出一个动态反馈负载均衡算法（Dynamic-feedback load balancing ），它结合内核中的加权连接调度算法，根据动态反馈回来的负载信息来调整服务器的权值，来进一步避免服务器间的负载不平衡。

在下面描述中，我们称客户的socket 和服务器的socket 之间的数据通讯为连接，无论它们是使用TCP 还是UDP 协议。对于UDP 数据报文的 调度，IPVS 调度器也会为之建立调度记录并设置超时值（如5 分钟）；在设定的时间内，来自同一地址（IP 地址和端口）的UDP 数据包会被调度到同一台服 务器。

内核中的连接调度算法

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

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

• 轮叫调度（Round-Robin Scheduling ）

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

• 加权轮叫调度（Weighted Round-Robin Scheduling ）

跟轮询调度算法基本类似，轮询调式适合于每个服务器的负载都相同的情况，而加权轮询，可以处理每个服务器负载不同的情况，比如说，应该给cpu 和内存多的服务器以更多的权重。

• 最小连接调度（Least-Connection Scheduling ）

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

• 加权最小连接调度（Weighted Least-Connection Scheduling ）

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

• 基于局部性的最少链接（Locality-Based Least Connections Scheduling ）

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

• 带复制的基于局部性最少链接（Locality-Based Least Connections with Replication Scheduling ）

带复制的基于局部性最少链接调度（ 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 集群系统的使用效率。

 

• 目标地址散列调度（Destination Hashing Scheduling ）

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

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

注：下面的hash 函数比较有用，可以很好的让key 均匀的散列在hash 表里，提高查询效率。

static inline unsigned hashkey(unsigned int dest_ip)

{

  return (dest_ip* 2654435761UL) & HASH_TAB_MASK;

}

 

• 源地址散列调度（Source Hashing Scheduling ）

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

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

 

• 最短预期延时调度（Shortest Expected Delay Scheduling ）
• 不排队调度（Never Queue Scheduling ）