3 ) 国家自然科学基金项目(60073045) 资助;国家“十五”国防预研基金项目(413150403) 资助。邓华锋邓华锋 博士研究生,主要研究方向为现代数据库技术和流数据算法。计算机科学2007Vol134 17分布式数据流处理系统的动态负载平衡技术分布式数据流处理系统的动态负载平衡技术3 )邓华锋邓华锋1 刘云生刘云生1 肖迎元肖迎元2(华中科技大学计算机学院 武汉430074) 1 (天津理工大学计算机科学与工程系 天津 300191) 2摘摘 要要 设计了一种新的大规模分布式数据流处理系统的体系结构。系统由一组异构的服务器集群组成,负载在每个服务器集群内部多台同构的服务器之间获得平衡,从而达到整个系统的负载平衡。集群设计的主要目标之一是以资源换性能,服务器集群中服务器的最大数目足够保证系统不再发生过载现象,不再需要会降低性能的卸载技术。而且投入运行的服务器的数目根据实际的系统负载来决定,负载较轻时,一部分服务器可以进入休眠状态来减少能源的消耗。根据系统动态增减服务器的特点,设计了全新的初始化算法、动态负载平衡算法。与以前的分布式数据流处理系统相比,由于单个集群的服务器的数目大大减少,算法复杂性降低、速度加快、优化的空间增大。关键词关键词 分布式数据处理流系统,动态负载平衡,卸载,节能Dynamic Load Balancing Techniques for the Distributed Stream Processing SystemsDENG Hua2Feng1 L IU Yun2Sheng1 XIAO Ying2Yuan2(School of Computer Science and Technology ,Huazhong University of Science and Technology ,Wuhan 430074) 1(Department of Computer Science and Engineering , Tianjin University of Technology , Tianjin 300191) 2Abstract In the novel architecture for the large2scale dist ributed st ream processing system , the whole system consist sof a group of heterogeneous computer clusters. The whole system can achieve the global load balancing by balancing ev2ery cluster which consist s of several homogeneous servers. The main goal of every cluster is exchanging the resourcesfor the performance. In the cluster , enough servers are employed to get rid of the occurrence of overload phenomenon ,so techniques for load shedding are not still necessary in the system. In the meanwhile , the number of active servers isdecided by the practical load level and some servers can be put into the sleep mode for the sake of energy conservationwhen the load is rather low. The band2new initialization algorithm and dynamic load balancing algorithm are designed toaccommodate the characteristic of increasing or decreasing the servers dynamically. Comparing to the t raditional large2scale st ream systems , these algorithms have better load balancing , lower complexity and faster response time becausethe number of servers in a single cluster is reduced sharply.Keywords Dist ributed st ream processing system , Dynamic load balancing , Load shedding , Energy conservation1 引言引言数据流处理系统广泛应用在众多领域,例如金融管理、网络监视、通信数据管理、Web 应用、传感器网络数据处理等。这些应用中有一个典型的特点:数据流数据量极大,具有相当高的突发性1 ;当数据到达的速度超出系统的处理能力时,系统会出现过载并且性能下降。所以,无论是集中式数据流处理系统,还是分布式数据流处理系统,负载管理均成为研究的热点与重点1 ,2 。在网络和多媒体研究领域,对负载管理问题的研究,与数据流的负载管理有许多相似之处, 但存在着本质上的区别1 ,3 。对集中式数据流处理系统的负载管理提出的解决办法是局部算子或整个系统的卸载35 。采用这种方法,检测到系统发生超载时,选择性地丢掉一些元组来保证系统的运行。这种方法的缺点是显而易见的,尽管在丢弃元组的时候要考虑系统的质量要求,但是显然系统的性能不可避免地会受到影响。由于流数据源及应用本身存在分布的特点,分布式流处理系统成为流处理研究的热点1 ,8 。在分布式流处理系统中,研究集中在如何将负载均衡地分布到各个服务器并保持系统的负载动态平衡。文 7 研究了在进行分布式流处理系统卸载时,如何协调各个服务器结点,获取全局最优。文9 提出一种分布式联邦流处理系统动态负载平衡算法,系统中各结点只在有协议的邻居之间平衡负载,并不寻求全局最优。文2 中,流处理功能被封装成一项项服务,负载平衡考虑的是从能够提供服务的服务器中挑选合适的一组来处理每个动态提交的应用,主要用于多媒体流数据的分发与处理。文6 对动态负载平衡进行了初步的探讨,相邻的算子尽量分布在同一服务器,以减少网络数据传输。以上的分布式流处理系统要求系统的各个结点是同构的,因为异构的系统之间迁移算子往往特别困难,甚至是不可能的。这些系统能消化的负载也相当有限,在应用中,往往清闲的时候所有服务器清闲,过载的时候所有服务器过载。在处理器等硬件越来越便宜的今天,越来越多地通过增加服务器组成集群的方法出现在网络和多媒体领域。在分布式流处理领域,文1 提出一种利用服务器集群处理负载过载问题的新方案。在该方案中,流数据的处理由一组由高速网120 络互连的无共享的同构服务器来共同承担。由于系统的复杂性,负载的近似平衡由一组贪婪算法来保证,算法同时还尽可能地保持系统的负载的变化最小。但是在大规模流数据处理的情况下,由于系统结构和算法的复杂性,平衡能力依然有限,只能避免过载现象的发生,而不能完全消除它的发生。而且该方法过于理想,实现的算法并不能应用于实际的分布式系统。如系统假定所有服务器之间通过高速网络连接、服务器之间传输数据忽略不计、服务器是同构的等。这些条件,实际的系统很难满足。在以上研究的基础上,我们提出了一种系统的新方案来解决以上提出的种种问题。在我们的分布式流处理系统中,一组异构服务器集群以对等的方式工作,每个服务器集群处理一个子领域的流数据,集群之间可以合作完成查询,但是流数据处理负载不在服务器集群之间迁移。每个服务器集群由多个同构的服务器组成,在_将要出现过载的时候,集群可以激活备用服务器。只要服务器数目足够,系统就不会过载,不再需要会降低性能的卸载技术;而在系统负载很轻时,可以让一些服务器进入“睡眠”模式。这样,既保证了服务质量,又避免了资源的浪费。考虑到各个子领域的负载不一致,各个集群最大服务器数目也可以不一样。这样,分布式系统的负载平衡问题就转变为单个服务器集群服务器负载平衡问题。所以,本文的研究成果也可以应用到集中式流数据处理系统。在整个分布式流数据处理系统分成若干个子领域后,每个领域的服务器集群服务器数目大大减少,降低了负载平衡算法研究的复杂性,为研究最优算法或更好的近似算法提供了可能,从而进一步提高了系统性能。2 问题的描述问题的描述2. 1 系统模型系统模型我们的分布式流处理系统由一组以P2P 方式合作的服务器集群组成。每个集群中服务器数目不等,但是构成与工作原理相同。这样,我们研究的重心就集中在单个服务器集群上。单个服务器集群系统模型如图1 所示。在采用服务器时,我们采用的是同构服务器。所有的同构服务器(CPU 、内存、流处理引擎等一样) 通过高速局域网互连,所以不再考虑网络的带宽的限制。在系统开始运行时,根据系统的负载,计算需要的服务器数目,从中任意挑选一台服务器作为调度服务器。各个服务器定期负责向调度服务器报告自己的负载情况。图1 集群的体系结构调度服务器在系统负载较轻的时候,负责全部流数据的处理与负载监控、负载预测;在负载超过一定阈值时,启动新的服务器,迁移一部分负载,并将工作中心转移到负载监控与数据流和查询的转发工作,减少其进行流数据处理的负载。当系统负载不均衡但可以在系统内平衡时,调用系统动态负载平衡算法,得出系统的最优调整方案,组织负载的迁移。当负载过轻时,调度服务器决定系统的最优负载调整方案,组织负载的迁移,减少服务器的数目。其他的工作服务器只负责流数据的处理与输出数据的转发。2. 2 负载的计算负载的计算流处理系统的查询网络由一系列流算子组成无循环的流水线形式。由于集群中所有的同构服务器通过高速局域网互连,网络带宽不再作为受限制的资源,只考虑CPU 的占用。我们把处理的时间分成定长的时间片段( T0 , T1 , T2 , ) ,算子的负载为其处理在每一个时间片段内到达的元组需要的CPU 时间。我们并不把统计得到的算子的负载作为计算的依据,而是作为使用一些预测技术(灰色预测、指数平滑、移动平均等) 来估计将来一段时间的负载的依据。根据若干时间片段的算子的实际负载,通过采用预测技术得到K 个预测值,记为L1 , L2 , , L K 。定义定义1 (算子计算负载) 算子Oi 的计算负载等于以上K 个预测值的最大值,记为L (Oi ) 。L (Oi ) = MAX L1 , L2 , , L K| 1 i K (1)取最大值的原因是因为负载经常波动。要保证在任何负载的情况下,都不允许系统过载。定义定义2 (工作服务器的实际负载) 工作服务器Si 的实际负载等于服务器的空荷负载( L E) 加上工作服务器上所有算子的负载之和,记为L R( Si ) 。服务器的空荷负载是指服务器启动就绪,准备处理流数据前所承担的负荷,也就是运行操作系统、流处理引擎等所要消耗的CPU 时间。L R( Si ) = L E( S i ) + Mj = 1 L (Oj ) (2)定义定义3 (服务器最大工作能力) 服务器最大工作能力是指一段时间内服务器能够提供服务的时间长度,记为P( S i ) 。定义定义4 (调度服务器的负载) 调度服务器的负载等于服务器的空荷负载、所有算子的负载、接收用户请求的负载( L A) 、接收与转发流数据的负载( L D) 、运行平衡算法的负载( L