性能約束的Ｐ２Ｐ Ｗｅｂ Ｃａｃｈｅ模型

摘要：為提高網(wǎng)絡(luò)瀏覽器緩存系統(tǒng)性能，降低用戶等待時(shí)間，提出了一種基于性能約束的P2P Web Cache模型。理論分析和模擬測(cè)試表明，該模型能夠減少連接時(shí)間和傳輸時(shí)間。

關(guān)鍵詞：緩存系統(tǒng)；性能約束；P2P Web Cache；可升級(jí)；存取時(shí)間

0 引言

隨著網(wǎng)絡(luò)存取數(shù)量的飛速增長(zhǎng)，如何提高網(wǎng)絡(luò)的服務(wù)質(zhì)量已成為研究的熱點(diǎn)。傳統(tǒng)的基于服務(wù)器代理的技術(shù)如Squid和Netcache，雖然易于管理和定位節(jié)點(diǎn)，但其集中控制性難于解決單個(gè)節(jié)點(diǎn)的失效或故障問題。此外，該結(jié)構(gòu)忽略了在該代理中請(qǐng)求未果的內(nèi)容是否能在其他客戶端找到。本文提出了一種基于性能約束的可升級(jí)的P2P Web Cache模型。與現(xiàn)有的模型結(jié)構(gòu)相比，該模型是可升級(jí)的，易于管理節(jié)點(diǎn)，最重要的是有效地降低了用戶的存取時(shí)間。

1 系統(tǒng)拓?fù)浣Y(jié)構(gòu)和原理分析

1．1系統(tǒng)結(jié)構(gòu)

系統(tǒng)結(jié)構(gòu)包括兩類節(jié)點(diǎn)：胖節(jié)點(diǎn)和瘦節(jié)點(diǎn)，參見圖1。胖節(jié)點(diǎn)類似于依賴式Web Cache方法中的服務(wù)器，不過它不處理整個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的相關(guān)信息，而只是處理某一區(qū)域內(nèi)所有節(jié)點(diǎn)的信息。胖節(jié)點(diǎn)上保存著該區(qū)域內(nèi)所有節(jié)點(diǎn)的地址列表和節(jié)點(diǎn)所共享的緩存內(nèi)容的索引。此外，一些常見查詢的緩存內(nèi)容也保存在胖節(jié)點(diǎn)中，這樣可以加快查找速度，降低網(wǎng)絡(luò)通信量。瘦節(jié)點(diǎn)類似于純分散式網(wǎng)絡(luò)方法中的對(duì)等點(diǎn)，可以和區(qū)域內(nèi)的所有節(jié)點(diǎn)直接進(jìn)行通信。當(dāng)某區(qū)域內(nèi)的胖節(jié)點(diǎn)失效時(shí)，各個(gè)瘦節(jié)點(diǎn)，找到離自己最近的胖節(jié)點(diǎn)，重新注冊(cè)自己的信息到該胖節(jié)點(diǎn)上。這種方法可以避免單點(diǎn)失效。

圖1 混合式Web Cache結(jié)構(gòu)

胖節(jié)點(diǎn)可以是原有的代理服務(wù)器，或者是通過瘦節(jié)點(diǎn)選舉產(chǎn)生：一種是靜態(tài)產(chǎn)生，另一種是動(dòng)態(tài)生成。所謂靜態(tài)產(chǎn)生是指當(dāng)系統(tǒng)中的節(jié)點(diǎn)增加到某一固定值時(shí)，系統(tǒng)指定新加入的節(jié)點(diǎn)為胖節(jié)點(diǎn)。動(dòng)態(tài)生成是指，系統(tǒng)根據(jù)整個(gè)域內(nèi)各個(gè)機(jī)器的CPU速率，內(nèi)存容量及硬盤容量，推選出性能最好的機(jī)器為胖節(jié)點(diǎn)。動(dòng)態(tài)生成的胖節(jié)點(diǎn)處理效率比較高。

胖節(jié)點(diǎn)之間的信息共享通過P2P Login Server實(shí)現(xiàn)，P2PLogin Server保存著整個(gè)P2P網(wǎng)絡(luò)中所有的節(jié)點(diǎn)以及他們?cè)L問的所有歷史網(wǎng)頁。歷史網(wǎng)頁采用基于url的快表方式存儲(chǔ)，查找方便高效。

1．2基本流程和模塊

基本流程如下：

(1)客戶節(jié)點(diǎn)向本區(qū)域內(nèi)胖節(jié)點(diǎn)注冊(cè)自己的信息。這些信息包括IP地址和自己的當(dāng)前狀態(tài)等等。

