引言
WWW是互聯網上最受歡迎的應用之一，其快速增長造成網絡擁塞和服務器超載，導致客戶訪問延遲增大，WWW服務質量問題日益顯現出來。緩存技術 被認為是減輕服務器負載、降低網絡擁塞、增強WWW可擴展性的有效途徑之一，其基本思想是利用客戶訪問的時間局部性（Temporal Locality）原理，將客戶訪問過的內容在Cache中存放一個副本，當該內容下次被訪問時，不必連接到駐留網站，而是由Cache中保留的副本提 供。
Web內容可以緩存在客戶端、代理服務器以及服務器端。研究表明，緩存技術可以顯著地提高WWW性能[1][2]，它可 以帶來以下好處：
（1）減少網絡流量，從而減輕網絡擁塞；
（2）降低客戶訪問延遲，其主要原因有：①緩存在代理服務器中的內容，客戶可以直接從代理獲取而不是從遠程服務器獲取，從而減小了傳輸延遲；② 沒有被緩存的內容由於網絡擁塞及服務器負載的減輕而可以較快地被客戶獲取；
（3）由於客戶的部分請求內容可以從代理處獲取，從而減輕了遠程服務器負載；
（4）如果由於遠程服務器故障或網絡故障造成遠程服務器無法響應客戶請求，客戶可以從代理中獲取緩存的內容副本，使得WWW服務的魯棒性 （Robustness）得到了加強。
Web緩存系統也會帶來以下問題：
（1）客戶通過代理獲取的可能是過時的內容；
（2）如果發生緩存失效，客戶的訪問延遲由於額外的代理處理開銷而增加。因此在設計Web緩存系統時，應力求做到Cache命中率最大化和失效 代價最小化；
（3）代理可能成為瓶頸。因此應為一個代理設定一個服務客戶數量上限及一個服務效率下限，使得一個代理系統的效率至少同客戶直接和遠程服務器相 連的效率一樣。
目前，圍繞Web緩存系統及其最優化問題已經開展了廣泛而深入的研究，這些研究工作主要是圍繞代理的作用展開的。
2 Web緩存系統的理想特性
一個理想的Web緩存系統應具有以下特性：
（1）快捷性：緩存系統應該能夠有效地降低客戶的訪問延遲；
（2）魯棒性：魯棒性意味著可用性，客戶希望Web服務隨時可用；
（3）透明性：緩存系統對客戶應是透明的，客戶得到的結果僅僅是快速的響應和良好的可用性；
（4）可擴展性：Web緩存系統應能夠隨著網絡規模和密度的不斷增長而很好地進行擴展；
（5）高效性：Web緩存系統給網絡帶來的開銷越小越好；
（6）適應性：緩存系統能夠適應客戶請求和網絡環境的動態變化，這涉及到緩存管理、緩存路由、代理配置等，對於獲得理想的緩存性能至關重要；
（7）穩定性：Web緩存系統采用的方案不應給網絡帶來不穩定；
（8）負載均衡：一個理想的緩存方案應能夠將負載均勻地分發到整個網絡，以避免某一個代理或服務器成為瓶頸或Hot spot點，而造成系統一部分甚至整個系統性能下降；
（9）異構處理能力：隨著網絡規模和覆蓋域的不斷增大，網絡將跨越一系列不同的硬件和軟件體系結構。Web緩存系統應能夠適應不同的網絡體系結 構；
（10）簡單性：簡單的方案容易實現且易被普遍接受，一個理想的Web緩存方案配置起來應簡單易行。
圍繞上述特性，一個Web緩存系統必須解決好以下問題：
（1）緩存體系結構：緩存代理在網絡中如何組織和配置；
（2）代理合作：代理間如何合作，相互合作的代理可以提高命中率而改善緩存系統的性能；
（3）緩存路由：當一處緩存代理失效時，如何將請求向其它緩存代理轉發；
（4）緩存替換算法：當緩存空間不夠時，緩存內容如何替換；
（5）緩存一致性：即緩存內容的時效性問題，如何防止緩存的內容過時；
（6）內容預取：代理如何決定從服務器或其它代理處進行內容預取以減少客戶的訪問延遲；
（7）負載平衡：如何解決網絡中的“Hot spot”現象；
（8）緩存內容：什麼樣的內容可以被緩存。
在設計Web緩存系統時，必須涉及上述問題。
3 Web緩存方案概述
3.1 Web緩存體系結構
一個Web緩存系統的性能取決於其客戶群的大小，客戶群越大，緩存的內容被再次請求的可能性就越高。相互合作的Cache組可能會提高命中率而 提高緩存系統的性能，因此緩存系統的體系結構應確保代理間能夠有效地進行合作。典型的緩存體系結構有以下幾種：層次式、分布式和混合式。
圖1 Web緩存系統體系結構圖
3.1.1 層次式緩存體系結構
Harvest項目[3]首先提出了層次式Web緩存體系結構。在層次式緩存體系結構中，Cache在網絡呈多級配置， 如圖1（a）所示。為簡單起見，假定有四級：底層Cache、局域層Cache、區域層Cache、廣域層Cache。底層是客戶/浏覽器Cache，當 客戶端Cache不能滿足客戶的請求時，該請求被轉發到局域層Cache，如果仍然得不到滿足，則該請求被轉發到區域層Cache直至廣域層Cache。 如果該請求在各級Cache中都得不到滿足，則請求最終被轉發到服務器。然後服務器對該請求的響應自頂向下地發送給客戶，在沿途的每一個中間層Cache 中留下一個副本。請求相同內容的其它請求則自下而上地進行轉發，直到在某一級Cache中得到滿足。
層次式緩存體系結構帶寬效率高，點擊率較高的Web內容可以快速高效地分布到網絡中。但該體系結構也存在一些不足[4]：
（1）建立層次式緩存體系結構，緩存服務器必須配置在網絡中關鍵的訪問點上，緩存服務器間需相互合作；
（2）每一級Cache都會帶來額外的延遲；
（3）高層Cache可能會成為瓶頸並帶來較長的排隊延遲；
（4）同一個內容的多個副本被保存在不同的Cache中，整個系統Cache空間利用率不高。
3.1.2 分布式緩存體系結構
針對層次式緩存結構的上述缺陷，一些研究者提出了分布式緩存體系結構，在這種結構中，只有低層Cache,如圖1（b）所示。文獻[5]中 的分布式Web緩存結構中，沒有超出局域層的中間Cache層，Cache之間相互協作以處理失效。為了確定將客戶請求轉發給哪一個局域層Cache來獲 取失效的內容，每一個局域層Cache保留一份其它局域層Cache中緩存內容的目錄信息，以便發生失效時將客戶請求准確地轉發到相應的局域層 Cache。緩存陣列路由協議CARP [6]（Cache Array Routing PRotocol）是一種分布式緩存方案，它將URL空間分割成不同的部分，將每一部分指定給一組松散耦合的Cache組，每個Cache只能緩存具有指 定給它的URL的Web內容，從而可以根據客戶請求內容的URL來確定將請求轉發給哪一個Cache。
在分布式緩存結構中，大多數的網絡流量都發生在網絡底層，不容易產生網絡擁塞，Cache空間利用率高，且可以更好地實現負載共享，容錯性更 好。然而，一個大規模的分布式緩存系統的配置可能會遇到幾個問題：連接次數較多、帶寬要求高、管理困難[4]。
3.1.3 混合式緩存體系結構
混合式體系結構如圖1（c）所示，同級Cache采用分布式緩存結構，相互合作。Harvest集團設計的互聯網緩存協議ICP（the Internet Cache Protocol）支持從RTT最小的父Cache或鄰居Cache中獲取相應的內容。
3.1.4 緩存體系結構的優化
研究表明[4]層次式緩存體系結構和分布式緩存結構相比，層次式緩存體系結構具有較短的連接時間，因此將較小的文檔緩存 在中間層Cache中可以減少訪問延遲；分布緩存結構具有較短的傳輸時間和較高的帶寬利用率。理想的方案就是將二者結合起來，充分發揮各自的長處，同時減 少連接時間和傳輸時間。
3.2 緩存路由
出於對Web緩存系統擴展性的考慮，大多數緩存系統將大量的Cache分散在互聯網上，這樣帶來的最大問題是如何快速地定位緩存有所需內容的 Cache，這就是緩存路由問題。該問題有點類似於網絡路由，但卻不能用同樣的方式解決。傳統的網絡路由可依地址聚類（層次式的地址表示使得地址聚類成為 可能）而進行，但是在WWW中，具有相同URL前綴或服務器地址前綴的文檔未必發送給相同的客戶，難以對路由地址進行聚類，這樣緩存路由表將大得難以管 理。此外，緩存內容不斷更新，過時的緩存路由信息將導致緩存失效。為降低Cache失效的代價，理想的緩存路由算法應該將客戶的請求路由到下一個代理，該 代理具有較高的命中可能性且位於或接近於客戶到服務器的網絡路徑上。
3.2.1 緩存路由表法
Malpani等人[7]將一組Cache組合起來，當客戶的請求被轉發到指定的Cache時，如果該Cache緩存有 請求的內容，則將其發送給客戶，否則通過ip組播將請求轉發給同組的其它Cache，由緩存有相應內容的Cache對客戶的請求進行響應，如果所有 Cache中都沒有緩存請求的內容，則該請求被轉發到源服務器。Harvest[3]緩存系統將Cache組織成層次式結構並使用 Cache解析協議ICP（Internet Cache Protocol），當發生Cache失效時，低層Cache在將客戶請求轉發到上一層Cache前，首先查詢兄弟節點Cache是否緩存有相應的內容， 以避免頂層Cache超載。自適應Web緩存系統[8]為每一個服務器建立Cache樹，樹中的Cache被組織成相互重疊的多點 傳送組，一個請求通過這些傳送組來獲取相應的緩存內容。該方法對每一個服務器構造不同的Cache樹，因此沒有根結點的超載問題，自配置性和魯棒性都比較 好。但是對點擊率較低的內容請求可能會經過較多的Cache，產生較大的Cache通信開銷，作者建議通過限制請求經過的Cache數來解決該問題。
3.2.2 哈希函數法
Cache陣列路由協議CARP[6]使用一個基於陣列成員列表和URL的哈希函數來確定一個Web對象確切的緩存地址 或一個Web對象應緩存在什麼地方。在Summary Cache[9]中，每個代理保存一個同組中其它代理所緩存內容的URL摘 要信息，該代理在轉發客戶請求時檢查這些摘要信息以確定將請求轉發給哪一個代理。為減小開銷，這些摘要信息定期進行更新。試驗表明該系統可以顯著地減少 Cache間的信息數量、帶寬消耗以及協議帶來的CPU開銷，而保持和ICP幾乎一樣的緩存命中率。
3.3 Cache替換算法
Cache替換算法是影響代理緩存系統性能的一個重要因素，一個好的Cache替換算法可以產生較高的命中率。目前已經提出的算法可以劃分為以 下三類：
（1）傳統替換算法及其直接演化，其代表算法有：①LRU（Least Recently Used）算法：將最近最少使用的內容替換出Cache；②LFU（Lease Frequently Used）算法：將訪問次數最少的內容替換出Cache；③Pitkow/Recker[10]提出了一種替換算法：如果 Cache中所有內容都是同一天被緩存的，則將最大的文檔替換出Cache，否則按LRU算法進行替換。
（2）基於緩存內容關鍵特征的替換算法，其代表算法有：①Size[10]替換算法：將最大的內容替換出 Cache；②LRU—MIN[11]替換算法：該算法力圖使被替換的文檔個數最少。設待緩存文檔的大小為S，對Cache中緩存 的大小至少是S的文檔，根據LRU算法進行替換；如果沒有大小至少為S的對象，則從大小至少為S/2的文檔中按照LRU算法進行替換；③LRU— Threshold[11] 替換算法：和LRU算法一致，只是大小超過一定阈值的文檔不能被緩存；④Lowest Lacency First[12]替換算法：將訪問延遲最小的文檔替換出Cache。
（3）基於代價的替換算法，該類算法使用一個代價函數對Cache中的對象進行評估，最後根據代價值的大小決定替換對象。其代表算法 有：①Hybrid[12] 算法：算法對Cache中的每一個對象賦予一個效用函數，將效用最小的對象替換出Cache；②Lowest Relative Value[13] 算法：將效用值最低的對象替換出Cache；③Least Normalized Cost Replacement（LCNR）[14]算 法：該算法使用一個關於文檔訪問頻次、傳輸時間和大小的推理函數來確定替換文檔；④Bolot等人 [15]提出了一種基於文檔傳 輸時間代價、大小、和上次訪問時間的權重推理函數來確定文檔替換；⑤Size—Adjust LRU（SLRU）[16] 算法：對緩存的對象按代價與大小的比率進行排序，並選取比率最小的對象進行替換。
總之，為了使Cache命中率最大化，圍繞Cache替換算法已經開展了大量的工作，但是替換算法的性能很大程度上取決於WWW訪問的特性，還 沒有哪一種替換算法能夠對所有Web訪問模式都優於其它算法。
3.4 緩存一致性
Web緩存系統可以減小訪問延遲，但帶來了一個副作用：緩存的副本提供給客戶的可能是過時的內容，因此必須有一套緩存一致性機制來確保緩存的內 容能夠及時進行更新及有效性確認，以便為客戶提供最新的內容。
目前主要有兩種緩存一致性類型：強緩存一致性和弱緩存一致性。
3.4.1 強緩存一致性
（1）客戶端確認：對於每一次訪問，代理都認為緩存的內容已經過時並隨請求發送一個“IF—ModifIEd —Since—date”報頭到服務器。如果在指定的時間後該內容發生了變化，則服務器將更新後的內容發送給代理並最終發送給客戶；如果請求內容未修改， 則發回 “304”響應，表示文檔未修改，緩存內容繼續有效。
（2）服務器確認：當服務器檢測到一個內容發生變化時，服務器向所有最近請求過該內容並有可能緩存該內容的客戶發送作廢信息[17]。 該方法要求服務器必須保存一個訪問該內容的客戶鏈表以便發送作廢信息，當客戶數量很大時，該方法將變得不適用，同時，該鏈表本身也可能過時，造成服務器向 許多已經不再緩存該內容的客戶發送作廢信息。
3.4.2 弱緩存一致性
（1）自適應TTL[18] （Time To Live）機制：通過觀察一個文檔的生存期來調整其生存時間，從而解決緩存一致性問題。如果一個文檔在一個相當長的時間內都未修改過，它往往不會再發生變 化。這樣，一個文檔的生存期屬性被賦予一個該文檔目前“年齡”（等於目前時間減去上一次修改的時間）的百分比。自適應TTL法可以將一個文檔過時的可能性 控制在＜5%的范圍內。大多數的代理服務器都使用該機制，但是這種基於文檔生存期的緩存一致性機制並不能確保緩存內容的有效性。
（2）捎帶作廢機制
Krishnamurthy等人提出使用捎帶作廢機制來提高緩存一致性的效率。他們提出了三種機制：①捎帶確認PCV[19]（Piggyback Cache Validation）機制：利用代理發送給服務器的請求來提高緩存一致性。例如，當一個代理向服務器發出請求時，它捎帶一系列緩存的但可能過時的來自該 服務器的內容進行有效性確認；②捎帶作廢PSI[20]（Piggyback Service Invalidation）機制：其基本思想是當服務器對代理進行響應時，把一系列上次代理訪問後變化的內容告訴代理服務器並由代理將這些內容作廢，從而 延長其它緩存內容在Cache中的緩存時間；③PSI和PCV混合機制[21]：該機制根據代理上次請求作廢的時間距當前時間間隔 的大小來確定采用何種機制，以實現最佳的總體性能。如果這個時間間隔較小，則使用PSI機制，否則使用PCV機制來對緩存內容進行確認。其基本原理是時間 間隔越小，與PSI一起發送的作廢數量就小，但隨著時間的增長，發送作廢的開銷將大於請求確認的開銷。
3.5 內容預取
Web緩存技術可以提高Web性能，但研究表明[22]，不管采用何種緩存方案，最大緩存命中率通常不大於 40～50%。為進一步提高緩存命中率，引入了預取技術。預取技術本質上是一種主動緩存技術，其基本思想是在處理客戶的當前請求時，利用客戶訪問內容或模 式的先驗知識，對客戶接下來的請求內容進行預測，並利用客戶請求的間隙將預測內容緩存在Cache中，從而更好地隱藏延遲，提高服務質量。
早期研究集中在浏覽器/客戶與Web服務器之間進行內容預取，當代理被引入後，人們的研究興趣轉到了代理與服務器之間的預取技術研究。研究表明 預取技術可以有效地降低客戶訪問延遲，但預取技術仍飽受爭議，原因有二：
（1）內容預取是一種實時性要求較高的任務，它主要利用客戶請求的間隔進行，而這個間隔一般情況下小於一分鐘[23]， 如果在這段時間內不能完成預取任務，預取將變得毫無意義。因此對預取算法的效率有較高的要求。
（2）內容預取是通過加重服務器負載及增加網絡流量為代價來降低客戶端響應時間的，因此對預取的准確度有較高的要求。同時，一個預取模型在確定 預取文檔的數量時，必須考慮客戶的訪問特性、服務器負載及網絡流量狀況，如果拋開這些因素來進行預取可能會造成事與願違的效果。
總之，一個良好的預取模型，效率、准確度要高，付出代價小。圍繞預取的高效性和准確性還需做進一步的研究。
3.5 負載平衡
當眾多客戶同時從一台服務器獲取數據或服務時就會發生Hot Spot現象，導致服務器性能下降甚至失效。目前處理該問題的方法大多數是使用某些復制策略將被請求的內容分貯在互聯網上，從而將負載分散到多個服務器 （代理）上[24]，避免單個服務器成為為瓶頸。
3.6 緩存內容
一個代理可能發揮多種作用，除進行數據緩存外還可以進行連接緩存和計算緩存。連接緩存指在客戶與代理、代理與服務器間使用持久連接，來減少建立 TCP連接開銷及服務器發送時的慢起動開銷，從而減小客戶訪問延遲時間[25]。計算緩存可以看作是Web服務器可以將它們的部分 服務遷移到代理，以減輕服務器瓶頸，其應用之一就是動態數據緩存，通過代理來緩存動態數據並將一部分計算遷移到代理，由代理來產生和維護緩存的動態數據， 從而提高客戶獲取動態數據的性能。
4 需要進一步研究的問題
圍繞Web緩存技術已經開展了大量的研究並取得了豐碩成果，但仍有一些問題需做進一步的研究。這些問題包括：
（1）客戶訪問模式研究：通過研究客戶的訪問模式，從而更好地進行緩存管理和內容預取，提高緩存命中率；
（2）動態數據緩存：目前Web緩存命中率不高的一個重要原因是相當一部分內容（私有數據、授權數據、動態數據等）不能被緩存。如何使得更多的 數據可以緩存以及如何減小客戶訪問非緩存頁面的訪問延遲已經成為提高Web性能的關鍵問題；
（3）Web流量特征：緩存系統的效率在於Web訪問流的時間局部性以及良好的Cache管理策略，理解Web客戶產生的負載特性對於更好地設 計和提供Web服務具有重要意義；
（4）代理配置：要獲得良好的Web性能，代理的配置至關重要，代理配置策略的理想標准是：自組織、高效路由、負載均衡、行為穩定等，圍繞此問 題還需做進一步的研究。
總之，提高Web性能的前沿研究在於開發擴展性、魯棒性、適應性、穩定性好、高效且能夠較好地配置在當前及今後網絡中的緩存方案。
