姚 瑤

(鄭州工程技術(shù)學(xué)院 信息工程學(xué)院，河南 鄭州 450044)

0 引 言

隨著網(wǎng)絡(luò)用戶和服務(wù)內(nèi)容的爆炸式增長，用戶對網(wǎng)絡(luò)服務(wù)質(zhì)量的要求越來越高，尤其是用戶訪問延遲正面臨著嚴峻的考驗。為了解決上述問題，學(xué)者們雖然采取了較為有效的方法，比如基于時間局部性原理的Web緩存機制[1]、基于空間局部性原理的Web預(yù)取機制[2]，以及基于地域性的CDN系統(tǒng)，但是對網(wǎng)絡(luò)延遲的影響仍然受限于內(nèi)存、命中率和帶寬等因素。

Web預(yù)取技術(shù)試圖在用戶提出請求之前主動提取資源，在一定程度上提高了命中率，降低了訪問延遲。最近客戶端訪問歷史常被用來預(yù)測在不久最可能被訪問的資源。但是存在投機性，有時還會額外增加帶寬。因此，該方法需要謹慎使用。也正是因為潛在的帶寬受限而使得Web預(yù)取技術(shù)在商業(yè)領(lǐng)域的應(yīng)用不是很好。Mozilla Firefox瀏覽器和Google搜索引擎相繼采用Web預(yù)取技術(shù)減少延遲。

利用數(shù)據(jù)去重技術(shù)分析數(shù)據(jù)的冗余度，從而適當減少網(wǎng)絡(luò)數(shù)據(jù)傳輸量，由此釋放被占用的帶寬資源[3]。該技術(shù)可以利用數(shù)據(jù)對象之間的信息冗余，獲得遠高于傳統(tǒng)壓縮方法及增量備份方法的空間利用率。數(shù)據(jù)去重技術(shù)早期應(yīng)用在存儲系統(tǒng)和備份系統(tǒng)中，目前是云存儲應(yīng)用中一種重要的存儲優(yōu)化技術(shù)[4-7]?；诖鎯ο到y(tǒng)內(nèi)在的數(shù)據(jù)相似性和數(shù)據(jù)重復(fù)訪問的特點，數(shù)據(jù)去重技術(shù)還被應(yīng)用于內(nèi)存性能優(yōu)化和延長SSD使用壽命等方面。隨著人們不斷利用其數(shù)據(jù)縮減優(yōu)勢來改進和優(yōu)化現(xiàn)有存儲和網(wǎng)絡(luò)系統(tǒng)的不足，數(shù)據(jù)去重技術(shù)的應(yīng)用將會越來越廣泛。文獻[8]提出基于網(wǎng)頁正文結(jié)構(gòu)和特征串的相似網(wǎng)頁去重算法，雖然取得了較高的去重率，但是應(yīng)用于預(yù)取系統(tǒng)時導(dǎo)致延遲較高，并且降低了預(yù)測準確率。在云計算環(huán)境下，文獻[9]提出了一種基于流水線的數(shù)據(jù)讀取模型，但是隨著冗余率增加，系統(tǒng)速度降低，影響了預(yù)取性能。文獻[10]在客戶端實現(xiàn)重復(fù)數(shù)據(jù)刪除技術(shù)，通過對文件進行分塊和在備份過程中去除重復(fù)數(shù)據(jù)塊，減少了客戶端與服務(wù)期間需要傳輸?shù)臄?shù)據(jù)量，使得文件備份的速度獲得較大提高，也降低了網(wǎng)絡(luò)帶寬要求，顯著提高了網(wǎng)絡(luò)備份系統(tǒng)的性能，但卻沒有考慮預(yù)取。

Web預(yù)取技術(shù)受限于帶寬，而數(shù)據(jù)去重技術(shù)由于減少轉(zhuǎn)移數(shù)據(jù)的體積從而釋放部分占用帶寬。所以，將預(yù)取技術(shù)與數(shù)據(jù)去重技術(shù)結(jié)合起來在減少網(wǎng)絡(luò)延遲方面有重大意義。文中首先改進了Web預(yù)取系統(tǒng)，其次通過移植數(shù)據(jù)去重模塊實現(xiàn)了預(yù)取系統(tǒng)的雙端去重，最后通過實驗所提方法進行驗證。