(2)客戶節(jié)點(diǎn)發(fā)起一個(gè)請(qǐng)求，如果沒有在本地命中，請(qǐng)求被轉(zhuǎn)發(fā)到本區(qū)域內(nèi)胖節(jié)點(diǎn)，胖節(jié)點(diǎn)搜索緩存列表，同時(shí)把請(qǐng)求送到P2P Login Server。

(3)如果請(qǐng)求命中胖節(jié)點(diǎn)，胖節(jié)點(diǎn)直接把緩存內(nèi)容返回給客戶節(jié)點(diǎn)；同時(shí)胖節(jié)點(diǎn)通知P2P Login Server該客戶節(jié)點(diǎn)訪問的頁面。

(4)如果沒有命中胖節(jié)點(diǎn)，而在P2P Login Server命中，P2P Login Server將命中的用戶返回給客戶節(jié)點(diǎn)?？蛻敉瑫r(shí)向多個(gè)節(jié)點(diǎn)發(fā)送請(qǐng)求，從響應(yīng)最快的節(jié)點(diǎn)獲取內(nèi)容；或者從中挑選一個(gè)距離最近的(同一個(gè)局域網(wǎng)內(nèi))節(jié)點(diǎn)發(fā)送請(qǐng)求，以保證響應(yīng)時(shí)間最短。同時(shí)P2P Login Server把請(qǐng)求該網(wǎng)頁的用戶加入到快表中。

(5)如果都沒有命中，請(qǐng)求直接轉(zhuǎn)發(fā)給server。同時(shí)P2PLogin Server在快表里增加一項(xiàng)以該url為鍵值的表項(xiàng)。

主要模塊如下：

在瘦節(jié)點(diǎn)上主要運(yùn)行Login、Browser Proxy和Listener兩個(gè)進(jìn)程，而在胖節(jié)點(diǎn)上主要運(yùn)行一個(gè)Fat Peer進(jìn)程，它在該區(qū)域內(nèi)扮演服務(wù)器的角色。P2P Login Server主要運(yùn)行一個(gè)server進(jìn)程。

各個(gè)進(jìn)程的主要功能如下：

Login：它是瘦節(jié)點(diǎn)和整個(gè)系統(tǒng)交互的接口。當(dāng)瘦節(jié)點(diǎn)加入系統(tǒng)時(shí)，負(fù)責(zé)查找本區(qū)域內(nèi)的Fat Peer，注冊(cè)該節(jié)點(diǎn)的IP地址、當(dāng)前狀態(tài)和本地緩存內(nèi)容；當(dāng)瘦節(jié)點(diǎn)離開系統(tǒng)時(shí)，向Fat Peer發(fā)送請(qǐng)求把該節(jié)點(diǎn)變?yōu)殡x線狀態(tài)。

Listener：它負(fù)責(zé)監(jiān)聽客戶端發(fā)給它的請(qǐng)求，提供相應(yīng)的下載服務(wù)，同時(shí)還負(fù)責(zé)向Fat Peer發(fā)送定時(shí)更新請(qǐng)求。

Browser Proxy：它充當(dāng)傳統(tǒng)的代理服務(wù)器，不過它運(yùn)行在本地機(jī)上。當(dāng)用戶請(qǐng)求某個(gè)頁面時(shí)，它截獲用戶的HTTP請(qǐng)求，首先在本地緩存里查找，命中則直接返回內(nèi)容。否則同時(shí)向本區(qū)域內(nèi)Fat Peer和P2P Login Server發(fā)送請(qǐng)求，如果在FatPeer中命中，胖節(jié)點(diǎn)直接把緩存內(nèi)容返回給客戶節(jié)點(diǎn)；如果在P2P Login Server命中，server把命中的節(jié)點(diǎn)信息(地點(diǎn)，主機(jī)，存在時(shí)間，類型)發(fā)送給客戶端。如果都沒有命中，請(qǐng)求被轉(zhuǎn)發(fā)到源端服務(wù)器。在本地或在其他節(jié)點(diǎn)命中的內(nèi)容應(yīng)保持常新鮮度限制。此外，它還負(fù)責(zé)緩存的替換，當(dāng)緩存內(nèi)容發(fā)生變化時(shí)，會(huì)通知本區(qū)域內(nèi)的Fat Peer更新目錄。

