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

1、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 with Load BalancingLiu De-Hui1 Zhou Ning2 Yin Gang1 Wang Huai-Min1 Zou Peng11 (School of Computer Science, National University of Defense Technology, Hunan Changsha, China,

3、 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 keywords distribution and load, which will influence the usability of the sy

4、stem 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 recorded. Our analysis

5、and simulation result show that QFMA can reduce the load of hot spot and achieve load balance, the query path length is also O(logN).Keywords: SOC; SOA; P2P; QFMA; Load Balance; Hot Spot1引言本文由国家973 重点基础研究发展计划(No.2005CB321804)和国家自然科学基金(No.90412011)资助. 刘德辉, 男, 1979年生, 博士研究生, 研究领域为分布计算, P2P数据管理. 周宁, 女,

6、 1974年生, 硕士, 研究方向为信息安全与软件工程; 尹刚, 男, 1975年生, 博士, 研究领域为P2P信任管理与信息安全; 王怀民, 男, 1962年生,教授, 博士生导师, 主要研究方向为分布计算与信息安全; 邹鹏,1957年生, 男, 教授, 博士生导师, 主要研究方向为分布计算. 邮箱: dhliu1997. 地址: 湖南国防科大计算机学院博士生队(410073)SOA(Service Oriented Architecture)以资源服务化为基础, 通过服务的发布、发现、调用等相关机制19, 为开放环境下的资源聚合提供强有力的支持. 随着应用规模的不断扩大,传统SOA中的集中

7、式注册中心(如UDDI)最终将成为系统的瓶颈. 研究219等表明P2P技术是实现SOA去中心化的有效方法, P2P环境下服务描述信息(WSDL, OWL-S)的存储, 服务资源的定位分别实现了传统SOA中的服务发布和发现功能, 不同的是注册中心的角色由分布在网络中的大量动态的P2P节点承担. 如何在P2P这样一个高度动态和异构的网络中, 实现高效的服务发布和发现则是需要研究的重要问题. 在P2P网络中服务的发布和发现仅需要服务描述信息, 因此本文研究适用于任意这样的系统(基于元数据的P2P系统): 资源驻留在本地, 资源描述发布到网络中, 资源使用者根据描述信息进行资源定位, 在资源所在节点获

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

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

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

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

12、dback based Multi-attribute Addressing). 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为形如 (a1=v1)Ù(a2=v2) &

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

15、那么n的负载率为un = ln/cn. 令节点n的负载率阈值为tn, 当un ³ tn时, 称节点n过载, 否则称节点n欠载. 如果负责H(k)的节点n处于过载状态, 则称k为过载关键字.在此基础上给出其它相关定义. 定义4 (路由路径) 令节点ns到节点nt的路由过程为ns, n1, ¼, np, nt, 其中np为nt的直接前驱节点. 称n1, ¼, np为从ns到nt的路由路径, 简称路径. 任意一条以nt为目标的路径p, 如果p中任意节点记录有nt的状态, 则称p命中nt的状态. 定义5 (节点状态): 节点n的状态sn可以表示为三元组(start-idn

16、, end-idn, idn, un), 其中start-idn, end-idn是节点n负责的标识区间, idn.是节点n的标识, un表示节点的负载率. 定义6 (查询消息): 查询消息表示为三元组(q, C, k), 其中q表示查询, 令Kq为q中所有关键字组成的集合, CÍKq是候选关键字集合, 由查询发起者进行初始化, 在查询路由过程中演化, k表示当前用于定位资源的关键字. 本文网络的构造和演化过程遵循Chord协议. 节点在加入网络时将本节点的资源描述存储到相应节点: 给定资源r及其属性序列(ai, vi), iÎ1, m, 对每个关键字vi, 采用一致性ha

