范新燦

(深圳職業(yè)技術(shù)學(xué)院 電信學(xué)院，廣東 深圳518055)

1 Web緩存技術(shù)

互聯(lián)網(wǎng)已經(jīng)滲透進(jìn)人們生活的方方面面，Web成為獲取、發(fā)布、加工和處理信息的重要平臺(tái)。Web用戶的快速增長，導(dǎo)致Web流量的爆炸性增長，Internet帶寬產(chǎn)生擁擠，出現(xiàn)訪問延遲、通信錯(cuò)誤增多、服務(wù)器過載等一系列問題，網(wǎng)絡(luò)帶寬的提高已經(jīng)跟不上用戶數(shù)量增長的速度，單純利用增加帶寬來解決速度遲緩問題不具有伸縮性，費(fèi)用也相當(dāng)昂貴。

獲取一個(gè)Web文檔的代價(jià)取決于該文檔的字節(jié)數(shù)、傳輸中鏈接可獲得的帶寬以及中間經(jīng)過的網(wǎng)段個(gè)數(shù)，若能將文檔的復(fù)本從原始服務(wù)器緩存到離用戶較近的機(jī)器中，顯然可以大大縮短訪問的距離，不僅可以減少檢索延遲，還可以減少網(wǎng)絡(luò)負(fù)載。Web緩存技術(shù)是一種避免Web服務(wù)瓶頸、縮減信息流量、提高可伸縮性的手段，是最常用、經(jīng)濟(jì)的解決網(wǎng)絡(luò)擁塞和服務(wù)器過載的方法。利用Cache技術(shù)，復(fù)制用戶經(jīng)常訪問的內(nèi)容，將其保存在緩存服務(wù)器中，降低了主干網(wǎng)絡(luò)冗余帶寬流量和原始服務(wù)器的負(fù)載壓力，減少文件在網(wǎng)絡(luò)上的重復(fù)傳輸，可降低網(wǎng)絡(luò)帶寬的浪費(fèi)，減輕Web服務(wù)器的負(fù)載，最終降低用戶的等待時(shí)間。

經(jīng)常被訪問的文件被緩存到了臨近的代理中，從而避免了從遠(yuǎn)端的服務(wù)器上傳輸數(shù)據(jù)，使傳輸時(shí)間最小化。由于網(wǎng)絡(luò)流量的縮減，沒有緩存的文件會(huì)相對(duì)更快地在網(wǎng)絡(luò)中傳輸，因而服務(wù)器響應(yīng)的速度也得到了提高，這些工作負(fù)荷被整個(gè)互聯(lián)網(wǎng)上的緩存代理分擔(dān)了，有效地縮減了對(duì)網(wǎng)絡(luò)帶寬的消耗，從而降低了網(wǎng)絡(luò)的流量，緩解了網(wǎng)絡(luò)擁塞。Web緩存技術(shù)成為互聯(lián)網(wǎng)建構(gòu)中廣泛應(yīng)用的技術(shù)。

2 決策樹

決策樹(decision tree)一般都是自上而下生成的。每個(gè)決策或事件（即自然狀態(tài)）都可能引出兩個(gè)或多個(gè)事件，導(dǎo)致不同的結(jié)果，把這種決策分支畫成圖形很像一棵樹的枝干，故稱決策樹。 決策樹的構(gòu)成有四個(gè)要素：決策節(jié)點(diǎn)、方案枝、狀態(tài)節(jié)點(diǎn)和概率枝。

決策樹法的決策程序如下：

(1)繪制樹狀圖，根據(jù)已知條件排列出各個(gè)方案和每一方案的各種自然狀態(tài)；

(2)將各狀態(tài)概率及損益值標(biāo)于概率枝上；

(3)計(jì)算各個(gè)方案期望值并將其標(biāo)于該方案對(duì)應(yīng)的狀態(tài)節(jié)點(diǎn)上；

(4)進(jìn)行剪枝，比較各個(gè)方案的期望值，并標(biāo)于方案枝上，將期望值小的(即劣等方案剪掉)所剩的最后方案為最佳方案。

決策樹算法是一種逼近離散函數(shù)值的方法。決策樹算法具有分類精度高、形成的模式簡單、對(duì)噪聲數(shù)據(jù)有很好的健壯性等優(yōu)點(diǎn)，因而是目前應(yīng)用最為廣泛的歸納推理算法之一，在數(shù)據(jù)挖掘中受到研究者的廣泛關(guān)注。