1 基于數(shù)據(jù)去重的Web預(yù)取系統(tǒng)

對傳統(tǒng)的Web預(yù)取系統(tǒng)框架進行改進，引入了客戶端重復(fù)數(shù)據(jù)去重模塊(CDM)和代理服務(wù)器端重復(fù)數(shù)據(jù)去重模塊(SDM)，實現(xiàn)了雙端數(shù)據(jù)去重。

1.1 Web預(yù)取系統(tǒng)架構(gòu)

1.1.1 代理服務(wù)器端

改進后的代理服務(wù)器端增加了響應(yīng)重組模塊、SDM模塊和響應(yīng)攔截模塊等，如圖1所示。

圖1 改進的代理服務(wù)器端體系結(jié)構(gòu)

服務(wù)器連接模塊：主要負責(zé)直接連接客戶端和服務(wù)器端，尤其是在處理響應(yīng)的時候，該模塊第一時間接收最原始HTTP響應(yīng)消息報頭，并傳遞給客戶端。然后把從服務(wù)器端接收的所有資源數(shù)據(jù)原封不動地傳遞給客戶端。文中所提方法對HTTP響應(yīng)消息報頭做了進一步的改進。報頭信息不僅僅包括現(xiàn)有保證連接的附加標題信息，而且涉及修改了標題值。例如，需要修改Content-Length。此外，由于該系統(tǒng)需要對消息實體做拆分處理，所以需要第一時間從服務(wù)器端接收完整的消息實體。當該過程終止時，再把修正過的實體內(nèi)數(shù)據(jù)回傳給客戶端。

響應(yīng)攔截模塊：由于改變了代理服務(wù)器端HTTP響應(yīng)報文的處理方式，故新設(shè)一個響應(yīng)攔截模塊，攔截來自服務(wù)器端的最原始的HTTP響應(yīng)報文，存儲在臨時緩沖區(qū)內(nèi)并做預(yù)處理，判斷傳輸方式是標準數(shù)據(jù)還是分塊方式。該模塊的具體工作：第一，檢查是否存在ETag(被請求變量實體的值)，如果存在取出其值；第二，檢查Content-Length和Transfer-Encoding字段，如果是前者存在并有效，則HTTP服務(wù)器響應(yīng)的報文必須和消息內(nèi)容的傳輸長度完全一致。對于動態(tài)的內(nèi)容或者在發(fā)送數(shù)據(jù)前不能判定長度的情況下，可以使用分塊的方法傳送編碼。該模塊檢索客戶端緩存關(guān)聯(lián)資源的自定義報頭的、以數(shù)組形式存儲的資源標識符。然后把裝有存儲的響應(yīng)頭、實體消息數(shù)據(jù)和資源標識符數(shù)組的緩沖區(qū)傳送給代理服務(wù)器數(shù)據(jù)去重模塊SDM。

SDM模塊：對響應(yīng)攔截模塊轉(zhuǎn)交過來的消息實體的數(shù)據(jù)執(zhí)行拆分。分兩個步驟完成：塊劃分和數(shù)據(jù)去重。該模塊存儲的主要字段是ETag、Chunk和Versions Historic。ETag存儲唯一ETag資源標識符，由資源版本號索引。Chunk存儲塊元信息，SDM模塊處理的所有資源版本號的所有塊，由塊哈希索引。Versions Historic存儲了所有資源版本號的Chunk的鏈接隊列，由資源版本號索引。

SDM模塊首先檢查ETag的狀態(tài)，如果是新資源，則生成一個新的資源標識符存儲于ETag中，使用分塊算法為資源分塊，生成塊鏈表，存儲在Versions Historic中。如果ETag已經(jīng)存在，意味著該資源先前已經(jīng)被SDM處理過，不需要重新分塊，僅檢索Versions Historic中存儲的資源版本號的塊鏈表。接下來，SDM執(zhí)行數(shù)據(jù)去重算法，使用兩個緩沖區(qū)分別存儲元數(shù)據(jù)和非冗余數(shù)據(jù)。SDM模塊遍歷塊鏈表，試圖找到一個匹配的散列塊內(nèi)的客戶端參考源。如果不匹配，SDM模塊在已經(jīng)被處理過的當前資源版本塊中再做一次查找(例如：自冗余數(shù)據(jù)案例)。如果找到一個匹配成功的冗余塊，SDM模塊添加塊的元信息到對應(yīng)緩沖區(qū)。對于非冗余塊，實體消息數(shù)據(jù)需要添加到非冗余緩沖區(qū)。SDM模塊建立了元數(shù)據(jù)和非冗余內(nèi)容的最終組合，通知重組響應(yīng)模塊數(shù)據(jù)拆分過程已經(jīng)完成。