17、sh算法H将vi映射为一个属性标识H(vi), 并将资源描述存储到H(vi)对应的节点.网络中的每个节点既可以是查询的发起者, 也可以是接受者, 另外还可以作为查询路由的中间节点; 节点定期根据接受的查询负载情况更新负载率; 每个节点需要维护一个状态列表, 用于记录途径本节点的查询反馈的过载节点的状态信息. 2.2状态管理算法从任意节点ns发起的查询q, 其路径为n1, ¼, np, nt为目标节点, nt执行完查询操作后会沿路径反向返回结果, 如果nt处于过载状态, 在结果中“捎带”nt的状态. 路径上的节点(np除外)在接收到带有状态的结果时, 调用State_Manager算法

18、对本节点的状态列表进行维护. 在本节点状态列表state_list中增加状态项时需要为其设置时间戳; 如果本节点已经存在nt的状态项时需重新设置其时间戳. 因为每个节点负责的标识区间不相交, 所以可以根据状态项中的start-idn对状态列表中的项进行排序, 以提高匹配速度; 为了提高状态命中概率, 在路径上各节点(np除外)的前驱节点和k(与系统设置相关)个后继节点上都记录相应的状态; 每个节点定期检查自己的state_list删除过时的状态项. 假设n为路径上的任意节点, state为结果消息中“捎带”的状态信息, 状态管理算法描述如下:算法1: 状态管理算法State_Manager(

19、n, state )在节点n的上记录该状态1. n.Add_State( state ) 在n的前驱节点上记录该状态2. n.precessor.Add_State ( state )在n的k个后继节点上记录该状态3.fori1 to k 4. n.successorj. 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, &

20、#188;, np, nt为查询q路由过程涉及的所有节点(ns为查询发起节点, n1, ¼, np为路由路径, nt为目标节点), 查询路由过程中的每个节点都调用Query_Rout算法执行路由操作. (1) ns首先从查询q中提取出所有关键字, 初始化候选关键字集合C; 依据本地状态列表从C中删除过载关键字(如果C中仅剩一个关键字, 则保留); 从C中随机选择一个关键字赋予当前关键字k, 初始化路由消息; 根据H(k)选择下一跳节点, 并向其转发查询消息. (2) 路径上的节点则根据本节点状态列表从C中删除过载关键字; 如果本节点记录有路由消息中当前关键字所在节点的状态信息, 则执

