連鑄智能化平臺Web訪問緩存替換策略

王紅濤，馮連強，劉穎，陳蕊，郝樂

(中國重型機械研究院股份公司，陜西 西安 710032)

專題綜述

連鑄智能化平臺Web訪問緩存替換策略

王紅濤，馮連強，劉穎，陳蕊，郝樂

(中國重型機械研究院股份公司，陜西 西安 710032)

針對目前連鑄技術與信息化技術高度融合，但已有的緩存替換策略對于數據交互傳輸存在局限性的問題，提出一種引用度模型來對Web訪問對象的空間局部性進行評價，并將其作為設計緩存替換策略的依據，提出一種基于引用度的緩存替換策略GDSR，改善了緩存替換策略的性能，為Web緩存替換策略的設計提供了一個新的方向和思路。

緩存替換策略；空間局部性；引用度模型

0 前言

互聯網的不斷發展使得網絡訪問量不斷增加，但服務器及網絡基礎設施的性能是有限的，服務器和網絡帶寬的負載都長期處于飽和狀態，導致網絡服務質量QOS下降。Web緩存技術是提高Web訪問速度的一個有效的手段。緩存替換策略是Web緩存技術的核心，它是決定Web緩存性能的最為重要的因素。依托中國機械工業集團有限公司“高品質特殊鋼特超厚板連鑄技術及創新平臺”科技發展基金項目，針對生產現場與設計中心智能化云平臺存在大量數據交互問題，進行了此方面內容的一些研究。

目前，已有的緩存替換策略大部分都利用Web對象訪問特性中的時間局部性、頻率分布特性和大小分布特性，而Web對象訪問的空間局部性在Web緩存替換策略中利用較少。本文提出一種引用度模型來對Web訪問對象的空間局部性進行評價，并將其作為設計緩存替換策略的依據，提出基于引用度的緩存替換策略GDSR，改善了緩存替換策略的性能。

1 Web緩存相關理論及技術

1.1 Web緩存原理

Web緩存的工作機制為：當連鑄智能化云平臺收到用戶請求時，首先在Web緩存中查找該對象，當對象在緩存中存在有效副本時，緩存直接將對象發送給用戶；當對象副本存在但已經失效時，從服務器更新對象，并將Web對象發送給用戶；當對象副本不存在時，從原始服務器獲取該對象，若緩存空間未滿，則將對象放入緩存，否則根據替換策略，用該對象替換陳舊對象，最后將該對象發送給用戶。

1.2 Web對象訪問特性

Web對象具有的訪問特性是Web緩存機制的基礎，同時也是設計Web緩存替換算法的重要依據。Web對象訪問具有以下特性：

(1)時間局部性。指請求過的連鑄智能化云平臺Web對象再次被請求的可能性較高。

(2)空間局部性。指與當前被訪問對象相鄰的對象在將來被訪問的概率較大，但Web對象訪問中空間局部性比較特殊：首先，Web對象沒有實際的存儲地址，因此兩個對象的相鄰關系由它們在訪問序列中的相鄰情況決定，例如，當連鑄智能化云平臺序列中間包數據對象在結晶器數據對象被訪問不久之后被訪問，那么可以認為結晶器數據對象與中間包數據對象相鄰，這種相鄰關系以多對多的形式普遍存在于Web對象訪問序列中。其次，Web對象訪問的空間局部性具有很強的單向性：如果中間包數據對象在結晶器數據對象被訪問不久之后被訪問，那么當結晶器數據對象被再次訪問時中間包數據對象很有可能再次被訪問，而中間包數據對象的訪問通常并不影響結晶器數據對象被再次訪問的概率，并且當結晶器數據對象不被訪問時，中間包數據對象也很有可能不會被訪問。

(3) 頻率分布。用戶對連鑄智能化云平臺Web對象的訪問通常存在一些熱點，將Web對象的訪問頻率按照降序進行排列，可以得到Web對象請求的分布序列，而這種分布大多服從Zipf-like定律。

(4)大小分布。當對象的大小超過某一數值之后，將概率分布服從Pareto分布。這種分布規律說明用戶訪問通常集中于較小的網絡對象。

