智能网络存储系统负载均衡算法研究

李昕

（陕西工业职业技术学院 陕西 咸阳 712000）

在INSS中，若写请求到达，首先判定文件大小，当为大文件请求时，必须先采用条带化技术对大文件进行切分，以此来提高用户对文件访问的并发性，从而来提高对大文件的访问性能，然后再将切分后数据块存储在同一区域多个节点上，在INSS中，需要设计一种基于负载均衡技术的数据放置策略，来避免在分配请求的任务过程中，某些服务器工作负载重，某些服务器工作负载轻。

1 负载均衡技术

分布式系统中的一个重要问题就是负载均衡问题[1]。分布式系统负载均衡的目标是根据处理机的性能来分配与其相称的任务，以最小化应用程序的执行时间。对各服务器来说，就是要根据负载均衡原则，为每个节点分配与其实际处理能力相适应的请求。这样可以避免集群中某些服务器工作负荷重，某些服务器工作负荷轻。

根据调节策略的不同，可以分为静态负载均衡和动态负载均衡两类，静态调度算法事先就己经确定好了请求任务的分发策略，它不管每个任务的性质、所需消耗的系统资源以及各个服务器运行时刻的负载情况，只是根据预先设定的分配方案对用户的请求进行分配。

根据任务调度模型的不同，我们又将动态负载均衡分为集中式控制与分布式控制集中式控制就是在负载均衡系统中设置一台中央控制服务器，我们把它叫做负载调度器。

2 静态负载均衡算法

2.1 轮转调度算法

轮转调度（Round Robin Scheduling RR）算法就是以轮转的方式依次将请求务调度到不同的服务器。将所有的服务器组成一个循环队列，当请求任务到达时，每次选取队头的服务器来响应当前请求任务，即调度器调度执行j=（i+1）mod n，选取第J台服务器来响应当前请求任务，i表示响应上一个请求任务的服务器[2]。如图1所示。

图1 轮转调度Fig.1 Round-robin scheduling

轮转调度算法是一种理想状况下的调度算法，无需考虑当前所有服务器的连接状态，采用无状态调度，固有处理能力相当因此属于静态调度算法。它假定各服务器是同构的，即所有的服务器，也不考虑各台服务器当前实际负载，中各服务器处理性能不一的情况，只使用于同构服务器。这种算法不适用于异构服务器事实上对于实际应用中的服务器绝大多数都是异构的，处理能力千差万别，而且各请求任务所消耗的时间以及各服务器的当前实际负载各不相同。

2.2 加权轮转调度算法

由于轮转调度算法不适用与异构系统，人们提出了它的改进算法一加权轮转调度（Weighted Round-Robin Scheduling}算法。为了处理各服务器处理性能不一的情况，加权轮转调度算法在轮转调度算法的基础上为各服务器增加了一个能代表该服务器固有处理能力的权值，请求任务分配时根据这个权值所确定的比例分配相对数量的请求任务，权值越大的服务器将会优先被调度到，而且调度次数也比权值小的服务器多，因此权值高的服务器较之权值低的服务器能接受更多的请求任务。

假设有 n 台服务器 S={S1，S2，L，Sn}，服务器 Si的当前调度权值为 W（Si），max（W（Si））表示所有服务器的最大权值，gcd（W（Si））表示所有服务器当前权值的最大公约数。如有请求任务到达，加权轮转调度算法将该请求任务分配给Sk，当且仅当 W（Sk）=max（W（Si）），Sk接受调度后，W（Sk）=W（Sk）-gcd（W（Si））。

Step1初始化权值表，根据固有处理能力为每个服务器设置合适的权值；

Step2若有请求任务到达，选择权值最大的服务器来响应该请求任务；

Step3 更新权值表，W（Sk）=W（Sk）-gcd（W（Si））；

Step4 若 W（Si）=0，从调度队列中退出。

3 动态负载均衡

3.1 最小连接调度算法

最小连接调度（Least Connections Scheduling）算法是选择当前各服务器中请求任务连接数最小的服务器作为下一个请求任务分配的目的地。这种算法考虑了各个服务器当前的负载信息，将连接数作为服务器当前的实际负载，连接数少的服务器实际负载较轻，较之连接数多的服务器具备相对多的剩余处理能力，能更快的响应并处理新到达的请求任务，因此选择连接数最小的服务器来响应下一个请求任务。最小连接调度算法利用动态反馈机制，周期性地跟踪各个服务器的当前连接数，将其记录在调度器内的负载表中，在当前周期内，请求任务被调度到当前连接数最小的服务器[3]，当下一个周期达到时，查询各服务器新的当前连接数，刷新调度器上负载表。

