WWW代理伺服器上快取同步機制之分析與設計

Abstract

WWW的興起為網路流量帶來驚人的成長，造成網路的壅塞與存取延遲的增加。快取（cache）技術可以減低網路流量，減少存取延遲與減輕伺服器的負荷，在網際網路上被廣為使用，然而要保證快取內的資料正確性，快取同步技術隨之興起。目前常見的技術有：TTL、Adaptive TTL、Poll、Poll-Each-Read、Callback與Lease六種，快取同步技術中的快取存活時間是一項很重要的參數，然而如何決定快取存活時間是一種問題。在本篇論文，我們用數學分析快取存活時間與快取錯誤率、快取空間與頻寬的使用的關係，藉由分析出來的式子來幫助我們決定快取的存活時間。此外，我們也提出了一個快取同步的機制：Selective Callback，在此機制中，我們僅對最受歡迎的文件做無效通知的動作，以減少Callback演算法中無效通知訊息的數量。Selective Callback可以設定成非強一致性同步機制，同時也可以成為強一致性同步機制。在變動快速的環境下，Selective Callback可以更有效的節省頻寬的使用。

Caching documents can reduce both network traffic and document access latency. However, to make sure cached copy to be useful, cache consistency must be maintained. There are two types of cache consistency mechanism: weak cache consistency and strong cache consistency mechanism. Weak cache consistency mechanism includes TTL (Time-To-Live), Adaptive TTL, and Poll and strong cache consistency mechanism includes Poll-Each-Read, Callback and Lease. How to determine the cache lifetime in TTL approach is a trade-off problem. We analyze the stale probability, state space and bandwidth usage under client-proxy-server caching structure and derive three formulations to help us to determine a suitable cache lifetime. We also propose a new cache consistency approach, called as Selective Callback. This approach can reduce the bandwidth usage when the update frequency is large enough. The simulation is given to show the effectiveness of Selective Callback approach.