王婷，任洪敏（上海海事大學(xué)信息工程學(xué)院，上海 201306）

Web端性能優(yōu)化的研究與實(shí)現(xiàn)

王婷，任洪敏
（上海海事大學(xué)信息工程學(xué)院，上海 201306）

為了提高Web端緩存的性能，在傳統(tǒng)的緩存替換算法GDS基礎(chǔ)上提出新的緩存替換算法GDS-TFH。改進(jìn)的算法除了考慮被訪問(wèn)對(duì)象的大小，還考慮被緩存的對(duì)象訪問(wèn)次數(shù)之間的時(shí)間間隔和被訪問(wèn)對(duì)象訪問(wèn)的次數(shù)或被訪問(wèn)的頻率。分析在有限的緩存空間內(nèi)改進(jìn)的算法GDS-TFH在請(qǐng)求命中率和字節(jié)命中率方面有比較好的提升。

GDS-TFH；緩存替換；代理服務(wù)器

0　引言

網(wǎng)頁(yè)加載的時(shí)間長(zhǎng)短在很大程度上影響著瀏覽網(wǎng)頁(yè)者的瀏覽體驗(yàn)和各個(gè)網(wǎng)站的競(jìng)爭(zhēng)力。在可以獲得同樣信息的網(wǎng)站之間，瀏覽等待的時(shí)間越短，用戶(hù)體驗(yàn)越好，網(wǎng)站競(jìng)爭(zhēng)力越大。根據(jù)網(wǎng)站Softpedia網(wǎng)站上公布的消息，Google檢索到的網(wǎng)頁(yè)加載速度平均為2.45秒。根據(jù)調(diào)查機(jī)構(gòu)KissMitrics研究的結(jié)果顯示：網(wǎng)頁(yè)加載的速度會(huì)影響用戶(hù)的消費(fèi)，如果電子商務(wù)每天收入為10萬(wàn)美元，那么1秒的延遲就會(huì)讓該網(wǎng)站每年損失250萬(wàn)美元。影響網(wǎng)頁(yè)加載速度的原因有很多。其中，在服務(wù)器方面，可以設(shè)置一個(gè)代理服務(wù)器，代理瀏覽用戶(hù)獲取網(wǎng)絡(luò)信息。代理服務(wù)器是一個(gè)緩存網(wǎng)絡(luò)數(shù)據(jù)的軟件，當(dāng)用戶(hù)發(fā)送Requests到服務(wù)器時(shí)，代理下載和緩存需要的網(wǎng)頁(yè)信息，當(dāng)其他用戶(hù)也發(fā)出同樣的Requests時(shí)，直接從代理服務(wù)器的緩存中獲取需要的網(wǎng)頁(yè)信息。若是緩存目錄使用量超過(guò)95%時(shí)，使用緩存替換算法，收回一部分當(dāng)前可能不需要的緩存信息，備份新緩存的信息，因此代理服務(wù)器的緩存替換算法的優(yōu)劣會(huì)影響代理服務(wù)器的性能。所以對(duì)緩存替換算法的優(yōu)化可以提高代理服務(wù)器的性能。

1　對(duì)現(xiàn)有緩存替換策略的調(diào)研

1.1被使用過(guò)的緩存替換策略部分簡(jiǎn)介

已經(jīng)出現(xiàn)的緩存替換策略有很多，例如Least Recently Used（LRU）、Least Frequently Used（LFU）、SIZE、LRU Threshold、Log（Size）+LRU、Lowest Latency First、Hybrid、Lowest Relative Value（LRV）等。可以把這些緩存替換算法依據(jù)不同的標(biāo)準(zhǔn)分成4類(lèi)：基于訪問(wèn)對(duì)象被訪問(wèn)的次數(shù)（Least Frequently Used（LFU）-最不經(jīng)常使用）、基于被訪問(wèn)對(duì)象訪問(wèn)之間的時(shí)間間隔（Least Recently Used（LRU）-最近最少使用）、基于被訪問(wèn)對(duì)象的大?。⊿IZE緩存置換算法）、基于被訪問(wèn)對(duì)象保存的價(jià)值（Hybrid緩存置換算法）。

1.2評(píng)判緩存替換策略的標(biāo)準(zhǔn)