利用訪問特性能夠對已訪問對象的未來訪問趨勢進行預測，從而評價該對象未來再次被訪問的可能性大小，并以此為根據設計連鑄智能化云平臺Web緩存替換算法。

1.3 Web緩存替換策略

連鑄智能化云平臺緩存替換策略的目標是盡可能保留那些緩存價值較高的對象，刪除那些緩存價值較低的對象。緩存替換策略主要分為以下幾類：(1)基于訪問時間間隔的替換策略主要利用了Web對象訪問特性中的時間局部性；(2)基于訪問頻率的替換策略利用了Web對象訪問特性中的頻率分布特性；(3)基于對象大小的替換策略利用了Web對象訪問特性中對象大小的分布特性；(4)基于目標函數的替換策略綜合利用Web對象訪問特性中的時間局部性、頻率分布特性和對象大小分布特性，同時結合訪問代價，利用目標函數計算出Web對象緩存價值，以此作為替換時的依據，每次將緩存價值最低的對象替換出緩存空間。其代表算法有GDS、GDSF、GD*等。

目前連鑄智能化云平臺Web對象訪問的空間局部性主要被用于Web預取技術中，在Web緩存替換算法中利用較少，比較有代表性的算法為PGDSF，該算法在GDSF算法基礎上進行改進，算法利用歷史訪問序列建立起基于Markov鏈模型的頻繁訪問樹，并以此為基礎得到一個預測對象集，該集合內的對象將不被替換出緩存空間。

1.4 Web緩存評價指標

連鑄智能化云平臺Web緩存系統的主要評價指標有：(1)命中率。從緩存中得到請求對象的數量占總請求數的比例；(2)字節命中率。從緩存中得到的對象的大小，即字節數，占總請求字節數的比例；(3)延遲率。從原始服務器得到對象與從緩存中獲取對象的時間之差；(4)移除率。從緩存中移除對象的次數與處理的請求總數的比值。

2 GDSR緩存替換策略

2.1 Web對象相鄰關系

相鄰關系是連鑄智能化云平臺Web對象訪問空間局部性的重要依據，對Web對象訪問的相鄰關系進行具體分析。

定義1 令X→Y表示兩個Web訪問對象X和Y在訪問序列中存在相鄰關系，并且Y緊跟在X之后被訪問。訪問序列中的相鄰關系分為三種：

(1)訪問邏輯相鄰。它是用戶訪問傾向的真實體現，它表征了用戶的上網瀏覽信息的行為習慣。假設每種訪問只請求一個獨立的Web對象，分別為A～F，那么當一個用戶具有訪問習慣模式“a-f-c-d-e-b”時，該用戶的訪問會產生A→F、F→C、C→D、D→E和E→B相鄰關系。對一個用戶來說，這種習慣可能是長時間不會改變的，并且可能有很多用戶具有相同或相似的訪問習慣，因此這種由用戶訪問習慣造成的訪問邏輯相鄰關系是比較穩定的，具有規律性。

(2)偶發物理相鄰。指Web緩存服務器接收到的訪問序列中兩個對象存在相鄰關系，但它們在邏輯上完全無關，只是在訪問的物理順序上出現相鄰。

(3)引用相鄰。由于連鑄智能化云平臺Web對象訪問過程中內在的引用關系產生的相鄰關系，Web對象的引用關系有兩種：一種是Web對象(主要是頁面)內引用其它資源文件產生的引用關系；另一種是用戶點擊超鏈接產生的引用關系。引用相鄰一旦出現將穩定存在，只是再次出現的概率大小不同。

通過分析不難看出，訪問邏輯相鄰和引用相鄰能夠真正體現出Web對象訪問的空間局部性，而偶發物理相鄰不具有任何參考意義。由于引用相鄰關系的存在是明確的，因此具有較高的識別效率，并且引用相鄰重復出現的概率很高，對空間局部性的體現具有很大的價值。因此本文通過引用相鄰關系來對Web對象訪問的空間局部性進行部分抽取。