算法流程如下：

假设有n台服务器 S={S1，S2，L，Sn}， 其当前连接数为 L={L1，L2，L，Ln}，在当前周期内达到的请求任务数为 Ф，最小连接调度算法将这Ф个请求任务数分配到服务器Sk上，当且仅当 Lk=min{L1，L2，L，Ln}。

Step1初始化负载表；

Step2测试当前周期内各个服务器的当前连接数，更新负载表，若在规定时间内未收到某台服务器的当前连接数，将其所对应负载表的记录标为+∞，表示该服务器无法到达；

Step3若有新的请求任务，从负载表中选取当前连接数最小的记录所对应的服务器，将其分配给该服务器；

Step4若下一个周期达到，刷新负载表；若收到前一周期负载表中记录为+∞所对应服务器的当前连接数，更新该记录。

3.2 加权最小连接调度算法

最小连接调度算法将当前连接数作为衡量服务器负载的标准，加权最小连接调度算法为每台服务器增加了一个权值作为服务器的固有处理能力，将当前服务器的请求任务连接数目与该权值的比值作为服务器的负载权值，该比值小说明服务器的负载小，其剩余处理能力强，因此分配请求任务时，将请求任务分配给连接数与权值比值最少的服务器。最小连接调度算法同样也采用动态反馈机制，周期性监控各服务器的连接数，当下一个周期到达时，刷新负载表。算法执行流程如图6所示[4-5]。

而在每一周期内，Lsum为常值，所以可简化为：

Step 1初始化负载表；

Step2测试当前周期内各个服务器的当前连接数，计算比值Li/W（Si），更新负载表，若在规定时间内未收到某台服务器的当前连接数，将其所对应负载表的记录标为+∞，表示该服务器无法到达；

Step3 若有请求任务达到，找出 min（Li/W（Si））记录所对应的服务器，将其分配给该服务器；

Step4若下一个周期达到，刷新负载表。

3.3 最小负载优先算法

最小负载优先算法就是将请求任务分配到负载最小的服务器上，它是一个动态负载均衡算法[6]，需要周期性地更新负载信息来不断地修正调度器内的负载表，而负载表中记录了各个服务器在当前周期内的负载信息，调度器利用这些负载信息计算出一个综合负载来表示各个服务器的负载状况，综合负载大的服务器负载较重，综合负载小的服务器负载轻。算法流程如下：

Step 1：初始化负载表；

Step 2：若负载表为空，利用轮转调度算法，依次选择子区域，直至更新周期到达；否则转第四步；

Step3：若更新周期达到，节点利用心跳算法将负载信息包发送至调度器，如果在规定时间内未收到某节点的数据包，认为其不可达到，取消其响应资格，若在下个更新周期到达时，调度器收到了该节点的负载信息，更新周期表；

Step4：调度器根据负载信息计算每个综合负载的Li，选择服务器K作为响应服务器。

最小负载优先算法也有着加权最小连接调度算法的缺点，由于总是将新到的请求发送到综合负载最小的节点上，特别是当到达的请求任务分布比较密集的时候，这种调度算法可能会使得某一个节点在一个周期内接受了大量请求，从而使得负载不均衡，系统性能下降。

3.4 随机负载均衡算法

前面的负载均衡算法都是以固定的转发模式分配请求任务，但是由于请求任务的到达具有随机性，而且负载调度器在更新周期到达时收集的负载信息对于周期内请求任务的分配是过时的信息，所有的请求任务仍然分配到很有可能己不是最小负载的服务器上，从而导致负载不均衡，固定转发有一定的局限性，因此人们依据请求的随机性在算法中引入一定的随机性如正态分布或泊松分布等来改善系统的性能，而且研究表明，引入一定的随机性可以改善系统的整体性能。

4 INSS负载均衡模型

