Vol.34 No.4 Computer Engineering ·博士论文·
文章编号：1000—3428(2008)04—0051—03
文献标识码：A
2008年2月
February 2008
中图分类号：TP393
一种分布式数据流系统负载平衡算法
王金栋1，戎晓霞2，丁秋林3
(1. 山东省计算中心，济南 250014；2. 山东大学数学与系统科学学院，济南 250100；
3. 南京航空航天大学信息科学与技术学院，南京 210016)
摘 要：分布式数据流系统中，当输入数据流速发生较大波动时，会引起部分节点过载，从而影响整个系统的数据处理能力。针对这个问题，该文分析了分布式数据流系统的特点以及现有负载平衡算法的局限性，提出了一种利用多层重叠结构进行负载信息收集和负载分配的平衡算法。该算法利用虚拟树形结构进行负载信息的收集和负载分配，具有较好的扩展性能。以环形虚拟结构中保存的节点相对位置信息为依据进行负载移动，从而有效降低系统的响应时间。实验结果表明该算法具有良好的负载平衡能力和一定的应用价值。 关键词：数据流；数据流系统；负载平衡；重叠网络
Load-balancing Algorithm for Distributed Data
Stream Management Systems
WANG Jin-dong1, RONG Xiao-xia2, DING Qiu-lin3
(1. Shandong Computer Science Center, Jinan 250014; 2. School of Mathematics and System Sciences, Shandong University, Jinan 250100;
3. College of Information Science & Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016)
【Abstract】In distributed data stream processing systems, part nodes overload caused by input data stream fluctuation may reduce data processingability of the whole system. Aiming at the practical problem, based on the characteristics of distributed data stream processing system andshortcomings of existing load-balancing methods, a multi-layer overlay based load balancing algorithm is proposed. Multi-layer overlay structure isused to collect load information of the system and redistribute load among node. Numerical experiment shows the well load-balancing ability andpracticability of the algorithm.
【Key words】data stream; data stream management system; load balance; overlay network
分布式数据流系统难以预测各节点的负载情况，并且初始化时，元操作在节点中的随机分布可能导致节点间负载差别较大。随着系统的运行，这种不平衡将迅速加剧。目前关于分布式数据流系统负载平衡问题的研究已取得了一些成果。文献[1]提出了契约方法，其契约是静态建立的，难以适应数据流系统的动态负载变化。文献[2]给出的方法需要通过中心节点收集负载信息，来确定各节点的目标负载。典型的分布式数据流系统[3]，都建立在以DHT表为基础的重叠网络上，无中心节点，节点可以自由地插入和离开。文献[2]中算法难以满足这类系统扩展性的要求。另外，该算法假设所有节点间通信不受带宽限制，而在实际环境下，这种情况很少。针对上述问题，本文对文献[2]中的方法进行扩展，提出了基于多层重叠结构的负载平衡算法。 示。下文用D(VN(i))表示T时间内节点Ni的负载波动情况，用ρ(v(i),v(j))表示Oi和Oj的负载变化趋势，ρ(VN(i)),VN(j))表由相关试验[2]知：示Ni和Nj的负载变化趋势。∑ρ(v(i),v(j))的减小必然引起∑ρ(VN(i)),VN(j))的增大。基于以上分析，本文负载平衡的目标可如下描述： 设系统中共有n个节点，E(VN(i))表示节点Ni负载的平均值。L表示系统的平均负载。通过负载平衡算法，希望得到如下目标： E(VN(1))≈E(VN(2))≈\"≈E(VN(n))≈L (1) max(∑ρ(VN(i)),VN(j))) (2) 1≤i 本文以chord模型[4]为例研究分布式数据流系统负载平衡问题。算法分两步：负载信息的搜集，负载的分配。 2.1 负载信息的搜集 本文采用文献[4-5]的虚拟服务器思想，在重叠网络的基础上建立一层k叉树虚拟结构收集负载信息。 k叉树的每一个节点驻留在重叠网络中的一个节点上，本文称k叉树节点为T_nd(虚拟节点)，称重叠网络中的节点基金项目：国家部委基金资助项目 作者简介：王金栋(1973－)，男，博士研究生，主研方向：数据流处理，重叠网络；戎晓霞，博士；丁秋林，教授、博士生导师 收稿日期：2007-02-28 E-mail：jind_w@163.com 2 负载平衡算法 根据概率论有关理论可知：负载波动情况可用负载向量的方差来描述，两个负载向量的变化趋势可用其相关系数表 —51— 为H_nd(物理设备)。每个非叶子T_nd可以拥有k个子孙(k≥2)。T_nd使用如下数据结构保存相关信息： Struct T_nd{ ID; Region; Level; Struct T_nd *children[1..k]; Struct T_nd *parents;} H_nd以L为其目标负载。 2.2 负载分配 本算法将负载分配分解为3个步骤：确定节点的相对位置；选择元操作；移动元操作。 2.2.1 相对位置的确定 根据文献[6]可知，网络中节点间的距离可由每个节点到多个固定节点间的数据传输延迟体现。在底层重叠网络中选定n个地址，这n个地址将整个地址空间分为n等份，管理这n个地址的节点本文称为为界点。设节点Ni到这些界点间的数据传输延迟分别为(li1,li2,…,lin)，本文称为延迟向量。如果3个节点有∑(l2i−l1i)2<∑(l3i−l1i)2，则说明节点N1与i=1i=1nnID为T_nd的地址，其取值范围与H_nd地址空间相同(本文中的“地址空间”指H_nd在重叠网络中的地址空间，本文后面所用的“地址”都表示重叠网络中的地址)。重叠网络T_nd的移动与重叠网络中含有地址的非节中有节点进出时，点元素移动方式相同，但T_nd并不与它们在同一个空间中分配地址。Region指明该T_nd所管理的地址范围。根节点管理整个地址空间，非叶子节点将其所管理的地址空间平均分为k份，每份由相应的子孙节点管理。Level表明节点所在的深度，根节点的深度为0，每延伸一层，Level的值加1。 建立初期，网络中只有一个节点——k叉树的根节点。该节点将重叠网络的中心地址作为其地址。k叉树节点随着重叠网络中节点的增加而增加，每个H_nd上可存在一个或多个T_nd。每隔一段时间，节点会针对每个T_nd运行检测程序。如是否需要生成或删除子孙节点。设某T_nd管理的地址范围为T_Region，其驻留H_nd管理的地址范围是H_Region，如果T_Region⊆H_Region则认为该T_nd为叶子节点，不需要增加子孙。否则通过检测程序生成子孙节点。检测程序的伪代码如下： T_TEST(T_nd X) (1) {if ((X= =NULL)&&(这是唯一节点)) (2) { CREAT_ROOT(); return; } (3) H=GET_HOST(); (4) if (X.Region⊆H.Region) (5) { if (X是叶子) return; (6) else DELETE_ND(X); return; } (7) for (j=1;j<=k;j++) (8) { if ((X.children[j]= =NULL) && (X.j_space ADD_ND(T_nd X, j);} } H.Region)) N2距离比较近；N1与N3距离比较远。 本文将节点的负载设为3种状态以降低节点间通信量：高负载，低负载，中间状态。设置一个参数ε，当节点 j的负载Lj满足Lj≥L+ε时，认为其处于高负载状态，可以向其他节点移出负载；如果Lj满足Lj≤L−ε，则认为其处于低负载状态，可以接收其他节点移出的负载；其他情况为中间状态。中间状态节点不需要进行负载移动。 2.2.2 元操作选择 设高负载节点中有n个元操作需保留。E(v(i))表示Oi负载向量的平均值，则n个元操作要满足如下要求： (1)∑E(v(i))≈L； i=1n (2)1≤i 对于此NP完全问题[2]，本文设计了一个贪婪算法求其近似最优解。设节点中共有n个元操作，v=∑v(i)−v(j)，相关i=1 系数ρ(v(j),v)表示元操作Oj与节点上其他所有元操作负载变化的相似程度，该数值若变大，则需要移出元操作Oj。相关伪代码如下： O_SELECTION() (1) { L=0; (2) while (L 其中，Oi_address为元操作Oi在重叠网络中的地址。 2.2.3 元操作移动 由2.2.1节可知，物理连接中临近节点间负载分配问题，可看作如何在超立方体中临近节点间分配负载的问题。 本文提出了一种虚拟环形映射方法：将n维超立方体中的节点按照其坐标映射到一个环形结构中，要求在超立方体中临近的节点映射到环形结构中也处于地址临近的位置。 本文将这样一个虚拟环形结构映射到底层的Chord结构中，虚拟环形节点的插入、删除等操作直接由底层完成。虚拟环形结构的地址采用底层Chord结构的地址。 由文献[7]可知， Hilbert曲线能够最好地保持空间点的局部邻接特性。本算法用Hilbert曲线贯穿所有节点，将其映射成一个虚拟环形结构，以Chord结构地址作为Hilbert曲线编号，利用2.1节中的树形结构进行元操作的移动。通过规范化处理将k基n维的超立方体坐标映射成地址空间为(2m)n的重叠网络地址，其中2m≥k。本算法中称这个地址为real_address。 Counti=∑Countc(j)，Countc(j)表示T_nd i第j个子孙向其汇报j=1 k 的节点计数信息。叶子节点不进行负载信息汇总，只向其父母节点汇报其所驻留H_nd的负载即可。H_nd根据T_nd的Level值，选择一个距离根节点最近的叶子节点汇报其负载，并设Count=1。假设系统中有n个节点，所有负载信息汇总到根节点后，根节点根据L=∑Lc(j)Count计算出整个系统的j=1k 平均负载，然后以从上往下的方式传播给每个节点。每个 —52— 高负载节点将要移出元操作组成如下结构发出负载分配信息(LDI)，其中Host_address为该H_nd在重叠网络中的地址，Ch表示该节点CPU的处理速度： Cl=∆L′，并且∆L′是不大于∆L的最大值，则匹配成Ch 负载波动率0.50.40.30.20.10.013579111315171921时间/s 图1 负载波动率随时间的变化情况 设节点j要移动的负载率为lj，则100个节点移动的负载率为∑li100。图2显示了负载移动率随时间的变化情况。 i=1100 LOAD_SCAN (T_nd X) (1) { H_list=NULL (2) L_list=NULL (3) if ( X是叶子节点) (4) { H=GET_HOST() (5) 将H的LDI保存到L_list或H_list;} (6) else (7) {X.children的LDI存放到L_list 或H_list;} (8) if ((L_list.size+H_list.size)>δ) (9) { MATCH_INF(L_list, H_list);} (10) else (11) {将H_list和L_list向X.parents汇报;}} 负载移动率/(%)功，向相应节点发出信息进行负载移动并删除高负载列表中的相应信息。如果∆L−∆L′>δ(δ是一个给定值)，则修改低负载列表中信息<∆L, Host_address, Cl>为<∆L−∆L′, Host_address, Cl>，否则删除低负载列表中的相应信息。列表中无法匹配的信息直接发送给父母节点。算法伪代码如下： 随机负载平衡算法本算法90807060504030201001357文献[4]算法91113151719时间/s 图2 负载移动率随时间的变化情况 图3显示了延迟时间随算法运行的变化。图4说明了延迟时间同负载间的关系。 随机负载平衡算法本算法10产生相应结果的时间/s文献[4]算法H_list为高负载信息列表，L_list为低负载信息列表。MATCH_INF()函数用于LDI信息的匹配，并将无法匹配的信息向父母节点汇报。当LDI匹配成功，2个节点进行负载移动时，相应的元操作在重叠网络中执行一次离开和插入操作，然后，重新定向该元操作的输入输出数据即可。 8642013579111315171921数据流入系统时间/s3 数值试验 在某研究所的Intranet上进行模拟试验，并与随机负载平衡算法[8]以及文献[2]给出的算法进行了比较。 实验选取100个节点，分为10个子网，每个子网通过一个数据转发装置与Intranet相连，通过调整转发装置的数据转发率来控制子网间的数据传输速度。以Chord模型建立底层结构，建立一个k=8的树形结构收集和传播负载信息。规定每个元操作的选择率及处理能力在系统运行中是固定不 变的。 通过调整数据源的发送速度来调整系统的负载。数据源的活动分为两个阶段：工作阶段和空闲阶段。工作阶段中，数据源以高、低两种速度向系统发送数据；空闲阶段则没有数据发送。两个阶段的变化满足指数分布。 测试了系统负载80%时，负载波动率、移动率和响应时间随时间的变化情况；以及负载波动率与平均负载的关系。 设节点j的负载向量为xj，Xj=E(xj)表示该节点平均 图3 延迟随时间的变化情况 本算法76延迟时间/s文献[4]算法随机负载平衡算法5432100.00.20.40.60.8平均负载图4 延迟时间与平均负载的关系 (下转第59页) —53— 型转换规则，则要定制类型转换规则。当源数据库结构及数据迁移到目标数据库后，根据源数据库中的表间关系，建立目标数据库表间关系。 数据迁移过程以从Oracle迁移到SQLServer为例：(1)创建表模块，通过调用数据转换规则库，创建与源数据类型相兼容的目标数据库，包括系统表、表间关系和数据表。(2)加载Oracle JDBC驱动的Query object 对象，通过SQL 语句 SELECT * FROM SCHEMANAME.TABLE 读取数据库结果集。(3)取出一条记录，将结果集中每条记录由RESULTSET.GET××()得到非字符串字段值x，再将这个值转由××.toString()完成，得到字符串y。换成JDBC类型字符串，(4)将y经过转义模块过滤后，加到INSER SQL语句中，形成新的SQL语句 INSERT INTO SCHEMANAME.TABLE VALUES(*,*,*)。(5)由已加载SQLServer JDBC驱动的Query object存储到目标数据库中去。 实现整体迁移，必须在目标数据库中建立与源数据库中表结构相同的表，才能将源表中的数据迁移到目标表中[2]。部分迁移则需要选择数据库，系统访问数据库读取元数据信息，如读取表名、读取字段名等，表和字段等元信息发送到用户界面由用户选择，根据选择的表和字段，经过数据转换规则的有效性检测，就可以用整体迁移类似的方法进行。 2.5 断点续传 在异构数据库迁移过程中，难免出现死机、停电、网络中断等内在和外在的原因，因而需要断点续传性能支持。数据库迁移的断点续传不同于文件传输的断点续传。文件传输以字节为元操作，它的续传可以从每个字节重新传输，而异构数据库迁移以记录为元操作，它的续传是从每个记录开始的，断开也是以记录为单位，实现代码如下： if (record_counts != 0) { for (int i = 1; i <= record_counts; i++) { source_rs.next(); }} 选用医院管理系统应用的HISSYS6.0数据库中的数据。该数据库的数据量大，数据类型丰富，如果能将HISSYS6.0数据库迁移到另一种DBMS 中，就能证明系统是成功的。HISSYS6.0系统的DBMS是SQL Server 2000，即源数据库，ORACLE与SQL Server 2000能够充分体现不同DBMS的异构性，因此，选择ORACLE8i作为目标数据库。以部分迁移作为应用实例：用户在操作界面上根据迁移之前创建的数据库、数据库表、数据库的表间关系及存储过程等，选择源和目标数据库，然后根据用户需求选择相应的数据库表以及所选表中的数据字段，提交以后就可以实现数据的部分迁移，源表中的数据成功迁移到目标数据表中。 通过项目实例，说明分布式异构数据库迁移系统具有较好的可行性和效率，系统的功能在应用中能够很好的实现，具有很高的实用价值。 4 结束语 分布式异构数据库迁移系统基于B/S模式，可利用网络中的任何终端对网络中的任何数据库进行操作，具有很高的实用价值。整个系统的功能相对强大和完善，能够满足应用需求。该系统已经应用于多个相关项目中，取得了很好的应用效果和经济效益。随着数据库技术、XML技术、网络的不断发展，该系统也将逐步趋于完善。 参考文献 [1] 分布式数据库概述[EB/OL]. (2005-08-03). http://fineboy,cnblogs. com/archive/ 2005/08/03/206395.html. [2] 孔祥疆. 软件开发方法与建立异构数据库使用平台模型[D]. 乌 鲁木齐: 中国科学院新疆理化技术研究所, 2005. [3] 梁陈剑, 张 威. JDBC3.0数据库开发与设计[M]. 北京：北京希 望电子出版社, 2003. [4] 罗林球, 孔祥疆, 李 晓. 基于CORBA/数据字典/JDBC的异构 数据库检索系统实现[J]. 计算机应用, 2006, 26(6): 91-94. [5] Snakebin. SQL数据类型详解[EB/OL]. (2005-07- 09). http://snakebin. bokee.com/ 2217273.html. 3 应用实例 在测试数据库迁移时，为了充分体现测试数据的异构性，(上接第53页) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Distributed Stream Processing[C]//Proc. of CIDR’03. Asilomar, CA: [s. n.], 2003: 257-268. [4] Stoica I, Morris R, Liben-Nowell D. Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications[J].IEEE/ACM Transactions on Networking, 2003, 11(1): 17-32. [5] Zhang Zheng, Shi Shuming, Zhu Jing. SOMO: Self-organized Metadata Overlay for Resource Management in P2P DHT[C]//Proc. of IPTPS’03. Berkeley, CA, USA: [s. n.], 2003: 170-182. [6] Ratnasamy S, Handley M, Karp R M, et al. Topologically-aware Overlay Construction and Server Selection[C]//Proc. of IEEE INFOCOM’02. [S. l.]: IEEE Press, 2002: 1190-1199. [7] Gotsman C, Lindenbaum M. On Themetric Properties of Discrete Space-filling Curves[J]. IEEE Trans. on Image Processing, 1996, 5(4): 794-797. [8] Harchol-Balter M, Crovella M E, Murta C D. On Choosing a Task Assignment Policy for a Distributed Server System[J]. Journal of Parallel and Distributed Computing, 1999, 59(2): 204-228. 4 结束语 从实验结果可以看出，该算法具有较好的负载平衡能力，而且通过选择临近节点进行负载移动，大大降低了系统的响应时间。从第2节的描述中还可以看出，该算法具有较好的扩展性，并且能够适应于不同处理能力计算机组成分布式数据流系统的环境。因此，该算法能适应实际应用中建立在DHT为基础重叠网络上的分布式数据流系统对扩展性的要求，已在某研究所数字化工程项目支撑环境中得到初步应用。 参考文献 [1] Balazinska M, Balakrishnan H, Stonebraker M. Contract-based Load Management in Federated Distributed Systems[C]//Proc. of NSDI’04. San Francisco: [s. n.], 2004: 197-210. [2] Ying Xing, Zdonik S, Hwang J H. Dynamic Load Distribution in the Borealis Stream Processor[C]//Proc. of ICDE’05. Tokyo, Japan: [s. n.], 2005: 791-802. [3] Cherniack M, Balakrishna H, Balazinska M, et al. Scalable —59— 因篇幅问题不能全部显示，请点此查看更多更全内容