摘  要： 針對超節(jié)點P2P系統(tǒng)的特點,，提出了一種有效且靈活的緩存策略,。該策略使用文件價值來決定緩存替換的對象，并且在替換之前使用“閾值”選擇要緩存的文件,，使其系統(tǒng)只緩存價值較大的熱點文件,。最后通過Trace-Driven的方法模擬實驗，結(jié)果表明,，與現(xiàn)有的緩存策略LRU和LFU相比,，這種緩存策略具有較好的緩存命中率和字節(jié)命中率。
關(guān)鍵詞： 超節(jié)點P2P,；緩存,；文件價值；閾值,；日志驅(qū)動模擬

    P2P(Peer-to-Peer)被稱為對等連接或?qū)Φ染W(wǎng)絡(luò),。P2P改變了傳統(tǒng)的客戶機/服務(wù)器模式，將網(wǎng)絡(luò)應(yīng)用的核心從中央服務(wù)器向網(wǎng)絡(luò)邊緣的終端設(shè)備擴散,。最早出現(xiàn)的P2P網(wǎng)絡(luò)是以Napster為代表的集中式P2P網(wǎng)絡(luò),，它采用中央服務(wù)器管理P2P的各節(jié)點，這種中心化的模式容易遭到直接的攻擊從而導(dǎo)致網(wǎng)絡(luò)不穩(wěn)定,。隨后出現(xiàn)的分布式P2P網(wǎng)絡(luò)雖然解決了抗攻擊問題,，但是缺乏快速搜索和擴展性[1]。為克服這些缺陷,，一些學(xué)者將P2P結(jié)構(gòu)模型和C/S結(jié)構(gòu)模型相結(jié)合，提出了超節(jié)點P2P網(wǎng)絡(luò)系統(tǒng),。
    P2P系統(tǒng)在用于信息共享領(lǐng)域時,，查詢與存取操作是其最基本的操作。因此,，如何提高超節(jié)點P2P網(wǎng)絡(luò)的存取效率是研究的一個重要內(nèi)容,，對于提高P2P系統(tǒng)的性能具有重要意義。當(dāng)前一種較為常用的方法是合理地使用緩存機制,。緩存機制是利用局部性原理來提高系統(tǒng)的性能,，其基本思想是利用網(wǎng)絡(luò)上其他機器緩存中的數(shù)據(jù)來提高本地機器性能[2]。目前大多數(shù)超節(jié)點P2P網(wǎng)絡(luò)應(yīng)用了傳統(tǒng)的緩存機制,，這種方法沒有區(qū)分不同節(jié)點對資源的需求及關(guān)注程度的差異,，導(dǎo)致偶爾訪問的對象可能替換經(jīng)常訪問的對象,。因此，在緩存不大的情況下,，使用這種放置方式必然導(dǎo)致替換發(fā)生次數(shù)過于頻繁而降低查詢效率[3],。
    為了解決上述問題，本文提出了使用文件價值來決定緩存替換的對象,，同時在緩存替換之前使用閾值選擇緩存文件的策略,。這種緩存策略使得系統(tǒng)只緩存價值較大的熱點文件，從而通過提高命中率有效地降低了網(wǎng)絡(luò)流量負(fù)載,。
1 超節(jié)點P2P系統(tǒng)
1.1 體系結(jié)構(gòu)
    在廣域網(wǎng)中存在大量的節(jié)點服務(wù)器,，這些節(jié)點服務(wù)器通過P2P路由機制自組織成一個虛擬的P2P網(wǎng)絡(luò)。在這個虛擬的P2P網(wǎng)絡(luò)中,，各節(jié)點服務(wù)器之間以無結(jié)構(gòu)的P2P的形式連接,，所有的服務(wù)器具有相同的能力和責(zé)任，任意兩臺服務(wù)器之間能夠相互通信,，并且所有的通信都是對等的,。系統(tǒng)通過這些服務(wù)器為用戶提供服務(wù)，這些節(jié)點服務(wù)器被稱為超節(jié)點,，而用戶節(jié)點被稱為普通節(jié)點,。超節(jié)點P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖1所示。

    從圖1可以看出,，超節(jié)點具有管理組內(nèi)普通節(jié)點,、向用戶返回查詢結(jié)果和轉(zhuǎn)發(fā)的功能。普通節(jié)點和超節(jié)點之間則以傳統(tǒng)的C/S模式連接在一起,，并且每個超節(jié)點與若干個普通節(jié)點形成組,。每個超節(jié)點都要維護以下信息表：
    (1)本地信息表：保存本地共享資源的索引表。
    (2)快捷興趣信息表：保存與本節(jié)點有快捷鏈接的興趣相似的超節(jié)點信息,。該表由(interest,，fag，num,，address)組成,，其中interest代表節(jié)點查詢的興趣，fag是快捷鏈接建立的標(biāo)志,，取值為0或1(建立快捷鏈接),，num代表查詢成功的次數(shù)，初始值為0,，address代表快捷鏈接的節(jié)點位置,。