Fat Peer：它主要負(fù)責(zé)保存當(dāng)前活動(dòng)節(jié)點(diǎn)的地址和狀態(tài)，以及某些常查詢的緩存內(nèi)容。當(dāng)某個(gè)用戶查找某對(duì)象時(shí)，由于網(wǎng)絡(luò)通信量被事先保存，因此，當(dāng)緩存內(nèi)容發(fā)生變化時(shí)通過Browser Proxy來更新并保存在本地節(jié)點(diǎn)中，F(xiàn)at Peer會(huì)直接將緩存內(nèi)容返回。這樣可以加快查找速度，降低網(wǎng)絡(luò)通信量。

Server：它主要負(fù)責(zé)實(shí)現(xiàn)胖節(jié)點(diǎn)之間的信息共享，構(gòu)建以u(píng)rl為鍵值的快表，提供高效的查找服務(wù)，同時(shí)根據(jù)客戶返回的消息，對(duì)每個(gè)url的所有用戶按照優(yōu)先級(jí)進(jìn)行排序，提供更有效的信息。

通信管理：通信管理提供一個(gè)對(duì)網(wǎng)絡(luò)的統(tǒng)一接口，提供額外的功能來保持和其他主機(jī)的持久連接，減少創(chuàng)建連接、拆除連接的開銷，減小過多的HTTP請(qǐng)求引起的速度下降。它支持TCP和UDP兩種通信方式。新節(jié)點(diǎn)加入系統(tǒng)時(shí)采用UDP發(fā)送組播數(shù)據(jù)查找區(qū)域內(nèi)胖節(jié)點(diǎn)，因?yàn)閁DP比TCP的速度快，且開銷較低；在傳輸更新和緩存內(nèi)容時(shí)，采用TCP通信，因?yàn)檫@時(shí)需要較高的可靠性。

1．3網(wǎng)絡(luò)模型描述

為方便分析，我們把底層拓?fù)鋱D描述成一個(gè)樹形模型，如圖2所示。用D表示胖節(jié)點(diǎn)和login server之間的距離，y表示login server和源端服務(wù)器之間的距離。胖節(jié)點(diǎn)和瘦節(jié)點(diǎn)之間的距離是1。

圖2 緩存的存放位置

2 延遲分析

我們對(duì)混合式Web Cache系統(tǒng)中的延遲建立模型?？偣惭舆tT包括三部分：T_o、T_c和T_t，其中T_o是定位時(shí)間，表示從節(jié)點(diǎn)發(fā)出請(qǐng)求到命中的節(jié)點(diǎn)信息或者熱點(diǎn)緩存對(duì)象被返回的時(shí)間間隔；T_c是連接時(shí)間，表示從文檔被請(qǐng)求到第一個(gè)數(shù)據(jù)包被返回的時(shí)間間隔；T_t表示從命中的節(jié)點(diǎn)或者從源端服務(wù)器到請(qǐng)求節(jié)點(diǎn)的傳送時(shí)間。因此，平均延遲E[T]可表示為E[T]=E[T_o]+E[T_c+E[T_t]。

2．1定位時(shí)間

定位時(shí)間取決于請(qǐng)求節(jié)點(diǎn)到命中的索引服務(wù)器的距離。令t代表一跳的延遲，L代表請(qǐng)求節(jié)點(diǎn)和命中的索引服務(wù)器之間的距離，P是每個(gè)胖節(jié)點(diǎn)負(fù)責(zé)的瘦節(jié)點(diǎn)個(gè)數(shù)，O_d代表在每個(gè)層次的定位時(shí)間，則E[T_o]可以表示為：E[T_o]= P(L=d)O_d。兩個(gè)節(jié)點(diǎn)之間的通信是基于TCP的，通信時(shí)間包括三次握手的延遲，搜索時(shí)間和第一個(gè)數(shù)據(jù)包的傳輸時(shí)間。第一個(gè)數(shù)據(jù)包可能是緩存對(duì)象的數(shù)據(jù)信息，也可能是命中的節(jié)點(diǎn)信息。如果請(qǐng)求在熱點(diǎn)緩存對(duì)象中命中，搜索時(shí)間可以忽略不計(jì)，在胖節(jié)點(diǎn)和P2P login server中的搜索時(shí)間和節(jié)點(diǎn)成對(duì)數(shù)關(guān)系。O_d可以表示為：

從這個(gè)公式可以看出，如果兩個(gè)節(jié)點(diǎn)的緩存是完全相同的，緩存相似度為l。對(duì)于節(jié)點(diǎn)i來說，請(qǐng)求在胖節(jié)點(diǎn)的索引中命中的概率是Max(CacheSim(pi，pj))，l≤j≤P，j≠i。假設(shè)請(qǐng)求平均分布在同一區(qū)域內(nèi)，那么P(L=1)=∑pMax(CacheSim(pi，pj))／P。P(L=D+1)表示請(qǐng)求在胖節(jié)點(diǎn)中的概率，因?yàn)樗袥]有在胖節(jié)點(diǎn)的熱點(diǎn)對(duì)象和索引中命中的請(qǐng)求都會(huì)轉(zhuǎn)發(fā)給P2P login server，P(L=D+1)可以表示為l—P(L=0)一P(L=1)。