通過(guò)衡量對(duì)象的大小區(qū)分請(qǐng)求命中率和字節(jié)命中率。目前為止，還沒(méi)有一種算法可以?xún)烧呒骖?，使緩存替換最優(yōu)。通過(guò)Arlitt M的實(shí)驗(yàn)可知，基于被訪問(wèn)對(duì)象的大小的緩存替換算法能夠使請(qǐng)求命中率值更高，基于訪問(wèn)對(duì)象被訪問(wèn)的次數(shù)的緩存替換算法能夠使字節(jié)命中率值更高。判斷緩存替換算法性能的標(biāo)準(zhǔn)一般有2種：

（1）請(qǐng)求命中率

請(qǐng)求命中率由用戶(hù)通過(guò)瀏覽器發(fā)出的Requests被命中的次數(shù)與用戶(hù)通過(guò)瀏覽器發(fā)出的所有Requests之比而得。當(dāng)用戶(hù)通過(guò)瀏覽器訪問(wèn)網(wǎng)頁(yè)時(shí)，若是此次請(qǐng)求的網(wǎng)頁(yè)在緩存中命中緩存，用σi=1表示，若是沒(méi)有在此次請(qǐng)求的網(wǎng)頁(yè)在緩存中命中緩存，用σi=0表示。請(qǐng)求的Requests之和用N表示。請(qǐng)求命中率（RHR）的公式是：

（2）字節(jié)命中率

字節(jié)命中率由用戶(hù)通過(guò)瀏覽器發(fā)出的Requests被命中的所有文檔的大小與用戶(hù)通過(guò)瀏覽器發(fā)出的Requests的所有的文檔大小之比而得。當(dāng)用戶(hù)通過(guò)瀏覽器訪問(wèn)網(wǎng)頁(yè)時(shí)，若是此次請(qǐng)求的網(wǎng)頁(yè)在緩存中命中緩存，用σi=1表示，若是沒(méi)有在此次請(qǐng)求的網(wǎng)頁(yè)在緩存中命中緩存，用σi=0表示。請(qǐng)求的Requests之和用N表示。用size（i）表示對(duì)象i的文檔大小。字節(jié)命中率（BHR）的公式是：

已知判斷緩存替換算法的性能有兩種標(biāo)準(zhǔn)，研究明白兩者之間的關(guān)系，有利于理解Web端緩存替換算法之間的優(yōu)劣。使用公式（2）除以公式（3），得到的是所有請(qǐng)求對(duì)象的平均大小與所有命中對(duì)象的平均大小之比，即可形象化地理解請(qǐng)求命中率（RHR）和字節(jié)命中率（BHR）之間的關(guān)系。即：

因?yàn)椋?/p>

在Web緩存系統(tǒng)中，一般RHR比BHR大，故（6）的值大于1，即所有請(qǐng)求對(duì)象的平均大小比所有命中對(duì)象的平均大小大，說(shuō)明小文件更容易被命中。

2　GDS緩存替換算法的研究與改進(jìn)

2.1艾賓浩斯遺忘曲線(xiàn)

艾賓浩斯遺忘曲線(xiàn)描述了人類(lèi)大腦對(duì)新事物遺忘的規(guī)律。用戶(hù)對(duì)某件事務(wù)感興趣的程度可以引用艾賓浩斯遺忘曲線(xiàn)的規(guī)律，表示用戶(hù)對(duì)某對(duì)象感興趣的程度。

圖1

曲線(xiàn)的表達(dá)式可以近似的表示為：

ΔT為表示對(duì)象i相鄰被訪問(wèn)次數(shù)之間的時(shí)間間隔，單位為ms。

2.2GDS算法

GDS（Greedy Dual Size）算法的基本思想是通過(guò)目標(biāo)函數(shù)計(jì)算所有的對(duì)象i的函數(shù)值，將函數(shù)值由大到小排列，當(dāng)有限的緩存空間的存儲(chǔ)量達(dá)到95%時(shí)，將函數(shù)值最小的對(duì)象清除?，F(xiàn)有的GDS緩存替換算法是Cao 和Irani在研究分析了13種不同的緩存替換算法，得

在公式（8）中，L為膨脹因子，初始值為0，當(dāng)有對(duì)象在緩存中被替換時(shí)，被替換對(duì)象的目標(biāo)函數(shù)值賦值給新進(jìn)入緩存對(duì)象的L。Size（i）為對(duì)象i的大小。Value （i）為對(duì)象i被引入到緩存需要的代價(jià)。