1.2 超節(jié)點間的資源搜索策略
    本文采用一種新的搜索策略，該搜索策略可以根據(jù)超節(jié)點的共享興趣,，逐步在具有相似興趣的超節(jié)點之間建立直接的快捷鏈接[4],。為了進一步提高查詢效率,，利用緩存存放訪問頻率較高的快捷鏈接。
1.2.1 快捷鏈接的建立
    當(dāng)一個節(jié)點服務(wù)器Pi剛加入超節(jié)點P2P網(wǎng)絡(luò)時,，Pi根據(jù)本地的共享資源建立本地信息表,，并且該表會隨著本地共享資源的變化而更新。當(dāng)Pi第一次發(fā)出查詢時,，它采用Gnutella的洪泛式搜索策略在網(wǎng)絡(luò)中搜索,，搜索的同時返回所有擁有該資源的節(jié)點表，這些節(jié)點都是快捷鏈接的候選者,。當(dāng)Pi成功地從Pj中下載資源時,，Pi中本地快捷興趣信息表的num加1；當(dāng)Pi的后續(xù)查詢繼續(xù)在Pj中搜索成功并完成下載時,，num繼續(xù)加1,；當(dāng)num達(dá)到設(shè)定的閾值時，fag置為1,，表示快捷鏈接的建立,。同時快捷鏈接還可以通過節(jié)點的快捷鏈接建立，如節(jié)點Pi向Pj發(fā)出查詢,，Pj首先通過自己的快捷鏈接進行查詢,，搜索成功后，將信息返回給節(jié)點Pi,，Pi成功下載后直接在本地興趣表中建立快捷鏈接,，并將num賦予規(guī)定的閾值。當(dāng)利用快捷鏈接搜索信息不成功時,，num就減1,，當(dāng)num小于設(shè)定的閾值時，就取消兩節(jié)點的快捷鏈接,。
1.2.2 快捷鏈接的緩存
    當(dāng)本地快捷興趣信息表建立后,，將快捷鏈接按照num值的大小進行排隊。如果某個快捷鏈接的num值最大(說明它經(jīng)常被使用),，就把它放在緩存中,，當(dāng)節(jié)點進行搜索時首先調(diào)用緩存的快捷鏈接。其他沒被緩存的鏈接按num值的大小在快捷興趣信息表中排隊,，num值大的排在上面，其他依次類推,。同時每個超節(jié)點的快捷興趣信息表可以自我調(diào)整,，以適應(yīng)網(wǎng)絡(luò)的變化。當(dāng)一個快捷鏈接的超節(jié)點離開網(wǎng)絡(luò),、或長時間不使用,、或命中率很低時,，應(yīng)及時調(diào)整它的num值以及存放的位置，直到最后把該快捷鏈接去除,。
1.3 超節(jié)點P2P系統(tǒng)中的對象定位
    當(dāng)普通節(jié)點P0發(fā)出查詢請求時：
    (1)P0首先查詢本地緩存,，若命中則查詢結(jié)束；否則轉(zhuǎn)到(2),。
    (2)P0訪問它所連接的超節(jié)點Pi,，若在Pi中命中則由Pi將命中的內(nèi)容返回給P0，查詢結(jié)束,；否則,，由Pi在超節(jié)點間轉(zhuǎn)發(fā)查詢，具體過程是：①Pi發(fā)出資源搜索時,，首先通過緩存中的快捷鏈接進行查詢,，若命中，則返回結(jié)果后結(jié)束,；否則轉(zhuǎn)②,；②Pi向自己的快捷興趣信息表中的快捷鏈接發(fā)出查詢，若命中,，則返回結(jié)果后結(jié)束,；否則轉(zhuǎn)(3)。
    (3)Pi將查詢請求轉(zhuǎn)發(fā)給文檔原來的存放站點,，若命中,，則返回結(jié)果后結(jié)束；否則發(fā)回錯誤報告,。
