QFMA一种支持负载均衡的多属性资源定位方法

1、刘德辉等QFMA: 种支持负载均衡的多属性资源定位方法#QFMA: 种支持负载均衡的多属性资源定位方法刘德辉1周宁2尹刚1王怀民1邹鹏11 (国防科技大学计算机学院 湖南长沙410073)2 (中国电子工程系统研究所北京100141)摘要：P2P技术是实现SOA去中心化的有效方法.在基于元数据的P2P系统中，描述资源属性的关键字分布和访问 的不均匀性使某些元数据存储节点极易成为负载热点，严重影响了系统可用性.在MAAN基础上给岀了一种支持负载均衡的多属性资源定位方法QFMA,将过载节点状态反馈到查询路径上，后续查询将根据反馈信息进行查询目标切换.分析和试验表明 QFMA以O(logN)的路径长

2、度实现资源的高效定位，并能够通过负载分流，有效缓解“热门”节点的负担，提高系统的负载均衡特性.关键词：SOC; SOA; P2P; QFMA;负载均衡；热点QFMA: An Approach for Multi-attribute Resource Addressing withLoad Balancing1 2 1 1 1Liu De-Hui Zhou Ning Yin Gang Wang Huai-Min Zou Peng1 (School of Computer Science, National University of Defense Technology, Hunan Chang

3、sha, China, 410073)2 (China Institute of Electronic System Engineering, Beijing China, 100141)Abstract It is an effective way to make SOA uncentralized with P2P. In meta-data based p2p system, hot spot may result due to non-uniform of keyword ' distribution and load, which will influence the usa

4、bility of the system seriously. In this paper, we propose QFMA, an algorithm for load balancing in meta-data based P2P systems based on MAAN. The main idea is that, record the status of the high load node along the query path, the other query will change their destination based on the status recorde

5、d. Our analysis and simulation result show that QFMA can reduce the load of hot spot and achieve load balance, the query path length is also O(log N).Keywords: SOC; SOA; P2P; QFMA; Load Balance; Hot Spot刘德辉等QFMA: 种支持负载均衡的多属性资源定位方法#刘德辉等QFMA: 种支持负载均衡的多属性资源定位方法71引言SOA(Service Oriented Architecture)以资源

6、服务化为基础，通过服务的发布、发现、调用等 相关机制19,为开放环境下的资源聚合提供本文由国家 973重点基础研究发展计划 (No.2005CB321804)和国家自然科学基金 (No.90412011)资助.刘德辉，男，1979年生，博士研究生，研究领域为分布计算，P2P数据管理.周宁，女，1974年生，硕士，研究方向为信息安 全与软件工程；尹刚，男，1975年生，博士，研究领域为P2P信任管理与信息安全；王怀民，男，1962年生，教授, 博士生导师，主要研究方向为分布计算与信息安全；邹鹏,1957年生，男，教授，博士生导师，主要研究方向为分布计算.邮箱：dhliu1997.地址:湖南国防科

7、大计算机学院博士生队(410073)强有力的支持随着应用规模的不断扩大，传统 SOA中的集中式注册中心(如UDDI)最终将成 为系统的瓶颈研究219等表明P2P技术是 实现SOA去中心化的有效方法，P2P环境下服 务描述信息(WSDL, OWL-S)的存储，服务资源的定位分别实现了传统SOA中的服务发布和发现功能，不同的是注册中心的角色由分布在网 络中的大量动态的 P2P节点承担.如何在P2P 这样一个高度动态和异构的网络中，实现高效的服务发布和发现则是需要研究的重要问题在P2P网络中服务的发布和发现仅需要服务描 述信息，因此本文研究适用于任意这样的系统 （基于元数据的P2P系统）:资源驻留在

8、本地,资 源描述发布到网络中，资源使用者根据描述信 息进行资源定位，在资源所在节点获取和使用 资源下文涉及的资源不仅限于服务资源P2P网络主要分为三类：结构化、非结构 化以及混合型其中基于DHT的结构化P2P网 络因为其高效性，高可扩展性在学术界和应用 领域得到了广泛关注 Chord，CAN，Pastry等具 有代表性的结构化 P2P网络一般只支持基于单 个关键字的精确的资源定位方法，而资源描述中包含多个属性，每个属性包含多个关键字，基于单个关键字必然严重影响资源定位的效率.为了克服该局限性，Cai等人提出了多属性资源 定位网络MAAN2以支持多属性查找.支持多关键字的DHT技术更加符合互联网