2.2 Web對象引用關系

(1)引用關系的來源。瀏覽器加載頁面時會自動獲取被引用的資源，并在頁面中進行展示，或者將其作為動態代碼和頁面樣式使用。這種引用關系在頁面HTML代碼相關部分不變時固定存在，即只要頁面被請求，那么瀏覽器就會請求被引用的資源，這種引用關系就是內部引用。

(2)引用關系的獲取。Web對象之間的引用關系同樣可以從HTTP協議中獲取，HTTP的請求頭中存在一個可選字段“Referer”，當一個對象是由于引用而被請求時，該字段會出現在請求頭中，其值為引用源的URL。如果一個HTTP請求報文中不存在“Referer”字段，則表示該對象的訪問請求是獨立的。因此，通過檢查HTTP請求頭中的“Referer”字段，能夠很容易的獲取Web對象之間的引用關系。

(3)引用關系的分析。為驗證引用關系的普遍存在，本文對連鑄智能化云平臺中某核心網絡設備1小時的流量日志進行了分析。該日志共包含1 771 417條有效訪問記錄，其中不重復的URL訪問960 315條，總的有效流量為31 155 285 780字節。其中共出現62種不同的對象類型，各類型所占數量如圖 1所示。

圖1 不同對象類型數量統計圖

當日志中的訪問記錄中HTTP請求中包含“Referer”字段，則說明該請求來自其它對象的引用，日志引用概況如表1所示。

表1 日志分析統計表

從分析結果可以看出引用關系在Web對象的訪問中普遍存在，并且引用源數量和被引用對象的數量差距極大，即少數的對象造成了引用關系的大量出現。

針對對象類型分析引用和被引用情況，發現引用其它對象的類型大量集中在是“text/html”、“application/x-shockwave-flash”、“text/xml”、“text/css”及“text/plain”類型的對象，見表 2。

表 2 不同類型對象引用情況統計表

從統計結果可以看出，大部分的引用是由Web頁面(text/html)類型的對象引起的，因為它包含大量內部資源(如圖片，JavaScript代碼等)的引用，同時還包含很多超級鏈接。而被引用的對象類型中圖片(image)所占比例最多，此外，除了Web頁面(text/html)類型以外，JavaScript代碼(text/javascript)和CSS文件(text/css)被引用的次數也比較多。因為圖片、JavaScript代碼和CSS文件很少被用戶直接訪問，基本都是作為其他頁面的內部資源被引用，因此被引用次數較多。并且這些類型的同一個對象經常會被多個不同的引用源引用，因為很多網站內的多個網頁會使用相同的圖片、JavaScript代碼和CSS文件。而超級鏈接的目標通常是Web頁面，因此Web頁面(text/html)被引用次數也較多。

圖 2 不同類型對象被引用情況統計圖

2.3 引用度計算模型

綜上所述，引用關系在連鑄智能化云平臺Web對象訪問中普遍存在，而這種引用關系將會直接影響被引用對象再次被訪問的概率。

若一個對象i被N個對象引用，則對象i由于引用關系的存在而再次被訪問的概率為

(1)

其中，P(n)為第n個引用源對象被再次訪問的概率，PR(n,i)為第n個引用源對象被再次訪問時引用對象i的概率。當引用關系為內部引用時PR(n,i)為1，當引用關系為非內部引用時0≤PR(n,i)≤1。

本文提出使用一個引用度計算模型來量化引用關系對對象再次被訪問可能性的影響。引用度是Web對象訪問中引用關系的量化表示，其目的在于將引用關系中隱含的一部分Web對象訪問空間局部性抽取出來，以便作為緩存替換策略的設計依據。引用度計算模型定義如下

若一個對象i存在N個引用源S1,S2,…,Sn，則對象i的引用度Ri為

(2)

式中，PR(Sn,i) 為引用源Sn被訪問時引用對象i的概率;R(Sn,i)為引用源Sn引用對象i的次數。其中

PR(Sn,i)=R(Sn,i)/F(Sn)

(3)

因此進一步得到

(4)

2.4GDSR緩存替換策略工作原理

