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

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

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

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

    本文提出了一種有效且靈活的緩存策略，該策略使用文件價(jià)值來決定緩存替換的對(duì)象，同時(shí)在緩存替換之前使用閾值選擇要緩存的文件，這使得系統(tǒng)只緩存價(jià)值較大的熱點(diǎn)文件。最后使用Trace-Driven的方法模擬實(shí)驗(yàn)，并且將其與傳統(tǒng)的LRU和LFU做了性能上的比較，驗(yàn)證了該緩存策略在性能上比傳統(tǒng)的LRU和LFU要好。
參考文獻(xiàn)
[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é)點(diǎn)P2P網(wǎng)絡(luò)中基于語(yǔ)義的協(xié)同緩存管理機(jī)制[J].計(jì)算機(jī)科學(xué)，2007，34(11):32-36，40.
[4] 楊振會(huì)，程楠.非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的資源搜索算法研究[J].現(xiàn)代計(jì)算機(jī)，2007，261:128-129，130.
[5] 高偉，韓華，代亞非.一種P2P環(huán)境下分布式文件存儲(chǔ)系統(tǒng)的緩存策略[J].計(jì)算機(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.