GDSF（Greedy Dual Size Frequency）算法因?yàn)樾枰紤]對(duì)象訪問(wèn)的頻率，所以實(shí)現(xiàn)起來(lái)稍微復(fù)雜一些。當(dāng)出現(xiàn)被訪問(wèn)次數(shù)多的對(duì)象被替換時(shí)，GDSF算法就會(huì)顯現(xiàn)出比GDS算法更好的健全性。GDSF算法的目標(biāo)函數(shù)中引入新的變量Fr（i），表示對(duì)象i訪問(wèn)的頻率。GDSF算法的目標(biāo)函數(shù)為：到了計(jì)算目標(biāo)函數(shù)的計(jì)算方法：

但是，當(dāng)對(duì)象訪問(wèn)頻率大且對(duì)象i的大小比較小的時(shí)候，近期卻不被用戶(hù)訪問(wèn)，當(dāng)然可能以后也不被訪問(wèn)到，這時(shí)就會(huì)造成部分緩存空間被長(zhǎng)期占用，使RHR和BHR的效率降低。

2.3GDS算法的改進(jìn)算法GDS-TFH

從訪問(wèn)的時(shí)間間隔來(lái)看，訪問(wèn)間隔的時(shí)間越短，對(duì)象被訪問(wèn)的概率越大。從訪問(wèn)的頻率來(lái)看，訪問(wèn)的頻率（次數(shù)）越大，對(duì)象被訪問(wèn)的概率也越大?？梢酝ㄟ^(guò)對(duì)時(shí)間間隔加權(quán)，再對(duì)不同分組中的時(shí)間間隔使用余弦相似性的方法提高算法的優(yōu)越性，當(dāng)余弦值越大，兩組的時(shí)間間隔越相似，用戶(hù)對(duì)對(duì)象訪問(wèn)具有規(guī)律性，表明用戶(hù)對(duì)此對(duì)象越感興趣。另外，當(dāng)用戶(hù)對(duì)某些數(shù)據(jù)記憶越深刻，表示用戶(hù)對(duì)此請(qǐng)求越感興趣，則對(duì)象請(qǐng)求的目標(biāo)函數(shù)也越大。

由此，引入了用戶(hù)感興趣的程度 （User-Interest-Level（UIL））這一概念，定義：用戶(hù)對(duì)Web對(duì)象的感興趣程度是分組之后的時(shí)間間隔之間具有余弦相似性，1和相似性累加和結(jié)果的乘方，其中指數(shù)為艾賓浩斯遺忘曲線(xiàn)函數(shù)。在此基礎(chǔ)上提出了GDS算法的改進(jìn)算法GDS-TFH（Greedy Dual Size-Time Frequency probability）。設(shè)計(jì)用戶(hù)感興趣的模型。

用空間向量表示：

其中：

ΔT表示對(duì)象i相鄰被訪問(wèn)次數(shù)之間的時(shí)間間隔，單位為ms。ΔTi中的下標(biāo)i表示第i個(gè)時(shí)間間隔。Fr（i）表示對(duì)象被訪問(wèn)的次數(shù)，且Fr（i）≥4。I在1到Fr（i）-3之間。對(duì)時(shí)間間隔依據(jù)艾賓浩斯遺忘曲線(xiàn)進(jìn)行加權(quán)，即：

其中ai，ai+1，ai+2位常數(shù)，分別對(duì)應(yīng)艾賓浩斯遺忘曲線(xiàn)中H（ΔTi），H（ΔTi+1）），H（ΔTi+2）的值。再求分組之后的時(shí)間間隔之間的余弦相似性。即，對(duì)wdFr（i）-3和wdi求余弦相似性，即：

函數(shù)的取值范圍在0和1之間，相似度越高越接近1。綜上，UIL公式如下：

用戶(hù)感興趣程度考慮了被訪問(wèn)緩存對(duì)象的時(shí)間間隔和被訪問(wèn)緩存對(duì)象出現(xiàn)的頻率（次數(shù)）和艾賓浩斯遺忘曲線(xiàn)函數(shù)，用戶(hù)感興趣程度UIL（ΔT，F(xiàn)r（i），H（ΔT））的計(jì)算值越大，則用戶(hù)訪問(wèn)對(duì)象具有時(shí)間規(guī)律，表示用戶(hù)對(duì)此緩存的對(duì)象越感興趣，目標(biāo)函數(shù)越大，對(duì)象緩存的價(jià)值越大，反之就越小。故，改進(jìn)后的GDS-TFH算法具體函數(shù)為公式（14）：