2 緩存策略
2.1 緩存對象的選擇
    在傳統(tǒng)的緩存策略中,，當(dāng)用戶訪問的文件不在離用戶最近的服務(wù)器上，那么不管該文件最近是否被訪問過,，都將該文件緩存到最近的服務(wù)器上,。在實際應(yīng)用中，這種緩存策略不能靈活地針對實際情況做實際的調(diào)整,，有時候會降低緩存的命中率,。為了克服這一缺點，本文使用閾值來選擇緩存對象[5],。
    在超節(jié)點P2P系統(tǒng)中,，當(dāng)文件和用戶的數(shù)量足夠大時，在短時間內(nèi)將會有大量的文件被訪問,，而對于單個的文件來說,，被訪問的頻率是不一樣的。本文根據(jù)文件的被訪問頻率用閾值來將它們區(qū)分為熱點文件和非熱點文件,。當(dāng)一個文件的被訪問頻率超過設(shè)定的閾值時稱為熱點文件,，否則為非熱點文件,。本文只緩存熱點文件，這樣能夠有效地利用服務(wù)器的緩存空間,，防止在緩存空間不足的情況下,，文件副本在緩存空間頻繁地替換而導(dǎo)致緩存的命中率下降。
    為了提高緩存的作用,，閾值的大小應(yīng)根據(jù)實際情況來調(diào)整,。可以根據(jù)緩存空間的大小和文件類型來設(shè)置閾值的大小,。當(dāng)緩存空間較大時,，可以適當(dāng)減小所有文件的閾值；當(dāng)緩存空間較小時,，應(yīng)適當(dāng)增大文件的閾值,，使得緩存策略更關(guān)注那些較熱的文件。同時,，可以為更新較少的文件類型設(shè)置一個較小的閾值,，這樣文件將更容易被緩存；為更新較多的文件類型設(shè)置一個較大的閾值,，那么該類型的文件就比較難于被緩存,。
2.2 緩存替換策略
    本文提出了使用文件價值決定緩存替換對象的替換策略，該策略要求所有的節(jié)點都維護同一請求列表,。請求列表中記錄著該節(jié)點訪問過的所有文件的基本信息,，如表1所示。

    當(dāng)一個節(jié)點從服務(wù)器中成功地下載文件A,，并判斷其被訪問的頻率大于設(shè)定的閾值后,，按照以下步驟進行緩存替換：
    (1)如果節(jié)點的緩存空間足夠容納文件A，那么文件被緩存,。否則轉(zhuǎn)到(2),。
    (2)比較文件A和緩存中候選文件的Costfile值。先與Costfile值最小的候選文件相比,，若文件A的值小,，則不進行緩存替換；若文件A的值大,，則將Costfile值最小的候選文件從緩存中去除,，然后判斷緩存空間的大小，轉(zhuǎn)到(1),。
