利用局部性原理的网格资源搜索方法

1、利用局部性原理的网格资源高效搜索方法赵维(金陵科技学院 南京 210001)()摘 要 在网络搜索技术中，P2P模式有C/S模式无可比拟的优势，网络资源搜索是P2P基础技术之一。定义资源搜索效率是应答数与查询消息总数的比值，是衡量搜索技术的基本技术指标。网络世界里存在局部性现象，MRD是利用局部性原理的网格资源高效搜索方法。理论证明和模拟分析表明，MRD技术比传统改良Flooding方法平均提高至少2个数量级。关键字 网格资源 搜索技术 局部性原理 P2P网络MRD(Multi-Responders-Domain): High Efficient Search for Grid Resourc

2、e by Exploiting Localities in P2P SystemZHAO Wei(Jinling Technology Institute, Nanjing, 210001)(ygzw)Abstract Peer-to-Peer systems have unexampled superiority to Client/Server networks on search technology. A high efficient search scheme for grid resource with locality principle is designed, whose n

3、ame is multi-responders-domain, MRD as shortening. Owing to the information exploding, searching the internet information with currently search technology, flooding or FloodNet as a example, will receive increasingly manifold results, which are most invalidation.Search efficiency is the ratio of the

4、 number of responders and of search messages, and it is basic criterion for evaluating search technology. Localities are basic phenomena in all huge systems, and also network. Theory prove and simulation analyses that MRD improves search efficiency by 100 times. Keyword grid resource, search technol

5、ogy, locality principle, p2p network1 引言当今的虚拟社会，网络规模膨胀、信息资源爆炸，搜索方法已经成为Internet的关键基础技术之一，而现有基于服务器客户机（Server/Client）模式的搜索技术都有（1）服务器更新不及时，产生大量过时信息；（2）产生许多无价值的垃圾信息；（3）服务器收集的信息量有限；（4）存在单点失效等缺点，探索更有效更高效的搜索方法与技术已经是信息工业，乃至整个计算机产业最重要的研究领域之一。而未来的网格环境下的资源将比今天的网络环境下更为丰富，更加多样，如果能够探索研究发明出更加先进高效的搜索理论方法和技术，必将产生巨大的社

6、会贡献和经济效益。相关的探索研究主要集中在P2P应用层网络技术，这是一个完全分散化的网络系统，能够有效解决服务器模式的缺点和问题；其被称为Peer的成员，在网络中地位对等；没有固定的系统拓扑结构，具体系统结构都是在发展中动态自发形成的。无结构的P2P网络的基本搜索思想是利用全部网络资源为每一个成员服务，基本搜索技术是泛洪（flooding），即用最短的时间开销把查询消息扩散到最多的网络成员处。这不可避免地带来大量无效消息，浪费宝贵的网络带宽及机器计算资源等矛盾和问题。定义资源搜索效率（Resource Search Efficiency，RSE），为资源查询回答者（Resource Searc

7、h Responders，RSR）数量与查询消息（Search messages，SM）的扩散总数量的比值，即。 资源搜索效率是一个小于等于1的真分数。著名的Gnutella协议1的flooding方法，在一个平均节点度为10的1000万节点的P2P文件共享网络中，通常发出的消息总数目可达107（假定网络无回路），而回答的节点总数仅约50100个，论文特别定义这些回答节点集合为回答域（Response Domains，RD），其资源搜索效率约为100/107，即0.000001（10-5）。即使象FloodTrail2、FloodNet3,4等的最优改进算法，目标是保证Flooding的覆盖范

8、围，消除7080%的多余查询消息5，资源搜索效率仍然在0.00001（10-4）以下。由此可见，已有的网络资源搜索方式的搜索效率是极其低下的。以往的网络搜索算法都忽略了这样一个基本事实：尽管网络资源无限爆炸，但每一个成员及其每一次查询，所涉及到的回答域都很有限，并且基本上保持固定不变。这就是著名的“局部性现象或局部性原理”，计算机体系结构中关键技术之一的Caching技术，就是程序执行过程中的局部性原理的有效应用。局部性原理有时间和空间两方面的含义：下一程序指令在前条指令附近的概率非常大；下一次数据访问在前次访问的数据附近的概率非常大。前者就是程序Cache，后者就是数据Cache的理论依据。