9、 资源定位的实际需要但是，资源描述中的关键 字分布和访问符合 Zipf定律，流行度”往往具 有很大差异，高流行度的关键字（如2008, cpu等） 的存储节点容易成为系统性能瓶颈，也就是说引发负载均衡问题随着结构化P2P系统研究 和应用的深入，其负载均衡问题引起了广泛关 注3,4,5,6,7,9，普遍认为导致负载均衡问题的 原因主要有3类：（1） DHT标识（标识资源和节点 的散列值）分布不均匀4,基于随机hash函数 会产生O（logN）的不平衡因子；节点能力异 构性9,以同等方式对待所有节点忽略了节点 能力上的差异；（3）负载分布不均匀3,由于互 联网中资源分布和访问符合Zipf定律11,

10、12,13,即少数 流行度”高的资源将接受大部分的访问，导致了少数热点”的工作负荷远远大于普通节 占八、第一类问题主要通过改进散列算法进行解决1,17;第二类，文章3,6,9已作相应讨论; 针对第三类原因产生的问题 ，主要有两种解决 方法：（1）基于复制和缓存的负载均衡方法 9,14,15,这种方法通过对资源本身进行复制 和缓存，有效分流 热点”资源的负载 （2）基于虚 拟服务器的负载均衡方法3,4,5,6,9,其主要思想是在系统中引入新的逻辑概念-虚拟服务器，每个虚拟服务器承担一段连续的标识，通过虚拟服务器在真实节点之间的迁移实现负载 均衡在基于元数据的P2P系统中有这样一类问题：假设k是一

11、个”热门”关键字如”2008”，必然 在很多资源描述信息和查询中包含k,如果n是k的散列值对应的节点，那么n上必然因为要存 储大量资源描述信息，接受大量的查询请求,而成为”热点”.这是因为标识（对应某关键字）负 载不均匀引起的第三类问题，但上述两种解决 办法对此问题并不适用：第一种方法在节点频 繁加入和退出网络时会导致大量无效的资源元 数据（资源节点已经退出网络，但其元数据却依 然存在）,引入较高的副本管理成本；第二种方法的前提是假设网络中所有标识的访问负载分 布均匀，即针对不同关键字的访问量相当，这显然与互联网应用的特征相违背针对该问题，本文提出一种支持负载均衡的多属性资源定位方法QFMA

12、（Query-Feedbackbased Multi-attribute Addressi ng）. QFMA 的主要 思想：以MAAN为基础，借鉴沿路复制的思想, 在查询路由路径上“捎带”发布“热门”关键 字所在节点的状态信息；其它查询根据这些状 态，在路由过程中进行查询目标切换，将“热门”关键字所在节点的负载分流到负担较轻的 节点上，提高网络的负载均衡特性本文研究的基本思路是复制和缓存，与其它相关研究9,14,15的区别在于，解决负载均 衡问题的同时，不会产生无效的资源元数据和 较大的副本管理开销：（1）资源加入时基于 MAAN对其元数据进行复制,因为副本存储的 位置是确定的，资源发生变化

13、时资源节点能够 直接对这些信息进行更新，不会产生无效的资 源元数据；（2）查询过程中复制的对象仅仅是状 态信息，状态信息有存活周期 ，资源节点的加 入退出以及资源属性的更新不会为状态管理带 来额外的开销第2节详细阐述QFMA的主要思想；第3 节对QFMA进行理论分析；第 4节实验验证； 第5节总结和展望2 QFMA算法2.1定义和说明根据文献2给出与资源及查询相关的形式 化定义.定义1 （资源描述）资源r的描述是一个包 含m个属性的集合，每个属性可表示为二元组 （a, v），其中a是属性名，v是属性值，以下属性 值也称为关键字.定义2 （查询）定义查询q为形如 （an） （a2=V2）（as=

