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

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

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