9、同样的事实在网络资源访问中依然存在：就每一个访问成员而言，下一次的网络资源访问的回答节点落在前次网络资源的回答域中的概率非常大，即网络世界里同样存在着所谓的 “虚拟组织”，其成员间保持着相同的兴趣爱好。论文的主要工作包括：（1）定义资源搜索效率，指出资源搜索效率是衡量网络资源搜索方法优劣的重要理论综合指标，已有的搜索技术的效率都十分低下；（2）指出网络世界中仍然存在着“局部性现象”，设计出基于局部性原理的多级回答域网格资源搜索方法，与现有网络搜索方法相结合，可以极大地提高它们的网络资源搜索效率；（3）理论研究和模拟实验表明，基于多级回答域的资源搜索算法能有效提高资源搜索效率。2 相关工作目前已

10、有的搜索技术都是在折中最快搜索速度、最低网络效率的flooding方法，与较少带宽消耗、很长响应时间、较少搜索结果的Random Walker方法。把局部性原理用于P2P网络搜索始于5，希望解决P2P搜索的查询追求更快的搜索质量与网络管理追求最小的搜索代价之间的矛盾。虽然P2P网络中的成员Peers之间都是对等关系，但同实际社会一样，网络社会中也总是存在所谓的幂律（Power-Law）：即（1）较少的系统成员掌握着较多的受欢迎（Popular）系统资源；而系统中还存在着一些从未被访问或极少访问的节点资源；（2）较少的Popular节点提供了绝大多数的查询响应；而有40%的free riders

11、节点从不提供任何服务。具体如图1所示，上面第一条更加弯曲的是查询响应曲线，下面的是结果文件提供者曲线，可以看出，小于10%的Popular节点提供了几乎所有的查询响应。因此网络中确实存在局部性现象。图1 P2P网络世界里的Power-Law示意图5中采取两个措施：（1）把网络中所有的Popular节点组成查询响应或内容提供（Content Abundant Cluster，CAC）子网。查询请求首先上行至CAC子网，然后在CAC中Flooding，大部分都将在CAC中获得结果，未找到结果的查询再从CAC中下行到整个网络；（2）在查询节点中保持可选择的预取响应节点的索引信息（Selectivel

12、y Prefetching Indices from Responding Peers，SPIRP），因为根据局部性原理，下次的查询结果最有可能还在前次的响应节点集合中。CAC-SPIRP方法有如下缺点：（1）CAC资源子网的维护相当麻烦，不容易判断一个节点是否属于CAC；（2）仍然需要在CAC中进行频繁的Flooding操作；（3）SPIRP表的容量和变化都可能很大，节点维护它可能会力不从心。5的本质仍然是利用全部网络资源为单个节点的查询服务。而事实上，一个节点通常只会对很少的几个有共同兴趣的Popular节点感兴趣，它们也几乎能够满足查询节点的所有请求，而不用访问到整个CAC。论文提出的多

13、级回答域（Multi-RD，MRD）搜索方法，克服了CAC-SPIRP方法的缺点，并且更加直接地利用了局部性原理，实现起来也更为简单。3 MRD网格资源搜索方法3.1 MRD方法原理在计算机硬件体系结构的Caching技术中，系统总是把当前访问的局部指令和数据调度到一级Cache，而把更常使用的放入距CPU更近的速度更快的二级Cache中，以此类推。MRD网格资源搜索方法中，查询节点首先应用P2P的Flooding方法获得平均约50100个响应节点，它们就将组成MRD算法的多级回答域。根据查询响应信息的Hops数值不同Hops是一个在17之间的代表响应节点与查询节点逻辑距离的跳数，可以把所有响

14、应节点都归入多级回答域，如三级MRD算法的1MN7，其中N7为一级回答域（1MRD），MN为二级回答域（2MRD），1M为三级回答域（3MRD），1MN7。MRD方法认为，所有的响应节点都是查询者感兴趣的Popular节点，从兴趣或逻辑距离上来讲，3MRD距离自己最近，2MRD次之，1MRD最远，但他们都属于当前节点的回答域，也即兴趣范围。从数量上讲，通常3MRD最少，2MRD次之，1MRD最多。节点再次查询时，就首先向3MRD发出查询；如果没有命中或命中数量不足，再向2MRD发出查询；如果还是没有命中或命中数量不足，再向1MRD；如果仍然没有命中或命中数量不足，就在全网执行Flooding操