GDSF是一種基于目標函數的替換算法，該算法綜合了頻率、大小、訪問代價三個因素，綜合性能優秀。GDSF策略計算每個對象的緩存價值并對其排序，每從緩存價值最低的對象開始替換。GDSF策略緩存價值計算方法如下

(5)

式中，Fi為對象i的訪問次數；Si為對象i的大小；Ci為將對象i引入緩存空間的代價；L為衰老因子。

將GDSF策略與引用度結合，將引用度加入緩存價值的計算過程，提出GDSR策略，其緩存價值計算方法如下

(6)

其中，FDi為對象i被獨立訪問的次數。GDSR策略使用將GDSF策略中的對象訪問次數進行了分解，將引用產生的訪問次數從中去除。對象的訪問次數使用引用度進行計算，從而確保不被重復累計。λ是一個調節參數，用來調整引用度對整個緩存價值的影響程度；Ci為將對象i引入緩存空間的代價。

本文采用的計算對象的獲取代價的標準為網絡標準：網絡標準：認為對象的獲取代價與獲取該對象需要傳輸的包數相關，將對象獲取代價設為

(7)

其中,Si為對象i的大小。536為TCP分段大小，單位是字節。

GDSF策略設計時考慮了Web對象訪問特性的頻率分布、大小分布特性。GDSR策略在此基礎上，通過引用度將空間局部性加入到緩存價值的判斷依據中，從而提高連鑄智能化云平臺緩存替換策略的性能。

2.5GDSR緩存替換策略工作流程

(1) 可緩存性判斷流程。Web對象的可緩存性的判斷流程如圖 3所示。為了降低算法實現的復雜度和運行代價，本文對判斷標準進行了簡化：在對HTTP狀態碼進行判斷時，只接受可緩存狀態碼，不考慮消極緩存類型的狀態碼；由于HTTP參數的獲取需要進行復雜的HTTP解析，因此不使用HTTP參數作為判斷依據。

圖3 可緩存性判斷流程圖

(2)引用信息更新流程。對象的引用信息需要作為引用度計算的依據，因此每當對象被引用訪問時，需要更新其引用信息，引用信息更新流程如圖 4所示。Web對象引用度計算流程如圖 5所示。

圖4 對象引用信息更新流程圖

圖5 Web對象引用度計算流程圖

(3)對象替換流程。當連鑄智能化云平臺Web緩存空間已滿時，需要執行替換操作將緩存中的一部分對象替換出去，替換的依據是從緩存中價值最小的對象開始，將價值小于待緩存對象的對象依次替換出，直到釋放了足夠的緩存空間。但是這種替換并不總能成功，如果當前緩存中價值最小的對象的價值高于待緩存對象的價值，則替換不能進行，此時需要將之前替換出的對象恢復，因此需要一個待刪除隊列來暫時存儲這些對象。對象替換具體流程如圖 6所示。

(4)GDSR策略工作流程。本文在以上設計的基礎上完成了GDSR策略工作流程的設計，GDSR策略工作流程如圖 7所示。

圖6 對象替換流程圖

圖7 GDSR工作流程圖

(未完，待續)

Web cache replacement strategy for intelligent platform of continuous casting

WANG Hong-tao, FENG Lian-qiang, LIU Ying, CHEN Rui, HAO Le

(China National Heavy Machinery Research Institude, Co., Ltd., Xi’an 710032, China)

Currently, the continuous casting technology and information technology are highly integrated. However, the existing cache replacement strategies have limitations on the data transmission. This paper proposed a reference model to evaluate the spatial locality of Web object accessing, and used the reference model as the basis of a new cache replacement policy-greedy-dual-size reference (GDSR). GDSR improved the performance of cache replacement strategy, provided a new direction and ideas for the design of Web cache replacement policies.

cache replacement strategy; spatial locality; reference model

2016-11-16；

2016-12-09

中國機械工業集團有限公司科技發展基金項目(SINOMACH12科167號)

王紅濤(1986- )，男，中國重型機械研究院股份公司工程師。

TP393

A

1001-196X(2017)02-0001-06