21、行目标切换, 否则直接选择下一跳节点转发查询消息; (3) 到达目标节点, 路由过程结束, 执行查询操作, 返回查询结果. 假设n是查询q路由过程中的任意节点, msg是对应的查询消息, 路由算法描述如下: 算法2: 路由算法Query_Rout(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 (h

22、as_state(n, msg k)&&( msg C) 9.msg krandom_sel(msg C) 10.msg CC- msg k 选择下跳节点, 转发送查询消息11. foword(msg) 初始化查询消息init_msg(msg)初始化C1.msg Cextract(msg q) 根据本节点状态列表, 删除C中过载关键字2.remove_overload(msg C)从C中随机选择一个作为当前关键字3.msg krandom_sel(msg C) 将该关键字从C中删除4.msg Cmsg C-msg k检查节点n上是否有负责k的节点的状态记录has_state(n

23、, k)1.for i0 to n.stata_list.length 1 2. if (n.stata_listi. start-idn H(k) && (H(k) n.stata_listi. end-idn)3.if is_intime(n.stata_listi)4.return true 5.return false 3算法分析3.1路由算法分析定理1 QFMA路由算法是收敛且完备的证明(1) 如果当前关键字所在节点处于非过载状态, 则查询路由过程不需要进行查询目标切换, 根据Chord路由算法知, 经过O(logN)跳后, 路由过程一定会结束. (2) 否则, 需要

24、进行查询目标切换, 执行切换的条件是当前关键字为过载关键字且候选关键字集合不为空. 因为候选关键字集合中元素个数是有限的, 假设其个数为x, 所以最多再执行x次切换, 每次切换之前经过的跳数最多为O(logN), 即最多经过O(xlogN)跳后要么当前关键字为非过载关键字, 要么候选关键字集合为空, 令此时的当前关键字为k, 那么之后的路由过程是以k为当前关键字, 不会执行切换操作, 路由过程再经过O(logN)步后结束. 根据(1), (2)知QFMA路由算法是收敛的. (3) 设r为任意满足查询q的资源, Kr为r包含的所有关键字组成集合, Kq为q包含的所有关键字组成的集合, 则Kq &

25、#205; Kr. 对任意关键字k ( kKq ), 显然kKr, 令n为负责H(k)的节点, 则n一定存有资源r的描述, 所以根据k一定可以定位到资源r. 因为k为Kq中任意关键字, 只要存在满足查询的资源就一定可以被定位. 即QFMA路由算法是完备的.综上所述, QFMA路由算法是收敛且完备的. 证毕.3.2节点负载分析假设任意节点n处于过载状态, 任一以n为目标的查询q, 路由过程中能否有效地进行查询目标切换, 与其路径能否命中的状态有关. 如果在n的直接前驱上记录状态, 后续以n为目标的查询路径都一定会命中该状态, 在状态有效时n将接受不到查询处于0负载情况, 状态失效后又将很快处于过

26、载状态, n的负载处于震荡状态, 所以我们不在n的直接前驱上记录其状态. 本文在路径上每个节点(n的直接前驱除外)的前驱节点和k个后继节点上记录其状态, 使得以n为目标的查询路径命中其状态的概率大大增加. 在n刚处于过载状态时, 发布到网络上的状态的数量很少, 其状态被命中的概率相对较小, 随着发布到网络上的状态增多时, 被命中的概率会大大提高. 状态存在有效期, 当状态失效后命中该状态的查询不会进行查询切换, 由于到达n的查询是有先后顺序的, 所以只要选择合适的状态有效期, 保证网络中存在相对稳定的状态数量, 那么状态命中概率将趋于稳定. 我们用Zipf定律描述关键字访问频度的分布, Zip

27、f定律一般表达式为: Fi=/ia, 为常数, i为该对象的流行度排列位次, Fi为其访问频度. 一般来讲1.6>a>0可以涵盖目前对互联网应用的分析结果7,为了简化问题本文取a=1, 用概率Pi代替频度, Pi=C/i, 其中C=(Mi=11/i)-1 1/lnM, M为关键字的总数, 则Pi 1/(lnM*i). 令系统中一共有N个关键字, 关键字k的流行度排行位次为i, 包含k的查询中涉及的关键字个数平均为M个. 那么在MAAN中任意查询以k所在节点为目标的概率约为1/(i*M*lnN). 设单位时间内的总访问量为A, 那么n的负载约为A/(i*M*lnN); 在QFMA中,

28、假设n的状态命中概率为p (稳定后), 那么n的负载约为A(1-p)/(i*M*lnN). 3.3平均路由长度定理2：QFMA的路由路径长度为O(logN)证明：令q为从ns发起的查询, Kq为q中包含的关键字组成的集合, |Kq|=M, k为查询消息中的当前关键字.如果k为非过载关键字, QFMA算法的查询路由过程与Chord一致, 所以路径长度也为O(logN). 如果k为过载关键字, 在查询路由过程中要进行查询目标切换, 路径长度会相应增加.因为|Kq|=M, 那么查询路由过程最多执行次M-1切换. 显然以某一关键字为当前关键字的路由过程在切换之前的路径长度最多为O(logN), 令整个

29、查询的路由路径长度为L,很显然LO(MlogN). 因为M是一个常数, 而且值一般都比较小, 所以QFMA路由路径长度为O(logN) . 证毕.4实验验证PeerSim16是欧洲BISON, DELIS项目的一部分, 它是由博洛尼亚大学基于JAVA语言开发的基于组件的通用P2P仿真平台, 该平台支持步长和事件两种模式. Trento大学在该平台上实现了标准Chord协议, 本文对Chord协议进行扩充实现了MAAN和QFMA, 并进行仿真比较. 环境设置: 网络节点数目1000, 网络拓扑通过PeerSim自动生成. 资源数目100000, 每个资源的属性为5个, 每个属性用一个关键字来表示

30、(在DHT中关键字和字符串是没有区别的), 关键字是从文献3中提取, 形成一个关键字集合. 从集合中随机选择5个不相同的关键字分配给一个资源, 作为其属性值. 文献中单词总数为12810, 有1793个不同的单词, 单词的出现情况如图1-a; 对文献中出现的关键字按照词频进行排序(词频相同名次相同), 分布情况如图1-b, 从图中可以看出, 关键字服从a1的zipf分布. 本文实验的工作负载将基于这些关键字形成.图1-a 单词出现情况图1-b 关键字分布4.1“热点”状态命中情况首先任取n个节点, 从这些节点发起仅包含同一关键字的查询, 在返回结果时沿路径(直接前驱除外)记录其所在节点的状态;

31、 然后任取10个节点发起仅包含该关键字的查询, 第一次命中该关键字所在节点状态时记录经过的跳数. 对每一个n模拟一次, 取步长的平均值得到曲线A. 从图中可以看出当n大于10时, 其它以该关键字为目标的查询, 平均三到四步可以命中其状态; 当n大于30以后一般经过两跳可以命中其状态. 图2 状态命中需要跳数其它设置相同, 返回结果时除了路径上的节点, 还在这些节点的前驱节点、k(取12)个后继节点上记录相应的状态, 根据实验结果得到曲线B. 从图中可以看出: n=0时, 跳数实际上表示在1000个节点的网络中路由路径长度, 为5.7; 当n大于10时, 命中状态的跳数稍大于1, 这明显好于仅在

32、路径上记录节点状态的情况. 4.2节点负载每个节点每10秒钟(时间点随机选择)从关键字集合中任取3个不同的关键字构成形如(a1=v1)Ù(a2=v2)Ù(a3=v)的查询, 在MAAN中运行, 每个节点记录自己接受查询的频度(以分钟为单位, 系统运行10分钟后取均值); 节点接受查询频度的阈值取每分钟20次, 状态有效期设为20秒, 其它设置同上, 对QFMA进行模拟. 从图3中可以看出在MAAN中, 有很少一部分节点负载远远高于普通节点, 大于100, 绝大部分节点的负载在05之间; 采用QFMA算法, 节点负载主要集中在310之间, 分布比MAAN均匀. 图3节点负载分

33、布对频度最高的关键字“the”所在节点的负载进行采样, 采样时间间隔为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 QFMA路由路径长度分布 同样的设置对MAAN协

34、议进行模拟, 路由跳数均值为5.3, QFMA路由跳数均值为5.88, 这表明我们在实现负载均衡时, 路由路径长度并没有明显增加. 5总结本文针对DHT中由于关键字负载分布不均匀引起的“热点”问题, 提出了一种支持负载均衡的多属性资源定位方法QFMA, 并在通用P2P仿真平台PeerSim上进行验证, 实验结果表明QFMA能够有效减轻“热门”关键字所在节点的负载, 提高系统的负载均衡性, 而且不会使网络中产生无效元数据, 不会带来额外的副本管理成本, 同时查询路径长度同样是O(logN). 本文没有考虑查询发起节点的分布特性, 针对查询分布的特点对相关算法进行改进是下一步研究的重点.参考文献1

35、 I. Stoica, R. Morris, D. Karger, F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service 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

36、 information services. In : 4th Intl Workshop on Grid Computing, Phoenix, AZ, 2003, 184191.3 Bharambe.A, Agrawal.M, Seshan. Mercury: Suppporting Scalable Multi-Attribute Range Queries, In: Proceedings of ACM SIGCOMM, Portland, Oregon, 2004, 353366. 4 Ananth Rao, Karthik Lakshminarayanan, Sonesh Sura

37、na, Richard Karp, and Ion Stoica. Load Balancing in Structured P2P Systems, In: Proceedings of IPTPS, Berkeley, CA, 2003, 6879.5 Godfrey. B., Lakshminarayanan. K., Surana.S., Karp.R., and Stoica.I. Load balancing in dynamic structured P2P systems. In: Proceedings of IEEE INFOCOM, Hong Kong, China, 2

38、004.6 P. Brighten Godfrey, I . Stoica. Heterogeneity and Load Balance in Distributed Hash Tables. In: IEEE INFOCOM, 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

39、 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, 2001, 202215.10 Cai.M, Fran