15、作。向MRD节点发出查询请求时，其TTL数值不是7，而是比相应级差小的一个数值：如3MRD中为 = M-1；2MRD中为 = N-M；1MRD中为 = 7-N。这样就用极其少量的查询消息就覆盖了几乎所有感兴趣的资源范围。这和Caching技术的原理和道理是完全一样的。3.2 MRD-Cache表应用MRD方法需要在发出查询的节点中生成MRD-Cache表，结构如表1所示。记录号MRD级数Hops回答节点ID111231312ij20027表1 查询节点的多级回答域MRD-Cache表结构示意图MRD-Cache表的大小可以根据需要调整，一般如Cache表一样都比较小，整个表空间大小也就几十K罢

16、了。MRD表应当随时维护，不能象一般Caching技术那样等表满时再运用淘汰算法，因为MRD的无效表项会产生更多无效查询消息，浪费网络带宽资源。一般情况下MRD级数与Hops保持一致，但查询者可以根据自己偏好网络传输速度等因素，重新调整MRD级数。MRD方法在整个网络空间中划出若干感兴趣的局部区域，并按个人偏好分成若干查询优先等级，如果这些偏好恰好与命中率成正比例，则是有效地利用了局部性原理。事实上在网络资源信息爆炸的时代，一个查询返回的条目数往往巨大，其中大多数是无关干扰项，通过有选择地划定查询目标区域的MRD方法，能够有效提高查询命中率。4 MRD方法评价给出实际网络环境中的资源搜索效率公

17、式，从理论上分析影响MRD方法效率的因素；基于不同的实际网络分布环境，模拟分析MRD方法的效率因素。4.1 理论分析与5维护一个整个网络的CAC不同，论文认为局部性原理总是针对具体个别查询节点而言的，一个节点所感兴趣的MRD与另一个节点应该毫无关系，只有查询方才有必要维护自己的MRD，网络中其余部分应该保持不变。这样的方案非常有利于系统实现。与Caching技术一样，MRD方法的效果直接取决于命中率，即查询结果落在MRD中的概率。假设MRD的命中率符合正态分布（1），而各级MRD又符合泊松分布（2），同级MRD间符合均匀分布，则查询的网络资源搜索效率应该为：（3），其中M0为网络中含有的查询结

18、果总数，i为MRD的级数，MAXi = i =1；ki为第i级的域数；Ti为消息扩散的跳数（Hops）；n为查询终止条件，是MAXi到1的一个数；网络查询响应结果的概率平面是非均匀分布的，（4）表示当前查询消息所遍历到的所有局部区域的概率和。从网络资源查询的搜索效率公式中，可以立即得出如下结论：（1）搜索效率RSE与网络中所含的相同资源数目（3）成正比，越大，说明待查找的资源十分普遍，随便发出几条查询消息都可以获得回答，则RSE当然很高。（2）正态分布均值（1）是回答节点x的最大度数的邻居节点，称为局部中心节点的，是局部中心节点，如果把它加入MRD时，相同的积分区间，正态分布的积分概率最大，搜

19、索效率也就最高，而且可以增加MRD表的稳定性。（3）正态分布均方差（1），表示资源的集中程度，越小，表示资源越集中于MRD附近，局部小区域的Flooding的TTL值Ti就可以越小，也即网络代价越小，RSE就越高。（4）泊松分布的均值方差（2），越小，表示资源越集中于高级MRD中，即Cache的命中率越高，网络代价就越小，搜索结束时n值就越高，即在更高级的Cache中就获得了足够数量的结果。（5）随着搜索范围的扩大，n值越小，所发出的消息数目越多，而获得的结果越少，所以搜索效率反而越来越低。（6）如果把MRD方法结合进Routing算法中，保持越频繁的响应者距离自己越近，即把最高级的MRD作为

20、查询节点的直接邻居，可以促使整个网络系统尽快进入稳定状态。与Flooding相比，MRD方法保持甚至加快了查询结果的响应速度，降低了网络带宽资源的消耗，更重要的是优先返回或只返回自己最感兴趣的结果，这正是网络信息资源查询技术所追求的最佳目标。因此MRD方法非常适合于目前正面临“一词多意”困扰的“关键字”方法的网页搜索系统。4.2 模拟评价模拟分析的主要任务是研究MRD方法在不同的网络资源分布情形下的搜索效率问题：（1）网络资源均匀分布情况下，不同Ti的MRD方法与Flooding的响应速度效率比较；（2）网络资源实际分布情况下，不同Ti的MRD与常用方法的响应速度和效率比较；（3）“颤动现象”