3 模擬實驗和結(jié)果
    為了驗證緩存策略的實際性能,，這里選取了一組Web Cache的訪問日志作為工作負(fù)載并使用Trace-Driven的方法模擬實驗。在實驗中，為了進行性能比較,，對LRU[6]和LFU[7]也進行了性能測試。
    實驗選取的Web Cache訪問日志為學(xué)校網(wǎng)絡(luò)中心的Web服務(wù)器在一天24小時內(nèi)的日志記錄,。在每一條日志記錄中包括的主要字段有：獨立用戶的IP地址,、上網(wǎng)時刻、目的網(wǎng)站的域名,、目的網(wǎng)站的IP地址,、URL、訪問文件的大小等,。然后實驗?zāi)M了分布在廣域網(wǎng)上的10臺節(jié)點服務(wù)器,。所有這些節(jié)點服務(wù)器按照P2P路由機制組成一個完全分布式無結(jié)構(gòu)的P2P網(wǎng)絡(luò)，并使用散列的方法把從日志中提取到的獨立的用戶均勻分布到這些服務(wù)器上去,，同時假設(shè)用戶在物理上距離自己所分配到的服務(wù)器最近,，然后用同樣的方法把從日志中提取到的互不重復(fù)的URL所對應(yīng)的文件均勻分布到這些服務(wù)器上去，假設(shè)每一個文件都位于自己所分配到的服務(wù)器上,。這樣,，就把Web Cache的訪問日志紀(jì)錄映射到虛擬的超節(jié)點P2P網(wǎng)絡(luò)中了。
    緩存策略性能的好壞可以從緩存命中率和緩存字節(jié)命中率這兩個方面來衡量,。緩存命中率(Hit Ratio)表示從緩存得到服務(wù)的請求占總請求的百分比,，緩存字節(jié)命中率(Byte Hit Ratio)表示從緩存得到服務(wù)的字節(jié)量占總請求字節(jié)量的百分比[8]。在實驗中,，只比較緩存空間在存儲空間中所占比重小于一半的情況,，因為緩存繼續(xù)增加對提高性能而言效果不再明顯。圖2和圖3顯示了該緩存策略與傳統(tǒng)緩存策略LRU和LFU的性能比較,。
    從圖2和圖3可以看出,，本文提出的緩存策略在性能上要好于傳統(tǒng)的LRU和LFU。當(dāng)緩存空間比較小時,，本文提出的緩存策略表現(xiàn)出更突出的性能,，隨著緩存空間的逐漸增大，這三種方法所表現(xiàn)出的性能趨于相同,。另外,，閾值設(shè)置的大小也會影響緩存的命中率和字節(jié)命中率，因此,，在實驗過程中要根據(jù)緩存空間的大小和文件的類型及時調(diào)整閾值,，以達(dá)到提高性能的目的。在參考文獻[5]中的部分結(jié)論選擇較為理想的,，如1,、2、3、4等較小的閾值,，具體設(shè)置在此不做詳細(xì)論述,。

    本文提出了一種有效且靈活的緩存策略，該策略使用文件價值來決定緩存替換的對象,，同時在緩存替換之前使用閾值選擇要緩存的文件,，這使得系統(tǒng)只緩存價值較大的熱點文件。最后使用Trace-Driven的方法模擬實驗,，并且將其與傳統(tǒng)的LRU和LFU做了性能上的比較,，驗證了該緩存策略在性能上比傳統(tǒng)的LRU和LFU要好。
參考文獻
[1] 張文,，趙子銘.P2P網(wǎng)絡(luò)技術(shù)原理與C++開發(fā)案例[M].北京:人民郵電出版社,，2008.
[2] PATTERSON D A， HENNESSY J L. Computer architecture: a quantitative approach[M]. Elsevier,， 2002.
[3] 陶燁,，王義麟，王遠(yuǎn),，等.一種超節(jié)點P2P網(wǎng)絡(luò)中基于語義的協(xié)同緩存管理機制[J].計算機科學(xué),，2007，34(11):32-36,，40.
[4] 楊振會,，程楠.非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的資源搜索算法研究[J].現(xiàn)代計算機，2007,，261:128-129,，130.
[5] 高偉，韓華,，代亞非.一種P2P環(huán)境下分布式文件存儲系統(tǒng)的緩存策略[J].計算機工程與應(yīng)用,，2004，30:45-49.
[6] MORI T,， ASAKA T,， TAKAHASHI T. A novel cooperative caching scheme for unstructured peer-to-peer networks[C].In: IEEE Consumer Communications and Networking Conference， Jan,， 2009:1-5.
[7] LAOUTARIS N,， SMARAGDAKIS G， BESTAVROS A,， et al. Distributed selfish caching[C].In: IEEE Transactions on Parallel and Distributed Systems,， 2007，18(10):1361-1376.
[8] SONG Jin-Woo,， PARK Kyo-Sung,， YANG Sung-Bong. An effective cooperative cache replacement policy for mobile P2P environments[C].In: IEEE International Conference on Hybrid Information Technology(ICHIT’06),， 2006，2:24-30.