在智能网络存储系统中，当Iro请求到达时，必须先判定是读请求还是写请求，若为读请求，判断该读请求的数据是否存在副本，存在副本的情况下，元数据服务器根据当前周期负载记录找出拥有副本的节点中负载最低的来响应；否则，元数据服务器根据其所保存的数据库信息，直接从拥有该数据的节点中直接读取。若为写请求，首先判定文件大小，当为大文件请求时，必须先采用条带化技术对大文件进行切分，以此来提高用户对文件访问的并发性，从而来提高对大文件的访问性能，然后再利用 TLDF（TwoLevel Dynamic Feedback）算法将切分后数据块存储在同一区域多个节点上，而小文件不利于条带化，所以一般是采用将单个文件存储在单个数据服务器上的策略，同样利用TLDF算法将小文件存储在某个区域的一个节点上。文中的负载均衡主要考虑的是写请求，因此TLDF算法在智能网络存储系统中实际上是利用负载均衡技术的一种数据放置策略[7]。

对于大文件和小文件的写请求，我们有如下规定：

大任务：一个大文件的写请求；

请求任务：未切分的小文件和大文件切分后的数据块所对应的任务。

负载均衡调度器主要工作是:周期性地监测并收集存储层中各个节点的负载信息，根据当前周期T内各节点的负载信息按照第一级负载均衡策略选择合适的子区域N，再根据第二级负载均衡策略将请求任务分配至况中的某些节点。图3是负载均衡调度器的基本框架，主要3个模块:负载收集模块、调度模块以及执行模块。

图2 负载均衡调度器的基本框架Fig.2 Basic framework of load balancing scheduler maps

在INSS系统中，甚至在所有的分布式系统中，对请求任务进行负载均衡调度，首先必须评估系统中所有节点的负载，因此负载收集是进行负载均衡调度的基本前提，负载收集模块进行的主要工作是:

1）对节点的负载信息进行周期性地收集、统计和存储；

2）判断系统中节点是否失效。

请求任务的负载均衡调度中最核心的模块是调度模块，它作为整个框架中的“大脑”，调度模块中算法设计的好坏决定了一个调度算法性能的优劣[8]，调度模块主要解决的问题是:根据负载收集模块提供的负载信息，再结合负载均衡算法，计算出各节点的负载权值，为执行模块提供分配权值。

执行模块的主要任务是:当请求任务到达时，按照分配权值来执行分配策略，通知元数据服务器和客户端，该请求任务应分配至哪些节点，并将具体的分配信息存储在位于元数据服务器的数据库内，以方便元数据服务器对节点的管理。

5 结束语

详细探讨了几种经典的负载均衡调度算法，介绍了它们的算法流程及其优缺点，说明对于INSS系统的数据放置策略需要一个更为有效的负载均衡算法，最后根据INSS存储系统结构模型及其I/O请求流程，提出了一种二级动态反馈负载均衡模型。

[1]蒋从锋.基于网格计算的大规模分布式动态虚拟环境仿真研究[D].武汉：华中科技大学，2007.

[2]马丹.任务间相互依赖的并行作业调度算法研究[D].武汉：华中科技大学，2007.

[3]龚卫华.数据库集群系统的关键技术研究[D].武汉：华中科技大学，2006.

[4]周云霞，赵跃龙，杨希.智能网络磁盘存储系统的容灾研究[J].计算机研究与发展，2012（7）：75-75.

ZHOU Yun-xia，ZHAO Yue-long，YANG Xi[J].Disaster research on intelligent network disk storage system[J].Research and Development of Computer，2012（7）：75-75.

[5]魏祥麟，陈鸣，张国敏.一种综合的结构化P2P系统负载均衡机制[J].北京邮电大学学报，2012（3）：36.

WEI Xiang-lin，CHEN Ming，ZHANG Guo-min.Load balancing mechanism of a comprehensive structured P2P system[J].Journal of Beijing University of Posts and Telecommunications，2012（3）：36.

[6]张汉.无线传感网中基于负载均衡的EAMCT-G优化算法研究[D].郑州：郑州大学，2012.

[7]李彦君，钟求喜，陈诚，等.多核平台入侵检测系统负载均衡算法设计与实现[J].计算机应用研究，2012（4）：11-12.

LIYan-jun，ZHONG Qiu-xi，CHEN Cheng，etal.Load equalization algorithm design and implementation of multicore platform intrusion detection system [J].Computer Application，2012（4）：11-12.

[8]何达，吴明.Ada-BP神经网络改进算法在电力负荷预测中的应用研究[J].陕西电力,2012（12）：21-24.

HE Da，WU Ming.Probe into application of Ada-BP neural network improved algorithm in electric power load forecasting[J].Shaanxi Electric Power，2012（12）：21-24.