21、在MRD中的影响与解决。论文的模拟条件为：214 = 16,384个P2P网络节点，平均节点度为5.932，节点自动生成邻居，没有内容和索引，只有应答概率，并按概率应答，不区分查询应答与内容提供；系统记录查询消息的总数和应答总数；MRD为三级Cache，各级分配为6、32、158，即MRD-Cache表容量为200；MRD-Cache表大小为200且已经设置良好。由随机函数生成概率函数的方法：首先化概率为真分数，即n/m，然后用随机函数生成一个m内的随机数q，如果q = n，则输出概率为真，否则为假。4.2.1 资源均匀分布情况下的比较均匀分布虽然简单，但实际生活中是不存在的，只能在理论分析模

22、型中使用，P2P网络系统完全支持理论上的均匀分布。此时用最少的消息扩散数量获取最大的覆盖范围，即覆盖率就是我们追求的搜索效率。图2 MRD方法与Flooding方法的消息扩散速度比较图2所示的MRD方法与Flooding算法的消息扩散速度比较可以看出，通常情况下，MRD方法经过4跳就达到了Flooding算法7跳时的覆盖范围，说明MRD方法的响应速度更快，覆盖范围更广。因为MRD用了Cache技术，同时向网络中的200个节点发出TTL=3的查询消息。图3 MRD方法与Flooding算法的效率比较图3中所示的MRD方法与Flooding算法的资源搜索效率比较，MRD方法每个局部小区域的Floo

23、ding的TTL = 3，此时几乎还没有形成环路3,4，效率几乎是100%；而Flooding算法开始几跳也因为没有形成环路，效率很高，当TTL跳数增高时，由于大量环路的产生导致搜索效率的急剧下降，说明产生了许多无用的消息，浪费了宝贵的网络带宽资源。4.2.2 Power-Law下的比较资源的不平均分布是复杂巨系统的基本现象和本质特征，Power-Law就是对其本质的揭示（，见第2节的相关工作部分）。我们考察自然矿产资源在地球上的分布，有的地方贫瘠，有的地方丰富，人们不会盲目地随处采矿，而是首先勘探出资源在地球某一区域上的储量分布，然后根据开采代价选择最有开采价值的地点开采。网络资源的分布也符

24、合同样的规律，采用同样的方法，必将提高资源搜索效率，这就是MRD方法的内在动因，MRD-Cache表中存储的就是网络中自己感兴趣（，也就是自己要搜索）的资源的分布信息。图4假设以3MRD作为节点的直接邻居，是网络资源的最富矿区，在Flooding及其改良方式中，没有考虑对于次富矿区的利用，而MRD算法可以把网络中的资源分布详细地分为许多等级，依资源含量高低逐次查询，资源查找效率随着查找范围的逐步扩大而逐渐降低。而传统的扩散算法，没有次富矿区的资源分布图，所以在查询完直接邻居后只能盲目搜索，所以效率就急剧下降。图4 MRD与原有算法的网络资源搜索效率比较通常MRD方法只要配合一个很小范围内的Fl

25、ooding，即TTL = 3，就达到了直接或改良Flooding算法的TTL = 7的范围。因此MRD方法的资源搜索效率通常在10%左右，即每发出10个消息就可以获得一个回答，而Flooding在0.01%附近，也即要发出1,000个消息才可以获得一个回答。因此，MRD方法显著地提高了网络资源搜索效率。4.2.3 解决颤动问题Cache技术都有可能出现颤动问题，即搜索问题的微小改变，就可能导致MRD-Cache表的变化，这样在不断搜索过程中，问题域实际上没有改变，但MRD-Cache表却频繁变化。这种现象就是颤动，也叫抖动，是利用局部性原理所必须避免的问题。解决的办法就是，不直接把回答节点作为MRD节点，而是把回答节点附近的局部中心节点，当作MRD节点。如图5所示，节点A是回答节点，节点A只有3度，节点A的直接邻居B却有6度，则把节点B，而不是节点A记为MRD。 图5 MRD方法的颤动问题AB综上所述，MRD方法利用了网络资源局部性分布的规律，采用在查询节点中增加MRD-Cache表，记录网络资源的分布状况图，从而加速资源定位，提高网络资源搜索效率。由以上分析可知，MRD方法是有效的网格资源搜索技术。5 结论论文定义了资源搜索效率，指出资源搜索效率是衡量网络资源搜索方法优劣的重要理论综合指