張同光，趙曉莉

（新鄉(xiāng)學院計算機與信息工程學院 新鄉(xiāng)453003）

1 引言

在無結構P2P網(wǎng)絡中，資源受歡迎程度相同的情況幾乎不存在，資源查詢請求的分布是十分不均勻的，網(wǎng)絡中存在少量非常受歡迎的熱點資源，這些熱點資源將使得存有該資源的節(jié)點負載變得很高，尤其是一些突發(fā)事件的發(fā)生，很容易引發(fā)P2P網(wǎng)絡中焦點集中的突發(fā)訪問(flash crowds)，從而導致訪問熱點(query hot spot)問題[1]，熱點問題將使得節(jié)點的性能嚴重降低，該節(jié)點能夠提供有效服務的QoS下降，同時使得整個網(wǎng)絡的負載不均衡，影響網(wǎng)絡性能。面對熱點問題，首先需要重點考慮的是如何避免熱點問題的發(fā)生以及為避免熱點問題可能需要花費的開銷。資源復制技術常被用于處理訪問熱點問題。

本文提出了一個基于ARIMA預測模型并考慮語義的熱點資源復制方法SARA。其基本思想為：通過引入預測函數(shù)，預測即將成為熱點的資源，對即將成為熱點的資源提前進行副本復制，并且將副本放置到頻繁發(fā)起請求的語義組中，利用較低的復制開銷達到較高的副本查詢效率，與目前的熱點資源復制方法不同，SARA有效地避免了不必要的副本復制浪費，減小了復制開銷，同時保證了較高的副本查詢效率。

2 相關研究

在無結構P2P網(wǎng)絡中，資源訪問熱點問題的解決方法基本可歸結為三大類：服務端復制方法、客戶端復制方法以及路徑復制方法。服務端復制方法是復制一個文件到靠近源文件節(jié)點的鄰居節(jié)點，其代表有PAST[2]、Backslash[3]和Proact[4]。客戶端復制方法是復制一個文件到文件請求節(jié)點或者復制一個文件到靠近文件請求節(jié)點的鄰居節(jié)點，其代表有FarSite[5]和LAR[6]。路徑復制方法是復制文件到全路徑節(jié)點，即文件請求節(jié)點至源文件節(jié)點的查詢路徑上的所有節(jié)點，其代表有CFS[7]和路徑隨機復制(path random replication)與路徑自適應復制(path adaptive replication)相結合的復制方法[8]。

這3類熱點資源復制方法各有自己的優(yōu)缺點。其中，服務端復制方法能減少熱點發(fā)生的概率,但對于搜索查詢開銷的減小效果不明顯；客戶端復制方法可以減少網(wǎng)絡中資源搜索查詢的開銷，但不能保證查詢副本的命中率；路徑復制方法雖然可以同時克服服務端復制方法和客戶端復制方法的缺點，但是該方法需要創(chuàng)建大量的副本，將會產(chǎn)生較高的副本創(chuàng)建開銷。

3 ARIMA預測模型介紹

ARIMA的基本思想是對于非平穩(wěn)的時間序列，用若干次差分使其成為平穩(wěn)序列，再將此序列表示成關于序列到過去某一點的自回歸和白噪聲的移動平均的組合。

對某一滿足ARIMA(p，d，q)模型的樣本數(shù)據(jù)集{Xt,t=0,±1,±2,…}，首先，取自然對數(shù)并進行d次差分后（差分算子階數(shù) d通常取 0或 1，最多為 2），可得到平穩(wěn)的 ARMA(p,q)序列。如一個ARIMA(2,1,2)時間序列在它成為平穩(wěn)序列之前先差分一次，然后用一個ARMA(2,2)模型作為它的生成模型。當然，一個ARIMA(p,0,0)過程表示了一個純AR(p)平穩(wěn)過程；一個ARIMA(0,0,q)表示一個純 MA(q)平穩(wěn)過程。然后，在確定模型參數(shù)并進行擬合和檢驗后，即可進行數(shù)據(jù)預測。

4 節(jié)點自適應資源復制算法

在這一部分中將詳細闡述SARA，分為相關定義和算法描述兩個子部分。

4.1 相關定義

定義 1(文件訪問頻率f)單位時間周期T內(nèi)，某文件i被查詢訪問的次數(shù)為k，則文件i的訪問頻率為：

定義2(節(jié)點負載率C)節(jié)點X的負載CX指該節(jié)點所有共享資源受歡迎程度的總和，即節(jié)點共享的所有資源的負載總和。假如節(jié)點X共享了m個文件，第i個文件的訪問頻率為fi，則該節(jié)點的負載率計算式為：

定義 3(節(jié)點負載因子ω)節(jié)點X的負載因子ωX表示節(jié)點X的負載狀態(tài)，用以檢測節(jié)點X是否處于過載狀態(tài)。其定義為：

其中，T表示單位時間周期，lX表示節(jié)點X在單位時間周期T內(nèi)所能處理查詢消息的最大值。因此，若ωX>1，則節(jié)點X過載，即訪問量超過節(jié)點X的查詢消息處理能力。

定義 4(文件狀態(tài)查詢表) 節(jié)點X的文件狀態(tài)查詢表（query state table，QST）的結構定義見表 1。

表1 節(jié)點X的文件狀態(tài)查詢表的結構定義

P2P網(wǎng)絡中每一個節(jié)點都會單獨擁有一個QST，用以記錄文件被訪問的相關信息，其相關信息用來判斷節(jié)點是否過載，每過一個時間周期T，文件訪問次數(shù)將會被清空，同時原有數(shù)據(jù)被保存在歷史記錄隊列中，另外，文件ID也將會進行一次更新。

