Web端性能優化的研究與實現

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

Web端性能優化的研究與實現

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

為了提高Web端緩存的性能，在傳統的緩存替換算法GDS基礎上提出新的緩存替換算法GDS-TFH。改進的算法除了考慮被訪問對象的大小，還考慮被緩存的對象訪問次數之間的時間間隔和被訪問對象訪問的次數或被訪問的頻率。分析在有限的緩存空間內改進的算法GDS-TFH在請求命中率和字節命中率方面有比較好的提升。

GDS-TFH；緩存替換；代理服務器

0　引言

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

1　對現有緩存替換策略的調研

1.1被使用過的緩存替換策略部分簡介

已經出現的緩存替換策略有很多，例如Least Recently Used（LRU）、Least Frequently Used（LFU）、SIZE、LRU Threshold、Log（Size）+LRU、Lowest Latency First、Hybrid、Lowest Relative Value（LRV）等。可以把這些緩存替換算法依據不同的標準分成4類：基于訪問對象被訪問的次數（Least Frequently Used（LFU）-最不經常使用）、基于被訪問對象訪問之間的時間間隔（Least Recently Used（LRU）-最近最少使用）、基于被訪問對象的大小（SIZE緩存置換算法）、基于被訪問對象保存的價值（Hybrid緩存置換算法）。

1.2評判緩存替換策略的標準

通過衡量對象的大小區分請求命中率和字節命中率。目前為止，還沒有一種算法可以兩者兼顧，使緩存替換最優。通過Arlitt M的實驗可知，基于被訪問對象的大小的緩存替換算法能夠使請求命中率值更高，基于訪問對象被訪問的次數的緩存替換算法能夠使字節命中率值更高。判斷緩存替換算法性能的標準一般有2種：

（1）請求命中率

請求命中率由用戶通過瀏覽器發出的Requests被命中的次數與用戶通過瀏覽器發出的所有Requests之比而得。當用戶通過瀏覽器訪問網頁時，若是此次請求的網頁在緩存中命中緩存，用σi=1表示，若是沒有在此次請求的網頁在緩存中命中緩存，用σi=0表示。請求的Requests之和用N表示。請求命中率（RHR）的公式是：

（2）字節命中率

字節命中率由用戶通過瀏覽器發出的Requests被命中的所有文檔的大小與用戶通過瀏覽器發出的Requests的所有的文檔大小之比而得。當用戶通過瀏覽器訪問網頁時，若是此次請求的網頁在緩存中命中緩存，用σi=1表示，若是沒有在此次請求的網頁在緩存中命中緩存，用σi=0表示。請求的Requests之和用N表示。用size（i）表示對象i的文檔大小。字節命中率（BHR）的公式是：

已知判斷緩存替換算法的性能有兩種標準，研究明白兩者之間的關系，有利于理解Web端緩存替換算法之間的優劣。使用公式（2）除以公式（3），得到的是所有請求對象的平均大小與所有命中對象的平均大小之比，即可形象化地理解請求命中率（RHR）和字節命中率（BHR）之間的關系。即：

因為：

在Web緩存系統中，一般RHR比BHR大，故（6）的值大于1，即所有請求對象的平均大小比所有命中對象的平均大小大，說明小文件更容易被命中。

2　GDS緩存替換算法的研究與改進

2.1艾賓浩斯遺忘曲線

艾賓浩斯遺忘曲線描述了人類大腦對新事物遺忘的規律。用戶對某件事務感興趣的程度可以引用艾賓浩斯遺忘曲線的規律，表示用戶對某對象感興趣的程度。

圖1

曲線的表達式可以近似的表示為：

ΔT為表示對象i相鄰被訪問次數之間的時間間隔，單位為ms。

2.2GDS算法

GDS（Greedy Dual Size）算法的基本思想是通過目標函數計算所有的對象i的函數值，將函數值由大到小排列，當有限的緩存空間的存儲量達到95%時，將函數值最小的對象清除。現有的GDS緩存替換算法是Cao 和Irani在研究分析了13種不同的緩存替換算法，得

在公式（8）中，L為膨脹因子，初始值為0，當有對象在緩存中被替換時，被替換對象的目標函數值賦值給新進入緩存對象的L。Size（i）為對象i的大小。Value （i）為對象i被引入到緩存需要的代價。

GDSF（Greedy Dual Size Frequency）算法因為需要考慮對象訪問的頻率，所以實現起來稍微復雜一些。當出現被訪問次數多的對象被替換時，GDSF算法就會顯現出比GDS算法更好的健全性。GDSF算法的目標函數中引入新的變量Fr（i），表示對象i訪問的頻率。GDSF算法的目標函數為：到了計算目標函數的計算方法：

但是，當對象訪問頻率大且對象i的大小比較小的時候，近期卻不被用戶訪問，當然可能以后也不被訪問到，這時就會造成部分緩存空間被長期占用，使RHR和BHR的效率降低。

2.3GDS算法的改進算法GDS-TFH

從訪問的時間間隔來看，訪問間隔的時間越短，對象被訪問的概率越大。從訪問的頻率來看，訪問的頻率（次數）越大，對象被訪問的概率也越大。可以通過對時間間隔加權，再對不同分組中的時間間隔使用余弦相似性的方法提高算法的優越性，當余弦值越大，兩組的時間間隔越相似，用戶對對象訪問具有規律性，表明用戶對此對象越感興趣。另外，當用戶對某些數據記憶越深刻，表示用戶對此請求越感興趣，則對象請求的目標函數也越大。

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