簡(jiǎn)要概括GDS-TFH算法的使用過(guò)程：

①：L為膨脹因子，初始值為0，UIL（ΔT，F(xiàn)r（i），H （ΔT））為1。

②：代理服務(wù)器處理用戶(hù)發(fā)出的請(qǐng)求，當(dāng)有限的緩存剩余量大于5%時(shí)，需要被緩存的對(duì)象直接進(jìn)入緩存；當(dāng)有限的緩存剩余量小于5%時(shí)，需要被緩存的對(duì)象計(jì)算對(duì)象i的目標(biāo)函數(shù)，使用公式（14），將結(jié)果與緩存中的所有對(duì)象的函數(shù)值做比較，替換出價(jià)值最小的對(duì)象空間并且將函數(shù)值最小的H賦值給對(duì)象i的L。

3　實(shí)驗(yàn)環(huán)境的搭建和結(jié)果分析

3.1實(shí)驗(yàn)環(huán)境的搭建

實(shí)驗(yàn)環(huán)境搭建在CentOS6系統(tǒng)上，使用Squid代理服務(wù)器，實(shí)現(xiàn)緩存替換策略的改進(jìn)。緩存替換策略對(duì)應(yīng)的算法存放在目錄/src/repl下面，通過(guò)在Squid代理服務(wù)器的Squid.conf文件中修改配置信息以及決定采用哪種緩存替換算法，通過(guò)自己編寫(xiě)shell腳本分析access.log日志文件，獲取請(qǐng)求命中率和字節(jié)命中率。在Squid中修改GDSF算法的源代碼，在其配置文件中設(shè)置使用的算法，可以得到3.2章節(jié)中描述的GDS-TFH算法。Squid工作流程如下：

圖1　Squid代理服務(wù)器的工作流程

第1步，客戶(hù)端向代理進(jìn)程發(fā)送請(qǐng)求；第2步，代理進(jìn)程將請(qǐng)求和數(shù)據(jù)緩存中的數(shù)據(jù)做對(duì)比；第3步，若是數(shù)據(jù)緩存中有請(qǐng)求的信息，執(zhí)行第3.1.1步，若是數(shù)據(jù)緩存中沒(méi)有請(qǐng)求的信息，執(zhí)行第3.2.1步；

當(dāng)執(zhí)行了第3.1.1步后，執(zhí)行第3.1.2步，代理進(jìn)程將從數(shù)據(jù)緩存中獲取的內(nèi)容發(fā)送給客戶(hù)端；當(dāng)執(zhí)行了第3.2.1步后，執(zhí)行第3.2.2步，代理進(jìn)程發(fā)送請(qǐng)求給遠(yuǎn)端服務(wù)器獲取緩存；當(dāng)執(zhí)行了第3.2.2步后，執(zhí)行第3.2.3步，遠(yuǎn)端服務(wù)器將獲得的緩存信息發(fā)送給代理進(jìn)程；當(dāng)執(zhí)行了第3.2.3步后，執(zhí)行第3.2.4步，代理進(jìn)程判斷從遠(yuǎn)端服務(wù)器下載的緩存是否需要存進(jìn)緩存中，然后將獲取的緩存信息發(fā)送給客戶(hù)端。

3.2實(shí)驗(yàn)結(jié)果分析

本次實(shí)驗(yàn)的分析數(shù)據(jù)來(lái)源于Squid代理服務(wù)器的日志Access.log文件中，日志文件里面包含了10個(gè)域。通過(guò)采集文件里面的請(qǐng)求完成的時(shí)間、HTTP請(qǐng)求命中的結(jié)果、被訪問(wèn)文件的大小，獲得詳細(xì)的請(qǐng)求命中率和字節(jié)命中率。另外，實(shí)驗(yàn)將對(duì)比LRU、GDSF、GDS-TFH算法在請(qǐng)求命中率和字節(jié)命中率方面的命中結(jié)果。結(jié)果如表1所示：

表1　命中率和緩存大小之間的關(guān)系

