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

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

關鍵詞：緩存系統；性能約束；P2P Web Cache；可升級；存取時間

0 引言

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

1 系統拓撲結構和原理分析

1．1系統結構

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

圖1 混合式Web Cache結構

胖節點可以是原有的代理服務器，或者是通過瘦節點選舉產生：一種是靜態產生，另一種是動態生成。所謂靜態產生是指當系統中的節點增加到某一固定值時，系統指定新加入的節點為胖節點。動態生成是指，系統根據整個域內各個機器的CPU速率，內存容量及硬盤容量，推選出性能最好的機器為胖節點。動態生成的胖節點處理效率比較高。

胖節點之間的信息共享通過P2P Login Server實現，P2PLogin Server保存著整個P2P網絡中所有的節點以及他們訪問的所有歷史網頁。歷史網頁采用基于url的快表方式存儲，查找方便高效。

1．2基本流程和模塊

基本流程如下：

(1)客戶節點向本區域內胖節點注冊自己的信息。這些信息包括IP地址和自己的當前狀態等等。

(2)客戶節點發起一個請求，如果沒有在本地命中，請求被轉發到本區域內胖節點，胖節點搜索緩存列表，同時把請求送到P2P Login Server。

(3)如果請求命中胖節點，胖節點直接把緩存內容返回給客戶節點；同時胖節點通知P2P Login Server該客戶節點訪問的頁面。

(4)如果沒有命中胖節點，而在P2P Login Server命中，P2P Login Server將命中的用戶返回給客戶節點。客戶同時向多個節點發送請求，從響應最快的節點獲取內容；或者從中挑選一個距離最近的(同一個局域網內)節點發送請求，以保證響應時間最短。同時P2P Login Server把請求該網頁的用戶加入到快表中。

(5)如果都沒有命中，請求直接轉發給server。同時P2PLogin Server在快表里增加一項以該url為鍵值的表項。

主要模塊如下：

在瘦節點上主要運行Login、Browser Proxy和Listener兩個進程，而在胖節點上主要運行一個Fat Peer進程，它在該區域內扮演服務器的角色。P2P Login Server主要運行一個server進程。

各個進程的主要功能如下：

Login：它是瘦節點和整個系統交互的接口。當瘦節點加入系統時，負責查找本區域內的Fat Peer，注冊該節點的IP地址、當前狀態和本地緩存內容；當瘦節點離開系統時，向Fat Peer發送請求把該節點變為離線狀態。

Listener：它負責監聽客戶端發給它的請求，提供相應的下載服務，同時還負責向Fat Peer發送定時更新請求。

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

Fat Peer：它主要負責保存當前活動節點的地址和狀態，以及某些常查詢的緩存內容。當某個用戶查找某對象時，由于網絡通信量被事先保存，因此，當緩存內容發生變化時通過Browser Proxy來更新并保存在本地節點中，Fat Peer會直接將緩存內容返回。這樣可以加快查找速度，降低網絡通信量。

Server：它主要負責實現胖節點之間的信息共享，構建以url為鍵值的快表，提供高效的查找服務，同時根據客戶返回的消息，對每個url的所有用戶按照優先級進行排序，提供更有效的信息。

通信管理：通信管理提供一個對網絡的統一接口，提供額外的功能來保持和其他主機的持久連接，減少創建連接、拆除連接的開銷，減小過多的HTTP請求引起的速度下降。它支持TCP和UDP兩種通信方式。新節點加入系統時采用UDP發送組播數據查找區域內胖節點，因為UDP比TCP的速度快，且開銷較低；在傳輸更新和緩存內容時，采用TCP通信，因為這時需要較高的可靠性。

1．3網絡模型描述

為方便分析，我們把底層拓撲圖描述成一個樹形模型，如圖2所示。用D表示胖節點和login server之間的距離，y表示login server和源端服務器之間的距離。胖節點和瘦節點之間的距離是1。

圖2 緩存的存放位置

2 延遲分析

我們對混合式Web Cache系統中的延遲建立模型。總共延遲T包括三部分：T_o、T_c和T_t，其中T_o是定位時間，表示從節點發出請求到命中的節點信息或者熱點緩存對象被返回的時間間隔；T_c是連接時間，表示從文檔被請求到第一個數據包被返回的時間間隔；T_t表示從命中的節點或者從源端服務器到請求節點的傳送時間。因此，平均延遲E[T]可表示為E[T]=E[T_o]+E[T_c+E[T_t]。

2．1定位時間

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

從這個公式可以看出，如果兩個節點的緩存是完全相同的，緩存相似度為l。對于節點i來說，請求在胖節點的索引中命中的概率是Max(CacheSim(pi，pj))，l≤j≤P，j≠i。假設請求平均分布在同一區域內，那么P(L=1)=∑pMax(CacheSim(pi，pj))／P。P(L=D+1)表示請求在胖節點中的概率，因為所有沒有在胖節點的熱點對象和索引中命中的請求都會轉發給P2P login server，P(L=D+1)可以表示為l—P(L=0)一P(L=1)。

2．2 連接時間

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

2．3傳輸時間

如果請求是在熱點緩存對象中命中，傳輸時間取決于緩存大小和線路傳輸率；否則請求是在胖節點索引中命中，傳輸時間取決于命中節點和請求節點之間的距離，他們可能在同一個區域內，也可能在不同的區域內，或者在源端服務器。平均傳輸時間E[T_t]可以表示為：

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

3 性能約束分析與模擬測試

系統采用日志驅動的模擬測試。日志總共有475685個請求，根據日志里的IP地址共有435個節點。系統是基于性能約束的，它應該滿足一個重要的限制：在SPCM中的定位時間(t0)和對象獲取時問(t1)之和小于直接從源端服務器獲取文件的時間(t)，即t0+t1

從上面的時間模型中，可以看出t0≈7．0029+8．508log₂n，其中n代表系統中所有的索引數。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)

假設x是平均緩存大小為8KB，由(2)得出，響應時間最多可以減少約471．5ms。當整個P2P系統中有2³⁵節點時，公式(1)才會成為等式。

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

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

4 結束語

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

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。