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

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

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