快取快取排它策略應用於網頁代理伺服器

代理伺服器时间:2021-03-03 阅读:()

快取排它策略應用於網頁代理伺服器

快取排它策略?用於??代理伺服器

Eviction Policy on Cache for Web Proxy Server

段裘?*?承丞 ?嘉言

Chiu-Ching Tuan* Chan-Chen Huang Chia-Yan Chien

?立?北科技大??子工程系*

??樵 Chen-Chau Yang

?立??科技大??子工程系

摘要

有?於快取空?的排?效?以及各??物件群?的再用程度不一等因素下,本研究提出一「快取排它策略」 ?用於??代理快取伺服器(WebPCS) ,藉以提?快取系?效能。

本研究主要的方法如后, 1)先透?Proxy 2日???分析?本,?分析WebPCS之群?式快取效能。 2)依前???,再?立出「快取排它??」 ?件,用以????物件作?快取?象。本快取效能模?之比??象???LRU vs.排它式LRU。

?由模??果得知,?排它???件??C3、 C4或C5之?,有高於99.5%用?端可?益於WebPCS之命中率上??平均等待??下降之??;但是,最多只?牲27%用?端可能受?於命中高容量物件的??而?致WebPCS之?料量命中率下降。此一研究成果??,?排它策略置於快取替??制之前,可?期改善系?的快取效益。

???:??代理快取伺服器、快取排它策略、快取替??制、存取日??、 LRU替?

法。

投稿受理??:90年10月28日 ?查通???:91年2月5日

ABSTRACT

This paper proposed a novel “cache eviction policy” CEP designedfor web proxy cache server WebPCS to improve the performance on cachingobjects First, we investigated the effects of grouped objects on cacheperformance of WebPCS through the on-line access logs of Proxy2 suppliedby NTUST Then from the data investigated as above, we could set the valuesof threshold with which the evictor could determine whether to evictobjects the server downloadedLast, we have selected two types ofreplacements policy, the conventional LRU LRU and evicted LRU LRU-evict,to be evaluated by the simulation system for comparing their cacheperformance, .

The experimental results shows that more than 99.5%of clients mayobtain more benefits, including the hit ratio rose and the averagelatency time fell, as the threshold conditions of LRU-evict were set tobe C3, C4, or C5On the other hand, at most only 27% of clients may losea chance to hit high-volume objects; therefore, the byte-hit ratio wouldbecome lower These findings confirmed that the overall performance ofcache systemcouldbe promotedby locating the CEP aheadof the replacementmechanism like LRU for intercepting low reusable objects.

Keywords:web proxy cache server, cache eviction policy, cachereplacement policy, access logs, LRU replacement壹、 ??

全球???(World Wide Web, )於1989年由?洲核子研究委??(CERN)的TimBerners-Lee所倡?[5] ,其意?建置一?分散式超媒?系?可?由???路快速存取散?在全球各地的研究?料。 ?后, Marc Andreessen和Eric Bina於1993年在美??家超??算?用中心(NCSA)??出??式超媒?文件的????器NCSA Mosaic[3] ,?此引??入高速成?的新?元。

一、之?展概?

根?我??策?F IND研究?告[17] ,2001年1月全球??的主??已超?一?台(10957?部) ,而台?也突破百?台(109?部)的成?。此外,累?至2001年9月底前,我????路用??已?755??且普及率攀升上34%。其中,台????(TANet)之用??就高?285?且季成?率?持7%。同年6月,我??外?路??之???已高?4.06 Gbps且成?率?23.6%,而?往美?之??以2.74 Gbps居冠。

??如何,?多的研究??均?示出???路之使用已是一股?不可?的新潮流且?影?人?生活型?甚?,而各?也都??地??因?之道。

?成功地加速了???路的使用?潮,然而相?於使用人口的快速激增,?行???路基?建?的速度??落后於??的需求。在?路??不足之??下更加?化?路的服?品?,分析其原因有如下??:

1.???容逐?地使用高容量的多媒?物件;

2.??伺服器端引用自?的??推播(push)?制;

3.??的商?系?大幅地整合?且改以??平台提供全球性?子商?作跨?服?;

4.???路服?供?商(ISP)群起?逐市?更加吸?大量新?的?路使用人口。

相?於???路服?品?的低弱,?了改善?路品?也有??相?的研究??,例如:

1.?路基?建?:建置???路?研?更高速的?路??技?,例如??????(Cable Modem)和非同步?位用???(ADSL) 。

2.?路?定:改良?有的通??定或者??更具效率的新?路?定。

3.?料??技?:????效率更佳的???比更大的??技?,以促使??后的高容量多媒?物件於?路???,可大幅地降??路??的使用。

4.??快取(cache)技?:??快取?制是利用?料?份的概念??到加速物件存取??省?路??的目的。

上述研究??中,以??快取在不????路基?建?之下,就可以立即得到成效?且?易地?用在?有的??代理快取伺服器(Web Proxy Cache Server, WebPCS)之中。因此目前的????大都透?快取系??加快存取速度??少??端伺服器作重?的物件要求,以期使有限的?路??作更有效的?用。