從關(guān)系表中可以看出，使用不同的緩存替換算法，請(qǐng)求命中率和字節(jié)命中率不一樣。在同等環(huán)境下，GDS-TFH算法優(yōu)于GDSF算法優(yōu)于LRU算法，另外，GDSF算法和GDS-TFH算法的字節(jié)命中率明顯優(yōu)于LRU算法。用戶(hù)可以根據(jù)需求，在某些條件下，選擇效率較高的算法。

4　結(jié)語(yǔ)

影響Web端性能的因素有很多，因此，在不同的需求環(huán)境下，可以使用其他的方法來(lái)提高Web端的性能。本文通過(guò)請(qǐng)求命中率和字節(jié)命中率評(píng)價(jià)緩存替換算法的性能優(yōu)劣，比LRU算法、GDSF算法多考慮了時(shí)間間隔對(duì)緩存的影響和對(duì)象被訪問(wèn)的頻率的結(jié)合，提高了命中率，改善了Web端的性能。但是由于改進(jìn)的算法考慮的因素多，當(dāng)訪問(wèn)量很大的時(shí)候，增加了計(jì)算的復(fù)雜度，因此還需要繼續(xù)研究和優(yōu)化。

［1］Softpedia.The Average Web Page Loads in 2.45 Seconds Google Reveals［EB/OL］.http∶//news.softpedia.com/news/The-Average-Web-Page-Loads-in-2-45-Seconds-Google-Reveals-265446.shtml.

［2］Aguilera M K，Strom R E，Sturman D C，et al.Matching Events in a Content-based Subscription System［C］.Proceedings of the 18th ACM Symposium on the Principles of Distributed Computing，Atlanta，GA，1999-05.

［3］Ashayer G，Leung H K Y，Jacobsen H A.Predicate Matching and Subscription Matching in Publish/Subscribe Systems［C］.Proceedingsof the 22nd International Conference on Distributed Computing Systems Workshops，2002.

［4］Arlitt M，F(xiàn)riedrich R，Jin T.Performance Evaluation of Web Proxy Cache Replacement Policies［J］.Performance Evaluation Journal，2000∶149-164.

［5］周揚(yáng)發(fā)，武斌，國(guó)海濤.一種改進(jìn)的Web代理服務(wù)器GDS緩存替換算法.虛擬運(yùn)營(yíng)與云計(jì)算——第十八屆全國(guó)青年通信學(xué)術(shù)年會(huì)論文集（下冊(cè)）［C］，2013.

［6］石磊，葉海琴，衛(wèi)琳，連衛(wèi)民.Web緩存命中率與字節(jié)命中率關(guān)系［J］.計(jì)算機(jī)工程，2007，33（13）∶84-86.

［7］Ludmila，Cherkasova.Improving WWW Proxies Preformance With Greedy-Dual-Size-Frequency Caching Policy.HPL–98–69（R.1），November，1998.

［8］張旺俊.Web緩存替換策略與預(yù)取技術(shù)的研究［D］.中國(guó)科學(xué)技術(shù)大學(xué)，2011.DOI∶10.7666/d.d141607.

［9］周揚(yáng)發(fā).Web代理服務(wù)器的緩存技術(shù)研究［D］.北京郵電大學(xué)，2014.

［10］楊春貴，吳產(chǎn)樂(lè)，彭鴻雁.一種有效的Web代理緩存替換算法［J］.計(jì)算機(jī)工程，2007，33（3）∶43-44，47.

GDS-TFH；Cache Replacement；Proxy Server

Research and Implement of Web Front-End Performance Optimization

WANG Ting，REN Hong-ming
（College of Information Engineering，Shanghai Maritime University，Shanghai201306）

To improve the performance of Web front-end cache，studies the traditional cache replacement algorithm GDS and based on it，presents a new cache replacement algorithm named GDS-TFH.The modified algorithm not only considers the size of object，but also the time interval between the object's visit times and the visit times or frequency.Analyzes the improved algorithm GDS-TFH in the limited cache room request hit rate and byte hit rate has a good upgrade.

1007-1423（2016）20-0024-05

10.3969/j.issn.1007-1423.2016.20.005

王婷（1991-），女，江蘇淮安人，碩士，研究方向?yàn)檐浖_(kāi)發(fā)方法與軟件項(xiàng)目管理

2016-05-04

2016-07-05