本文研究的智能緩存模型采用GATree決策樹算法，該算法是用遺傳算法優(yōu)化產(chǎn)生的決策樹算法。采用二叉樹結(jié)構(gòu)來表達(dá)決策樹，每個(gè)節(jié)點(diǎn)有兩個(gè)不同節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有隨機(jī)值，選擇一個(gè)隨機(jī)的屬性，如果其是離散的，則自由選擇值；如果這個(gè)屬性是連續(xù)的，則隨機(jī)選擇最小最大值范圍之內(nèi)的一個(gè)整數(shù)值，這樣可以減少搜索空間的范圍。

算法的基本形式引入了變異和交叉操作的最小范圍，變異操作選擇的是期望生成的樹的隨機(jī)節(jié)點(diǎn)，替代了節(jié)點(diǎn)的具有隨機(jī)選擇值的測試值，當(dāng)隨機(jī)節(jié)點(diǎn)是葉子節(jié)點(diǎn)時(shí)，替代了具有新的隨機(jī)選擇類的意境設(shè)置好的類。交叉操作選擇兩個(gè)隨機(jī)節(jié)點(diǎn)并且交換這些節(jié)點(diǎn)的子樹，不會(huì)影響決策樹的連貫性。

3 緩存模型構(gòu)建

設(shè)計(jì)基于決策樹的智能緩存模型模擬器，如圖1所示，模型總體分為構(gòu)建數(shù)據(jù)建模、模擬器和緩存輸出模塊。模擬器是模型的關(guān)鍵，分為NextAccess離散化、構(gòu)造決策樹、權(quán)重分配和決策樹輸出4個(gè)模塊。

模型首先讀取Web日志中的記錄，并將其進(jìn)行數(shù)據(jù)建模。根據(jù)Web請求序列數(shù)據(jù)請求對(duì)象，將產(chǎn)生的數(shù)據(jù)存入緩存數(shù)據(jù)表中。根據(jù)數(shù)據(jù)流的輸入，構(gòu)建決策樹智能緩存策略的數(shù)據(jù)挖掘模型。首先將同一URL下次被訪問前接受的請求總數(shù)（NextAccess）作為分類的目標(biāo)，進(jìn)行離散化，構(gòu)建決策樹。權(quán)重分配模塊采用典型的替換算法LRU進(jìn)行頁面替換，當(dāng)緩存中沒有足夠的容量來容納新來的Web對(duì)象時(shí)，調(diào)用替換算法做出替換決定。根據(jù)當(dāng)前請求序列的預(yù)測結(jié)果，更新決策樹節(jié)點(diǎn)信息，觀察屬性集，計(jì)算預(yù)取闕值，進(jìn)行決策樹輸出。

3.1 數(shù)據(jù)建模緩存數(shù)據(jù)表

智能模型設(shè)計(jì)一個(gè)Web數(shù)據(jù)表，數(shù)據(jù)來源是代理服務(wù)器日志文件中的數(shù)據(jù)，產(chǎn)生包括預(yù)處理和編碼來實(shí)現(xiàn)數(shù)據(jù)選擇、清洗和數(shù)據(jù)轉(zhuǎn)換。設(shè)計(jì)數(shù)據(jù)表tb_cache，關(guān)鍵字段定義如下：

Ndir：URL 的目錄層

FirstDir：URL的第一層目錄

NextAccess:同一URL下次被訪問前接受的請求總數(shù)

LastAccess:同一URL上次被訪問到當(dāng)前的請求總數(shù)

FileExtension：請求的URL文件的文件名后綴的代碼標(biāo)識(shí)

Size：返回客戶端的字節(jié)

數(shù)據(jù)表的每一行數(shù)據(jù)存儲(chǔ)代理服務(wù)器的一個(gè)事務(wù)，但Web文檔可被緩存必須是HTTP協(xié)議、是GET請求、請求中沒有“?”和HTTP響應(yīng)碼是200，這些數(shù)據(jù)需要在模型中進(jìn)行過濾清洗，把相應(yīng)事務(wù)導(dǎo)入數(shù)據(jù)庫中。

3.2 構(gòu)建基于決策樹分類的模擬器

數(shù)據(jù)表字段NextAccess存儲(chǔ)的是同一URL下次被訪問前接受的請求總數(shù)，為了把決策樹作為智能緩存策略的數(shù)據(jù)挖掘模型，需要將NextAccess離散化、構(gòu)造決策樹所用的觀察屬性集和權(quán)重分配算法。下面作幾個(gè)定義：

ORCLCaches(s)：緩存大小為 s的使用 ORCL緩存策略的Web緩存系統(tǒng)；

