一種基于ＤＨＴ的Ｗｅｂ緩存共享方法
2008-12-31 00:00:00劉建孫曉輝倪宏
計算機應用研究 2008年12期
(中國科學院 a.研究生院; b.聲學研究所， 北京 100190)
摘 要：
提出了一種基于DHT技術的Web緩存共享方法。該方法使得企業網絡中所有節點能夠相互共享瀏覽器中的本地緩存，從而形成一個高效的、大規模的分布式緩存共享系統。針對Web緩存共享的系統響應迅速的要求提出一種路由步長為O(2)的路由協議，保證Web查詢請求最多只經過一次轉發就可到達目標節點。性能分析和仿真實驗的結果證明其在路由可靠性、命中率、系統響應和緩存代價方面均有滿意的效果。
關鍵詞：分布式哈希表； Web緩存； 命中率； 系統響應
中圖分類號：TP303 文獻標志碼：A
文章編號：10013695(2008)12380403
Web caching system based on DHT architecture
LIU Jiana， b， SUN Xiaohuia，b， NI Hongb
(a. Graduate School， b. Institute of Acoustics， Chinese Academy of Sciences， Beijing 100190， China)
Abstract:This paper proposed a Web caching plan based on DHT， whose underlying ideology was that all the terminals in an Intranet were able to share their local caching to constitute a largescale， effective distributed Web caching system. Given the responding rapidly characteristic of Web caching， proposed a new routing scheme with a constant O(2) hop per lookup request， with which a Web query request could reach the target node within only one transfer. Furthermore， the evaluation results prove that it achieves a satisfied performance in routing reliability， hitsratio， latency of response and caching cost.
Key words：distributed hash table(DHT); Webcache; hitsratio; system response
Web緩存技術實現Web內容的關鍵節點存儲，它能減少網絡帶寬的占用，改善響應時間，提高用戶的訪問效率。現在大多數Web緩存技術采用代理服務器和網絡緩存的方式實現，即緩存內容保存在特定的緩存服務器上面，這樣可能會造成緩存服務器負載過重，沒有充分利用網絡上大部分PC節點的帶寬，距離緩存服務器很遠的節點響應速度沒有改善。如果讓網絡中的節點能夠共享本地緩存，不僅可以提高用戶的Web信息獲取速度，而且可以大大降低該網絡的外部流量。
本文提出一種基于P2P overlay結構分布式Web緩存共享方法，采用分布式哈希表(DHT)將節點和緩存目錄信息均映射到同一個鍵值空間（或者叫做標號空間）中，鍵值為k的緩存目錄信息存儲在標號為k的節點上。所有Web緩存對象目錄信息均勻分布在所有節點上，節點負載小，同時采用分區域管理的方式，使得緩存目錄信息查詢路由最多只需要O（2）步，即查詢消息最多只經過一次轉發就可以定位到目標節點，大大提高了緩存響應的速度，保證緩存獲取的高效性。
1 相關研究
基于DHT各種應用的區別在于路由方式的不同，每個基點上的路由表保存了不同的信息，導致路由步長不一樣。一種是如Chord[1]、 Pastry、Tapestry、 Koorde、Viceroy采用多跳路由方式，路由表僅需要維護O(log N)或O(1)個節點的狀態信息，查詢步長均為O(log N)。另外一種是Kelips[2]系統，以及A.T.Mizrakd等人和A.Gupta等人提出的采用超級節點結構的單跳路由算法[3]，每個超級節點的路由表維護全局路由狀態，路由表維護(O(N))或O(N)個節點的狀態信息，但查詢路由步長僅需要O(1)跳。
Web共享的目標是共享所有節點上的緩存信息，用戶需要系統響應迅速，可以很快定位目標節點并獲取緩存，同時保證節點維護代價比較小。現在提出的基于P2P的Web緩存共享方法已經有人提出： BuddyWeb[4]采用自適應跳步算法查詢目標節點，步長2~7，聚類失敗將會導致查詢失敗；Squirrel[5]基于Pastry構建DHT，查詢路由步長為O(log N)；Kache[6]路由步長為O(1)，但是每個節點需要保存位于當前分組的所有節點上的緩存目錄信息，并采用泛洪方式進行組內信息的傳遞，目錄信息存儲和維護代價高。
本文試圖找到一種查詢步長短，節點負載小，緩存內容及目錄信息分布存儲的Web緩存共享方法。采用DHT的overlay結構，可以使節點地址和Web緩存得到統一，通過緩存對象的hash值可以查詢到存儲該緩存的源節點地址。考慮到chord環的抗干擾性和Kelips的分組思想，設計一種節點易于管理、抗干擾性強、常數路由步長的DHT方法，作為Web緩存共享應用的基礎。
2 實現方法
2. 1 路由協議
通過一致性hash函數如SHA1將節點n映射為節點空間(k×m)中的一點，用hash值(k， id)來表示每一個節點。形象地說，首先將所有節點分為k個子區域，每個子區域內的所有節點均勻分布在大小為m的環形值域空間，那么在節點n的hash標號(k，id)中，k為區域標號，id為子區域環上標號。
所有Web緩存對象的目錄信息分布存儲在所有節點中，將緩存URL作為key并通過hash運算映射到空間(k×m)中的一點(k，id)，該鍵值為key的緩存對象的目錄信息（IP，端口）就存儲在節點(k，id)的后繼節點上（類似chord定義節點(k，id)的后繼節點(k′，id′)滿足：首先k′=k，即位于同一個子區域；其次id′≥id，即如果節點(k，n)是活動的，那么其后繼節點就是它本身，否則是環上該節點后面的空間距離最近的活動節點）。圖1所示為(6×8)個節點的子區域劃分情況。
每個節點管理的信息包括本地緩存信息、緩存目錄信息和路由表。
a)本地緩存信息指該節點上實際存儲的各種Web緩存信息，包括URL、緩存內容、緩存大小、上次修改日期、過期日期等。
b)因為目錄標號為(k，n)的緩存信息存儲在節點標號為(k，n)后繼節點上，所以緩存目錄信息指該節點負責管理的緩存目錄，包括目錄標號，網絡中實際存儲該緩存的源節點的信息列表（IP和端口）。圖2為節點(4，3)的緩存目錄信息表結構圖。
c)路由表包括兩部分，即子區域內所有節點的路由信息和其他子區域內的鄰居節點。通過前者可以單跳到達本子區域內的任意節點；通過后者可以單跳到達空間內的其他任意子區域，這種結構可以保證最多兩跳查詢到目標節點。子區域內節點路由信息一共m項，每一項包括后繼節點標號和IP。區域間路由信息包括(k-1)項，每一項保存其他子區域內物理距離較近的物理鄰居節點列表，包括節點標號、節點IP和網絡延時RTT值。圖3表示節點(4，3)的路由表結構。
2. 2 本地緩存管理
當節點發送請求或者收到響應以后，首先應該判斷請求或者響應的Web對象是否能夠緩存，因為現在有越來越多的Web對象具有動態性交互性，不符合緩存的條件，沒有必要向其他節點查詢Web共享緩存，直接向服務器請求，可以加快用戶的響應速度。判斷Web對象的可緩存性可以通過分析http的請求方式，http的響應狀態碼和URL的后綴屬性等方法[7]來判定。節點通過解析http請求和響應的報文，通過特定的規則，來判斷出對象的可緩存性。
節點為每個緩存對象建立一個結構體，保存緩存信息：
typedef struct{
const char* url，//緩存網頁的URL
void*cache_data，//緩存數據的地址
size_t size，//緩存數據的大小
const char*content_type， //http響應頭中的contenttype
const char*response_header，//http響應頭
int last_time_modified，//上次修改時間
intlast_time_visited，//上次訪問時間
int time_expired，//過期時間
int visit_times，//緩存命中次數
PriorityListNode*pnode，//優先級鏈表節點指針
}CacheData；
節點通過URL的hash值建立本地緩存目錄索引，所有的緩存對象放在一個hash表中，通過hash值可以很快查找出對應的緩存信息。
為保持緩存對象的一致性，必須對緩存作不定時更新和清除等。節點為所有緩存的引用維護一個雙向列表priorityList，采用LRU(least recently used)策略對緩存進行維護，如果緩存被請求命中，將該對象調整至列表首位，最新命中的緩存和命中次數多的緩存具有較高的優先級。當Web對象第一次被緩存時，該緩存引用加入列表首位，同時將該緩存目錄信息通知此節點對應的目錄索引節點。系統也不定期地進行緩存清理，維持緩存規模大小和最新狀態，將時間過期的、命中次數低的緩存對象從hash表和priorityList中清除，同時通知保存該目錄信息的節點更新其緩存目錄信息，保持系統同步更新。
2. 3 節點查詢
節點截獲到自身的http請求以后，首先判斷是否滿足緩存條件，如果可緩存，向網絡中其他節點查詢，否則直接向Web服務器請求。向其他節點查詢緩存的過程如下：
a)首先計算URL的hash值，得到該目錄存儲的目標節點(k， id)。
b)若目標節點在本子區域，直接轉發給(k，id)的后繼節點；否則，向路由表區域k中物理距離最近的鄰居節點發送目錄查詢請求，鄰居節點再將查詢請求轉發給(k，id)的后繼節點，如果命中，將緩存目錄信息返回，否則返回查詢失敗的消息。
c)發起者收到目錄信息，向實際存儲該緩存的節點發送緩存內容請求，在規定時間內如果收到內容，則查詢結束；否則直接向Web服務器請求Web對象。
d)發起者獲取了完整的Web對象以后，如果該對象可緩存，將該對象添加到本地緩存中，同時通知目標節點(k，id)的后繼節點自己擁有該緩存副本。
整個查詢過程最多只經過一次轉發，查詢步長為O(2)，考慮緩存獲取高效性，根據實際響應最大延時設定查詢時限，超時即認為查詢失敗。
消息類型和消息體的定義如下：
typedef enum{
CACHE_DATA_REQUEST， //請求緩存對象
CACHE_IP_REQUEST，//請求緩存源節點
CACHE_DATA_RESPONSE，//響應緩存對象
CACHE_IP_RESPONSE， //響應緩存源節點
CACHE_REQUEST_FAIL，//查詢請求失敗
NOTIFY_HAS_URL，//通知擁有緩存副本
NOTIFY_NODE_LEAVE，//通知節點離開
NOTIFY_URLINDEX_TRANSFER，//通知緩存目錄轉移
}MsgType；
typedef struct{
MsgType msg_type；//消息類型
int url_id； //URL目錄的hash值
unsigned intsrc_ip；//請求發起者的IP
unsigned int ip；//消息發起者的IP
char* data；//消息返回內容
}MsgData；
2. 4 節點的加入和離開
在一個動態網絡中，節點可以在任意時刻加入和離開。為了確保系統在網絡中能及時定位查找目標節點，需要及時更新相關節點的路由表信息。
節點加入時，可以通過某種方式（如廣播）獲得一個相同子區域內的某個鄰居n，然后用n的路由表來初始化自己的路由表，并向自己的后繼節點請求管理自己負責的緩存目錄信息，同時修改自己的區域內節點信息列表，并將自己上線的消息信息采用泛洪的方式通知子區域內的其他所有節點。
節點離開，正常退出時也只要自己負責的緩存目錄信息轉移到環上相鄰的下一個活動節點并通知本子區域自己離開；非正常退出時，子區域內的節點信息采用被動發現的方式更新。區域內任意節點執行查詢操作發現某后繼節點無效后，更新自己的節點信息表，并通知大家。節點加入和退出需要發送O(m)條消息告知所屬區域其他節點。
路由表中區域間鄰居節點采用動態加入更新的辦法，對于每個子區域均對應管理一個節點列表，只要其他子區域有節點與自己發生連接，就將該節點按照RTT值大小插入到列表中。其實每個區域內的所有節點可以維護一個相同的區域間鄰居節點，但是每個節點具有平等性并且RTT值不一樣，所以采用獨自管理的方式。在空閑期，發送測試消息維護列表最新狀態，將無法響應的節點從列表中刪除，當列表出現空鄰居后，可以從區域內鄰居節點獲取。
3 性能評估
3. 1 性能分析
1）負載均衡 它是影響分布式系統性能的重要因素，本文采用一致性哈希函數保證所有的緩存以很大的概率均勻分布在系統的各個節點上。同時節點向其他節點獲取緩存成功之后，緩存該Web對象，即同一對象在系統中有多個副本，對于提高獲取速度和解決Web訪問熱點現象均有效。
2）節點代價 在這個系統中本地緩存的開銷可以設定為固定大小，并定時更新維護。每個節點除了本地緩存以外需要管理大量信息，在（N=k×m）大小的系統中內存開銷可以表示為S(k，N)=A×N/k+B×(k-1)+C(其中：A為子區域內每個節點的路由信息;B為到達其他子區域的路由信息;C為緩存目錄信息)。在系統負載均衡條件下，緩存目錄信息C大小近似相等，每個子區域的路由信息對應一個節點列表，可以取B=2A，那么S(k，N)在k=N/2時取最小值。比如在N=100 000的系統中，劃分k=223個子區域，每個區域有447個節點。假定每個節點路由信息需要40 Byte，每條緩存目錄信息（緩存系統中可能有多項副本）需要500 Byte，每個節點管理100條目錄信息，那么平均每個節點的內存開銷S(223，100 000)只有 85.7 KB。
3）狀態維護 當系統中的節點發生變化（包括發布緩存消息、節點加入和離開），系統必須做兩件事，即更新節點自身信息和通知其他節點發生了變化。
系統發布緩存消息只需要查找到目標節點的后繼，然后存儲目錄信息即可。系統路由查詢只需要O(2)的代價，而且相當部分緩存消息發布均是副本發布，可以直接利用緩存請求得到的路由查詢結果。
節點加入和離開的消息通知采用泛洪（flooding）方式，一個節點變化只需要通知該子區域內的其他節點。關于Gnutella和Napster的一項研究[8]表明：在100 000個節點規模的開放式網絡中，平均每秒只有19個成員發生狀態變化。那么可以推論出在一個105~106個節點的網絡緩存系統中，只有20~200個節點發生狀態變化，平均每個子區域不到一次，而且每個子區域內的節點數目數量級在103以下，由此可知節點加入和離開的泛洪消息造成的背景帶寬負載很小。節點離開時后繼節點接管自己的緩存目錄信息，對其他節點也無影響。
區域節點鄰居的更新采用主動探測的方式。當該子區域內有節點與自己相互發生查詢請求或其他連接，就將該節點作為子區域鄰居候選節點，根據RTT值更新區域鄰居列表。這樣保持區域鄰居節點均是最近活動且物理距離相對近的。同時將相互共享過緩存的節點設為物理鄰居，可以增加節點按興趣聚類的可能，提高查詢速度。
4）其他 為了減輕系統的存儲壓力，位于同一個頁面下的大量不同Web對象的目錄信息只存儲一次，因為在同一個頁面下的Web對象具有極大相關性，通常請求是連續發生，所以只需要將主頁面的目錄信息存儲在目標節點，節點在響應用戶請求時，在發送主頁面對象的同時，將相關的Web對象一起響應給用戶，也提高了用戶的響應速度。
3. 2 仿真實驗評估
本文采用NS2網絡仿真軟件對緩存系統進行仿真實驗評估，多用戶節點運行在同一臺機器。仿真對象來自UC Berkeley home IP Web traces[9]位于proxy緩存服務器上的trace記錄，一共916個節點，95 768 條請求，時間為4 h，應用proxy中心緩存方式。仿真時每個客戶節點對應于一個仿真節點，所有節點位于一個網關下面，節點之間的鏈路延時是毫秒級；網絡拓撲采用GT拓撲生成器生成，節點之間采用flat模式以0.2概率互連。節點分組如下：916個節點，分成23個子區域，每個子區域40個節點。假定每個節點的默認緩存大小為1 MB，節點以指數分布概率離開網絡。仿真實驗主要基于以下度量指標：命中率、外部帶寬、系統響應延時、緩存空間大小。
1）命中率 包括響應命中率和字節命中率。前者指網絡中所有節點發出的請求被緩存命中響應的百分比；后者指緩存命中的字節數占所有請求總字節數的百分比。本地分布緩存命中字節數可以降低網絡外部帶寬。影響緩存命中率的因素包括節點的緩存大小、系統的動態性（包括節點的加入和退出）。
圖4是緩存大小變化對命中率大小的影響。原日志中記錄響應命中率為0.335，字節命中率為0.258。可以看出，隨著每個節點本地緩存的增加，命中率得到很大的提高，超過1 MB以后變化很緩慢，均已接近中心緩存的命中率大小，所以說在具有適當緩存空間大小條件下，本方法可以與中心緩存效果相當；同時可以看出字節命中率比響應命中率要小，這時因為緩存存儲一般采用的是小文件優先的原則。
2）外部帶寬 緩存可以降低網絡的外部帶寬，圖5比較了DHT緩存、proxy中心式緩存和無緩存三種情況下網絡外部帶寬的變化情況。可以看出DHT分布式緩存和中心式緩存一樣，都極大地降低了網絡的外部帶寬，降低了系統對外的流量。
3）響應延時 圖6、7統計所有命中記錄的延時，包括目標查詢延時和目標獲取延時，可以看出查詢目標節點延時集中在100~150 ms，獲取目標對象延時集中在150~200 ms，因為目標對象鏈路傳輸的延時稍大。在O(2)步長DHT存儲的條件下，緩存命中的總時間一般小于500 ms，具有低延時特點。
4）緩存大小
為了控制緩存的規模和實際應用的需要，設定每個節點上的最大緩存為10 MB。圖8揭示了緩存大小隨時間的變化趨勢，可以看出節點上的平均緩存大小隨時間增長而變大，在4 h以內平均緩存大小大約在500 KB以下。可以看出，本方法對緩存空間要求相對比較小，易于在內存受限的設備上使用。
4 結束語
本文設計了適用于Web緩存應用的查詢路由步長為O(2)的路由方法，并提出一種查詢步長短、節點負載小、緩存內容及目錄信息分布存儲的基于DHT的Web緩存共享方法。從仿真實驗可以看出，此分布式Web緩存在命中率、內存空間成本、系統響應延時等方面均有令人滿意的性能。它相對于傳統proxy中心緩存，充分利用了單個節點帶寬和資源，提高了http請求的響應速度，節約網絡帶寬，適用于構建一個高效大規模的緩存系統。
參考文獻：
[1]STOICA L， MORRIS R， KARGER D， et al. Chord: a scalable peertopeer lookup protocol for internet application[J]. IEEE/ACM Trans on Networking， 2003，11(1):1732.
[2]GUPTA I， BIRMAN K， LINGA P. Kelips: building an efficient and stable P2P DHT through increase memory and background overhead[C]//Proc of the 2nd International Workshop on PeertoPeer Systems. 2003:160169.
[3]GUPTA A， LISKOV B， RODRIGUES R. One hop lookups for peertopeer overlays[C]//Proc of the 9th Workshop on Hot Topics in Operating Systems. Berkeley: USENIV Association， 2003.
[4]凌波，王曉宇，周傲英，等.一種基于peertopeer技術的Web緩存共享系統的研究[J].計算機學報， 2005，28(2):170178.
[5]LYER S， ROWSTRON A， DRUSCHEL P. Squirrel: a decentralized peertopeer Web cache[C]//Proc of the 21st ACM Symposium on Principles of Distributed Computing. 2002:213222.
[6]LINGA P， GUPTA I， BIRMAN K. Kache: peertopeer Web caching using Kelips[J]. ACM Trans on Information System， 2004，5(9):129.
[7]石磊，衛琳，古志明，等.Web對象可緩存性研究及加速方案[J]. 計算機工程， 2005，31(18):7477.
[8]SAROIU S， GUMMADI P K， GRIBBLE S D. A measurement study of peertopeer file sharing systems[C]//Proc of Multimedia Computing and Networking 2002(MMCN’02).2002:156170.
[9]UC Berkeley home IP Web traces homepage [EB/OL] .http://ita.ee.lbl.gov/html/contrib/UCB.homeIPHTTP.html.