14、vs） s 1,的表达式.给 定任意查询q, Kq是q中所有关键字组成的集合， r为任意资源，Kr是其描述信息中所有关键字组 成的集合，如果Kq 乂 Kr,则称资源r满足查询 q.根据文献5给出节点负载率相关的定义.节点接受查询请求，执行查询处理，返回 查询结果需要消耗一定的计算资源和网络带宽 资源.本文用单位时间内接受的查询请求数量 来衡量节点的负载情况，称之为节点负载.每个节点都有计算和带宽的限制，定义节点单位时间内能够接收和处理查询请求的最大数量为 其能力.定义3 （节点负载率）令节点n的能力为Cn, 负载为In,那么n的负载率为Un = ln/Cn.令节点 n的负载率阈值为tn,当Un

15、 一 tn时，称节点n过 载，否则称节点n欠载.如果负责H（k）的节点n 处于过载状态，则称k为过载关键字.在此基础上给出其它相关定义.定义4 （路由路径）令节点ns到节点nt的路 由过程为ns, n1, ., np, nt,其中np为m的直接前 驱节点.称n1, ., np为从足到m的路由路径，简 称路径.任意一条以nt为目标的路径 p,如果p 中任意节点记录有 nt的状态，则称p命中nt的 状态.定义5 （节点状态）:节点n的状态sn可以 表示为三兀组（start-idn, end-idn, idn, Un）,其中 start-id n, end-idn是节点n负责的标识区间,idn. 是

16、节点n的标识，un表示节点的负载率.定义6 （查询消息）：查询消息表示为三元 组（q, C, k）,其中q表示查询，令Kq为q中所有 关键字组成的集合，C Kq是候选关键字集合， 由查询发起者进行初始化，在查询路由过程中 演化,k表示当前用于定位资源的关键字.本文网络的构造和演化过程遵循Chord协议.节点在加入网络时将本节点的资源描述存 储到相应节点：给定资源r及其属性序列（a, Vi）, l 1, m,对每个关键字Vi,采用一致性hash算 法H将Vi映射为一个属性标识H（vj,并将资源描述存储到H（vi）对应的节点.网络中的每个节点既可以是查询的发起者，也可以是接受者，另外还可以作为查询

17、路由的 中间节点；节点定期根据接受的查询负载情况 更新负载率；每个节点需要维护一个状态列表，用于记录途径本节点的查询反馈的过载节点的 状态信息.2.2状态管理算法从任意节点ns发起的查询q,其路径为n1, ，np, nt为目标节点，nt执行完查询操作后会沿 路径反向返回结果，如果nt处于过载状态，在 结果中 捎带”m的状态.路径上的节点（np除外） 在接收到带有状态的结果时，调用 State_Ma nager算法对本节点的状态列表进行维 护.在本节点状态列表state_list中增加状态项 时需要为其设置时间戳；如果本节点已经存在 nt的状态项时需重新设置其时间戳 因为每个节点负责的标识区间不

18、相交，所以可以根据状态项中的 start-idn对状态列表中 的项进行排序，以提高匹配速度；为了提高状 态命中概率，在路径上各节点(np除外)的前驱 节点和k(与系统设置相关)个后继节点上都记录 相应的状态；每个节点定期检查自己的 state_list删除过时的状态项假设n为路径上的 任意节点，state为结果消息中捎带”的状态信息，状态管理算法描述如下：算法1：状态管理算法State_Manager( n, state)在节点n的上记录该状态1. n.Add_State( state )在n的前驱节点上记录该状态2. n.precessor.Add_State ( state )在n的k个后

19、继节点上记录该状态3. fori j 1 to k4. n.successor j . add_state(state)Add_State( state)根据idn判断该状态项是否已存在1. if exist( state )更新节点状态中的负载率和时间戳2. updata( state )3. else将 state 插入 state_list4. insert( state )2.3路由算法令ns, n1,，np, nt为查询q路由过程涉及的 所有节点(ns为查询发起节点，n1, ., np为路由 路径，m为目标节点),查询路由过程中的每个 节点都调用Query_Rout算法执行路由操作.