響應(yīng)重組模塊：準備和發(fā)送回傳的響應(yīng)報文。響應(yīng)報頭信息進行重組，更新/創(chuàng)建Content-Length附加上新的實體消息數(shù)據(jù)長度；添加兩個新的報頭信息X-vrs(資源版本號標識符)和X-mtd(元數(shù)據(jù)長度)。響應(yīng)重組模塊通過附加非冗余內(nèi)容塊到元數(shù)據(jù)塊之后重組新的實體內(nèi)容數(shù)據(jù)塊(entity content data block)，最終重組后的回傳響應(yīng)報文包含報頭和消息實體內(nèi)容。

組合過的響應(yīng)報文被多功能的服務(wù)器連接模塊攔截，背負式(piggybacks the hintlist)報頭信息并丟棄未改變的實體消息塊，最終重組過的HTTP響應(yīng)報文傳遞給客戶。

預(yù)測引擎模塊：主要任務(wù)是在每一次資源被請求的時候預(yù)測即將可能訪問的頁面。該模塊依據(jù)預(yù)測算法將產(chǎn)生一系列最近被訪問頻率最高的資源的URL，并將結(jié)果放入決策數(shù)據(jù)庫中。

1.1.2 客戶端

改進后的客戶端引入了Resource Versions數(shù)據(jù)文件模塊、CDM模塊，體系結(jié)構(gòu)如圖2所示。

圖2 改進的客戶端體系結(jié)構(gòu)

Resource Versions數(shù)據(jù)文件：客戶端新增的模塊，用來存儲重組的消息實體數(shù)據(jù)，由資源標識符索引。實質(zhì)上擔任了客戶端瀏覽器的角色。數(shù)據(jù)存儲文件中的資源信息與Fetched Objects中的信息是同步的，存儲的是資源關(guān)聯(lián)而不是具體的消息實體。資源版本號(Resource Versions)由客戶端數(shù)據(jù)去重模塊CDM保存。

CDM模塊：攔截客戶端UserRequests或者是Prefetch Requests模塊發(fā)送的HTTP請求報文。具體工作：查詢Resource Versions數(shù)據(jù)存儲文件，獲得客戶端緩存中的所有資源的資源標識符。CDM通知Communications Interceptor(通信攔截)模塊對報文做繼續(xù)處理。CDM分配一個緩沖區(qū)，采用塊劃分算法重組來自服務(wù)器的原始資源。CDM檢查元數(shù)據(jù)，每一chunk由一個元組引用，復(fù)制Resource Versions數(shù)據(jù)存儲中的消息實體數(shù)據(jù)到重組緩沖區(qū)。當數(shù)組和chunk之間不匹配時，CDM復(fù)制非冗余數(shù)據(jù)塊，維持原chunk的順序。通過這種方法，原資源版本被重組。CDM在Resource Version數(shù)據(jù)存儲中存儲最新的資源版本號，如果發(fā)現(xiàn)相同資源較早的版本出現(xiàn)，則替換出去，保證客戶端總能保證資源最新的版本。

預(yù)取管理模塊(Prefetch Manager Block)：預(yù)取引擎位于客戶端則會有較好的預(yù)取效果。故在客戶端添加預(yù)取管理模塊。通過讀取記錄模塊的訪問隊列，檢查預(yù)取對象池(Fetched Objects)，確認資源是否已經(jīng)預(yù)取過。若沒有預(yù)取過，則把請求發(fā)送給服務(wù)器，預(yù)取管理模塊創(chuàng)建多個User Request線程并等待一個新的請求。當從服務(wù)器接收到響應(yīng)資源時，預(yù)取管理模塊檢查其URL是否在預(yù)取隊列中，若在則移除URL并插入到預(yù)取對象池。預(yù)取模塊同時檢查請求隊列是否為空，若為空，當一個新用戶請求入隊時直接被送至服務(wù)器。當一個新的客戶端請求入隊時，預(yù)取管理模塊暗示刪除已經(jīng)預(yù)取過的資源并清空Hint List數(shù)據(jù)存儲。