用空間向量表示：

其中：

ΔT表示對象i相鄰被訪問次數之間的時間間隔，單位為ms。ΔTi中的下標i表示第i個時間間隔。Fr（i）表示對象被訪問的次數，且Fr（i）≥4。I在1到Fr（i）-3之間。對時間間隔依據艾賓浩斯遺忘曲線進行加權，即：

其中ai，ai+1，ai+2位常數，分別對應艾賓浩斯遺忘曲線中H（ΔTi），H（ΔTi+1）），H（ΔTi+2）的值。再求分組之后的時間間隔之間的余弦相似性。即，對wdFr（i）-3和wdi求余弦相似性，即：

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

用戶感興趣程度考慮了被訪問緩存對象的時間間隔和被訪問緩存對象出現的頻率（次數）和艾賓浩斯遺忘曲線函數，用戶感興趣程度UIL（ΔT，Fr（i），H（ΔT））的計算值越大，則用戶訪問對象具有時間規律，表示用戶對此緩存的對象越感興趣，目標函數越大，對象緩存的價值越大，反之就越小。故，改進后的GDS-TFH算法具體函數為公式（14）：

簡要概括GDS-TFH算法的使用過程：

①：L為膨脹因子，初始值為0，UIL（ΔT，Fr（i），H （ΔT））為1。

②：代理服務器處理用戶發出的請求，當有限的緩存剩余量大于5%時，需要被緩存的對象直接進入緩存；當有限的緩存剩余量小于5%時，需要被緩存的對象計算對象i的目標函數，使用公式（14），將結果與緩存中的所有對象的函數值做比較，替換出價值最小的對象空間并且將函數值最小的H賦值給對象i的L。

3　實驗環境的搭建和結果分析

3.1實驗環境的搭建

實驗環境搭建在CentOS6系統上，使用Squid代理服務器，實現緩存替換策略的改進。緩存替換策略對應的算法存放在目錄/src/repl下面，通過在Squid代理服務器的Squid.conf文件中修改配置信息以及決定采用哪種緩存替換算法，通過自己編寫shell腳本分析access.log日志文件，獲取請求命中率和字節命中率。在Squid中修改GDSF算法的源代碼，在其配置文件中設置使用的算法，可以得到3.2章節中描述的GDS-TFH算法。Squid工作流程如下：

圖1　Squid代理服務器的工作流程

第1步，客戶端向代理進程發送請求；第2步，代理進程將請求和數據緩存中的數據做對比；第3步，若是數據緩存中有請求的信息，執行第3.1.1步，若是數據緩存中沒有請求的信息，執行第3.2.1步；

當執行了第3.1.1步后，執行第3.1.2步，代理進程將從數據緩存中獲取的內容發送給客戶端；當執行了第3.2.1步后，執行第3.2.2步，代理進程發送請求給遠端服務器獲取緩存；當執行了第3.2.2步后，執行第3.2.3步，遠端服務器將獲得的緩存信息發送給代理進程；當執行了第3.2.3步后，執行第3.2.4步，代理進程判斷從遠端服務器下載的緩存是否需要存進緩存中，然后將獲取的緩存信息發送給客戶端。

3.2實驗結果分析

本次實驗的分析數據來源于Squid代理服務器的日志Access.log文件中，日志文件里面包含了10個域。通過采集文件里面的請求完成的時間、HTTP請求命中的結果、被訪問文件的大小，獲得詳細的請求命中率和字節命中率。另外，實驗將對比LRU、GDSF、GDS-TFH算法在請求命中率和字節命中率方面的命中結果。結果如表1所示：

表1　命中率和緩存大小之間的關系

從關系表中可以看出，使用不同的緩存替換算法，請求命中率和字節命中率不一樣。在同等環境下，GDS-TFH算法優于GDSF算法優于LRU算法，另外，GDSF算法和GDS-TFH算法的字節命中率明顯優于LRU算法。用戶可以根據需求，在某些條件下，選擇效率較高的算法。

4　結語

影響Web端性能的因素有很多，因此，在不同的需求環境下，可以使用其他的方法來提高Web端的性能。本文通過請求命中率和字節命中率評價緩存替換算法的性能優劣，比LRU算法、GDSF算法多考慮了時間間隔對緩存的影響和對象被訪問的頻率的結合，提高了命中率，改善了Web端的性能。但是由于改進的算法考慮的因素多，當訪問量很大的時候，增加了計算的復雜度，因此還需要繼續研究和優化。

［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，Friedrich R，Jin T.Performance Evaluation of Web Proxy Cache Replacement Policies［J］.Performance Evaluation Journal，2000∶149-164.

［5］周揚發，武斌，國海濤.一種改進的Web代理服務器GDS緩存替換算法.虛擬運營與云計算——第十八屆全國青年通信學術年會論文集（下冊）［C］，2013.

［6］石磊，葉海琴，衛琳，連衛民.Web緩存命中率與字節命中率關系［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緩存替換策略與預取技術的研究［D］.中國科學技術大學，2011.DOI∶10.7666/d.d141607.

［9］周揚發.Web代理服務器的緩存技術研究［D］.北京郵電大學，2014.

［10］楊春貴，吳產樂，彭鴻雁.一種有效的Web代理緩存替換算法［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-），女，江蘇淮安人，碩士，研究方向為軟件開發方法與軟件項目管理

2016-05-04

2016-07-05