ORCLAvgDSize(s)：Web緩存中的平均文檔的大?。?/p>

ORCLTertile(t,s),t{1，2，3}：緩存存儲(chǔ)狀態(tài)為 t*33.3%時(shí)的文檔數(shù)；

ORCLMax(s)：緩存滿時(shí)的個(gè)體數(shù)，等于 ORCLTertiles(3,s)。

3.2.1 NextAccess的離散化

在決策樹模型設(shè)計(jì)中，將NextAccess作為分類的目標(biāo)，利用決策樹作為一個(gè)分類器，預(yù)測NextAccess的值，將值離散化到幾個(gè)類別中，定義如下：

Class0：NextAccess[1，ORCLTertile(1,s)];

Class1：NextAccess[ORCLTertile(1,s)，ORCLTertile(2,s)];

Class2：NextAccess[ORCLTertile(2,s)，ORCLTertile(3,s)];

Class3：NextAccess[ORCLTertile(3,s)，ORCLMax(s)];

緩存系統(tǒng)在經(jīng)過NextAccess次請求后，可能成功緩存某一資源，這個(gè)概率依賴于緩存系統(tǒng)中的實(shí)體個(gè)數(shù)，當(dāng) NextAccess在[1，ORCLTertile(1,s)]之間時(shí)，經(jīng)過 NextAccess次請求后有66.66%～100%的可能性；當(dāng)NextAccess 在[ORCLTertile(1,s)，ORCLTertile(2,s)]之間時(shí) ，概率下降到 33.33%～66.66%； 界于 [ORCLTertile(2,s)，ORCLMax(s)]之間，概率下降到0-33.33%，因此低類值的要給予高優(yōu)先權(quán)。

3.2.2 權(quán)重分配

替換策略的權(quán)重分配如下：

WLRU(Ei)=j，j為文檔 E的第j次訪問。

S3替換策略的權(quán)重分配如下：

Ws3(Ei)=j+a(c)*AvgDsize(s)/Ei.size;c∈{0,1,2,3};c為文檔Ei根據(jù)GATree算法所在類別。

a(3)=Max(s)；

a(c+1)=2a(c)；

Ei.size為文檔Ei的大小。

3.2.3 觀察屬性集與輸出決策樹

將 Ndir、FirstDir、LastAccess、FileExt、Hour、Size 作為GATree算法的觀察屬性。GATree輸出決策樹如下：

4 緩存模型試驗(yàn)結(jié)果

實(shí)驗(yàn)采用網(wǎng)站的真實(shí)訪問，獲得訪問日志數(shù)據(jù)，進(jìn)行數(shù)據(jù)預(yù)處理，建立緩存數(shù)據(jù)表，并采用本文提出的基于決策樹算法構(gòu)建模型。仿真實(shí)驗(yàn)選擇傳統(tǒng)的替換算法LRU和本文所建立緩存模型進(jìn)行比較，從緩存性能的指標(biāo)命中率（HR）、字節(jié)命中率（BHR）、延遲率（LR）三個(gè)環(huán)節(jié)進(jìn)行分析。HR表示用戶從緩存中取到的對(duì)象數(shù)和所獲得的總對(duì)象數(shù)，BHR表示用戶從緩存中獲取對(duì)象的平均字節(jié)數(shù)和從網(wǎng)上獲取的全部字節(jié)數(shù)的比值，LR表示從服務(wù)器下載對(duì)象到客戶端緩存的總時(shí)間。

從如圖 2、圖 3、圖 4所示，基于決策樹的職能緩存模型比傳統(tǒng)的LRU替換算法具有較高的命中率和字節(jié)命中率，并且延遲率較小，可見本文提出的緩存優(yōu)化模型較傳統(tǒng)的算法減少了緩存文件的冗余度，提高了命中率，改善了系統(tǒng)性能。

[1]鄧?yán)?，陳志剛，黃鍵，等.基于 AOP的智能 Web緩存框架[J]. 計(jì)算機(jī)工程，2008，34(22)：283-285.

[2]韓向春，田玉根.基于預(yù)測的Web緩存替換算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010,31(1):110-113.

[3]BALAMASH A，KLUNZ M.An overview ofweb caching replacementalgorithms[J].IEEE Communications Surveys and Tutorials，2004，6(2)：44-56.

[4]Ristenpart T Back to the Future：A framework for automatic malware removal and system repair[C]//Proc.of the Annual Computer Security Applications Conference.Miami，F(xiàn)L，USA：IEEE Computer Society，2006.