云计算数据中心负载均衡调度-技术发展与应用

（一）云计算数据中心综合负载均衡调度策略概述

云计算数据中心将虚拟机按用户需求规格（可能不一致）动态、自动化地分配给用户，但是由于用户的需求规格和数据中心所有的物理服务器的规格配置不一致，如果采用简单的分配调度方法，例如常用的轮转法、加权轮转法、最小负载（或链接数）优先、加权最小负载优先法、哈希法等，很难达到物理服务器负载均衡，进而会造成服务性能不均衡和其他相关问题。

轮转法（Round Robin）通常是预先设定好一个轮转周期（例如物理服务器个数），依次将用户需求的虚拟机分配给不同的物理服务器，一个轮转周期结束后重新开始新一个轮转。轮转法不能解决物理服务器和用户需求规格不一致造成的负载不均衡问题。

加权轮转法预先对物理服务器设定权值，在负载均衡分配虚拟机的过程中，轮转选择物理服务器，如果被选择的物理服务器的权值为0，则跳过该服务器并选择下一台，如被选择的服务器的权值不为0，则选中该服务器并将该服务器的权值减1，后继的选择在前一次选择的基础上轮转。以权值分别为1，2，3的3台物理服务器（PM1，PM2，PM3）为例，第一次选择第一台物理服务器PM1其权值减为0，第二次选择第二台物理服务器PM2，其权值减为1，第三次选择第三台物理服务器PM3，其权值减为2，第四次轮转到第一台服务器PM1，但是其权值为0，继续轮转，选择第二台服务器PM2，同时其权值减为0，依，此类推。6次选择依次是：PM1，PM2，PM3，PM2，PM3，PM3。这样权值高的服务器获得的服务次数就与其权值成正比，但是当用户需求规格不一致时仍然存在负载不均衡的问题；另外加权轮转法需要在均衡过程中修改各台服务器的权值，这些公共变量需要进行加锁、解锁，影响执行速度。

（二）云计算数据中心负载均衡调度策略中主要调度算法分析

本节主要介绍的调度算法包括：轮转调度算法、加权轮转调度算法、目标地址哈希调度算法、源地址哈希调度算法、加权最小链接算法。

1.轮转调度算法

把新的连接请求按顺序轮流分配到不同的服务器上，从而实现负载均衡。该算法的优点在于简单易行，但不适用于每个服务器性能不一致的情况。

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

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

轮转调度算法流程：假设有一组服务器S=｛S0，S1，S2……Sn-1｝，一个指示变量i表示上一次选择的服务器，W（Si）表示服务器Si的权值。变量i被初始化为n-1，其中n＞0。

轮转调度算法假设所有的服务器处理性能均相同，不管服务器的当前连接数和响应速度。该算法相对简单，不适用于服务器组中处理性能不一致的情况。

2.加权轮转调度算法

克服轮转调度算法的不足，用相应的权值表示服务器的处理能力，权值较大的服务器将被赋予更多的请求。一段时间后服务器处理的请求数趋向于各自权值的比例。

加权轮转调度算法流程：

假设有一组服务器S=｛S0，S1，…，Sn-1｝，W（Si）表示服务器Si的权值，一个指示变量i表示上一次选择的服务器，指示变量cw表示当前调度的权值，max（S）表示集合S中所有服务器的最大权值，gcd（S）表示集合中所有服务器权值的最大公约数。变量i初始化为-1，cw初始化为零。

加权轮转调度算法考虑了服务器处理性能不一致、服务器的当前连接数等因素。该算法相对轮转调度实用性更强，但是当请求服务时间变化比较大时，加权轮转调度算法容易导致服务器间的负载不平衡。

3.目标地址哈希调度算法(www.xing528.com)

以目的地址为关键字查找一个静态哈希（Hash）表来获得所需的真实服务器。

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

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

假设有一组服务器S=｛S0，S1，…，Sn-1｝，W（Si）表示服务器Si的权值，C（S）表示服务器Si的当前连接数。ServerNode［］是一个有256个桶（Bucket）的哈希表，一般来说，服务器的数目会远小于256，当然表的大小也是可以调整的。

算法的初始化是将所有服务器顺序、循环地放置到ServerNode表中。若服务器的连接数大于2倍的权值，则表示服务器已超载。

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

其中，2654435761UL是2到232（4294967296）间接近于黄金分割的素数。

4.源地址哈希调度算法

以源地址为关键字查找一个静态Hash表来获得所需的真实服务器。

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

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

5.加权最小链接算法

克服最小链接算法的不足，用相应的权值表示服务器的处理能力，将用户的请求分配给当前连接数与权值之比最小的服务器。它是LVS（Linux Virtual System）默认的负载分配算法。假设有一组服务器S=｛S0，S1，…，Sn-1｝，W（Si）表示服务器Si的权值，C（Si）表示服务器Si的当前连接数，所有服务器当前连接数的总和为。当前的新连接请求会被发送到服务器Sm，当且仅当服务器满足以下条件：

其中W（Si）不为零。因为Csum在这一轮查找中是个常数，所以判断条件可以简化为：

其中W（Si）不为零。

因为除法所需的CPU周期比乘法多，且在Linux内核中不允许浮点除法，服务器的权值大于零，所以判断条件可以进一步优化为C（Sm）×W（Sm）＞C（Si）×W（Si）

同时保证服务器的权值为零时，服务器不被调度。所以算法只要执行以下流程：