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