User Requests模塊接收來自預(yù)取管理模塊的請求，再傳遞給Request模塊。為了避免后來資源的預(yù)取，當從服務(wù)器接收到一個響應(yīng)資源時，User Requests把響應(yīng)報頭的hint插入到預(yù)取隊列(Prefetch List)數(shù)據(jù)存儲中，把資源的URL插入到預(yù)取對象池中。

1.2 數(shù)據(jù)去重模塊基本原理

文中采用的數(shù)據(jù)去重系統(tǒng)來源于dedupHTTP系統(tǒng)。其中，CDM和SDM分別工作在客戶端和代理服務(wù)器端。雙端數(shù)據(jù)去重系統(tǒng)架構(gòu)如圖3所示。

圖3 雙端數(shù)據(jù)去重架構(gòu)

具體工作流程如下：

當SDM接收到一個給定的資源請求，檢索由CDM發(fā)送的參考源標識符的一個自定義的請求報頭。然后SDM從服務(wù)器中取出該資源。接收過充分響應(yīng)的報頭和數(shù)據(jù)后，SDM給資源分配一個新的標識符。將資源數(shù)據(jù)劃分為塊，塊的元信息存儲在數(shù)據(jù)存儲文件中。在這個數(shù)據(jù)存儲庫中SDM保證了塊的哈希索引的元信息資源的所有版本的所有塊。

SDM遍歷資源所有塊。對每個資源塊，將在參考源具有相同散列塊。如果有一塊沒有匹配的參考源，SDM會在當前響應(yīng)資源塊中搜索。因此，冗余檢測不僅在資源在CDM的高速緩存執(zhí)行，而且在資源被送交CDM時也執(zhí)行。SDM組合最終響應(yīng)資源發(fā)給CDM。響應(yīng)由元數(shù)據(jù)段開始。元數(shù)據(jù)的大小(字節(jié))存儲在一個自定義HTTP響應(yīng)報頭中。元數(shù)據(jù)的內(nèi)容從響應(yīng)的資源標識符開始。在每個參考源中包含了四元組，每個元組包含的信息是CDM能夠在緩存中找到每一個冗余塊的必需信息。具體包含的字段是當前響應(yīng)的偏移量Offset，資源標識符Resource identifier，資源內(nèi)部的偏移量InOffset和塊的長度。

數(shù)組按照在原始響應(yīng)中相應(yīng)塊的順序排列。在元數(shù)據(jù)塊的結(jié)尾，附加上非冗余數(shù)據(jù)內(nèi)容，仍然保持原響應(yīng)中的順序。由于對該元組和非冗余數(shù)據(jù)的順序維護，CDM僅需數(shù)組的第一偏移量就可知道如何在非冗余數(shù)據(jù)附加上冗余數(shù)據(jù)。

當CDM收到響應(yīng)后，為所有的數(shù)據(jù)重建原有的資源，包括從本地緩存資源中復(fù)制塊引用信息和復(fù)制接收到響應(yīng)的非冗余數(shù)據(jù)內(nèi)容。CDM并不存儲任何一塊元信息，也不需要發(fā)送或存儲哈希。

通信攔截模塊：負責(zé)對CDM和請求端信息做語法處理。當Communications Interceptor接收到CDM的通知時，該模塊為信息添加自定義報頭“X-vrs”，即客戶端參考源的X-vrs報頭就包含了資源標識符。Communications Interceptor把報頭信息附加在HTTP請求報頭上，給Requests模塊，最后傳給服務(wù)器。

