P2P网络中基于语义组的自适应资源预测复制算法*

张同光，赵晓莉

（新乡学院计算机与信息工程学院 新乡453003）

1 引言

在无结构P2P网络中，资源受欢迎程度相同的情况几乎不存在，资源查询请求的分布是十分不均匀的，网络中存在少量非常受欢迎的热点资源，这些热点资源将使得存有该资源的节点负载变得很高，尤其是一些突发事件的发生，很容易引发P2P网络中焦点集中的突发访问(flash crowds)，从而导致访问热点(query hot spot)问题[1]，热点问题将使得节点的性能严重降低，该节点能够提供有效服务的QoS下降，同时使得整个网络的负载不均衡，影响网络性能。面对热点问题，首先需要重点考虑的是如何避免热点问题的发生以及为避免热点问题可能需要花费的开销。资源复制技术常被用于处理访问热点问题。

本文提出了一个基于ARIMA预测模型并考虑语义的热点资源复制方法SARA。其基本思想为：通过引入预测函数，预测即将成为热点的资源，对即将成为热点的资源提前进行副本复制，并且将副本放置到频繁发起请求的语义组中，利用较低的复制开销达到较高的副本查询效率，与目前的热点资源复制方法不同，SARA有效地避免了不必要的副本复制浪费，减小了复制开销，同时保证了较高的副本查询效率。

2 相关研究

在无结构P2P网络中，资源访问热点问题的解决方法基本可归结为三大类：服务端复制方法、客户端复制方法以及路径复制方法。服务端复制方法是复制一个文件到靠近源文件节点的邻居节点，其代表有PAST[2]、Backslash[3]和Proact[4]。客户端复制方法是复制一个文件到文件请求节点或者复制一个文件到靠近文件请求节点的邻居节点，其代表有FarSite[5]和LAR[6]。路径复制方法是复制文件到全路径节点，即文件请求节点至源文件节点的查询路径上的所有节点，其代表有CFS[7]和路径随机复制(path random replication)与路径自适应复制(path adaptive replication)相结合的复制方法[8]。

这3类热点资源复制方法各有自己的优缺点。其中，服务端复制方法能减少热点发生的概率,但对于搜索查询开销的减小效果不明显；客户端复制方法可以减少网络中资源搜索查询的开销，但不能保证查询副本的命中率；路径复制方法虽然可以同时克服服务端复制方法和客户端复制方法的缺点，但是该方法需要创建大量的副本，将会产生较高的副本创建开销。

3 ARIMA预测模型介绍

ARIMA的基本思想是对于非平稳的时间序列，用若干次差分使其成为平稳序列，再将此序列表示成关于序列到过去某一点的自回归和白噪声的移动平均的组合。

对某一满足ARIMA(p，d，q)模型的样本数据集{Xt,t=0,±1,±2,…}，首先，取自然对数并进行d次差分后（差分算子阶数 d通常取 0或 1，最多为 2），可得到平稳的 ARMA(p,q)序列。如一个ARIMA(2,1,2)时间序列在它成为平稳序列之前先差分一次，然后用一个ARMA(2,2)模型作为它的生成模型。当然，一个ARIMA(p,0,0)过程表示了一个纯AR(p)平稳过程；一个ARIMA(0,0,q)表示一个纯 MA(q)平稳过程。然后，在确定模型参数并进行拟合和检验后，即可进行数据预测。

4 节点自适应资源复制算法

在这一部分中将详细阐述SARA，分为相关定义和算法描述两个子部分。

4.1 相关定义

定义 1(文件访问频率f)单位时间周期T内，某文件i被查询访问的次数为k，则文件i的访问频率为：

定义2(节点负载率C)节点X的负载CX指该节点所有共享资源受欢迎程度的总和，即节点共享的所有资源的负载总和。假如节点X共享了m个文件，第i个文件的访问频率为fi，则该节点的负载率计算式为：

定义 3(节点负载因子ω)节点X的负载因子ωX表示节点X的负载状态，用以检测节点X是否处于过载状态。其定义为：

其中，T表示单位时间周期，lX表示节点X在单位时间周期T内所能处理查询消息的最大值。因此，若ωX>1，则节点X过载，即访问量超过节点X的查询消息处理能力。

定义 4(文件状态查询表) 节点X的文件状态查询表（query state table，QST）的结构定义见表 1。

表1 节点X的文件状态查询表的结构定义

P2P网络中每一个节点都会单独拥有一个QST，用以记录文件被访问的相关信息，其相关信息用来判断节点是否过载，每过一个时间周期T，文件访问次数将会被清空，同时原有数据被保存在历史记录队列中，另外，文件ID也将会进行一次更新。

4.2 复制算法描述

当一个普通节点X被预测函数预测即将过载时，ωX>1（复制触发条件），节点X首先查询预测函数预测下一时刻流行度的表，不失一般性，按照文件访问频率f降序进行排序 {f1，f2，f3，f4，f5，f6，f7，f8，f9，…}。接下来，算法分 3 个阶段完成，具体如下。

（1）第1阶段

取出前h个文件f1到fh，将其副本分别放置到之前对其发起请求节点的语义组中。

（2）第2阶段

当副本到达发起请求节点的语义组后，副本的具体放置位置并不一定是之前发起请求的节点，而是放置在处理能力强或者比较空闲的节点上。具体操作时，通过式（3）对该语义组中节点的负载因子ω进行计算，并对各个节点的负载因子进行比较，选择负载因子最低的节点放置副本。也就是说，选择这个语义组中最不可能出现过载情况的节点来分担负载的任务，其目的是在分担负载时，尽量避免该节点成为二次过载节点。

