基于用戶訪問(wèn)行為分析的代理緩存系統(tǒng)

基于用戶訪問(wèn)行為分析的代理緩存系統(tǒng)

1代理服務(wù)器存儲(chǔ)機(jī)制隨著互聯(lián)網(wǎng)的發(fā)展，世界上的移動(dòng)網(wǎng)絡(luò)網(wǎng)絡(luò)已經(jīng)成為互聯(lián)網(wǎng)上的主要應(yīng)用程序。然而，許多信息訪問(wèn)也突出了互聯(lián)網(wǎng)現(xiàn)在存在的問(wèn)題。由于網(wǎng)絡(luò)帶寬不足，用戶無(wú)法閱讀網(wǎng)站網(wǎng)站的web信息。解決這一問(wèn)題的途徑是緩沖區(qū)用戶訪問(wèn)社交網(wǎng)絡(luò)的狀態(tài)。作為一個(gè)副本，緩慢消息被保存為副本。下一次訪問(wèn)時(shí)，用戶無(wú)需連接到web服務(wù)的記錄網(wǎng)站，而是信任第一次保留的那個(gè)鏈接。這降低了訪問(wèn)延遲，降低了web服務(wù)器負(fù)荷。此外，還釋放了要占用的網(wǎng)絡(luò)帶寬，以改善網(wǎng)絡(luò)過(guò)載現(xiàn)象。一般說(shuō)來(lái),有3種緩存實(shí)現(xiàn)方式,即客戶端、服務(wù)器端以及代理服務(wù)器端緩存機(jī)制.客戶端的緩存通常是捆綁在瀏覽器上的,如Netscape公司的Navigator和Communicator瀏覽器、Microsoft公司的InternetExplorer瀏覽器都提供了緩存用戶一定時(shí)期內(nèi)訪問(wèn)過(guò)的主頁(yè)信息的緩存機(jī)制.這種緩存機(jī)制的主要特點(diǎn)是緩存的每個(gè)主頁(yè)信息長(zhǎng)度有限、實(shí)現(xiàn)的一致性策略和替換策略都比較簡(jiǎn)單,它經(jīng)常提供給用戶的是一些失效了的陳舊(stale)信息,因此是一種不大可靠的緩存機(jī)制.服務(wù)器端的緩存機(jī)制是和Web服務(wù)器軟件捆綁在一起的,通常在服務(wù)器上實(shí)現(xiàn)二級(jí)或三級(jí)cache作為緩存空間,它比存放主頁(yè)的硬盤具有更高的訪問(wèn)速度.當(dāng)服務(wù)器響應(yīng)用戶對(duì)某個(gè)主頁(yè)的訪問(wèn)請(qǐng)求后,也在緩存空間保留一個(gè)副本,下一次如果有相同的訪問(wèn)請(qǐng)求,就直接將緩存空間保存的副本提供給用戶.這種緩存機(jī)制能夠適當(dāng)?shù)亟档驮L問(wèn)延遲,但是對(duì)服務(wù)器的要求較高,增加了服務(wù)器軟件的復(fù)雜度.最后一種緩存方式是代理服務(wù)器緩存機(jī)制,簡(jiǎn)稱為代理緩存.用戶對(duì)某個(gè)網(wǎng)站的主頁(yè)訪問(wèn)請(qǐng)求到達(dá)代理服務(wù)器后,一旦服務(wù)器存放有該主頁(yè)的副本,服務(wù)器直接提供給用戶作為響應(yīng);如果服務(wù)器沒(méi)有該主頁(yè)的副本,則將請(qǐng)求重定向到駐留網(wǎng)站,獲得該主頁(yè)給用戶,并且在服務(wù)器上保存一個(gè)副本.這種緩存機(jī)制的工作方式如圖1所示,它具有多個(gè)用戶可以共享所有主頁(yè)副本的特點(diǎn),降低了訪問(wèn)延遲和費(fèi)用.同時(shí),由這些代理服務(wù)器提供的緩存服務(wù)還可以連接在一起,構(gòu)成層次型緩存模型,在Internet緩存協(xié)議(internetcacheprotocol,ICP)中詳細(xì)描述了這種模型的規(guī)范.典型的代理緩存機(jī)制有Colorado大學(xué)實(shí)現(xiàn)的HarvestObjectCache、Netscape公司的NetscapeProxyServer以及在Harvest基礎(chǔ)上NLANR開發(fā)的Squid緩存系統(tǒng)等.比較3種緩存方式,代理緩存機(jī)制是解決WorldWideWeb訪問(wèn)速度慢、服務(wù)器負(fù)載重和網(wǎng)絡(luò)阻塞等問(wèn)題的最好方法.它具有訪問(wèn)延遲低的優(yōu)點(diǎn),因?yàn)橥ǔ４矸?wù)器都是和客戶機(jī)在同一個(gè)局域網(wǎng)內(nèi),主頁(yè)信息從代理服務(wù)器到達(dá)客戶機(jī)的延遲時(shí)間可以忽略不計(jì).其次,由于緩存由專門的代理服務(wù)器實(shí)現(xiàn)和維護(hù),緩存機(jī)制可以占用較大的磁盤空間,有利于存放日益增多的大容量多媒體信息.第三,緩存的一致性維護(hù)策略和替換策略可以比較復(fù)雜,從而提高命中率和減少顛簸.最后,由所有代理服務(wù)器構(gòu)成的層次型緩存,可以將最接近用戶的主頁(yè)副本返回給用戶,增加了信息的本地化(locality),也降低了訪問(wèn)延遲.但是,目前的一些緩存系統(tǒng)都是基于用戶對(duì)某個(gè)主頁(yè)的訪問(wèn)進(jìn)行緩存的,并以此來(lái)計(jì)算命中率,不能真正反映用戶的訪問(wèn)行為,因此性能仍然比較低,通常命中率只在40%左右.我們認(rèn)為一個(gè)高效、實(shí)用的代理緩存機(jī)制必須記錄和分析用戶的訪問(wèn)行為,在提高命中率的同時(shí)也要考慮降低用戶對(duì)主頁(yè)的訪問(wèn)延遲.在分析用戶訪問(wèn)行為的基礎(chǔ)上,我們?cè)O(shè)計(jì)了一個(gè)基于網(wǎng)站圖模型的代理緩存系統(tǒng)URAC(userrequestattentivecache).在這一系統(tǒng)中,每個(gè)網(wǎng)站被當(dāng)成一個(gè)以用戶訪問(wèn)過(guò)的該網(wǎng)站主頁(yè)為元素的向量,緩存的一致性維護(hù)是由服務(wù)器后臺(tái)進(jìn)行的,而緩存的替換算法以整個(gè)向量為對(duì)象進(jìn)行計(jì)算.同時(shí),對(duì)某個(gè)網(wǎng)站的主頁(yè)存放目錄結(jié)構(gòu)按命中率進(jìn)行重新排列,提供用戶最短訪問(wèn)路徑獲得所需主頁(yè).本文其他各節(jié)的組織如下:第2節(jié)提出網(wǎng)站圖模型;第3節(jié)對(duì)用戶訪問(wèn)行為進(jìn)行分析,提出URAC的設(shè)計(jì)思想;第4節(jié)介紹URAC的工作原理和體系結(jié)構(gòu);第5節(jié)將對(duì)URAC進(jìn)行性能評(píng)價(jià);最后本文給出結(jié)論.2http-ghp的實(shí)現(xiàn)HTTP協(xié)議將WWW上所有的信息資源以一個(gè)統(tǒng)一的資源識(shí)別符表示,即URI(uniformresourceidentifier),用戶的每個(gè)訪問(wèn)請(qǐng)求都是以這個(gè)URI為請(qǐng)求地址的,一個(gè)HTTP請(qǐng)求地址可以描述如下:其中host是某個(gè)網(wǎng)站的域名或者IP地址;port是提供HTTP協(xié)議服務(wù)的TCP/IP端口號(hào),缺省時(shí)為80;abspath是訪問(wèn)請(qǐng)求的絕對(duì)路徑,絕對(duì)路徑由“/”開頭,它定位到某個(gè)網(wǎng)站維護(hù)的某個(gè)主頁(yè);相對(duì)路徑頭部沒(méi)有“/”,它描述了某個(gè)網(wǎng)站的所有主頁(yè)的目錄結(jié)構(gòu),同時(shí)通過(guò)引入“;”和“?”字符,提供HTTP協(xié)議中GET等方法處理需要的參數(shù)和輸入串.已有的一些緩存系統(tǒng)都是針對(duì)用戶訪問(wèn)的某個(gè)具體的主頁(yè)進(jìn)行緩存,實(shí)際上要求用戶在下一次訪問(wèn)這個(gè)主頁(yè)時(shí)也必須清楚該主頁(yè)的URI,這將影響代理緩存系統(tǒng)提供資源共享的性能.由于WWW本身具有網(wǎng)絡(luò)連接特性,尤其是在主頁(yè)中提供的超鏈接(hyperlink)可以實(shí)現(xiàn)主頁(yè)的互相引用,使用戶從一個(gè)URI轉(zhuǎn)到另一個(gè)URI,這個(gè)特性有助于用戶對(duì)WWW更方便地訪問(wèn).為此,我們提出了描述WWW的網(wǎng)站圖模型Site-Graph,通過(guò)模型的實(shí)現(xiàn)可以在代理緩存服務(wù)器上仍然保持主頁(yè)在原始網(wǎng)站的相互引用關(guān)系,并指導(dǎo)用戶更快地找到需要的信息.一般說(shuō)來(lái),由于提供HTTP服務(wù)的軟件在服務(wù)器上運(yùn)行時(shí)需要定義一個(gè)入口主頁(yè)以及主頁(yè)存放的路徑,如CERNHTTPD在srm.conf配置文件中通過(guò)DirectoryIndex和DocumentRoot設(shè)置入口主頁(yè),在access.conf配置文件中通過(guò)〈Directory〉〈/Directory〉設(shè)置存放路徑.網(wǎng)站的所有主頁(yè)信息則通過(guò)HTML定義的Anchor標(biāo)志(即〈A〉〈/A〉,〈HREF〉,〈SRC〉等)連接在一起,這樣,一個(gè)網(wǎng)站就可以看成一個(gè)有向圖Wn=(P,E),它的頂點(diǎn)(pi∈P,i=0,…,s)是存放在網(wǎng)站上的任一主頁(yè),其中p0是入口主頁(yè).有向邊(eij∈E,i,j=0,…,s)表示通過(guò)主頁(yè)pi可以訪問(wèn)到主頁(yè)pj.一個(gè)有5個(gè)可訪問(wèn)主頁(yè)的網(wǎng)站可以如圖2(a)描述.由于WWW本身是一個(gè)網(wǎng),Wn是一個(gè)網(wǎng)狀圖,根據(jù)對(duì)HTML的Anchor標(biāo)志進(jìn)行分析,任一頂點(diǎn)都可能存在自身回路、由該頂點(diǎn)引出的邊以及到達(dá)該頂點(diǎn)的邊.實(shí)際上每個(gè)網(wǎng)站不是獨(dú)立存在的,在網(wǎng)站地址為host1內(nèi)的某個(gè)主頁(yè),可以通過(guò)httpURI訪問(wèn)到網(wǎng)站地址為host2的某個(gè)主頁(yè),這樣就存在如圖2(b)所示的一條從Wn的頂點(diǎn)p2到Wm某個(gè)頂點(diǎn)的邊,我們稱這種網(wǎng)站為外連網(wǎng)站,與之相對(duì)的,只在網(wǎng)站內(nèi)部互相連接的就稱為孤立網(wǎng)站.在本文,我們主要討論孤立網(wǎng)站的代理緩存系統(tǒng).這里我們定義pj的前趨集PVS為所有以pj為終點(diǎn)的有向邊的源點(diǎn)pi的集合,定義pj的后繼集SVS為所有以pj為源點(diǎn)的有向邊的終點(diǎn)pi的集合.同時(shí)定義那些在外連網(wǎng)站中可以到達(dá)相鄰網(wǎng)站的頂點(diǎn)集為外連頂點(diǎn)集EVS:O(Wn)=P(Wni)∩P(Wn),這樣,對(duì)一個(gè)外連網(wǎng)站限制在同一個(gè)網(wǎng)站內(nèi)部進(jìn)行分析時(shí),我們用P(Wn)\O(Wn)來(lái)描述其網(wǎng)站內(nèi)頂點(diǎn)集.進(jìn)一步,我們用一個(gè)道路矩陣來(lái)表示網(wǎng)站圖,其中:m是用來(lái)唯一表示網(wǎng)站圖Wm的整數(shù),pj∈P(Wm)表示pj是Wm的一個(gè)頂點(diǎn).即,如果存在pi到pj的有向邊,就將aij賦值為1,否則取其最短路徑.此外,我們?yōu)槊總€(gè)頂點(diǎn)pi定義一個(gè)訪問(wèn)計(jì)數(shù)器c(pi),用于后面的訪問(wèn)行為分析和替換策略設(shè)計(jì).下面描述網(wǎng)站圖的生成和維護(hù)算法當(dāng)一個(gè)用戶提交請(qǐng)求到代理緩存服務(wù)器時(shí)如果是對(duì)一個(gè)新的網(wǎng)站的訪問(wèn),一個(gè)新的網(wǎng)站圖就從此建立,否則在原來(lái)的網(wǎng)站圖上進(jìn)行增加頂點(diǎn)的操作.圖3給出了一個(gè)網(wǎng)站圖的生成過(guò)程和道路矩陣的增長(zhǎng)過(guò)程.生成與插入算法:同時(shí),如果代理緩存進(jìn)行副本替換時(shí),一些副本將被換出,體現(xiàn)在網(wǎng)站圖上為某些頂點(diǎn)將被刪除,下面給出刪除算法:3跟蹤用戶的訪問(wèn)行為,并正確實(shí)現(xiàn)用戶的訪問(wèn)軌跡產(chǎn)生這樣結(jié)果的原因是一般緩存系統(tǒng)針對(duì)孤立的主頁(yè)進(jìn)行操作,這些主頁(yè)在緩存空間是互不相關(guān)地存放的,緩存策略不能自動(dòng)地發(fā)現(xiàn)哪些信息有用,而哪些信息可以被替換出去.同樣,這種互不相關(guān)的存放方式不能幫助用戶以最短的訪問(wèn)路徑獲得信息即使用戶所需的主頁(yè)已被緩存經(jīng)過(guò)多次的連接調(diào)用才能得到主頁(yè)副本,并未減少訪問(wèn)延遲時(shí)間.因此,需要記錄用戶的訪問(wèn)行為并進(jìn)行分析,以此指導(dǎo)用戶最快獲得目標(biāo)主頁(yè).考慮到用戶的訪問(wèn)具有局部性特點(diǎn),在一次連續(xù)的訪問(wèn)過(guò)程中,訪問(wèn)請(qǐng)求通常是到達(dá)同一個(gè)網(wǎng)站的,以網(wǎng)站為單位分析用戶訪問(wèn)行為可以作為緩存系統(tǒng)的有效輔助信息,這也是我們?cè)O(shè)計(jì)的代理緩存系統(tǒng)的基本思想.借助于上面定義的網(wǎng)站圖,可以對(duì)用戶的訪問(wèn)行為進(jìn)行跟蹤記錄和分析.每次修改道路矩陣實(shí)際上是對(duì)用戶訪問(wèn)行為的一次記錄,通過(guò)這種方式就可以逐步建立起用戶對(duì)某個(gè)網(wǎng)站的訪問(wèn)軌跡圖.我們用一個(gè)序列r,r,…,r[n]來(lái)表示用戶的訪問(wèn)過(guò)程,在某個(gè)時(shí)間段,這個(gè)序列是定位在同一個(gè)服務(wù)器上的.進(jìn)一步,我們通過(guò)比較每個(gè)頂點(diǎn)的pi訪問(wèn)計(jì)數(shù)器c(pj)來(lái)判斷某個(gè)主頁(yè)副本是否為用戶訪問(wèn)的目標(biāo).假設(shè)pj在pi的SVS中,如果c(pj)c(pj)/k,k=#SVS,那么pj不值得在代理服務(wù)器中緩存.因此,通過(guò)對(duì)用戶訪問(wèn)行為進(jìn)行跟蹤和分析,使得代理服務(wù)器中保存了最有價(jià)值的主頁(yè)副本,提高了空間利用率和命中率.同時(shí),我們?cè)诜治鼋Y(jié)果的基礎(chǔ)上,代理服務(wù)器在對(duì)某個(gè)訪問(wèn)請(qǐng)求進(jìn)行響應(yīng)的同時(shí),也將該主頁(yè)頂點(diǎn)pi的鄰接頂點(diǎn)pk1,pk2,…,pkl,pj的URI以命中次數(shù)為序作為輔助信息返回到用戶的瀏覽器上,假設(shè)用戶的目標(biāo)主頁(yè)是,他就可以省去對(duì)pk1,pk2,…,pkl的訪問(wèn),而直接選擇pj的URI進(jìn)入,縮短了訪問(wèn)過(guò)程,從而大大降低了訪問(wèn)延遲.4服務(wù)器集群下的并行系統(tǒng)URAC是在一個(gè)可擴(kuò)展的Web服務(wù)器集群系統(tǒng)上實(shí)現(xiàn)的,因此我們?cè)O(shè)計(jì)的緩存空間可以相當(dāng)大,用以存放大量的主頁(yè)內(nèi)容,包括一些多媒體信息.Web服務(wù)器集群的特點(diǎn)是每臺(tái)服務(wù)器單獨(dú)可以對(duì)外提供服務(wù),這樣一些訪問(wèn)請(qǐng)求可能在不同的服務(wù)器上進(jìn)行處理.為了在服務(wù)器集群上只保存一份緩存副本,需要將所有服務(wù)器的空間進(jìn)行共享.在服務(wù)器集群系統(tǒng)上建立這樣一個(gè)并行文件系統(tǒng),它提供和URI定義相同的目錄結(jié)構(gòu),這樣的文件系統(tǒng)可以加快服務(wù)器檢索緩存副本的速度,從而提高響應(yīng)時(shí)間;另一方面,使服務(wù)器平臺(tái)對(duì)URAC透明,緩存系統(tǒng)在訪問(wèn)文件時(shí)不必考慮文件實(shí)際存放在哪臺(tái)服務(wù)器上.圖4給出了這個(gè)緩存系統(tǒng)在整個(gè)服務(wù)器集群中的位置.本文不對(duì)文件系統(tǒng)進(jìn)行討論,下面從軟件結(jié)構(gòu)、一致性策略和替換算法3方面對(duì)URAC進(jìn)行介紹.4.1頂點(diǎn)pi深化增加在HTTP/1.0和1.1協(xié)議中規(guī)定,只有那些GET和HEAD的訪問(wèn)請(qǐng)求可以緩存,URAC目前的實(shí)現(xiàn)滿足這個(gè)規(guī)定,以后將增加對(duì)動(dòng)態(tài)主頁(yè)的緩存.URAC是建立在網(wǎng)站圖基礎(chǔ)上的,對(duì)應(yīng)于某個(gè)網(wǎng)站圖Wn,動(dòng)態(tài)分配一個(gè)整數(shù)數(shù)組Cn,數(shù)組的下標(biāo)對(duì)應(yīng)Wn的每個(gè)頂點(diǎn)pi.Cn的長(zhǎng)度是動(dòng)態(tài)變化的,等于增加到Wn的頂點(diǎn)數(shù).Cn[i]初值為0,代表頂點(diǎn)pi第一次增加到網(wǎng)站圖中;以后用戶pi對(duì)頂點(diǎn)訪問(wèn)一次Cn[i]就執(zhí)行加一計(jì)算,作為pi的命中計(jì)數(shù)器.同時(shí),動(dòng)態(tài)分配一個(gè)保存每個(gè)頂點(diǎn)URI的字符串?dāng)?shù)組Un.代理緩存機(jī)制在對(duì)訪問(wèn)請(qǐng)求進(jìn)行響應(yīng)后,會(huì)在代理服務(wù)器集群上保留一個(gè)響應(yīng)副本,在上文提到的并行文件系統(tǒng)上以URI的類似的目錄結(jié)構(gòu)存放,如圖5所示.這是一個(gè)目錄樹,葉子節(jié)點(diǎn)是主頁(yè)內(nèi)容,從根到葉子就是一個(gè)完整的httpURI.這樣的目錄結(jié)構(gòu)有助于緩存系統(tǒng)快速獲得提供響應(yīng)的主頁(yè)副本,降低訪問(wèn)延遲.在分析用戶訪問(wèn)行為時(shí),在第一次建立起網(wǎng)站圖時(shí),需要判斷在代理服務(wù)器上是否已經(jīng)有該網(wǎng)站的緩存內(nèi)容,這是通過(guò)訪問(wèn)目錄樹實(shí)現(xiàn)的.為了加速這個(gè)檢索過(guò)程,緩存機(jī)制對(duì)根目錄下的一級(jí)目錄,即網(wǎng)站按域名和IP地址建立了索引Hindex,對(duì)host以域名提供的訪問(wèn)請(qǐng)求按域名從后往前匹配,而IP地址從前往后匹配.Hindex的輸出是對(duì)應(yīng)于該網(wǎng)站的唯一整數(shù)碼值,即Wn的下標(biāo)n.下面給出URAC對(duì)訪問(wèn)請(qǐng)求的響應(yīng)流程:上面的流程不包括緩存的時(shí)效處理和替換,下面將介紹URAC的一致性維護(hù)策略和替換算法.4.2不同待更新時(shí)間副本的再選擇HTTP/1.1協(xié)議對(duì)一個(gè)主頁(yè)的副本生存期(timetolive,TTL)定義為:(1)如果響應(yīng)中有“Cache-Control:max-age=...”通用頭,那么生存期=max-age值;(2)否則,如果響應(yīng)中有Expires實(shí)體頭,那么生存期=Expires值—Date值;(3)否則,Cache可以根據(jù)某種啟發(fā)式算法給出一個(gè)生存期.但是,若在這種情況下給出的生存期超過(guò)24小時(shí),而且響應(yīng)的年齡雖大于24小時(shí)但仍小于生存期,從而被認(rèn)定是新鮮時(shí),必須在響應(yīng)中增加一個(gè)警告碼為13的Waring響應(yīng)頭.同時(shí)還提供了Age響應(yīng)頭記錄某個(gè)主頁(yè)副本的當(dāng)前年齡.參考這些規(guī)定,在URAC中對(duì)緩存副本設(shè)定當(dāng)前年齡pCurrentAge為本次訪問(wèn)時(shí)間HTTPdate減去該主頁(yè)在駐留網(wǎng)站創(chuàng)建的時(shí)間Date.每個(gè)緩存副本的生存期按以上的規(guī)則定義,在響應(yīng)中沒(méi)有Expires等實(shí)體頭時(shí)設(shè)定生存期pTTL為緩存副本當(dāng)前年齡的兩倍(在第一次訪問(wèn)時(shí)設(shè)定,以后再命中時(shí)不再修改).這樣判斷一個(gè)緩存副本是否有效,并作為響應(yīng)返回給客戶的條件是pCurrentAge<pTTL,即一個(gè)緩存副本變成陳舊,需要從駐留網(wǎng)站更新以維護(hù)一致性的條件是pTTL>pCurrentAge.然而在pTTL>pCurrentAge情況下,并不一定要強(qiáng)制從駐留網(wǎng)站下載整個(gè)主頁(yè).由于在駐留網(wǎng)站可用Last-Modified實(shí)體頭指明主頁(yè)的最近修改時(shí)間,由代理服務(wù)器發(fā)出的訪問(wèn)請(qǐng)求可以增加If-Modified-Since頭,使GET成為條件取,其含義是當(dāng)GET所確定的資源在指定的時(shí)間后確實(shí)改變了,就完成GET的功能;否則,返回一個(gè)304(沒(méi)有改變)響應(yīng).響應(yīng)304是不含實(shí)體的.這樣當(dāng)主頁(yè)實(shí)際沒(méi)有改變時(shí),可以節(jié)省帶寬.這時(shí)修改緩存副本的生存期pTTL為當(dāng)前年齡pCurrentAge的1.5倍.在上節(jié)描述的URAC工作流程中,當(dāng)緩存機(jī)制在代理服務(wù)器上檢索到對(duì)應(yīng)于用戶訪問(wèn)請(qǐng)求的主頁(yè)副本時(shí),先進(jìn)行緩存的一致性判斷,如果緩存副本仍然有效,則直接作為響應(yīng)返回;否則,進(jìn)行條件取,必要時(shí)更新代理服務(wù)器上的緩存副本.假設(shè)網(wǎng)站W(wǎng)n的頂點(diǎn)pi是一個(gè)陳舊副本,如果代理服務(wù)器發(fā)出條件取請(qǐng)求到駐留網(wǎng)站后得到的是304響應(yīng),那么仍然增加pi的命中計(jì)數(shù)Cn[i];如果得到的響應(yīng)是一個(gè)更新的pi,在代理服務(wù)器上保存這個(gè)新的主頁(yè)副本,并重置Cn[i]為0;如果得到的是404響應(yīng)(找不到),可能該主頁(yè)在駐留網(wǎng)站上已被刪除,此時(shí)應(yīng)將pi從網(wǎng)站圖上刪除,即在Cn數(shù)組中刪除Cn[i],在Un數(shù)組中刪除Un[i].4.3基于低速率的l裝置設(shè)計(jì)由于代理服務(wù)器上的緩存空間是有限的,當(dāng)存放了一定數(shù)量的主頁(yè)副本后,為了保存新的訪問(wèn)請(qǐng)求的響應(yīng)副本,只能將已經(jīng)保存的一些副本替換出去以騰出空間.常用的Cache替換算法有根據(jù)每個(gè)緩存副本的文件長(zhǎng)度選擇合適的副本進(jìn)行替換的SIZE算法、記錄每個(gè)緩存副本的命中時(shí)間選擇最久未被訪問(wèn)的副本進(jìn)行替換的LRU算法以及記錄每個(gè)緩存副本的命中次數(shù)選擇最少命中的副本進(jìn)行替換的LFU算法等.這些方法各有各的優(yōu)缺點(diǎn),如在Harvest緩存系統(tǒng)中采用了LRU算法,通常采用模擬的方法對(duì)這些算法進(jìn)行性能比較,文獻(xiàn)對(duì)此進(jìn)行了分析比較,并得出結(jié)論,對(duì)具體的緩存系統(tǒng)應(yīng)當(dāng)設(shè)計(jì)相應(yīng)的替換算法.在網(wǎng)站圖模型中,對(duì)某個(gè)主頁(yè)副本是否可以在代理服務(wù)器上保存更長(zhǎng)時(shí)間的判斷提供了有效的信息.URAC采用的替換算法綜合考慮了副本存放的期望值、利益、訪問(wèn)頻度和最近訪問(wèn)時(shí)間這幾個(gè)主要的因素.借助道路矩陣,這些參數(shù)的定義如下:(1)pi的期望值:(2)pi的利益值:期望值指的是pi被引用的可能,參與計(jì)算的是它的前趨集;利益值指的是通過(guò)pi可以訪問(wèn)的信息量,參與計(jì)算的是它的后繼集;最近訪問(wèn)時(shí)間體現(xiàn)了pi在緩存空間中未被命中的存活時(shí)間;而訪問(wèn)頻度正好反映了pi提供有效信息的概率.其中,期望值、利益值以及訪問(wèn)頻度越大,表明該副本被命中的可能性越大,因此不該被替換出去.相反,最近訪問(wèn)時(shí)間參數(shù)越大,表明該副本已沒(méi)有保存的價(jià)值,可以被替換出去.根據(jù)這一原則,我們定義替換函數(shù)為R=R(e,p,t,f),對(duì)每個(gè)頂點(diǎn)pi,它的替換因子為某個(gè)頂點(diǎn)的替換因子值越大,被替換的可能性也就越大.5代理服務(wù)器性能與代理存儲(chǔ)系統(tǒng)性能的比較我們實(shí)現(xiàn)了一個(gè)原型系統(tǒng),并對(duì)URAC進(jìn)行了概率模擬,得出的命中率結(jié)果和LRU進(jìn)行了比較.假設(shè)每個(gè)主頁(yè)的長(zhǎng)度為32KB,緩存空間為300MB(可以保存100個(gè)網(wǎng)站和9600個(gè)主頁(yè)副本),模擬請(qǐng)求序列長(zhǎng)度為192000.模擬的請(qǐng)求序列的分布狀態(tài)設(shè)計(jì)為高度集中、集中以及隨機(jī)3種類型,得到的結(jié)果如表1所示.這里我們采用的是有效命中率參數(shù),考慮到傳統(tǒng)的命中率計(jì)算方法將大量的索引性主頁(yè)副本的命中也計(jì)算在內(nèi),而我們對(duì)用戶訪問(wèn)行為的分析結(jié)果表明,這種命中是無(wú)效命中,而且占用了代理服務(wù)器的空間,并增加了訪問(wèn)延遲,所以我們引進(jìn)有效命中率VHR(validhitrate)參數(shù)來(lái)描述代理緩存系統(tǒng)的性能.有效命中指的是那些命中的主頁(yè)副本是能夠提供接近用戶訪問(wèn)目標(biāo)信息的命中.VHR定義為有效命中和所有訪問(wèn)請(qǐng)求的比值.這些結(jié)果表明,URAC具有比LRU更好的性能,在每個(gè)網(wǎng)站少于192個(gè)主頁(yè),并且只有40%的有效信息時(shí),我們可以得到70%的命中率,同時(shí),空間的利用率可達(dá)80%.另一方面,我們也看到了當(dāng)網(wǎng)站數(shù)目和有效信息比率增加時(shí),URAC的性能降低