4.2 復制算法描述

當一個普通節(jié)點X被預測函數(shù)預測即將過載時，ωX>1（復制觸發(fā)條件），節(jié)點X首先查詢預測函數(shù)預測下一時刻流行度的表，不失一般性，按照文件訪問頻率f降序進行排序 {f1，f2，f3，f4，f5，f6，f7，f8，f9，…}。接下來，算法分 3 個階段完成，具體如下。

（1）第1階段

取出前h個文件f1到fh，將其副本分別放置到之前對其發(fā)起請求節(jié)點的語義組中。

（2）第2階段

當副本到達發(fā)起請求節(jié)點的語義組后，副本的具體放置位置并不一定是之前發(fā)起請求的節(jié)點，而是放置在處理能力強或者比較空閑的節(jié)點上。具體操作時，通過式（3）對該語義組中節(jié)點的負載因子ω進行計算，并對各個節(jié)點的負載因子進行比較，選擇負載因子最低的節(jié)點放置副本。也就是說，選擇這個語義組中最不可能出現(xiàn)過載情況的節(jié)點來分擔負載的任務，其目的是在分擔負載時，盡量避免該節(jié)點成為二次過載節(jié)點。

（3）第3階段

目標節(jié)點收到副本后，發(fā)送Gossip消息通知臨近的節(jié)點。如圖1所示，舉例說明SARA算法的執(zhí)行過程。

以h=1為例，節(jié)點X是語義組S1中的一個節(jié)點，文件k是節(jié)點X中的一個文件，語義組S4中的一個節(jié)點P頻繁地對文件k發(fā)起查詢請求，通過預測函數(shù)預測，發(fā)現(xiàn)節(jié)點X將要成為熱點節(jié)點（過載狀態(tài)），同時，節(jié)點X中文件k的訪問度最高。這時，復制文件k并將其副本發(fā)送至節(jié)點P所在的語義組S4中。當文件k的副本到達語義組S4后，語義組S4中的節(jié)點通過式（3）計算并比較，找到了負載因子ω最小的節(jié)點Y，于是將文件k的副本放置在節(jié)點Y中。節(jié)點Y收到副本后，發(fā)送Gossip消息通知鄰近的節(jié)點。此時，副本復制過程到此結束。

5 仿真結果

將仿真實驗工具PeerSim[9]作為仿真實驗平臺。通過PeerSim可以實現(xiàn)自己設計的算法，并對算法產(chǎn)生的結果進行顯示和統(tǒng)計。筆者在仿真實驗中，主要采用副本查詢效率和復制開銷作為實驗的性能指標來衡量SARA復制算法的優(yōu)勢。在測試數(shù)據(jù)的選取上，使用TREC[10]作為在仿真實驗中的測試數(shù)據(jù)。在本實驗中，將采用1 000個節(jié)點的網(wǎng)絡規(guī)模，仿真實驗中的相關參數(shù)見表2。

表2 SARA復制算法仿真實驗參數(shù)

將本文所提出的SARA復制方法與以下4種復制方法進行比較：服務端復制法、路徑復制法、客戶端復制法和ARDC復制法[11]。在PeerSim上實現(xiàn)了5種文件復制方法。為了便于對比，在相同環(huán)境下對5種復制方法分別進行實驗，分別進行結果統(tǒng)計。仿真實驗結果如圖2和圖3所示。

圖2是在節(jié)點已經(jīng)過載的情況下，5種復制方法在復制操作次數(shù)與文件復制數(shù)量之間關系的比較。在圖2中，可以明顯地看到文件復制的數(shù)量隨著復制操作次數(shù)的增加而增加，其中路徑復制方法產(chǎn)生的副本數(shù)量最高，其他4種復制方法產(chǎn)生的副本數(shù)量相同，這是因為在每次執(zhí)行復制操作中，ARDC方法、SARA方法、客戶端復制法和服務端復制方法分別復制一個文件放置到另外一個節(jié)點中，而路徑復制方法卻是沿著查詢路徑的所有節(jié)點復制文件，所以，路徑復制方法產(chǎn)生大量的副本，導致較高的復制開銷。

圖3是5種復制算法關于復制操作次數(shù)與查詢成功率的比較。從圖3中，可以看到，在復制操作次數(shù)相同的情況下，路徑復制方法的資源查詢成功率最高，其原因當然是路徑復制法復制了大量的副本，但是其開銷巨大。服務端復制法，由于僅僅在熱點節(jié)點的一跳鄰居范圍內(nèi)復制副本，導致查詢成功率最低，客戶端復制法在請求節(jié)點的附近復制副本，在一定程度上可以提高查詢成功率。ARDC使用動態(tài)社區(qū)，在很大程度上提高了資源查詢的成功率，但是，SARA復制方法引入了語義組，相比ARDC來說，對于資源查詢成功率的提高幅度更大。

實驗結果表明，盡管路徑預測法的資源查詢成功率較高，但是其巨大的復制開銷使得其不是一種好的復制技術。SARA預測復制算法在成功率相近的情況下，復制開銷大大地減小。

6 結束語

在本文中，筆者提出了SARA資源復制算法，由于SARA引入ARIMA預測模型，并且充分考慮了無結構P2P網(wǎng)絡中語義拓撲結構的特性，對于可能出現(xiàn)的熱點資源提前進行副本復制，極大地提高了資源的查詢成功率，同時，減小了復制開銷。仿真實驗也顯示了SARA在查詢成功率和復制開銷方面的優(yōu)勢。

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