一種多業(yè)務(wù)web緩存器的實(shí)現(xiàn)

一種多業(yè)務(wù)web緩存器的實(shí)現(xiàn)

0web文件存儲機(jī)制緩沖區(qū)存儲技術(shù)是使所需數(shù)據(jù)更接近存儲區(qū)域的技術(shù)。通過將頻繁請求的對象保留在本地服務(wù)器中,能明顯地減少網(wǎng)絡(luò)延時和滿足用戶對網(wǎng)絡(luò)帶寬的需求。目前,Web緩沖存儲器技術(shù)已經(jīng)成為Internet基本結(jié)構(gòu)中的重要組成部分。與傳統(tǒng)的內(nèi)存緩存一樣,Web緩存的一個關(guān)鍵性問題是緩存內(nèi)容的替換策略。現(xiàn)有的大多數(shù)代理緩存器是基于傳統(tǒng)內(nèi)存頁調(diào)度機(jī)制來實(shí)現(xiàn)的,在Web環(huán)境中卻不是一個好的替換策略。其原因是Web文檔大小的可變性很大且必須在Internet上傳輸,會經(jīng)歷很大延遲,而在內(nèi)存緩存中,緩存對象(頁)的大小和通信延遲都是不變的;另外,Web文檔的訪問來自不同用戶,應(yīng)該考慮不同用戶的興趣度。因此,本文提出了一種基于對象角色的替換算法,該算法綜合考慮了文檔的大小、訪問代價、訪問頻率、最近一次被訪問的時間以及訪問興趣度,通過實(shí)驗(yàn)對性能指標(biāo)進(jìn)行測量,驗(yàn)證了該方法優(yōu)于其他文獻(xiàn)的方法。1是否可以刪除小文件。主要有以下幾種一個好的代理緩存的替換策略來源于對WWW業(yè)務(wù)訪問特性的深刻認(rèn)識,因此目前所提出的替換策略大部分來源于對WWW訪問特性的分析。a)LRU(leastrecentlyused)算法。刪除緩存中最近、最少使用的文檔。算法實(shí)現(xiàn)簡單,但沒有考慮文檔的尺寸和訪問代價等。b)LFU(least-frequently-used)算法。最先移出緩存中最少使用的文檔,其優(yōu)點(diǎn)是很簡單,其缺點(diǎn)除了LRU的缺點(diǎn)以外,如果沒有失效機(jī)制,可能使過時的文檔永遠(yuǎn)留在緩存器里。c)SIZE算法。刪除緩存中尺寸最大的文檔,刪除大的文檔可以緩存更多的小文檔,從而提高緩存命中率。其缺點(diǎn)是字節(jié)命中率偏低,可能會使得小文檔永遠(yuǎn)留在緩存中。d)Hybrid算法。主要目標(biāo)是降低總的訪問延遲,通過一個函數(shù)來計算每一個文檔的替換權(quán)值。在進(jìn)行替換操作時,刪除具有最小替換權(quán)值的文檔,而來自服務(wù)器s的文檔p的函數(shù)值為F=(cs+wbbs)(np)Wnzp(1)F=(cs+wbbs)(np)Wnzp(1)其中:cs是與服務(wù)器s連接的代價;bs是到服務(wù)器的帶寬;np是文檔p的請求次數(shù);zp是文檔p的尺寸;wb和wn是常量。該算法綜合考慮了文檔的尺寸、文檔的訪問代價以及文檔的訪問頻率等,但最大的缺點(diǎn)是參數(shù)計算復(fù)雜。e)Greedydual-size算法。由最近最少使用算法LRU發(fā)展而來,該算法對每一存儲在Web緩存中的文檔p設(shè)置了一個關(guān)聯(lián)權(quán)值H,當(dāng)需要將某文檔存儲到Web緩存時,初值H被設(shè)置為1/size(總為正值);當(dāng)進(jìn)行替換時,具有最低H值的文檔將被替換,同時所有存儲在緩存中的文檔H值減去某一最小值(被替換文檔的H值);如果文檔被再次訪問,則其H值恢復(fù)為初值。因此,最近使用的網(wǎng)頁將比長時間未用的網(wǎng)頁具有更大的H值,通過時間的推移逐漸減小H值并在網(wǎng)頁再次被存取時恢復(fù)。其缺點(diǎn)是沒有考慮文檔使用率和網(wǎng)絡(luò)延遲。2緩慢機(jī)程序?qū)崿F(xiàn)現(xiàn)有算法大多基于傳統(tǒng)內(nèi)存緩存算法,雖在實(shí)際中取得了一定的效果,但均存在不足之處。a)對不同站點(diǎn)的文檔考慮不足。例如,設(shè)緩存器中有兩個大小相同的文檔a和b,a來自用戶感興趣的、經(jīng)常訪問的站點(diǎn)Sa,b來自用戶很少訪問的網(wǎng)站Sb,經(jīng)過一段時間的訪問,兩個文檔的替換權(quán)值H相等,當(dāng)有替換發(fā)生時,應(yīng)盡量將文檔a留在緩存存儲器中,目前的算法并不能做到這一點(diǎn);其次,同一個Web站點(diǎn),不同的緩存器有著不同的訪問量。通過分析得出,每一個緩存器一般存在著固定的用戶群體,用戶經(jīng)常使用相同的緩存器去訪問他們感興趣的網(wǎng)站,不同的用戶對不同的Web站點(diǎn)有著不同的興趣度,從而不同的緩存器對不同的Web站點(diǎn)訪問興趣度也不同。b)沒有考慮文檔最近一次訪問的時間。例如有一個文檔雖然它的訪問次數(shù)很大,而其權(quán)值也比較大,但是由于近期內(nèi)沒有被訪問,依據(jù)Web訪問的時間局部性可知在將來的一段時間內(nèi)可能訪問不到,那么它的存在就會阻止其他的文檔進(jìn)入緩存。針對以上問題,本文綜合考慮Web文檔對象特性,將每個文檔賦予不同的角色,把文檔的大小、訪問頻率、訪問興趣度、最近一次被訪問的時間以及訪問興趣度作為角色的屬性,每個角色根據(jù)其所具有的屬性計算其價值。本文提出的算法根據(jù)每個文檔的角色值R(p)來評估Web文檔的價值。2.1膨脹因子p當(dāng)某文檔被再次點(diǎn)擊時,增加R(p)值,使其大于新進(jìn)入文檔r的權(quán)值,即R(r)<R(p)。定義文檔的權(quán)值公式為R(p)=L+d(p)×c(p)/s(p)(2)其中:c(p)為文檔p的開銷(下載時間、占用頻帶寬等);s(p)為文檔p的大小;d(p)為文檔p的訪問次數(shù);L為一個膨脹因子。為防止被多次點(diǎn)擊的文檔權(quán)值過大,應(yīng)設(shè)置d(p)的最大值maxd,這一設(shè)置可以防止早期文檔永久地保留在緩存池中,maxd值的大小可以根據(jù)實(shí)際運(yùn)行情況或經(jīng)驗(yàn)予以調(diào)整。2.2不同站位的web訪問行為分析Web站點(diǎn)的訪問規(guī)模不平衡,通常不足10%的站點(diǎn)承擔(dān)著80%以上的用戶訪問,圖1為Boeing公司W(wǎng)eb訪問結(jié)果。分析表明,不同站點(diǎn)用戶的訪問興趣度不同。訪問興趣度定義如下:I(p)=Ds/Us(3)其中:Ip表示文檔p的訪問興趣度;Ds表示緩存服務(wù)器s的總訪問規(guī)模;Us表示緩存服務(wù)器s的不重復(fù)訪問規(guī)模。2.3不同函數(shù)對權(quán)值函數(shù)的影響計算文件的最近一次訪問時間對角色值R(p)造成的影響。令t=tknow-tlast(單位為s),tnow為進(jìn)行替換的時間,tlast為文檔的最近一次訪問時間。f(t)應(yīng)該隨著t的增大而減小,不過f(t)取值不當(dāng)會把權(quán)值函數(shù)中其他項(xiàng)的影響淹沒掉,使得算法基本上與LRU算法類似。考慮到Web請求具有時間局部性:大約三分之一的再度訪問發(fā)生在上次訪問的一個小時內(nèi);大約三分之二的再度訪問發(fā)生在上次訪問后的24小時內(nèi)?；谶@種規(guī)律把t分為三種情況來考慮,f(t)表示為f(t)=?????h1(t)0≤t≤3600h2(t)3600<t<86400h3(t)t>86400(4)f(t)={h1(t)0≤t≤3600h2(t)3600<t<86400h3(t)t>86400(4)其中:h(t)是隨時間變化的函數(shù)。t=0表示緩存中沒有的文件;0<t<3600表示上次訪問發(fā)生在一個小時以內(nèi)的文件;3600<t<86400表示上次訪問發(fā)生在24小時以內(nèi)的文件;t>86400表示上次訪問發(fā)生在一天前的文件。從式(4)可以看出,只要適當(dāng)?shù)剡x擇以上三個函數(shù)即可。如果函數(shù)取值太小,就不會表現(xiàn)出上次訪問時間對函數(shù)值的影響;相反,如果取值過大,就會淹沒其他因素的影響。當(dāng)0<t<3600時,認(rèn)為這種文件在近期內(nèi)還會訪問,因此所占的比重應(yīng)該比較大,選擇常數(shù)0.5;當(dāng)3600<t<86400和t>86400時,由于這兩個區(qū)間內(nèi)t的取值差距太大,為了減小這種差距,對t取對數(shù),得f(t)為f(t)=C(logt)α=?????0.50≤t≤36001/logt3600≤t≤864001/2logtt>86400(5)f(t)=C(logt)α={0.50≤t≤36001/logt3600≤t≤864001/2logtt>86400(5)考慮到文檔的原始大小對權(quán)值函數(shù)的影響比較大,使得較大的文檔被替換出去的可能性也相對增大,降低了字節(jié)命中率。為了提高算法字節(jié)命中率、減小算法對文檔大小的依賴性,把文檔大小改為log(s(p)),則文檔p最終的角色值計算方法為R(p)=L+d(p)×c(p)×I(p)×f(t)/log(s(p))(6)3用戶訪問屬性見表1本文以緩存命中率(H)和字節(jié)命中率(BH)兩個指標(biāo)來衡量緩存算法的性能。H=r/R(7)其中:r為命中的次數(shù);R為用戶訪問文檔的總次數(shù)。BH=b/B(8)其中:b為命中的字節(jié)數(shù);B為用戶訪問文檔的總字節(jié)數(shù)。緩存命中率與字節(jié)命中率的側(cè)重點(diǎn)不同,緩存命中率側(cè)重于減少用戶的響應(yīng)時間,而字節(jié)命中率則著眼于減少帶寬開銷。4實(shí)驗(yàn)分析4.1動態(tài)訪問序列生成Trace驅(qū)動模擬是基于某些運(yùn)行的代理服務(wù)器或Web服務(wù)器上對用戶訪問請求的跟蹤記錄文件,經(jīng)過有選擇的預(yù)處理(如過濾掉動態(tài)信息等)生成訪問序列,利用這組訪問序列作為緩存算法模擬系統(tǒng)的輸入數(shù)據(jù)、仿真程序的流程如圖2所示。4.2不同算法在樣品記錄中的性能對比實(shí)驗(yàn)采用公有的軌跡文件對算法進(jìn)行比較,它們分別由DEC和NASA的代理服務(wù)器采集。DEC代理服務(wù)器包含的數(shù)據(jù)是從1996年9月1日～1996年9月22日,每個域記錄了請求時間、來自服務(wù)器的服務(wù)時間、大小和協(xié)議等。NASA數(shù)據(jù)為1995年8月1日～1995年8月31日的所有訪問信息。對日志文件先進(jìn)行過濾處理,去除CGI類的不可緩存的文件,然后將處理后的日志作為輸入,軌跡的基本統(tǒng)計量如表1所示。在緩存命中率和字節(jié)命中率兩個性能指標(biāo)上對ORB算法和以往的算法(LRU、LFU、SIZE、Hybird、GD-SIZE)作了對比,圖3～6中顯示了LRU、LFU、SIZE、Hybird、GD-SIZE和ORB算法在兩種軌跡下的命中率情況。從圖3～6中可以看出,在緩存命中率方面,ORB、GD-SIZE、LFU這三種算法要明顯優(yōu)于其他算法,而Hybird算法則表現(xiàn)最差。Hybird算法由于沒有考慮文檔訪問的時間局部性,緩存命中率較低。式(1)中參數(shù)zp采用的是文檔的原始大小,對文檔的大小依賴性比較大,這樣較大的文檔被替換出去的可能性就相對較大,因此就導(dǎo)致算法的字節(jié)命中率較低。隨著緩存尺寸的增加,SIZE和Hybrid算法的字節(jié)命中率增加的幅度比較明顯,因此這兩種算法適用于緩存尺寸較大的系統(tǒng)。ORB算法由于考慮到各種因素,性能表現(xiàn)始終很好;在考慮字節(jié)命中率時,ORB算法由于調(diào)節(jié)權(quán)值函數(shù)的參數(shù),性能也比其他算法