當從代理服務(wù)器端接收到HTTP響應(yīng)報文，Communications Interceptor模塊對報頭進行語法分析，分別從X-vrs和X-mtd報頭提取資源標識符和元數(shù)據(jù)的長度。為了進一步處理拆分數(shù)據(jù)，分別進入三個不同的緩沖區(qū)，一個緩沖區(qū)存放報頭信息，一個存放元數(shù)據(jù)，一個存放非冗余數(shù)據(jù)。最后又將所有數(shù)據(jù)傳給CDM。

1.3 基于滑動窗口的數(shù)據(jù)塊劃分

基于滑動窗口的數(shù)據(jù)塊劃分方法主要依據(jù)塊的內(nèi)容劃分，該方法的查重率高、分塊更為合理有效[11-12]。SDM模塊采用LBFS算法將服務(wù)器響應(yīng)給客戶端的每一個資源版本號劃分為索引數(shù)據(jù)chunk。

第一步：當客戶端發(fā)出一個請求時，服務(wù)器將資源劃分為若干索引chunk。判斷出該資源的哪些部分客戶端已經(jīng)存在，哪些部分是新的、需要發(fā)送的。

令ci為第i個資源流的字節(jié)，k為Karp-Rabin塊的長度，b為進制的基數(shù)。Karp-Rabin塊[13]的哈希如下：

H(ci…ci+k)=ci×bk-1+ci+1×bk-2+…+

ck-1×b+ck

其中，b是一個常數(shù)。

函數(shù)的應(yīng)激性允許計算下一個字節(jié)的哈希，如下：

H(ci+1…ci+1+k)={[H(ci…ci+k)-ci×bk]+

ck+1}×b

第二步：選擇代表資源的哈希。為了節(jié)省內(nèi)存空間，選擇合適的哈希作為較大數(shù)據(jù)塊的邊界。選擇窗口機制，能夠提供更好的冗余檢測。分別確定最小和最大的chunk尺寸，對比期望chunk大小，基于文中方法的內(nèi)容可能會造成過大的chunk或者過小的chunk。

塊哈希表的查找復(fù)雜度是O(p/k)，其中p是參考源中塊的數(shù)量，k是一個常數(shù)。最壞情況下，參考源中不存在塊信息。SDM的哈希查找算法的復(fù)雜度是O(n*m*p)，其中n是當前處理的塊數(shù)量，m是參考源的數(shù)量。當m相當小，例如最終用戶并且緩存中只剩下很少的資源數(shù)量，大文件小容量塊，將得到n*p?m，可見算法復(fù)雜度的決定性影響因子是塊的大小。

2 實驗與結(jié)果分析

2.1 實驗參數(shù)

系統(tǒng)的評價標準分別是字節(jié)節(jié)省率和延遲。前者是指每次請求所節(jié)省的字節(jié)傳輸作為冗余塊的總和，即沒有從代理發(fā)送客戶端而是從客戶機獲得引用資源的數(shù)據(jù)塊的字節(jié)數(shù)的總和。后者指對于一個給定資源，從客戶端GET請求直到客戶端響應(yīng)該資源的時間間隔。

客戶端機器配置：Intel Pentium 4，2.16 GHz，4 GB內(nèi)存，操作系統(tǒng)Linux Mint 14-32b。服務(wù)器配置：Intel Pentium 4,3.20 GHz，6 GB內(nèi)存，操作系統(tǒng)Linux Mint 14-32b。實驗運行在帶寬為54 MB/s的局域網(wǎng)。限制帶寬下測試，模擬藍牙有效帶寬2.1 Mb/s。

工作負載中應(yīng)用的各種測試是通過下載一個典型的新聞網(wǎng)站(www.dn.pt)3個層次的深度的文件。實驗中，請求所有的工作文件，相當于客戶機-服務(wù)器之間傳輸約20 MB的文件。具體地，最大的字節(jié)數(shù)為214 595，最小字節(jié)數(shù)為298，平均字節(jié)數(shù)29 672，總大小為19.8 MB。

客戶端請求自動使用Wget實用程序。為了模擬一個真正的用戶發(fā)起Web導(dǎo)航，引入用戶請求允許預(yù)取操作之間的空閑時間，使用了Wget開關(guān)“-w10”和“randomwait”，主要為了引入一個5、15秒請求之間的隨機延遲。

2.2 實驗結(jié)果分析