2．2 連接時(shí)間

當(dāng)節(jié)點(diǎn)收到響應(yīng)時(shí)，如果請(qǐng)求在熱點(diǎn)緩存對(duì)象中命中，它不需要連接其他節(jié)點(diǎn)，連接時(shí)間是0；如果它在胖節(jié)點(diǎn)中命中，它將會(huì)連接同一區(qū)域內(nèi)的節(jié)點(diǎn)，距離是2。如果它在P2P loginserver中命中，它將會(huì)連接不同區(qū)域內(nèi)的節(jié)點(diǎn)，最短的距離是4；否則它將會(huì)連接源端服務(wù)器。平均的連接時(shí)間可以表示為：(CacheSim(pi，pj))／P。P(L=D+1)表示在P2P login server中的概率，和胖節(jié)點(diǎn)類似，它可以用組相似度來表示：

2．3傳輸時(shí)間

如果請(qǐng)求是在熱點(diǎn)緩存對(duì)象中命中，傳輸時(shí)間取決于緩存大小和線路傳輸率；否則請(qǐng)求是在胖節(jié)點(diǎn)索引中命中，傳輸時(shí)間取決于命中節(jié)點(diǎn)和請(qǐng)求節(jié)點(diǎn)之間的距離，他們可能在同一個(gè)區(qū)域內(nèi)，也可能在不同的區(qū)域內(nèi)，或者在源端服務(wù)器。平均傳輸時(shí)間E[T_t]可以表示為：

我們假設(shè)：(1)每一個(gè)路由器的處理能力是相同的，延遲為tr。每一個(gè)路由器采用最短路徑優(yōu)先策略。(2)在Intranet中每一條線路的傳輸延遲是相同的，我們用u₁表示；在Intranet和源端服務(wù)器的線路傳輸速率為u₂。(3)存文件的平均大小為S，而且在P2P網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)都不會(huì)成為瓶頸，等待時(shí)間可以忽略不計(jì)。

3 性能約束分析與模擬測(cè)試

系統(tǒng)采用日志驅(qū)動(dòng)的模擬測(cè)試。日志總共有475685個(gè)請(qǐng)求，根據(jù)日志里的IP地址共有435個(gè)節(jié)點(diǎn)。系統(tǒng)是基于性能約束的，它應(yīng)該滿足一個(gè)重要的限制：在SPCM中的定位時(shí)間(t0)和對(duì)象獲取時(shí)問(t1)之和小于直接從源端服務(wù)器獲取文件的時(shí)間(t)，即t0+t1

從上面的時(shí)間模型中，可以看出t0≈7．0029+8．508log₂n，其中n代表系統(tǒng)中所有的索引數(shù)。t1≤2．5489x+15．418，t≈23．69x+317．81，x表示文件大小單位是KB。

t0+t1＜t

(1)

7．0029+8．508log2n+2．5489x+15．418<23．69x+317．81(2)

假設(shè)x是平均緩存大小為8KB，由(2)得出，響應(yīng)時(shí)間最多可以減少約471．5ms。當(dāng)整個(gè)P2P系統(tǒng)中有2³⁵節(jié)點(diǎn)時(shí)，公式(1)才會(huì)成為等式。

圖3顯示了該模型分別在網(wǎng)絡(luò)I／O最快(6am)、最慢(9pm)、較快及較慢情況下的降低延遲情況。圖4顯示了本模型與直接訪問服務(wù)器相比所降低的延遲情況。通過理論分析和模擬試驗(yàn)，我們可以得出如下結(jié)論：該模型中定位時(shí)間和存取時(shí)間總和小于直接從原服務(wù)器訪問的時(shí)間。

圖4 不同情況下的延遲降低情況

4 結(jié)束語

本文提出了基于性能約束的P2P Web Cache模型，分析了這種混合式的Web Cache的性能，它所需的連接時(shí)間和傳輸時(shí)間比直接從源端服務(wù)器獲取所需時(shí)間少。盡管這種混合式的結(jié)構(gòu)會(huì)增加額外的定位時(shí)間，但這對(duì)整個(gè)延遲的影響并不大。不管是理論分析還是模擬測(cè)試都表明系統(tǒng)可以減少連接時(shí)間和傳輸時(shí)間。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。