一种基于负载预测的动态负载均衡方法

一种基于负载预测的动态负载均衡方法

对于面向分布的实时系统，不同主机之间的动态排序和编程对系统的性能有很大影响，因此受到关注。各国研究人员对此进行了大量的研究，提出了一系列动态负载均衡算法。所有这些方法都从某方面改进了动态负载均衡，提高了分布式/并行系统的性能。但因为分布式/并行系统的任务在各结点动态分配生成，而各结点上的负载是不断变化的，以上各算法多是收集结点负载的旧值或大概估计值作为任务在各结点分配的依据，不仅精确度不够，更可能造成进程迁移的抖动，从而导致算法的实用效果并不甚理想。如果能够预先了解结点的负载变化，平衡系统在进行任务分配时就有提前量，这样可以避免因信息传递时延使决策信息过时而造成的某一任务在结点间来回迁移得不到执行的情况，减少了任务再分配的发生，从而使负载均衡的性能得到较大提高。基于这一思想，我们提出了一种动态的基于负载预测的均衡方法，给出了该方法的实现模型和相关算法，并进行了性能分析，最后得到了实验结果。1基于负载时间序列模型的负载预测美国的Dinda和O’Halloran在1997年和1998年分两次对39台DECAlphaDUX主机进行了长期跟踪抽样，获得了大量的负载图样（LoadTrace）。通过对负载图样进行统计分析，他们总结出了主机负载随时间变化有很强关联性的特性，由此Dinda和O’Halloran评估了多种线性时间序列模型应用于大型分布式系统中负载预测的效果，并以此建立了RPS(ResourcePredictionSystems）。按照RPS的思想，我们构建了HLPS(HostLoadPredictionSystem）模型，并在Linux工作站上用C++编译实现了HLPS模型，这为研究基于预测的动态负载均衡提供了较好的基础。2基于预测的动态负载平衡模型2.1负载均衡控制假定分布式/并行系统由p个结点组成，基于预测的动态负载均衡模型如图1。人为将所有结点分为n个组，每个组固定k个结点。为了限制调度的注意点，设定组间不进行信息交换和任务迁移。这时为了保证每个组获得相近的处理性能，避免较大的组间不均衡现象，在人为分组时尽量使每个组的k个结点在整体上具有相近的处理能力。若系统的结点数较少，就不需要对结点进行分组，系统模型从局部分布式变成了全局分布式。每个结点参加负载均衡的部分包括检测器(sensor)、预测机和调度机。检测器监测主机的负载状况(包括CPU队列长度、自由内存大小、磁盘可利用空间等),获得主机的平均负载量(AverageLoad)，并定期提交负载信号给预测机。预测机结构如图2。抽样器定期触发sensor，指示其提交负载信号；它收集sensor发来的负载信号，对负载信号进行量化抽样处理，生成标准可衡量的负载流，并对负载流进行缓冲。可衡量的负载流送到模型器，模型器载入预测模型模板库，选择合适的预测模型，生成预测器。预测器根据选定的时间间隔对负载流进行预测，产生预测流送入缓冲器和评估器。评估器对送入的预测流信号和负载流信号持续进行比较，并计算预测误差，若预测误差超过限定的标准误差，评估器产生Refit信号给预测器。预测器通知模型器对预测模型进行修正，并更新预测器。这种良好的反馈机制可以保证负载突变时较好的预测性能。预测信号经输出缓冲送往调度机，调度机对预测信号进行阈值判断并执行相应的调度操作。2.2基于响应信号的接收在选择调度驱动策略时，考虑一个原则：当系统中各结点都处于忙碌状态时，进行任务转移或进程迁移并不能在效率上带来好处；只要能使各结点处于忙碌状态，就能加快系统中应用程序的执行，获得较好的资源利用率。我们设计了改进型接收者驱动策略，它的基本思想是：当系统中某结点预测到自己将到达空闲状态，则向组内的所有其他成员广播任务请求信号。组内成员接收到请求信号后就记录该结点到接收者表。组内成员若预测自己将来是轻载或适载状态，则不予回应；若预测自己将达到重载状态，则发回响应信号给启动者。接收启动者收到响应信号后记录响应结点到发送者表，并从发送者表中按照任务通信量、结点间通信时间和待分配任务数计算任务转移的效益，选择效益最高的发送者结点发送任务迁移请求。接收启动者收到迁移的任务后，清除发送者表内容，并广播命令信号给组内成员，指示将其从接收者表中删除。若当接收启动者广播任务请求时，组内没有重载结点，接收启动者则保持等待状态，直到接收到响应信号。与传统的接收者驱动策略和其他相关算法策略相比，我们的改进型接收者驱动策略具有3个主要特点：(1)接收启动者发出的任务请求不是逐一传递给相邻结点，而是广播给组内所有的成员，这样既避免了系统初启或轻载时空闲结点对邻结点的反复打扰，更可以使均衡调度获得局部乃至全局最佳均衡点；(2)信息交换不是由负载状态变化驱动，而是由接收者驱动，即只有当系统中出现空闲结点和空闲结点接收到新任务时，空闲结点和系统中的重载结点才进行信息交换，这样大大减少了信息交换的频度和空间，减少了对结点的打扰；(3)在定位每次均衡调度的发送者时，我们计算了组内所有符合调度条件的结点，获得了组内最佳的均衡结点。3负载均衡调度该动态负载均衡算法主要包括两部分：预测算法和调度算法。预测机调用预测算法程序对sensor提交的负载信号进行预测，得到下一抽样时间的负载值；调度机根据该预测负载值启动调度算法程序进行均衡调度处理。每个结点通过设定双阈值Lmin和Lmax来判断自己的负载状态。当负载低于Lmin时，结点处于空闲状态成为接收者；当负载高于Lmax时，结点处于重载状态成为发送者；若处于两阈值之间，表明结点负载适中，不需要参与负载均衡。每个结点同时保存两张表：接收者表和发送者表，分别保存小组中所有接收者和发送者的状态信息，作为调度决策的依据。3.1预测器的预测值Step1预测机的抽样器定期向检测器发出负载抽样命令。检测器根据抽样允许标志判断是否输出。抽样周期T设定为系统任意两结点往返通信最小时间的2倍。Step2抽样器收到检测器提交的负载信号，对其进行量化抽样处理，获得抽样负载序列{Lt}t∈T。Step3抽样序列{Lt}送往模型器和评估器。(1)模型器经分析判断，从模型模板库中选取合适的预测模型，建立相应的预测器。预测器把抽样序列{Lt}放入其历史空间，调用预测模型算法，产生下一抽样时间的负载预测值Lp，送往评估器和输出缓冲。(2)评估器持续比较负载预测值Lp和负载抽样值Lt，计算预测误差errk(t)，k表示预测模型。若预测误差超过最大允许误差errmax，评估器发出修正（refit）信号给预测器，指示预测器修改预测模型，重新进行预测，跳到(1)；否则转Step1。Step4算法结束。抽样周期T是预测算法较难确定的因素。抽样周期越短，结点不均衡发现得越早，负载均衡实施得越快，但负载均衡的开销也越大。考虑到从接收者发出任务请求到接收到任务，接收者和发送者之间要经历2次“握手”过程，而接收者收到任务后应达到空闲状态，所以设定抽样周期T等于系统任意两结点往返通信最小时间的2倍，以简化算法的复杂度。预测模型目前采用了3种线性时间序列模型MR、AR、ARMR，以后可以增加ARIMA、ARFIMA以及神经网络BP、线性回归、模糊聚类等其他相关预测模型到模型模板库，以提高负载预测的广度和精度。3.2任务迁移响应面的记录与分析Step1系统初始化，所有结点的接收者表和发送者表均为null。Step2检查预测机的输出，判断预测负载值Lp。IfLp<Lmin结点空闲then启动接收者处理过程(1)发送任务请求信息包给组内所有其他成员，包括接收者地址Ra、请求的任务数量Jr;(2)向检测器发出停止负载抽样，置抽样允许标志为否；(3)系统转wait状态；(4)接收到响应信息包，包括发送者地址Sa、待分配任务数量Jw、待分配任务与已分配任务的通信量Cs，记录到发送者表数据结构中。计算信号往返时间T(r,s)并记录到发送者表；计算发送者表中所有发送者的发送效益指数(5)E=Jw/(Cs*T(r,s));(6)选择效益指数E最高的发送者返回任务迁移指令if收到迁移的任务then向所有组内成员发送删除该接收者指令，跳到(7)if收到删除发送者指令then从发送者表中删除该结点，选择效益指数E次高的发送者返回任务迁移指令，直到收到迁移的任务，否则按照从大到小的次序选择E对应的发送者返回任务迁移指令；如果没有可选择的发送者，则跳回(4)(7)清空发送者表；(8)启动负载抽样；(9)转Step2。ifLp>=Lmax结点重载then启动发送者处理过程(1)检查接收者表，若接收者表不空，跳到(3)；若接收者表空，等待任务请求；(2)收到任务请求信息包，将请求包中的接收者地址Ra、请求的任务数量Jr记录到接收者表中；(3)向接收者表中所有接收者发送响应信息包，包括Sa、Jw、Cs;then选择<Jr,Jw>min发送待分配任务，并向各接收者发送删除该发送者的指令，跳到(5)(5)转Step2。elseifLmin<=Lp<Lmax结点适载then转Step2。Step3算法结束。调度算法主要是一个循环判断处理过程，调度机根据预测负载值的大小启动相应的操作。在接收者处理过程中，接收者按照最佳原则选择发送者，而不是按照最近响应原则选择发送者，这是因为负载预测机制保证了最佳发送者的可靠性，因而获得了更高的均衡性能。4算法分析4.1通过高效的均衡调度决策信息增加了节点及接收者基于预测的局部分布式动态负载均衡算法最大的特点一是基于预测的方法获得负载信息，二是采取了改进型接收者驱动策略。另外，该算法还具有以下几个突出优点：(1)基于预测的方法获得负载信息，使均衡调度的决策信息有提前量，不仅可以减少空闲结点等待新任务的时间，加快重载结点的任务迁移，使每次均衡调度过程缩短；更重要的是大大减少了结点探询和任务重新转移的次数，降低了任务迁移的抖动性，从而提高了均衡系统的效率。实际上任务的重复分配是影响均衡代价的最大因素。(2)以空闲结点作为接收者驱动均衡调度，可以尽快使系统处于忙碌状态，使每个结点都有任务执行，获得较好的资源利用率。(3)接收者根据发送效益指数E选定最佳的发送者迁移任务，提高了均衡系统的性能。(4)负载信息交换只在接收者和发送者之间进行，降低了均衡系统的开销。4.2循环迭代的均衡我们用3台Linux工作站（Redhat7.3、P41.6GHz、512MBRAM、100MB网卡）组成了一个小型分布式网络，并行编程环境为PVM，采用典型的求质数例子。求质数程序的循环迭代相互独立，而且每个循环的执行时间不相同，比矩阵乘程序更能产生分布式计算不均衡的现象。我们比较了3种负载均衡下并行执行求质数程序的情况，分别是采用基于预测的均衡算法、文献的均衡算法、无负载均衡。图3是实验比较情况。实验结果显示，在数据规模不大的情况下，3种负载均衡方法的效果没有显著的差别，随着数据规模的增大，我们基于预测的负载均衡方法取得明显更好的效果，这是因为计算的规模愈大，负载均衡带来的额外开销相比愈小，性能优越的负载均衡算法可以获得满意的均衡效果。5负载均衡研究的展望如何提高动态负载均衡的性能，