web服務器和proxxx服務器的特性研究

web服務器和proxxx服務器的特性研究

1總結(jié)1.1web存儲協(xié)同緩沖系統(tǒng)的分類對web業(yè)務特征的分析，如業(yè)務源模型和自相似模型的模型。這些研究的基本數(shù)據(jù)來自web服務器事務或統(tǒng)計地址，其研究結(jié)果與數(shù)據(jù)來源相關(guān)。這是因為web服務事務月報或統(tǒng)計月報反映了在特定區(qū)域訪問web業(yè)務的特征，并且訪問特征受到文化背景和習俗的影響。每個國家、地區(qū)和民族都是不同的。因此，不同國家的web服務時間和統(tǒng)計日期反映的訪問特性可能會不同。這是我們這項研究的主要動機。研究WWW訪問特性是研究WebServer,Web中間件(proxy,Web緩存)及人工合成Web負載的基礎(chǔ).如一個好的Webcachingsystem的替換算法來源于對WWW業(yè)務訪問特性的深刻認識,因此目前所提出的Web緩存替換算法大部分來源于對WWW訪問特性的分析,如LRU,LFU,Size,LRV,GreedyDual-Size等等.以下,我們根據(jù)各種訪問特性對目前的Web緩存替換算法進行一個分類.(1)利用時間局部性——LRU算法(least-recently-used)基于WWW訪問中存在的時間局部性,將最不常被訪問的Web文檔替換出緩存,這是一種非常容易實現(xiàn)的Web緩存替換算法,其派生出的一種算法LRU-Threshold利用了一個訪問特性即大于某個閾值的Web文檔極少被訪問.Pitkow/Recker算法則在LRU算法的基礎(chǔ)上利用了另一個訪問特性,如果文檔都是今天訪問的,則將最大的Web文檔替換.(2)利用Web靜態(tài)頁面的訪問特性——LFU算法(least-frequently-used)基于Web靜態(tài)頁面的訪問特性,將訪問頻率最低的Web文檔替換出去.Hyper-G算法是對LFU算法的一種擴展,使用訪問頻率作為第1關(guān)鍵字,在訪問頻率相等時再分別使用最后一次訪問時間和文檔大小作為第2和第3關(guān)鍵字.(3)利用Web靜態(tài)頁面的大小分布特性——Size算法利用了用戶傾向于訪問較小的Web文檔的訪問特性,在替換發(fā)生時將最大的Web文檔替換出去.Log(Size)+LRU算法替換具有最大的Log(Size)值的文檔,如果有多個同樣的Log(Size)值的文檔,則替換最不常被訪問的文檔(LRU).(4)以降低用戶訪問延時為目標——LLF算法(lowest-latency-first)使用訪問Web文檔時的延時來作為替換的標準,在替換發(fā)生時優(yōu)先考慮訪問延時最小的Web文檔.Hybrid算法則在主要考慮訪問延時的基礎(chǔ)上兼顧訪問頻率與文檔大小.(5)LRV算法(lowestrelativevalue)考慮了獲取文檔的代價、文檔的大小,并利用對WebProxy訪問日志的分析,計算文檔下一次被訪問、一段時間后被訪問的概率,最后形成一個計算公式,其值即為替換的依據(jù)(6)GreedyDual-Size算法賦予每一個緩存中的文檔一個H值,H的初始值為C/S,C為將文檔帶入緩存的開銷,S為文檔大小,當替換發(fā)生時,選出H值最小的文檔將其替換出去,并將所有的緩存中的文檔的H值均減去這個最小的H值,而當文檔訪問命中時,則將文檔的H值恢復為C/S.其中C可以為1,packets,latency,Hops等等,這正是此算法的靈活之處,可以根據(jù)不同的需要變換C,達到提高命中率或降低網(wǎng)絡(luò)開銷的目的.因為不可能有一種算法滿足所有的需求.1.2靜態(tài)醫(yī)療設(shè)計文獻研究的基本介紹WWW業(yè)務表現(xiàn)為一系列的訪問序列.而WebServer和ProxyServer的日志很好地記錄了這種訪問序列的過程及特性.為此我們研究了一個國內(nèi)的WebServer和兩個ProxyServer的日志,對Web頁面請求的分布、Web靜態(tài)文檔的大小分布、Web靜態(tài)文檔訪問距離的分布等特性進行了統(tǒng)計和分析,得出了一些結(jié)論,有些和相關(guān)文獻研究相符,有些不同.靜態(tài)文檔是指在Http請求到達WebServer之前已經(jīng)在WebServer中存在的Web文檔,包括頁面、各種圖標、文件等.之所以要研究靜態(tài)文檔是因為在對Web文檔的訪問中,對靜態(tài)文檔的訪問占絕大多數(shù),如表1,表2所示.雖然目前對動態(tài)文檔的訪問逐漸增多(如CGI腳本產(chǎn)生的Web文檔,Server端腳本Asp文檔、Php文檔、Jsp文檔等),但并非動態(tài)文檔中的所有內(nèi)容均是動態(tài)產(chǎn)生,比如它可能會引用一些靜態(tài)的圖標文件,而通過對日志的分析可以證明,對這些圖標文件的訪問量非常大,因此本文選擇Web靜態(tài)文檔作為研究重點.文章是這樣組成的:第2節(jié)為相關(guān)的工作;第3節(jié)為日志數(shù)據(jù)的收集和對日志數(shù)據(jù)的分析;第4節(jié)為結(jié)論;第5節(jié)為后續(xù)工作.2相關(guān)工作2.1web頁面請求分布與受比分布的關(guān)系相關(guān)文獻研究認為Web頁面請求(對Web靜態(tài)頁面的請求,下文中提到的頁面均為靜態(tài)頁面)的概率分布符合Zipf分布,即P(j)=kjT,其中P(j)是第j個Web頁面出現(xiàn)的頻率,j為根據(jù)訪問概率降序排列的索引,k為一個常數(shù),T為一個非常接近1的數(shù).1994年Glassman在對DEC公司的Proxy日志中的100000個HTTP請求進行分析時發(fā)現(xiàn)Web頁面請求分布與Zipf分布符合得非常好,T接近1.1995年,Cunha等在設(shè)計記錄用戶訪問的WWW請求的實驗中發(fā)現(xiàn)Web頁面請求分布符合一個T為0.986的Zipf分布.1996年,Almeida等在分析波士頓大學計算機系WebServer的訪問日志時,提到Web頁面請求分布遵循一個T為0.85的Zipf分布.1998年,日立公司的Nishikawa等研究了一個包含2000000個HTTP請求的Web存取日志,發(fā)現(xiàn)頁面請求分布遵循T=0.75的Zipf分布.在1999年的IEEEWorkshoponInternet上,JunbiaoZhang等發(fā)表了一篇關(guān)于建立一個Webcaching研究環(huán)境的論文,文中提到,他們在實驗中發(fā)現(xiàn)Web頁面請求分布符合T為0.8～0.95的Zipf分布.在1999年的IEEEINFOCOM上,LeeBreslau等發(fā)表了關(guān)于Webcaching和Zipf分布的關(guān)系的文章,文中研究了6個Proxy日志,頁面請求分布均符合Zipf分布,T參數(shù)的范圍為0.64～0.83.然而在研究地區(qū)文化背景對Proxy的影響時,VirgilioAugustoFAlmeida等人發(fā)現(xiàn)他們研究的Proxy日志中的Web頁面請求分布并不符合Zipf分布.2.2靜態(tài)醫(yī)療負載特性Web靜態(tài)文檔的概率分布有兩個含義,一是指WebServer上的靜態(tài)文檔的概率分布(文檔只出現(xiàn)一次),二是指在訪問傳輸過程中的所傳輸?shù)腤eb靜態(tài)文檔的概率分布(文檔可以出現(xiàn)多次),前者反映Web文檔原始的大小分布,后者反映用戶訪問的文檔的趨向(愛好).1995年,Cunha等在上文提到的實驗中,對所研究的訪問集中的Web靜態(tài)文檔大小的分布進行了研究,提出Web靜態(tài)文檔的大小的分布函數(shù)服從Pareto分布,即P[X≤x]=1-(k/x)T,T,k≥0,x≥k,而傳輸文檔的訪問率則和傳輸文檔的大小成反比.1996年的ACMSIGMETRICS會議上,MartinF.Arlitt等發(fā)表了關(guān)于WebServer負載特性的論文,在研究了6個WebServer的日志后,提出WebServer上的靜態(tài)文檔的大小分布函數(shù)服從Pareto分布,特別是其尾分布服從0.4≤T≤0.63的Pareto分布.1997年波士頓大學計算機科學系的PaulBarford和MarkCrovella在研究人工合成Web負載時,WebServer上的靜態(tài)文檔大小的分布函數(shù)是基于一個混合模型,體分布為一個＿=9.357;e=1.318的對數(shù)正態(tài)分布,尾分布為k=133K;T=1.1的Pareto分布,而傳輸靜態(tài)文檔的分布使用k=1000;T=1.0的Pareto分布來作為模型.1999年的WorldWideWeb,SpecialIssueonCharacterizationandPerformanceEvaluation中Barford,Bestavros等在對比1995年和1998年的日志特性時,也使用了基于對數(shù)正態(tài)分布和Pareto分布的混合模型來描述Web靜態(tài)文檔大小的分布函數(shù).2.3離n+1訪問距離是指某個Web靜態(tài)文檔兩次訪問之間的其它Web靜態(tài)文檔的個數(shù)再加1,即若某個Web靜態(tài)文檔兩次訪問之間的其它Web靜態(tài)文檔的個數(shù)為n,則其訪問距離為n+1;文獻中使用了一種稱為堆棧距離的模型來描述這一特性,在文獻中則稱為PageRequestInterarrivaltimes即對同一個Web頁面兩次訪問之間的頁面?zhèn)€數(shù),實際上也是指的訪問距離,但考慮的是頁面,我們在本文中只考慮Web靜態(tài)文檔.VirgilioAlmeida,AzerBestavros等在1996年的96上發(fā)表的文章中使用了堆棧距離模型來研究時間局部性,在他們的研究中,認為Web文檔訪問距離的分布服從對數(shù)正態(tài)分布模型.3本文件的工作3.1記錄特征為充放電平臺的記錄,包括web團隊的訪問代理和開發(fā)數(shù)據(jù)庫以ve日志數(shù)據(jù)來源于一個WebServer和兩個ProxyServer的日志,WebServer的用途為發(fā)布信息.兩個ProxyServer均為研究機構(gòu)的訪問代理,日志數(shù)據(jù)格式全部為NCSACLF格式,日志的詳細描述數(shù)據(jù)如表1和表2所示.3.2web頁面請求遵循文圖所見Web頁面請求的分布可以通過統(tǒng)計日志中對靜態(tài)Web頁面的Get請求來獲取.抽取WebServer日志中所有Web頁面的訪問(不包括其中內(nèi)嵌的圖標、圖像、script文件),根據(jù)訪問的頻率由高到底排列,如圖1所示,圖中的x軸和y軸均為log10刻度,即圖中畫出的是將原數(shù)據(jù)求以10為底的對數(shù)得到的數(shù)據(jù)的關(guān)系圖.圖1為按log-log方式畫出的請求分布圖,另外圖中還畫出了在去掉前10個文檔后進行曲線擬和的圖形.可以看到從某個頁面n后(圖中為x=1,對應的頁面為10)的Web頁面請求分布符合冪分布(圖形為直線),且斜率非常接近1(如表3所示),因此可以認為n之后的頁面請求分布符合Zipf分布.在文獻中也提到,曲線擬和是去掉了前100個文檔進行的,即100個之后的Web靜態(tài)文檔訪問分布曲線擬和的結(jié)果符合T為0.64到0.83的Zipf分布.根據(jù)以上的數(shù)據(jù)分析,我們認為,我們研究的WebServer的Web靜態(tài)頁面的請求分布服從以下分布,即T1<0.5,n為介于1和總的Web靜態(tài)文檔總數(shù)之間,但是遠遠小于總的Web靜態(tài)文檔總數(shù)的數(shù).和文獻的研究不同,我們沒有忽略前n個頁面的分布,因為前n個頁面的請求數(shù)占總請求數(shù)的1/10,在總的請求數(shù)中這是一個不能忽略的數(shù)另外我們對兩個ProxyServer日志的Web頁面請求分布進行了分析,結(jié)果如圖2所示.其中x軸,y軸均為取log10后得到的值,由圖2可見,在我們研究的ProxyServer日志中,Web頁面請求遵循Zipf模型程度不是十分明顯.3.3web靜態(tài)相關(guān)圖Web靜態(tài)文檔大小的分布是指一個WebServer上的靜態(tài)文檔的大小分布(在請求序列中至少出現(xiàn)一次),可以通過分析訪問日志獲取一個WebServer上的靜態(tài)文檔的大小分布.根據(jù)前文,如果Web靜態(tài)文檔大小的尾分布函數(shù)服從Pareto分布,則有即按對數(shù)刻度畫出的大于x的Web靜態(tài)文檔的累計概率和與x的關(guān)系在x>k時應為線性關(guān)系.這種繪圖方式稱為LLCD(log-logcomplementarydis-tribution).圖3為WebServer日志中的Web靜態(tài)文檔的累計概率和與x的關(guān)系圖.圖中x軸為靜態(tài)文檔大小,y軸為大于x的Web靜態(tài)文檔的累計概率和.從圖3可以看出,當x>k(k為某個常數(shù),圖中的k≈104.5,即Web靜態(tài)文檔大小為30K左右)圖形表現(xiàn)近似為一條直線,這與相關(guān)文獻研究相同,即Web靜態(tài)文檔的大小大于某個數(shù)值時的分布服從Pareto分布.然而,圖3中Pareto分布的形狀(shape)參數(shù)T的值大于2,比相關(guān)文獻中的T值普遍要大.根據(jù)重拖尾分布的定義:如果具有重拖尾效應,應有0<T<2.在滿足重拖尾效應的分布中,落在圖形尾上的概率是不可忽略的,對Web靜態(tài)文檔來說,即Web靜態(tài)文檔較大的概率不可忽略.這意味著在我們研究的WebServer日志中不存在相關(guān)文獻研究中的重拖尾效應,即Web靜態(tài)文檔較大的概率很小.X≤k時,其分布顯然無法用Pareto分布來解釋.而根據(jù)文獻[9,10],≤時的分布可以用對數(shù)正態(tài)分布來近似描述:設(shè)隨機變量y=log10x,則有為此我們畫出了WebServer上x軸刻度為log10的文檔大小與其出現(xiàn)次數(shù)的關(guān)系圖(注意,不是在整個日志中的出現(xiàn)次數(shù),而是在Web靜態(tài)文檔集中的出現(xiàn)次數(shù)),如圖4所示.圖4中x軸為靜態(tài)文檔大小,y軸為其出現(xiàn)的頻率.在x<4.5,即web靜態(tài)文檔大小小于30K,圖形與正態(tài)分布密度函數(shù)的圖形非常相似,因為橫軸為log10刻度,因此當Web靜態(tài)文檔大小小于10K時,分布可以用對數(shù)正態(tài)分布來近似描述.從圖4可以清晰地看出,整個圖形分為兩個部分,x≤4.5,服從正態(tài)分布,x>4.5服從Pareto分布.3.4緩沖相關(guān)文獻的訪問頻率Web傳輸文檔是指在訪問過程中成功傳輸?shù)奈臋n,這些文檔可能會被傳輸多次,因此傳輸過程中的文檔分布實際上反映了用戶訪問文件大小的趨勢.圖5是兩個ProxyServer的日志中Web傳輸文檔的大小分布(x軸為log10刻度),圖中x軸為靜態(tài)文檔大小,y軸為其出現(xiàn)的頻率.曲線擬和表明,從圖中某個位置之后,遵循指數(shù)分布,而在此之前,無法確定其分布.在圖5中可以看到,從總體來說,用戶還是傾向于訪問較小的文檔,但也不是越小的文檔訪問率越高,顯然這個與Web文檔本身的分布有關(guān),如圖4所示,由于某個大小范圍之內(nèi)的文檔數(shù)較多,因此造成這個范圍之內(nèi)的文檔的訪問概率較大.值得一提的是,很多Web緩存替換算法(如Size,GreedyDual-Size等)利用Size作為替換的依據(jù)雖然利用了用戶訪問小文檔較多的訪問特性但同時忽略了一個事實,即用戶訪問文檔大小的傾向并不是單調(diào)的,因此在利用Size作為替換依據(jù)時,還應該兼而考慮其它因素,如訪問頻率.根據(jù)這種想法,我們使用Size/Frequency作為Web緩存替換策略的替換策略,使用ProxyServer的日志進行了緩存模擬,結(jié)果如表4～6所示:表4～6針對兩種Web緩存替換算法(Size,WeightedSize即以Size/Frequency作為替換策略)分別計算了在各種不同的緩存大小下的緩存命中率、Byte命中率、減少傳送分組率,這些指標均是相對值,即所得結(jié)果除以在無窮緩存大小的情況下的值.由此可以看出,WeightedSize(即以Size/Frequency作為替換策略)的結(jié)果要好于只用Size作為替換策略,這個結(jié)果證實了我們的分析,在利用Size作為替換依據(jù)時,還應該兼而考慮文檔的訪問頻率.3.5prox分析定義1.如果對同一個Web文檔j的兩次訪問之間有d-1個Web文檔,則稱對Web文檔j有一個訪問距離d.文獻中在研究了4個WebServer的日志后,認為Web文檔的訪問距離服從對數(shù)正態(tài)分布.即繪出log10(訪問距離)與訪問距離出現(xiàn)次數(shù)的關(guān)系圖應與正態(tài)分布的圖形相似.然而,在我們對WebServer日志的分析中,上述關(guān)系圖未表現(xiàn)出與正態(tài)分布的圖形相似,如圖6所示(圖中x軸為訪問距離,y軸為出現(xiàn)的頻率).分析造成差異的原因發(fā)現(xiàn),在文獻中的日志的訪問距離為1的出現(xiàn)頻率并不是最高,而是訪問距離為100左右,而在我們研究的日志中訪問距離為1的出現(xiàn)頻率最高,這說明在我們分析的日志中,時間局部性更加明顯.對數(shù)據(jù)進行曲線擬和的結(jié)果表明,與圖6中曲線最相近的分布是指數(shù)分布,因此可以認為WebServer靜態(tài)文檔的訪問距離服從指數(shù)分布.圖7(圖中x軸為訪問距離,y軸為出現(xiàn)的頻率)為對Proxy日志分析Web靜態(tài)文檔訪問距離的結(jié)果,為清晰,圖中只畫出了訪問距離小于200的圖形,曲線擬和表明,當訪問距離小于200時,可以用k=1,T∈(0,1)的Pareto分布來近似描述,當訪問距離大于200時,沒有找到相應的分布模型.由于指數(shù)分布要比冪分布(Pareto分布)衰減得快,而Pareto分布在T∈(0,2)之間時表現(xiàn)出重拖尾特性,即會有比較大的概率落在尾上,因此以上結(jié)果意味著在Proxy的日志中出現(xiàn)大的訪問距離的概率不可忽略,而相對來說在WebServer的日志中出現(xiàn)大的訪問距離的概率則較小.4web服務器靜態(tài)相關(guān)文獻的分布本文對一個WebServer和兩個ProxyServ