20、 ns首先从查询q中提取出所有关键字，初始化 候选关键字集合C;依据本地状态列表从C中删除过载关键字(如果C中仅剩一个关键字，则 保留);从C中随机选择一个关键字赋予当前关 键字k,初始化路由消息；根据H(k)选择下一跳 节点，并向其转发查询消息.(2)路径上的节点 则根据本节点状态列表从C中删除过载关键字；如果本节点记录有路由消息中当前关键字所在节点的状态信息，则执行目标切换，否则直接 选择下一跳节点转发查询消息；(3)到达目标节点，路由过程结束，执行查询操作，返回查询结 果.假设n是查询q路由过程中的任意节点 msg是对应的查询消息，路由算法描述如下：算法2:路由算法Query_Rout(

21、 n, msg)判断是否为目标节点1. if is_dest_node(n)执行查询操作2. n.excute(msg.q)3. return查询发起节点4. if is_init_node( n)5. init_msg( msg )6. else n上存在与k相关状态，C不为空.7. remove_overload (msg C)8. if (has_state(n, msg k)&&( msg cd )9. msg kJ random_sel(msg C)10. msg CjC- msg k选择下跳节点，转发送查询消息11. foword(msg)初始化查询消息init_m

22、sg(msg)初始化C1. msg Cj extract(msg q)根据本节点状态列表，删除C中过载关键字2. remove_overload(msg C)从C中随机选择一个作为当前关键字3. msg kJ random_sel(msg C)将该关键字从C中删除4. msg Cj msg C- msg k检查节点n上是否有负责k的节点的状态记录has_state(n, k)1. for i j 0 to n.stata_list.length 12. if (n.stata_listi. start-idn w H(k) &&(H( k)<n.stata_listi.

23、end-idn)3. if is_intime( n.stata_listi)4. return true5. return false3算法分析3.1路由算法分析定理1 QFMA路由算法是收敛且完备的 证明(1) 如果当前关键字所在节点处于非过载 状态，则查询路由过程不需要进行查询目标切换,根据Chord路由算法知,经过O(logN)跳后, 路由过程一定会结束(2) 否则，需要进行查询目标切换，执行切 换的条件是当前关键字为过载关键字且候选关键字集合不为空因为候选关键字集合中元素 个数是有限的，假设其个数为x,所以最多再执 行x次切换，每次切换之前经过的跳数最多为 O(logN),即最多经过

24、 O(xlogN)跳后要么当前关 键字为非过载关键字，要么候选关键字集合为 空，令此时的当前关键字为k,那么之后的路由过程是以k为当前关键字,不会执行切换操作， 路由过程再经过O(logN)步后结束.根据(1),知QFMA路由算法是收敛的.(3) 设r为任意满足查询q的资源，Kr为r包含的所有关键字组成集合，Kq为q包含的所 有关键字组成的集合，则Kq二Kr.对任意关键 字k ( k Kq ),显然k Kr,令n为负责H(k)的节 点，则n定存有资源r的描述,所以根据k 一 定可以定位到资源r.因为k为Kq中任意关键字 只要存在满足查询的资源就一定可以被定位.即QFMA路由算法是完备的.综上所

25、述,QFMA路由算法是收敛且完备 的.证毕.3.2节点负载分析假设任意节点n处于过载状态，任一以n为目标的查询 q,路由过程中能否有效地进行 查询目标切换，与其路径能否命中 n的状态 有关.如果在n的直接前驱上记录状态，后续以 n为目标的查询路径都一定会命中该状态，在状态有效时n将接受不到查询处于 0负载情况, 状态失效后又将很快处于过载状态，n的负载处于震荡状态，所以我们不在 n的直接前驱上记 录其状态.本文在路径上每个节点(n的直接前 驱除外)的前驱节点和k个后继节点上记录其状 态，使得以n为目标的查询路径命中其状态的 概率大大增加.在n刚处于过载状态时，发布到网络上的状态的数量很少，其状

26、态被命中的概 率相对较小，随着发布到网络上的状态增多时，被命中的概率会大大提高 .状态存在有效期， 当状态失效后命中该状态的查询不会进行查询 切换，由于到达n的查询是有先后顺序的，所以 只要选择合适的状态有效期，保证网络中存在相对稳定的状态数量，那么状态命中概率将趋 于稳定.我们用Zipf定律描述关键字访问频度的分 布，Zipf定律一般表达式为：Fi= 9 /ia, 0为常数， i为该对象的流行度排列位次，Fi为其访问频度.一般来讲1.6>a>0可以涵盖目前对互联网应用 的分析结果7,为了简化问题本文取a=1,用概率Pi代替频度，Pi=C/i,其中C=(寸i=11/i)-1 1/l

27、nM, M为关键字的总数,则Pi 1/(lnM*i).令系统中一共有 N个关键字，关键字k的 流行度排行位次为i,包含k的查询中涉及的关 键字个数平均为M个.那么在MAAN中任意查 询以k所在节点为目标的概率约为1/(i*M*lnN).设单位时间内的总访问量为A,那么n的负载约为A/(i*M*lnN);在QFMA中，假设n的状态命中 概率为p (稳定后),那么n的负载约为 A(1-p)/(i*M*l nN).3.3平均路由长度定理2: QFMA的路由路径长度为 O(logN) 证明：令q为从ns发起的查询，Kq为q中包含的 关键字组成的集合，|Kq|=M, k为查询消息中的 当前关键字.如果k

28、为非过载关键字，QFMA算法的查询 路由过程与Chord 一致，所以路径长度也为O(logN).如果k为过载关键字,在查询路由过程中 要进行查询目标切换，路径长度会相应增加.因 为|Kq|=M,那么查询路由过程最多执行次 M-1 切换.显然以某一关键字为当前关键字的路由 过程在切换之前的路径长度最多为 O(logN),令 整个查询的路由路径长度为L,很显然LP（MlogN）.因为M是一个常数，而且值一般 都比较小，所以QFMA 路由路径长度为 O（logN）.证毕.4实验验证PeerSim16是欧洲 BISON, DELIS 项目的 一部分，它是由博洛尼亚大学基于 JAVA语言开 发的基于组件

29、的通用 P2P仿真平台，该平台支 持步长和事件两种模式.Trento大学在该平台上 实现了标准Chord协议，本文对Chord协议进行 扩充实现了 MAAN和QFMA,并进行仿真比 较.环境设置：网络节点数目1000,网络拓扑 通过PeerSim自动生成.资源数目100000,每个 资源的属性为 5个，每个属性用一个关键字来 表示（在DHT中关键字和字符串是没有区别的）,关键字是从文献3中提取，形成一个关键字集 合.从集合中随机选择5个不相同的关键字分配给一个资源，作为其属性值.文献中单词总数为 12810,有1793个不同 的单词，单词的出现情况如图1-a;对文献中出现的关键字按照词频进行排

30、序（词频相同名次相同）,分布情况如图1-b,从图中可以看出，关 键字服从a 1的zipf分布.本文实验的工作负 载将基于这些关键字形成.数个词单50®3 9 0 5 0 4 8 2 3出现频率图1-a单词出现情况名排度频词单2001000159 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77单词出现次数图1-b关键字分布4.1 “热点”状态命中情况首先任取n个节点，从这些节点发起仅包 含同一关键字的查询，在返回结果时沿路径（直 接前驱除外）记录其所在节点的状态；然后任取 10个节点发起仅包含该关键字的查询，第一次命中该关键字所在节

31、点状态时记录经过的跳数.对每一个n模拟一次，取步长的平均值得到曲 线A.从图中可以看出当 n大于10时，其它以 该关键字为目标的查询，平均三到四步可以命 中其状态；当n大于30以后一般经过两跳可以 命中其状态.图2状态命中需要跳数其它设置相同，返回结果时除了路径上的 节点，还在这些节点的前驱节点、k（取12）个后继节点上记录相应的状态，根据实验结果得到 曲线B.从图中可以看出：n=0时，跳数实际上 表示在1000个节点的网络中路由路径长度 ，为 5.7;当n大于10时，命中状态的跳数稍大于1,这明显好于仅在路径上记录节点状态的情况.4.2节点负载每个节点每10秒钟（时间点随机选择）从关 键字集

32、合中任取3个不同的关键字构成形如刘德辉等QFMA: 种支持负载均衡的多属性资源定位方法8刘德辉等QFMA: 种支持负载均衡的多属性资源定位方法#(a1=V1)(a2=V2)(a3=v)的查询，在 MAAN 中运 行,每个节点记录自己接受查询的频度(以分钟为单位，系统运行10分钟后取均值);节点接受 查询频度的阈值取每分钟 20次，状态有效期设 为20秒，其它设置同上，对QFMA进行模拟. 从图3中可以看出在 MAAN中，有很少一部分 节点负载远远高于普通节点，大于100,绝大部 分节点的负载在 05之间；采用QFMA算法, 节点负载主要集中在310之间，分布比数个询查1800016000140

33、00120001000080006000400020000123456789101112跳数图 5 QFMA路由路径长度分布同样的设置对 MAAN协议进行模拟，路由刘德辉等QFMA: 种支持负载均衡的多属性资源定位方法#MAAN均匀.700跳数均值为5.3, QFMA路由跳数均值为 5.88,这表明我们在实现负载均衡时，路由路径长度刘德辉等QFMA: 种支持负载均衡的多属性资源定位方法9厂601o o o o o o5 4 3o o o o2 1数个点节033551010151520 203030404050>100节点负载(X60s)图3节点负载分布对频度最高的关键字“ the”所在节

34、点的负载进行采样，采样时间间隔为1分钟，该节点1小时内的负载状况如图4所示.从图中可以看出该节点的负载在20左右，并且一旦超过 20很快就会调整到20以下.图4节点负载>钟广载负4.3平均路由长度对查询消息进行扩充(q, C, k, H),增加参数H记录消息已经过的跳数，查询发起者将其初 始化为0,每一跳加1,到达目标节点时，记录 该消息经过的跳数在上述设置下模拟10分钟, 一共产生60000个查询，查询路由跳数分布如 图5所示.从图中可以看出查询路由跳数主要 集中在 4, 5, 6, 7, 8.并没有明显增加5总结本文针对DHT中由于关键字负载分布不均 匀引起的“热点”问题，提出了一种

35、支持负载均 衡的多属性资源定位方法QFMA,并在通用P2P仿真平台PeerSim上进行验证，实验结果表 明QFMA能够有效减轻“热门”关键字所在节 点的负载，提高系统的负载均衡性，而且不会使网络中产生无效元数据，不会带来额外的副本管理成本，同时查询路径长度同样是 O(logN).本文没有考虑查询发起节点的分布特性，针对查询分布的特点对相关算法进行改进是下 一步研究的重点.参考文献1 I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H.Balakrishnan. Chord: A scalable peer-to-peer lookup ser

36、vice for internet applications. In : Proceedings of ACM SIGCOMM, San Diego, CA, 2001, 149160.2 M. Cai, M. Frank, J. Chen, and P. Szekely. MAAN:A multi-attribute addressable network for grid information services. In : 4th Int ' Workshop on Grid Computing, Phoenix, AZ, 2003, 184191.3 Bharambe.A, A

37、grawal.M, Seshan. Mercury: Supp- porting Scalable Multi-Attribute Range Queries, In: Proceedings of ACM SIGCOMM, Portland, Oregon, 2004, 353366.4 Ananth Rao, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp, and Ion Stoica. Load Balancing in Structured P2P Systems, In: Proceedings of IPTPS, Ber

38、keley, CA, 2003, 6879.5 Godfrey. B., Lakshminarayanan. K., Surana.S., Karp.R., and Stoica.Load balancing in dynamic structured P2P systems. In: Proceedings of IEEE INFOCOM, Hong Kong, China, 2004.6 P. Brighten Godfrey, I . Stoica. Heterogeneity and Load Balance in Distributed Hash Tables. In: IEEE I

39、NFOCOM, Miami, FL, USA ,2005, 596606.7 Theoni Pitoura, Peter Triantafillou. Load Distribution Fairness in P2P Data Management Systems, In: Proceedings of ICDE, Istanbul, Turkey, 2007, 396405.8 Saroiu S, Gummadi KP, Dunn RJ, Gribble SD, Levy HM. An analysis of Internet content delivery systems. In: Proceedings of OSDI. Boston: USENIX Association, 2002, 3153279 Dabek F, Kaashoek F, Karger D, Morris R, Stoica I. Wide-Area cooperative storage with CFS. In: Proceedings of SOSP. New York: ACM Press,