實驗一：重點分析當執(zhí)行數(shù)據(jù)去重時，冗余檢測效率對塊大小的依賴情況。預(yù)取(PF)和數(shù)據(jù)去重(DDP)同時執(zhí)行(PFON-DDPON)，塊的平均尺寸依次設(shè)置為32、64、128、256、512、1 024和2 048個字節(jié)。一般情況下，設(shè)置最小塊的大小等于平均塊尺寸的1/4，塊的最大尺寸等于平均塊大小的2倍。實驗結(jié)果參見圖4和圖5。

圖4 PFON_DDPON相對于PFON_DDPOFF 字節(jié)節(jié)省率(帶寬54 Mbs)

圖4顯示了PFON_DDPON時刻相對于PFON_DDPOFF時刻的字節(jié)節(jié)省率。結(jié)果表明，最好的冗余檢測獲得的塊大小為128字節(jié)，節(jié)省了34.2%的字節(jié)數(shù)量。

圖5 相對于標準HTTP傳輸情況 (PFON_DDPON，帶寬54 Mbs)

圖5顯示延遲時間和塊大小成反比關(guān)系。原因是隨著塊尺寸的增加，塊的數(shù)量減少，那么數(shù)據(jù)去重的計算開銷也要增加。因此數(shù)據(jù)去重算法執(zhí)行時間也要兼顧。

為了獲得更高的字節(jié)節(jié)省率，設(shè)置塊大小為128字節(jié)。具體實驗對比了PFOFF_DDPOFF和PFOFF_DDPON，PFON_DDPOFF和PFON_DDPON。帶寬設(shè)置為54 Mbs，在字節(jié)節(jié)省率方面，PFOFF_DDPON方法比PFOFF_DDPOFF方法節(jié)省了34.1%，PFON_DDPON方法比PFON_DDPOFF方法節(jié)省了34.2%。結(jié)果表明，引入數(shù)據(jù)去重技術(shù)可以節(jié)省34%的字節(jié)傳輸。

實驗二：使用該系統(tǒng)傳輸每種資源的延遲時間與標準HTTP傳輸時延遲的比值對比如圖6所示。對比標準HTTP傳輸，僅有去重時能夠減少大約8%的延遲，有預(yù)取時減少的延遲更明顯，分別減少14.7%和8.9%。差別的原因在于數(shù)據(jù)去重算法存在一定的計算開銷。綜合考慮可見，當使用預(yù)取和數(shù)據(jù)去重時，數(shù)據(jù)去重保證了一定的字節(jié)節(jié)省率，但是以適度增加的等待時間為代價，保證了系統(tǒng)的整體性能。

圖6 相對于標準HTTP傳輸延遲情況

實驗三：評估在可達到的冗余值中對不同帶寬的影響效果。分別在LAN條件(54 Mbs)和藍牙條件(2.1 Mbs)下進行PFON_DDPON操作的比較測試，如表1所示。

表1 不同帶寬下相對于HTTP標準傳輸 的延遲 %

結(jié)果表明，帶寬對字節(jié)節(jié)省率基本無影響。在藍牙情況下每個資源的延遲時間減少的幅度是LAN情況下減少的一半，分別為4.4%和8.9%。由于預(yù)取頻度依賴于用戶請求之間的空閑時間，增加的延遲意味著請求需要更長的時間完成，因此可以減少空閑時間，從而減少預(yù)取請求啟動的機會。

3 結(jié)束語

提出一種基于客戶-服務(wù)器端雙端去重的Web預(yù)取系統(tǒng)的設(shè)計方法，旨在提高網(wǎng)絡(luò)訪問效率，改善用戶預(yù)期的延遲。實驗結(jié)果表明，該系統(tǒng)一方面相對于正常傳輸?shù)淖止?jié)數(shù)傳輸量顯著減少，節(jié)約了大約34%；另一方面可以實現(xiàn)減少大約8%的用戶預(yù)期的延遲，即使因為網(wǎng)絡(luò)的客觀條件影響實際效果，也能夠保證降低4%的延遲。未來將進一步研究如何更準確地判定數(shù)據(jù)去重階段的相似塊以及如何降低數(shù)據(jù)去重算法的時間開銷。