二、本研究的主要目的?作法

有?於WebPCS之快取效能??行之服?品?具有??性的影?,所以本研究?先以??物件之「?料量」大小?分群?;再佐以群?物件?估因子作快取分析,以期研判出影?快取效能的??要素,藉以??出各不同群?物件所呈?出的再用性[10, 11] 。

依?上述??物件群?再用性之分析事?,再制定一新式的「快取排它策略」(Cache Eviction Policy)用以改善WebPCS?行快取的效能。

本研究主要的方法?步?概述如下:

1.先以Squid Proxy System[12]??例,??述??式快取系?之?作模式。

2.以群?物件方式?分析WebPCS之快取效能,包括「群??存取比」、「群??命中比」、「群???料量命中比」 ? 「群?平均使用?」等四?。

●分析?本?台?科大Proxy2日??。

3.依前???分析,?立出群?物件影?快取效能的??,??以研?快取排它策略、效能?量因子?效能比??象(如下) 。

●??LRU vs.排它式LRU(LRU-evict) 。

4.?作一?窗式效能模?系?,用以???探?此快取排它策略的??效?。

三、本文之章?架?

本文之章??序如后,第????Squid??式??快取系?;第??以Proxy2 日??分析WebPCS之快取效能;第肆?探究快取排它策略?系?效能分析;最后一?,第伍?作扼要??。

?、 Squid??式??快取系?

本??明TANet校??路架??例???式WebPCS之?作方式。

一、 TANet校??路?例架?

?一所示?TANet校??路?例架?,其?外之?路??方面,台?科大校???以一?T345Mbps?接至TANet,而TANet再??

?一TANet校?WebPCS之??架??:以台?科大Proxy2?例

?STM-1155.5×2 Mbps跨接至美?[18] 。

於台?科大???,?有?部快取容量各?20.6 GB之本地WebPCS,分?是??快取??外?域物件的//0>. . tw(Proxy)?快取????域物件的proxy2.//. (Proxy2) [16] 。至於Proxy2於Squid系???中所?定的?同式WebPCS包括如下:

●兄弟?同WebPCS:

兄弟?同WebPCS?//. . tw?//. . tw,其?作模式是以「快取摘?」 (caching digest)方式???所?存取的??物件存在?否[12] 。

●父?同WebPCS:

以//.?proxy1.//.??父?同WebPCS,?者?是以「?替式」 (round robin)的?作模式作??取父?同的??。

二、 ??式快取系?之?作

WebPCS之使用??可以有效地提?????的服?品?,其??可加快??下?的速度;?外可?少?相同的物件作重?性要求,藉以舒??端伺服器的工作?荷。此外,尚可降低?外?路??的使用,以提高???作效能??足?域?用?端群的需求。

?行所用的快取系?可分?用?端之??器快取??域?路中心之WebPCS等??,而WebPCS之系??品中?著名的有Aratech-2000 、Compaq-b17、Dell-100、 IBM-330、Lucent-100z、 Microbits-P、 Microsoft-2、 NetApp-C6100、 Squid-2.4.D4以及Swell-1450等[6, 19-28] 。

快取系?架?可?照?一之?例,?WebPCS接收到由?域?用?端所?出的???求?,WebPCS?先?查????料是否存在於本地伺服端的快取硬碟中。

?由??物件搜?之后,若是快取命中(cache hit) ,?直接地取用本地?料??回?用?端。反之,若?快取?失(cache miss) ,?WebPCS?向上??同快取之WebPCS或者向?域外之?端??伺服器代????求??候?料回?。

稍后,?WebPCS收到回?的??物件,除了?它再回??用?端之外;同?,?之??副本存入本地的快取硬碟中,以等待?后若再度被取用?能直接命中而快速的回??用?端。

至於?? 「快取替?」 (replacement)策略的研究,目前大致可???三?:

1.沿用??式策略,例如LRU、 LFU?FIFO等。

2.依多??特徵次序作比?,例如LOG2-Size和HYPER-G[13]等。

3. 制定?算公式作??量基?, 例如 LRFU[4] 、 LUV[11] 、LNC-R-W3[7,8]?Grey-based[9]等。

惟?行的WebPCS系?,例如Squid所用之替?策略仍以??式LRU?主,原因在於LRU演算程序???易且快速,但是其快取效能通常?不彰?。

再者,WebPCS所快取的各???物件,其?料量大小的相差?距甚大(由?MB至?KB) ;且各??物件原始?址(URL)所在的伺服器端也散?全球,故??物件下?所需要的等待??就存在更大的差距。?常使得不耐久候的用?端??常中??求服?,而更加?化?路的壅塞?浪??路??的使用。

因此,一效率佳的??快取技?可??地?少??物件在?路上的重???,?且可加速用?端存取???料。所以,有?於高效能??快取或?取技?的研?,目前而言仍然?具有高度的研??值。

?、 WebPCS之快取效能分析

由於WebPCS所快取的物件?型繁多,?且???多的用?端群所??的??意向也不相同,故WebPCS很?以?知其用?端群於后?中?存取??之??;也不易去?估一???物件??保留於快取中的使用?值。