（3）第3阶段

目标节点收到副本后，发送Gossip消息通知临近的节点。如图1所示，举例说明SARA算法的执行过程。

以h=1为例，节点X是语义组S1中的一个节点，文件k是节点X中的一个文件，语义组S4中的一个节点P频繁地对文件k发起查询请求，通过预测函数预测，发现节点X将要成为热点节点（过载状态），同时，节点X中文件k的访问度最高。这时，复制文件k并将其副本发送至节点P所在的语义组S4中。当文件k的副本到达语义组S4后，语义组S4中的节点通过式（3）计算并比较，找到了负载因子ω最小的节点Y，于是将文件k的副本放置在节点Y中。节点Y收到副本后，发送Gossip消息通知邻近的节点。此时，副本复制过程到此结束。

5 仿真结果

将仿真实验工具PeerSim[9]作为仿真实验平台。通过PeerSim可以实现自己设计的算法，并对算法产生的结果进行显示和统计。笔者在仿真实验中，主要采用副本查询效率和复制开销作为实验的性能指标来衡量SARA复制算法的优势。在测试数据的选取上，使用TREC[10]作为在仿真实验中的测试数据。在本实验中，将采用1 000个节点的网络规模，仿真实验中的相关参数见表2。

表2 SARA复制算法仿真实验参数

将本文所提出的SARA复制方法与以下4种复制方法进行比较：服务端复制法、路径复制法、客户端复制法和ARDC复制法[11]。在PeerSim上实现了5种文件复制方法。为了便于对比，在相同环境下对5种复制方法分别进行实验，分别进行结果统计。仿真实验结果如图2和图3所示。

图2是在节点已经过载的情况下，5种复制方法在复制操作次数与文件复制数量之间关系的比较。在图2中，可以明显地看到文件复制的数量随着复制操作次数的增加而增加，其中路径复制方法产生的副本数量最高，其他4种复制方法产生的副本数量相同，这是因为在每次执行复制操作中，ARDC方法、SARA方法、客户端复制法和服务端复制方法分别复制一个文件放置到另外一个节点中，而路径复制方法却是沿着查询路径的所有节点复制文件，所以，路径复制方法产生大量的副本，导致较高的复制开销。

图3是5种复制算法关于复制操作次数与查询成功率的比较。从图3中，可以看到，在复制操作次数相同的情况下，路径复制方法的资源查询成功率最高，其原因当然是路径复制法复制了大量的副本，但是其开销巨大。服务端复制法，由于仅仅在热点节点的一跳邻居范围内复制副本，导致查询成功率最低，客户端复制法在请求节点的附近复制副本，在一定程度上可以提高查询成功率。ARDC使用动态社区，在很大程度上提高了资源查询的成功率，但是，SARA复制方法引入了语义组，相比ARDC来说，对于资源查询成功率的提高幅度更大。

实验结果表明，尽管路径预测法的资源查询成功率较高，但是其巨大的复制开销使得其不是一种好的复制技术。SARA预测复制算法在成功率相近的情况下，复制开销大大地减小。

6 结束语

在本文中，笔者提出了SARA资源复制算法，由于SARA引入ARIMA预测模型，并且充分考虑了无结构P2P网络中语义拓扑结构的特性，对于可能出现的热点资源提前进行副本复制，极大地提高了资源的查询成功率，同时，减小了复制开销。仿真实验也显示了SARA在查询成功率和复制开销方面的优势。

1 Rubenstein Dan，Sahu Sambit.Can unstructured P2P protocols survive flash crowds? Transactions on Networking，2005，13(3):501～512

2 Rowstron Antony，DruschelPeter.Storage managementand caching in PAST,a large-scale,persistent peer-to-peer storage utility.Proceedings of the 18th ACM Symposium on Operating Systems Principles,Banff,Canada,ACM,2001（35）：188～201

3 Stading T,Maniatis P,Baker M.Peer-to-peer caching schemes to addressflash crowds.Proceedingsofthe 1stInternational Workshop on Peer-To-Peer Systems (IPTPS 2002),Cambridge,MA,USA,Springer-Verlag,2002

4 Alqaralleh Bassam A,Wang Chen,Zhou Bingbing,et al.A proactive method for content distribution in a data indexed DHT overlay.Proceedings of the 3rd International Conference on High Performance Computing and Communications (HPCC 2007),Houston,TX,United states,Springer Verlag,2007

5 Adya A,Bolosky W J,Castro M,et al.FARSITE:Federated,available,and reliablestorageforan incompletely trusted environment.Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI 2002),Boston,MA,ACM,2002

6 Gopalakrishnan Vijay,Silaghi Bujor,Bhattacharjee Bobby,et al.Adaptive replication in peer-to-peer systems.Proceedings of the 24th International Conference on Distributed Computing Systems(ICDCS 2004),IEEE Computer Society,2004(24):360～369

7 Dabek F,Kaashoek M F,Karger D,et al.Wide-area cooperative storage with CFS.Proceedings of the 18th ACM Symposium on Operating Systems Principles， Banff,Canada， ACM,2001

8 Yamamoto Hiroshi,Maruta Daisuke,Qie Yuji.Replication methods for load balancing on distributed storages in P2P networks.IEICE Transactions on Information and Systems,2006(1):171～180

9 PeerSim simulator.http://peersim.sourceforge.net

10 Text REtrieval Conference(TREC).http://trec.nist.gov

11 Gong Yan,Yang Fangchun,Su Sen,et al.ARDC:an adaptive file replication method based on dynamic community in peer-to-peer networks.Proceedings of the IEEE International Conference on Advanced Computer Control(ICACC 2010),Shenyang,China,2010