一种INSS动态反馈负载均衡算法

摘要： 负载均衡策略是智能网络存储系统(INSS)的关键性技术之一。本文介绍了智能网络存储系统的存储结构，提出了一种新的负载均衡算法。该算法采用周期动态反馈原理，以节点的最小化负载方差为目标，动态调整节点分配权值，最后引入随机概率的转发模式。在实验室搭建的系统平台上，对该算法以及WRR和WLC两种负载均衡算法进行了对比测试，试验结果表明该算法性能更优。

关键词： 智能网络存储系统；负载均衡算法；随机概率转发

中图分类号：TP392 文献标识码：A文章编号：1006-4311（2012）04-0149-030引言

随着Internet应用的不断增长，信息社会也发生了重大的改变。早期的“以计算机为中心”的数据处理已经演化为“以数据为中心”的模式。信息需求使得存储容量的增长速度超过了服务器处理能力的增长速度，网络存储技术应运而生。目前经典的存储技术有NAS和SAN[1]，但是这两种网络存储体系结构存在一些问题：NAS的集中式“瘦文件服务器”结构容易产生单点故障失效问题，而SAN一般需要专门的光纤交换机设备和光接口的存储器，是一种成本较高的网络存储方案[2]。

针对目前网络存储中存在的不足之处，我们提出了一种新的网络存储系统——智能网络存储系统INSS（Intelligent Network Storage System）。智能存储系统具有一定的自组织性和自管理性，能够满足异构系统互操作性，存储容量在线扩展，负载均衡，并发性，可用性，可靠性，安全性等一系列目前主流网络存储系统中的需求，实现用户处理数据的高效性，同时降低管理人员对存储系统管理的难度。

对于INSS来说，节点的负载过重或过轻，在很大程度影响着INSS的效率。因此，需要一个良好的负载均衡算法。它的主要工作是将请求任务合理的分担到多个节点设备上分别处理，提高系统的总体性能，减少用户等待响应的时间。目前负载均衡算法包括两大类[3]：①静态负载均衡算法如转轮调度算法（RR）、加权轮转调度算法（WRR）等，只是根据预先设定的分配方案对用户的请求进行分配，因此算法简单，使用方便，但是自适应性和并行性较差；②动态负载均衡算法是根据各个服务器运行时刻的负载情况，按照某种算法将用户请求分配给当前负载最小的服务器，如最小连接调度算法（LC）、加权最小连接调度算法（WLC）等。与静态算法比较，动态算法更加灵活、高效，但是它必须收集节点负载信息，因此需要额外的系统开销。然而，这种开销常常可以被提高的计算机效率所抵消掉。因此动态负载均衡算法成为目前研究的重点。

本文提出的一种新的动态反馈负载均衡算法（INSSDI Intelligent Network Storage System Dynamic Feedback），算法流程相对简单，不仅考虑了各节点的当前负载和实际处理能力，而且设置了临界深度来抑制节点进入饱和状态，最后引入了随机概率的转发模式。

1智能网络存储系统和负载均衡模型

1.1 智能网络存储系统结构智能网络存储系统INSS是在SAN的基础上，引入重复数据删除技术，虚拟存储技术，并行化技术，以及智能化技术使设计的网络存储系统达到海量、高性能、高可靠、安全、智能化的要求。系统的整体框架如图1所示，主要由智能客户端IC（Intelligent Client），传输网络（LAN/WAN/SAN），并行化服务器PMS（Parallel Metadata Server），智能存储节点ISN（Intelligent Storage Node）四部分组成。其工作原理：客户端层发出请求，主机层解析其请求，通过网络层的调度，存储层某些节点响应本次请求。

在INSS中请求都是数据文件的读取或写入，如果客户层需要读取某一数据文件只需存储该数据文件的一些节点响应其读取请求即可。当有数据文件写入请求时，由于引入了并行化技术，数据文件在写入时先在主机层按照固定的切割方式被分割成大小相等的数据块，然后由网络层通过负载均衡调度方式，选择某些合适的节点响应这些数据块的写入请求。在这里，我们将客户端的一个写入请求称为一个大任务，而将分割后的一个数据块的写入请求称之为一个请求任务，因此这里所有的请求任务量均相等。

1.2 智能网络存储系统负载均衡模型根据图1的智能网络存储结构建立了相应的负载均衡模型，如图2所示。模型中的主要模块是位于网络层的负载均衡调度器，它主要工作是：周期性地监测并收集存储层中各个节点的负载信息，根据当前周期T内各节点的负载信息按照负载均衡策略将请求任务分发给存储层中的节点。

2负载均衡算法

2.1 负载权值由于系统中节点的异构性，同一个请求任务分配到不同的节点所产生的负载有较大的差异。因此，如何准确地评估节点上的工作负载成为负载均衡算法首先需要解决的问题。而对一个节点的处理能力和实际负载的准确量化需要考虑多种指标参数，例如CPU、内存、网络等因素。因此本文考虑如下的指标参数来计算节点的实际负载信息：CPU使用率Ci，内存使用率Mi，磁盘利用率Di，磁盘状况Si={0，1}，网络状态Ni={0，1}。而且，我们引入一组系数λc、λm、λd来表示各个负载参数的权重，其中λc+λm+λd=1。故节点的实际负载可以通过以下公式进行量化：

li=（λc、λm、λd）CiMiDi*Ni*Siλc+λm+λd=1（1）

我们通过对负载均衡调度器收集的负载信息对系数λc、λm、λd进行测试和修正，将λc、λm、λd的固定为0.4，0.4，0.2。由于周期性地收集和处理负载信息，负载均衡调度器开销较大大，所以我们一般将周期间隔设置为5~10s之间。

2.2 算法思想设智能网络存储系统有n个节点，其中节点Si（i=1，2，…，n），根据负载均衡调度器器监测的指标参数，由（1）可以得到节点的综合负载为li，由于各节点需要支持自身系统，消耗了一定负载L■■，因此我们将L■■称为基本负载，而将L■■=li-L■■定义为节点的有效负载，即由节点执行请求任务所产生的实际负载。

当系统达到负载均衡时，所有节点的有效负载应相对均衡，使方差?滓＝■最小。显而易见min（?滓）=0，有L■■=L■■=…=L■■=■。当然这只是极理想的情况，可以引入一个的偏差量?酌，我们可考虑以下情况：

■-L■■?燮?酌i=1，2，…，n （2）

故有?啄?燮?酌，节点的有效负载分布在特定区域内，而且这个区域由偏差量?酌决定。这时可以认为系统达到了负载均衡状态。因此，我们利用负载均衡器监测到当前周期节点的负载信息计算出有效负载，通过调整各节点的有效负载使其满足（2）式，而将调整值作为分配权值，这样可以根据节点应分配与之能力相匹配负载的原则，对负载高的节点减少分配给它的请求任务，对负载低的节点增加分配给它的请求任务。

2.3 分配权值分配权值如何确定是整个算法的关键，即怎样确定上述负载均衡原理中的调节值使其满足（2）式。首先对其中某个节点进行实际测试，其测试结果如图3所示。