P2P網(wǎng)絡(luò)中基于語義組的自適應(yīng)資源預(yù)測復(fù)制算法*

張同光，趙曉莉

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

1 引言

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

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

2 相關(guān)研究

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

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

3 ARIMA預(yù)測模型介紹

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

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

4 節(jié)點自適應(yīng)資源復(fù)制算法

在這一部分中將詳細(xì)闡述SARA，分為相關(guān)定義和算法描述兩個子部分。

4.1 相關(guān)定義

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

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

定義 3(節(jié)點負(fù)載因子ω)節(jié)點X的負(fù)載因子ωX表示節(jié)點X的負(fù)載狀態(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）的結(jié)構(gòu)定義見表 1。

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

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

4.2 復(fù)制算法描述

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

（1）第1階段

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

（2）第2階段

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

（3）第3階段

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

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

5 仿真結(jié)果

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

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

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

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

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

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

6 結(jié)束語

在本文中，筆者提出了SARA資源復(fù)制算法，由于SARA引入ARIMA預(yù)測模型，并且充分考慮了無結(jié)構(gòu)P2P網(wǎng)絡(luò)中語義拓?fù)浣Y(jié)構(gòu)的特性，對于可能出現(xiàn)的熱點資源提前進(jìn)行副本復(fù)制，極大地提高了資源的查詢成功率，同時，減小了復(fù)制開銷。仿真實驗也顯示了SARA在查詢成功率和復(fù)制開銷方面的優(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