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

王紅濤，馮連強(qiáng)，劉穎，陳蕊，郝樂

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

專題綜述

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

王紅濤，馮連強(qiáng)，劉穎，陳蕊，郝樂

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

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

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

0 前言

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

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

1 Web緩存相關(guān)理論及技術(shù)

1.1 Web緩存原理

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

1.2 Web對象訪問特性

Web對象具有的訪問特性是Web緩存機(jī)制的基礎(chǔ)，同時(shí)也是設(shè)計(jì)Web緩存替換算法的重要依據(jù)。Web對象訪問具有以下特性：

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

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

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

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

利用訪問特性能夠?qū)σ言L問對象的未來訪問趨勢進(jìn)行預(yù)測，從而評價(jià)該對象未來再次被訪問的可能性大小，并以此為根據(jù)設(shè)計(jì)連鑄智能化云平臺Web緩存替換算法。

1.3 Web緩存替換策略

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

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

1.4 Web緩存評價(jià)指標(biāo)

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

2 GDSR緩存替換策略

2.1 Web對象相鄰關(guān)系

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

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

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

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

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

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

2.2 Web對象引用關(guān)系

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

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

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

圖1 不同對象類型數(shù)量統(tǒng)計(jì)圖

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

表1 日志分析統(tǒng)計(jì)表

從分析結(jié)果可以看出引用關(guān)系在Web對象的訪問中普遍存在，并且引用源數(shù)量和被引用對象的數(shù)量差距極大，即少數(shù)的對象造成了引用關(guān)系的大量出現(xiàn)。

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

表 2 不同類型對象引用情況統(tǒng)計(jì)表

從統(tǒng)計(jì)結(jié)果可以看出，大部分的引用是由Web頁面(text/html)類型的對象引起的，因?yàn)樗罅績?nèi)部資源(如圖片，JavaScript代碼等)的引用，同時(shí)還包含很多超級鏈接。而被引用的對象類型中圖片(image)所占比例最多，此外，除了Web頁面(text/html)類型以外，JavaScript代碼(text/javascript)和CSS文件(text/css)被引用的次數(shù)也比較多。因?yàn)閳D片、JavaScript代碼和CSS文件很少被用戶直接訪問，基本都是作為其他頁面的內(nèi)部資源被引用，因此被引用次數(shù)較多。并且這些類型的同一個(gè)對象經(jīng)常會(huì)被多個(gè)不同的引用源引用，因?yàn)楹芏嗑W(wǎng)站內(nèi)的多個(gè)網(wǎng)頁會(huì)使用相同的圖片、JavaScript代碼和CSS文件。而超級鏈接的目標(biāo)通常是Web頁面，因此Web頁面(text/html)被引用次數(shù)也較多。

圖 2 不同類型對象被引用情況統(tǒng)計(jì)圖

2.3 引用度計(jì)算模型

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

若一個(gè)對象i被N個(gè)對象引用，則對象i由于引用關(guān)系的存在而再次被訪問的概率為

(1)

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

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

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

(2)

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

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

(3)

因此進(jìn)一步得到

(4)

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

GDSF是一種基于目標(biāo)函數(shù)的替換算法，該算法綜合了頻率、大小、訪問代價(jià)三個(gè)因素，綜合性能優(yōu)秀。GDSF策略計(jì)算每個(gè)對象的緩存價(jià)值并對其排序，每從緩存價(jià)值最低的對象開始替換。GDSF策略緩存價(jià)值計(jì)算方法如下

(5)

式中，F(xiàn)i為對象i的訪問次數(shù)；Si為對象i的大??；Ci為將對象i引入緩存空間的代價(jià)；L為衰老因子。

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

(6)

其中，F(xiàn)Di為對象i被獨(dú)立訪問的次數(shù)。GDSR策略使用將GDSF策略中的對象訪問次數(shù)進(jìn)行了分解，將引用產(chǎn)生的訪問次數(shù)從中去除。對象的訪問次數(shù)使用引用度進(jìn)行計(jì)算，從而確保不被重復(fù)累計(jì)。λ是一個(gè)調(diào)節(jié)參數(shù)，用來調(diào)整引用度對整個(gè)緩存價(jià)值的影響程度；Ci為將對象i引入緩存空間的代價(jià)。

本文采用的計(jì)算對象的獲取代價(jià)的標(biāo)準(zhǔn)為網(wǎng)絡(luò)標(biāo)準(zhǔn)：網(wǎng)絡(luò)標(biāo)準(zhǔn)：認(rèn)為對象的獲取代價(jià)與獲取該對象需要傳輸?shù)陌鼣?shù)相關(guān)，將對象獲取代價(jià)設(shè)為

(7)

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

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

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

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

圖3 可緩存性判斷流程圖

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

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

圖5 Web對象引用度計(jì)算流程圖

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

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

圖6 對象替換流程圖

圖7 GDSR工作流程圖

(未完，待續(xù))

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

中國機(jī)械工業(yè)集團(tuán)有限公司科技發(fā)展基金項(xiàng)目(SINOMACH12科167號)

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

TP393

A

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