時(shí)立鋒 劉?？? 包翰榕

【摘要】 信息技術(shù)不斷的更新和發(fā)展推動(dòng)全球進(jìn)入大數(shù)據(jù)時(shí)代。傳統(tǒng)型廣域網(wǎng)傳輸方案伴隨通信量的急劇增長(zhǎng)已經(jīng)很難滿足用戶的數(shù)據(jù)傳輸要求。面對(duì)廣域網(wǎng)遇到的現(xiàn)狀，主要研究了一種數(shù)據(jù)去重算法，并將其用于廣域網(wǎng)優(yōu)化系統(tǒng)中。重點(diǎn)研究了數(shù)據(jù)分塊算法，采用一種新型的滑動(dòng)塊檢測(cè)技術(shù)，并利用時(shí)間淘汰算法選出重復(fù)的數(shù)據(jù)塊，從而提高重復(fù)數(shù)據(jù)削減率，可以有效節(jié)約網(wǎng)絡(luò)帶寬并加快廣域網(wǎng)傳輸速率。

【關(guān)鍵詞】 數(shù)據(jù)去重 數(shù)據(jù)分塊算法 廣域網(wǎng)優(yōu)化 時(shí)間淘汰算法

隨著信息技術(shù)產(chǎn)業(yè)的飛速發(fā)展，當(dāng)前已涌現(xiàn)出各種新型網(wǎng)絡(luò)應(yīng)用，致使廣域網(wǎng)上的帶寬流量迅猛增加，網(wǎng)絡(luò)也因此出現(xiàn)帶寬緊缺、延時(shí)高等問題。

面對(duì)上述問題，廣域網(wǎng)加速隨即成為討論的熱點(diǎn)。數(shù)據(jù)去重技術(shù)脫穎而出，它能夠?qū)W(wǎng)絡(luò)中的數(shù)據(jù)實(shí)施全面的、不間斷的重復(fù)數(shù)據(jù)檢測(cè)，而且其壓縮效率明顯優(yōu)于傳統(tǒng)概念的壓縮技術(shù)。調(diào)查顯示，廣域網(wǎng)中有接近60%的流量數(shù)據(jù)都是重復(fù)的[1]。例如，網(wǎng)絡(luò)中同一文件可能在某些時(shí)間段內(nèi)分發(fā)給多個(gè)人，因此便造成相同數(shù)據(jù)反復(fù)傳送[2]。郵件群發(fā)也會(huì)導(dǎo)致大量冗余[3]；互聯(lián)網(wǎng)上的web頁(yè)面同樣也會(huì)造成大量重復(fù)數(shù)據(jù)[4]。在廣域網(wǎng)流量中約48%的網(wǎng)頁(yè)內(nèi)容幾乎相同[5]；如果能在廣域網(wǎng)加速系統(tǒng)中結(jié)合去重技術(shù)，將極大限度提升整個(gè)帶寬的利用率。

在這個(gè)以用戶體驗(yàn)為主導(dǎo)的時(shí)代，去重優(yōu)化系統(tǒng)能夠?yàn)閭€(gè)人和企業(yè)提供優(yōu)質(zhì)的網(wǎng)絡(luò)體驗(yàn)。其原理是：采用數(shù)據(jù)去重技術(shù)對(duì)TCP流進(jìn)行去重處理，采用雙向緩存存儲(chǔ)字段，并以非常小的代價(jià)消除重復(fù)數(shù)據(jù)，確保冗余流量不會(huì)重復(fù)發(fā)送，該方法有效減少了不必要的帶寬浪費(fèi)，此舉可以達(dá)到提高傳輸速率和帶寬利用的目的。通常情況下，廣域網(wǎng)加速系統(tǒng)會(huì)同時(shí)部署在客戶端和服務(wù)端，因此可以保證對(duì)通過的TCP流進(jìn)行雙向數(shù)據(jù)優(yōu)化。系統(tǒng)示意圖如圖1所示。

數(shù)據(jù)去重系統(tǒng)一般由TCP透明代理和去重處理兩部分構(gòu)成。TCP透明代理的主要功能是截取數(shù)據(jù)流交給去重模塊，處理完冗余后再將去重之后的數(shù)據(jù)進(jìn)行發(fā)送，另外一端數(shù)據(jù)去重系統(tǒng)負(fù)責(zé)將接收的數(shù)據(jù)作還原處理。

目前，思科已經(jīng)率先在網(wǎng)絡(luò)優(yōu)化領(lǐng)域展開了研究工作。它推出一款名為WAAS設(shè)備，在傳輸協(xié)議環(huán)境內(nèi)消除重復(fù)數(shù)據(jù)并采用雙向模式，有效地消除了網(wǎng)絡(luò)中的冗余流量，為其它應(yīng)用預(yù)留出更多的空間。

一、數(shù)據(jù)去重原理和方法

1.1 數(shù)據(jù)去重的定義及分類

數(shù)據(jù)去重是一種消除重復(fù)數(shù)據(jù)[6]的方法，又稱之為智能壓縮、單實(shí)例存儲(chǔ)或冗余數(shù)據(jù)刪除[7]，根據(jù)粗粒度消除冗余，此技術(shù)不僅支持文件級(jí)去重功能，而且對(duì)數(shù)據(jù)塊也能起到很好去重效果。

第一類：相同數(shù)據(jù)檢測(cè)技術(shù)：完全文件檢測(cè)技術(shù)使用hash算法以整個(gè)文件為單元進(jìn)行去重處理；數(shù)據(jù)塊級(jí)重復(fù)數(shù)據(jù)去重技術(shù)通常采用固定快算法[8]、基于內(nèi)容的邊長(zhǎng)分塊算法[9]、滑動(dòng)塊檢測(cè)技術(shù)[10]來分析查找出重復(fù)的數(shù)據(jù)塊。

第二類：相似數(shù)據(jù)檢測(cè)技術(shù)：該技術(shù)一般采用模式匹配技術(shù)、shingle技術(shù)[11]以及bloom filter技術(shù)[12]尋找出數(shù)據(jù)的相似點(diǎn)，然后對(duì)相似部分使用delta編碼技術(shù)[13]實(shí)現(xiàn)編碼壓縮。

1.2 數(shù)據(jù)去重的原理及流程

數(shù)據(jù)去重的原理是利用算法查找數(shù)據(jù)流中的重復(fù)數(shù)據(jù)，隨后用短小標(biāo)簽來替代那些重復(fù)值，以此避免大量相同數(shù)據(jù)反復(fù)傳送于網(wǎng)絡(luò)中，從而可以提升帶寬利用效率。數(shù)據(jù)去重基本流程如圖2所示。

圖2中數(shù)據(jù)去重技術(shù)主要分為三步：

（1）協(xié)議棧將符合規(guī)則的數(shù)據(jù)流傳送到數(shù)據(jù)去重模塊中，并采用適當(dāng)?shù)臄?shù)據(jù)塊劃分算法處理數(shù)據(jù)流。常用的數(shù)據(jù)塊劃分算法有固定分塊算法、可變分塊算法、滑動(dòng)塊檢測(cè)技術(shù)。

（2）當(dāng)數(shù)據(jù)流被劃分成數(shù)據(jù)塊之后，就需要判斷其是不是重復(fù)數(shù)據(jù)塊了，為了解決這個(gè)問題，可以利用hash值來作為區(qū)別不同數(shù)據(jù)塊的指紋。通常使用SHA-1、MD5等函數(shù)來計(jì)算數(shù)據(jù)塊hash值。

（3）通過計(jì)算數(shù)據(jù)塊的hash值去搜索數(shù)據(jù)指紋庫(kù)，如果在數(shù)據(jù)指紋庫(kù)中匹配到該指紋，則需要對(duì)該數(shù)據(jù)塊進(jìn)行去重操作。反之，則需要將此數(shù)據(jù)塊對(duì)應(yīng)的指紋添加到數(shù)據(jù)指紋庫(kù)中，與此同時(shí)記錄該數(shù)據(jù)塊。

二、數(shù)據(jù)去重關(guān)鍵技術(shù)的研究與改進(jìn)

2.1 數(shù)據(jù)塊劃分算法

（1）固定分塊檢測(cè)算法

固定分塊檢測(cè)技術(shù)是一種用于處理數(shù)據(jù)塊級(jí)的簡(jiǎn)單重復(fù)檢測(cè)技術(shù)，它采用預(yù)設(shè)的固定分塊將原始數(shù)據(jù)集切分為等長(zhǎng)且互不重疊的數(shù)據(jù)塊，然后再計(jì)算其每個(gè)數(shù)據(jù)塊的指紋值。

（2）基于內(nèi)容的變長(zhǎng)分塊（CDC）檢測(cè)算法

變長(zhǎng)分塊檢測(cè)機(jī)制則按照數(shù)據(jù)所包含的內(nèi)容來確定塊長(zhǎng)。該方法采用滑動(dòng)塊窗口的方式讀取數(shù)據(jù)流，然后將窗口內(nèi)數(shù)據(jù)塊通過Rabin滾動(dòng)哈希算法計(jì)算其特征值，假如特征值未能滿足設(shè)定要求，則將窗口向后偏移一字節(jié)，以此類推，直到特征值滿足設(shè)定的要求，此時(shí)將上一個(gè)分塊的邊界到窗口右邊沿所包括的數(shù)據(jù)作為一個(gè)新的分塊。

（3）滑動(dòng)塊檢測(cè)算法

滑動(dòng)塊檢測(cè)技術(shù)[14]則有效利用上述兩種算法的特點(diǎn)，該算法采用固定大小的滑動(dòng)窗口來讀取數(shù)據(jù)流，并使用弱hash算法計(jì)算窗口內(nèi)數(shù)據(jù)塊的指紋，如果在數(shù)據(jù)指紋庫(kù)中匹配，則再次計(jì)算此數(shù)據(jù)塊的強(qiáng)hash指紋值并在數(shù)據(jù)指紋庫(kù)中匹配，匹配成功則認(rèn)為滑動(dòng)窗口內(nèi)所有的數(shù)據(jù)內(nèi)容為一個(gè)有效數(shù)據(jù)塊，否則將窗口向后挪動(dòng)一個(gè)字節(jié)重新利用弱hash算法計(jì)算。如果滑過一個(gè)塊大小的距離依然沒能找到對(duì)應(yīng)的指紋，則認(rèn)定此滑動(dòng)窗口內(nèi)的數(shù)據(jù)為一個(gè)數(shù)據(jù)塊邊界。

2.2 改進(jìn)的滑動(dòng)塊檢測(cè)算法

即使滑動(dòng)塊檢測(cè)算法是一種結(jié)合弱hash校驗(yàn)和強(qiáng)hash校驗(yàn)分塊算法，不過該方法依然無法百分百保證準(zhǔn)確性。有可能弱hash和強(qiáng)hash同時(shí)發(fā)生碰撞導(dǎo)致發(fā)送了錯(cuò)誤的索引，從而引起數(shù)據(jù)傳輸錯(cuò)誤。針對(duì)該問題我們提出了一種新的方法。在滑動(dòng)塊檢測(cè)算法的基礎(chǔ)上，將原來計(jì)算滑動(dòng)窗口內(nèi)數(shù)據(jù)指紋的弱hash算法，用滾動(dòng)哈希算法來替換。而二次匹配數(shù)據(jù)指紋的強(qiáng)hash算法，利用逐個(gè)字節(jié)比較的方法進(jìn)行替換，這樣就可以避0免將兩個(gè)不同的數(shù)據(jù)塊劃分為重復(fù)數(shù)據(jù)塊而發(fā)送錯(cuò)誤的數(shù)據(jù)塊索引，引起的傳輸錯(cuò)誤問題。

2.3 數(shù)據(jù)塊指紋及其檢索

數(shù)據(jù)指紋如果能作為數(shù)據(jù)塊的唯一標(biāo)識(shí)將可以很好地用于檢索方面。而目前比較適合計(jì)算數(shù)據(jù)指紋的是hash算法。hash算法以不定長(zhǎng)度的數(shù)據(jù)作為入?yún)?，然后利用hash函數(shù)計(jì)算出定長(zhǎng)的輸出值，該輸出就是hash值，或稱之為數(shù)據(jù)指紋。Hash算法的數(shù)學(xué)表達(dá)式為key=hash（content），主要的hash算法有MD5、sha-1等。

對(duì)于大存儲(chǔ)容量的數(shù)據(jù)去重系統(tǒng)來說，尋找一個(gè)數(shù)量巨大的指紋庫(kù)，性能往往會(huì)成為一種制約。不過Hash以O(shè)（1）的時(shí)間復(fù)雜度超過其它諸多信息檢索方式成為廣泛認(rèn)可的高性能查找算法。

三、基于數(shù)據(jù)去重的廣域網(wǎng)加速優(yōu)化系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

3.1 方案設(shè)計(jì)與實(shí)現(xiàn)

廣域網(wǎng)數(shù)據(jù)優(yōu)化系統(tǒng)是一個(gè)對(duì)等的雙邊系統(tǒng)，系統(tǒng)兩端同時(shí)支持?jǐn)?shù)據(jù)壓縮和恢復(fù)功能。如圖3所示，該系統(tǒng)主要由TCP透明代理和數(shù)據(jù)去重兩部分構(gòu)成，工作過程中需要先確認(rèn)收發(fā)兩端是否部署了該系統(tǒng)，如果存在，則對(duì)TCP流進(jìn)行數(shù)據(jù)去重優(yōu)化；否則，不做任何處理將該TCP報(bào)文轉(zhuǎn)發(fā)出去。數(shù)據(jù)發(fā)送時(shí)，TCP透明代理模塊將符合規(guī)則的TCP數(shù)據(jù)流截取下來，隨后進(jìn)行重組，當(dāng)滿足一定條件時(shí)，就將該數(shù)據(jù)段交付給去重模塊處理，最終將處理過的新數(shù)據(jù)發(fā)到廣域網(wǎng)上；接收端，TCP透明代理監(jiān)測(cè)數(shù)據(jù)流中的索引號(hào)，當(dāng)發(fā)現(xiàn)有重復(fù)數(shù)據(jù)的索引值時(shí)則將其發(fā)送給去重模塊進(jìn)行還原，最終將還原后的數(shù)據(jù)送往目的端。對(duì)于客戶端而言，整個(gè)過程無需進(jìn)行任何配置操作，Linux操作系統(tǒng)提供的netfilter框架可以很好地實(shí)現(xiàn)代理功能。數(shù)據(jù)經(jīng)過廣域網(wǎng)數(shù)據(jù)去重優(yōu)化系統(tǒng)時(shí)協(xié)議棧會(huì)自動(dòng)將符合規(guī)則的數(shù)據(jù)報(bào)文截獲并交給自定義的用戶空間協(xié)議棧處理[16]。

系統(tǒng)工作過程中，接收線程通過IPQueue機(jī)制將符合條件的IP數(shù)據(jù)包截取并放入用戶空間的預(yù)處理隊(duì)列。TCP_ prep報(bào)文預(yù)處理線程主要對(duì)的數(shù)據(jù)報(bào)文的排序、重組和TCP連接管理，TCP_prep線程將預(yù)處理后的控制報(bào)文直接放入發(fā)送隊(duì)列，同時(shí)將重組后的數(shù)據(jù)報(bào)文放到待處理數(shù)據(jù)隊(duì)列中。Data_proc數(shù)據(jù)處理線程封裝了重復(fù)數(shù)據(jù)消除模塊，當(dāng)待處理隊(duì)列中的數(shù)據(jù)滿足一定條件觸發(fā)定時(shí)器時(shí)線程TCP_timer時(shí)，Data_proc作為處理數(shù)據(jù)的線程從待處理隊(duì)列中讀取數(shù)據(jù)并交給去重模塊處理，將處理過后的數(shù)據(jù)放入發(fā)送隊(duì)列中。TCP_sender發(fā)送線程讀取待發(fā)送隊(duì)列信息，然后根據(jù)端口和ip調(diào)用Raw Socket將這些信息發(fā)到指定的終端上，圖4是報(bào)文在TCP處理中的處理流程。

3.2 改進(jìn)的滑動(dòng)塊檢測(cè)算法的實(shí)現(xiàn)

本系統(tǒng)采用改進(jìn)的滑動(dòng)塊檢測(cè)算法，改進(jìn)后的滑動(dòng)塊檢測(cè)算法（滑動(dòng)窗口2KB）如圖5所示。

改進(jìn)的滑動(dòng)塊檢測(cè)算法具體流程如下：

Step 1：數(shù)據(jù)分塊開始時(shí)如圖6所示，首先利用滾動(dòng)哈希函數(shù)計(jì)算圖6滑動(dòng)塊窗口里面2KB個(gè)字節(jié)的數(shù)據(jù)塊哈希值，然后在數(shù)據(jù)指紋庫(kù)里面進(jìn)行索引，若未能索引到則將窗口向后挪動(dòng)一個(gè)字節(jié)如圖7所示，如果索引到了則把這個(gè)數(shù)據(jù)塊和在數(shù)據(jù)指紋庫(kù)里面索引到的hash值對(duì)應(yīng)的數(shù)據(jù)塊進(jìn)行逐個(gè)字節(jié)比較。如果這兩個(gè)數(shù)據(jù)塊逐個(gè)字節(jié)比較完全一樣則說明索引成功，此時(shí)我們就將滑動(dòng)窗口內(nèi)的字節(jié)劃分?jǐn)?shù)據(jù)塊1，并且將前一個(gè)數(shù)據(jù)塊后邊界和此時(shí)滑動(dòng)窗口前邊界之間的數(shù)據(jù)劃分為數(shù)據(jù)塊2，同時(shí)還將滑動(dòng)窗口向后移動(dòng)2KB個(gè)字節(jié)如圖8所示，如果逐個(gè)字節(jié)比較不完全一樣則發(fā)生hash沖突索引失敗，這說明這個(gè)數(shù)據(jù)塊不是一個(gè)重復(fù)的數(shù)據(jù)塊，這時(shí)需要將滑動(dòng)窗口向后移動(dòng)一個(gè)字節(jié)如圖7所示。對(duì)于數(shù)據(jù)塊2來說，如果大小小于2KB則不能將這數(shù)據(jù)塊加入到數(shù)據(jù)指紋庫(kù)當(dāng)中，如果等于2KB則把這個(gè)數(shù)據(jù)塊（segment）和其hash值一起加入到數(shù)據(jù)指紋庫(kù)當(dāng)中。對(duì)于1數(shù)據(jù)塊，由于是重復(fù)的，所以不需要將其加入到數(shù)據(jù)指紋庫(kù)當(dāng)中。

Step 2：有一種特殊的情況即連續(xù)滑動(dòng)了2KB個(gè)字節(jié)，此時(shí)不管滑動(dòng)窗口內(nèi)的數(shù)據(jù)有沒有在數(shù)據(jù)指紋庫(kù)里面索引成功，直接將滑動(dòng)塊前面的2KB個(gè)字節(jié)劃分為一個(gè)數(shù)據(jù)塊，并且將其hash值和數(shù)據(jù)塊都加入到數(shù)據(jù)指紋庫(kù)當(dāng)中。

3.3 數(shù)據(jù)傳輸編解碼協(xié)議

在TCP數(shù)據(jù)流通過去重模塊之后就要開始進(jìn)行廣域網(wǎng)傳輸了，在傳輸之前需要自己制定一套編解碼協(xié)議，以便收發(fā)雙方可以更好的對(duì)去重后的TCP數(shù)據(jù)流進(jìn)行接收和發(fā)送。

XCODEC_PIPE_OP_HELLO：主站或者小站發(fā)送的第一個(gè)數(shù)據(jù)，表示數(shù)據(jù)傳輸即將開始，后面跟著發(fā)送數(shù)據(jù)者的UUID，接收者收到此UUID，據(jù)此UUID找到對(duì)應(yīng)的接收數(shù)據(jù)指紋庫(kù)（以下都稱為Cache）。

XCODEC_PIPE_OP_ASK：小站收到主站發(fā)來的索引，但是自己的Cache中沒有此索引，因此不能得到真實(shí)數(shù)據(jù)，這時(shí)發(fā)送這個(gè)消息，向主站請(qǐng)求真實(shí)數(shù)據(jù)。這個(gè)消息中包含有此索引（hash值）。

XCODEC_PIPE_OP_LEARN：主站收到XCODEC_PIPE_OP_ASK消息后，從中解析出HASH值，從自己的Cache中取出數(shù)據(jù)，發(fā)給小站，這個(gè)數(shù)據(jù)包的格式就采用這個(gè)類型。如果主站Cache中沒有此hash值，則發(fā)生致命錯(cuò)誤，需要斷開連接。

XCODEC_PIPE_OP_FRAME：正常數(shù)據(jù)都放入到FRAME中。數(shù)據(jù)也是有格式的。FRAME的最大長(zhǎng)度是XCODEC_PIPE_MAX_FRAME，為32768。

XCODEC_MAGIC：是個(gè)標(biāo)記，遇到此標(biāo)記，表明隨后緊挨的一個(gè)字節(jié)是一種操作類型。這種操作類型有以下幾種。

操作類型：

XCODEC_OP_ESCAPE：表示這是原始數(shù)據(jù)，而且XCODEC_MAGIC本身也是原始數(shù)據(jù)的一部分。發(fā)送者，對(duì)于原始數(shù)據(jù)，在ESCAPE時(shí)，要逐個(gè)字節(jié)尋找數(shù)據(jù)中的XCODEC_MAGIC，如果找到，就在后面插入一個(gè)XCODEC_ OP_ESCAPE。

XCODEC_OP_EXTRACT：表示后面的2k數(shù)據(jù)應(yīng)該存入Cache，接收者收到這種操作，需要計(jì)算后面2k數(shù)據(jù)的HASH值，并存入自己的Cache。

XCODEC_OP_BACKREF：表示后面的一個(gè)字節(jié)是個(gè)索引號(hào)，接收者需要根據(jù)此索引號(hào)在自己的window中找到對(duì)應(yīng)的HASH值，再由HASH從cache中找到真實(shí)數(shù)據(jù)。

XCODEC_OP_REF：表示后面的8個(gè)字節(jié)是個(gè)HASH值，接收都需要根據(jù)此HASH值在自己的cache中找到真實(shí)數(shù)據(jù)。

如果不能依據(jù)XCODEC_OP_BACKREF找到相對(duì)應(yīng)的數(shù)據(jù)，則會(huì)導(dǎo)致致命錯(cuò)誤的發(fā)生。如果不能根據(jù)XCODEC_OP_ REF找到對(duì)應(yīng)數(shù)據(jù)，則需要發(fā)送XCODEC_PIPE_OP_ASK向發(fā)送者要真實(shí)的數(shù)據(jù)。

3.4 數(shù)據(jù)指紋庫(kù)Cache管理

Cache數(shù)據(jù)都放在內(nèi)存中，基本數(shù)據(jù)結(jié)構(gòu)是一個(gè)基于hash的Map結(jié)構(gòu)如圖10，可以快速地由Hash值找到對(duì)應(yīng)數(shù)據(jù)段。在這基礎(chǔ)上為了防止Cache占用過多內(nèi)存，要加入淘汰功能，限制Cache的大小。為此我們提出了如下策略，首先維護(hù)一個(gè)鏈表，將新加入Cache的Hash值放在鏈表末尾，如果一個(gè)段被命中了，則也把它放到鏈表末尾。為了能高效的由Hash值找到其在隊(duì)列中的位置，維護(hù)了一個(gè)Map，是Hash值到鏈表結(jié)點(diǎn)指針的映射。有了這些數(shù)據(jù)結(jié)構(gòu)，在加入一個(gè)段到Cache中時(shí)，就要看看是不是有可以淘汰的段。淘汰時(shí)自然是從鏈表頭開始淘汰，因?yàn)殒湵眍^放的是最久未使用的段。如果Cache沒有滿，那自然是不用淘汰。為了避免在Cache太小時(shí)，把剛才命中的段淘汰掉，又對(duì)每一個(gè)段維護(hù)了一個(gè)使用時(shí)間，在新加入，或者命中時(shí)更新此時(shí)間，在淘汰時(shí)，只能淘汰已經(jīng)超時(shí)的段，超時(shí)時(shí)間要根據(jù)具體情況設(shè)置。如果一個(gè)段沒有超時(shí)，即使是Cache滿了也不能淘汰。 為了進(jìn)入一步減小數(shù)據(jù)量，發(fā)送方與接收方各自維護(hù)了一個(gè)window如圖11所示， 其中存放了最近使用的Hash值，這些值很有可能使用。在發(fā)送者發(fā)送Hash值時(shí)，先查找window中有沒有對(duì)應(yīng)的HASH值，如果有，則只要把window的下標(biāo)發(fā)送過去就行了，window大小是256，因此下標(biāo)是1字節(jié)，相比較發(fā)送8個(gè)字節(jié)的Hash值，又減小了發(fā)送數(shù)據(jù)量。

二、測(cè)試及結(jié)果分析

4.1 測(cè)試方法

評(píng)價(jià)指標(biāo)：數(shù)據(jù)去重技術(shù)旨在加速收發(fā)雙方的通信速度，所以可以用速度提升百分比來作為評(píng)價(jià)指標(biāo)。

測(cè)試環(huán)境：采用兩個(gè)普通電腦當(dāng)作數(shù)據(jù)傳輸?shù)氖瞻l(fā)兩端，在另外兩個(gè)雙網(wǎng)卡機(jī)器上運(yùn)行廣域網(wǎng)數(shù)據(jù)優(yōu)化軟件，延遲為600ms，丟包率為0.005%的條件下對(duì)數(shù)據(jù)傳輸進(jìn)行加速測(cè)試，測(cè)試網(wǎng)絡(luò)結(jié)構(gòu)圖如圖12。

測(cè)試方法：

4.2 測(cè)試結(jié)果及分析

從以上測(cè)試結(jié)果我們可以得出如下結(jié)論：

（1）結(jié)論1：方案一和方案二的對(duì)比可以看出廣域網(wǎng)的延遲對(duì)于數(shù)據(jù)傳輸產(chǎn)生了很大的影響，使得傳輸速率下降非常明顯。

（2）結(jié)論2：方案二和方案三的對(duì)比可以得出透明代理可以加速有巨大延遲的廣域網(wǎng)的傳輸速度，加速效果非常明顯。

（3）結(jié)論3：方案四的兩次測(cè)試對(duì)比可以看出在透明代理的基礎(chǔ)上，數(shù)據(jù)去重技術(shù)的加速效果異常明顯，第一次由于數(shù)據(jù)去重的開銷，速率相比透明代理有小幅下降，但是第二次的測(cè)試充分說明了數(shù)據(jù)去重對(duì)于廣域網(wǎng)傳輸優(yōu)化有著極大的改善，速率提升很明顯。

從方案一、二、三、四的對(duì)比可以看出來透明代理和數(shù)據(jù)去重對(duì)數(shù)據(jù)傳輸加速都起到了很大的加速效果。尤其是數(shù)據(jù)去重功能將原來的速度提升了很多，這不但加速數(shù)據(jù)傳輸，而且減少了在網(wǎng)絡(luò)上傳輸?shù)臄?shù)據(jù)量，減少了對(duì)帶寬的占用。極大的改善了廣域網(wǎng)絡(luò)傳輸?shù)沫h(huán)境，提升了傳輸速率。

五、結(jié)束語(yǔ)

本文首先對(duì)數(shù)據(jù)去重技術(shù)的研究背景和現(xiàn)況進(jìn)行了介紹，然后對(duì)數(shù)據(jù)去重涉及到的關(guān)鍵技術(shù)進(jìn)行了研究和改進(jìn)，并在這些理論的基礎(chǔ)上設(shè)計(jì)出一種帶有數(shù)據(jù)去重的廣域網(wǎng)優(yōu)化加速系統(tǒng)。并且經(jīng)過實(shí)例測(cè)試這個(gè)系統(tǒng)工作正常，性能達(dá)到了預(yù)期加速的目的，改善了廣域網(wǎng)傳輸?shù)沫h(huán)境。但還是可以在如下幾個(gè)方面進(jìn)行改進(jìn)：

（1）對(duì)重復(fù)數(shù)據(jù)的檢索是限制重復(fù)數(shù)據(jù)消除性能的瓶頸，在內(nèi)存資源有限的情況下就只能存儲(chǔ)有限的數(shù)據(jù)塊和hash值，這就會(huì)引起重復(fù)數(shù)據(jù)檢索成功率的降低。所以平衡數(shù)據(jù)指紋庫(kù)和和內(nèi)存之間的關(guān)系可以最優(yōu)化檢索效率，這也是以后研究的重點(diǎn)。

（2）兩邊的數(shù)據(jù)指紋庫(kù)即Cache同步也是一個(gè)很大的問題，同步機(jī)制是在假設(shè)網(wǎng)絡(luò)條件理想的情況下才可以的，但是真實(shí)的網(wǎng)絡(luò)環(huán)境條件很差，這就為cache同步機(jī)制帶來了極大的挑戰(zhàn)，如何解決這個(gè)問題變得很迫切。

參 考 文 獻(xiàn)

[1] Mcknight J， Asaro T， Babineau B. Digital archiving： end-user survey and market forecast 2006-2010[J]. Milford， MA， USA： Enterprise Strategy Group，2006.

[2] Santry D S， Feeley M J， Hutchinson N C， et al. Deciding when to forget in the Elephant file system[J]. In Proceedings of the 17th ACM Symposium on Operating System Principles（SOS99）. New York， USA： ACM Press，1999：1 10-123.

[3] Tolia N， Kaminsky M， Andersen D G， et al. An architecture for internet data transfer[J]. In Proceedings of the 3rd Symposium on Networked Systems Dsign and Implementation （NSDI06）.San Jose， CA，USA：USENIX Association，1006：253-266.

[4] Mogu J C， Chan Y M， Kelly T. Design， implementation， and evaluation of duplicate transfer detection in HTTP[J].In Proceedings of the 1st Conference on Symposiums on Networked Systems Design and Implementation（NSDI04）.Berkeley， USA：USENIX Association，2004：4-4.

[5] Shivakumar N， Garcia-Molina H. Finding near-replicas of documents on the Web[J]. In Proceeding of the 2nd International Workshop on the World Wide Web and Databases（WebDB99）.Berlin，Germany：Springer-Verlag，1999：204-212.

[6] 敖莉，舒繼武，李明強(qiáng).重復(fù)數(shù)據(jù)消除技術(shù)[J].軟件學(xué)報(bào).2010，（05）.

[7] Chuanyi Liu， Yingping Lu， Chunhui Shi， et al. ADMAD： Application Driven Metadata Aware De-duplication Arc hival Storage System[J]. Digital Object Indetifier， September 2008.29-35.

[8] Bobbarjung Dr， Jagannathan S， Dubnicki C. Improving duplicate elimination in storage systems[J]. ACM Trans. on Storage，2006，424-448.

[9] Jain N， Dahlin M， Tew ari R. Taper： Tiered approach for eliminating redundancy in replica synchronization[J]. In： Proc. Of the 4th usenix Conf. on File and Storage Technologies（FAST 2005）. Berkeley： USENIX Association，2005.

[10] Broder AZ. Identifying and filtering near-duplicate documents[J]. In： Giancarlo R， Sankof D， eds. Proc. of the 11th annual Symp. On Combinatorial Pattern Matching.London： Springer-Verlag，2000.1-10.

[11] Han B， Keleher P. Implementation and performance evaluation of fuzzy file block matching[J]. In： Proc of the 2007 USENIX Annual Technical Conf.（USENIX 2007）.Berkeley： USENIX Association，2007.199-204.

[12] Bloom BH. Space/time trade-offs in hash coding with allowable errors[J].Communications of the ACM，1970， 13（7）：422-426.

[13] Ouyang Z， Memon N， Suel T， Trendafilov D. Cluster-Based delta compression of a collection of files[J]. In：Proc. Of the 3rd Intl Conf. on Web Information Systems Enginerring. Washington： IEEE Computer Society Press，2006.257-266.

[14] Hsu W W S， Ong S. System and method for dividing data into predominantly fixed-sized chunks so that duplicate data chunks may be identified[J]. US Patent：US7281006B2.2007：23-32.

[15] Tin Thein Thwel， Ni Lar Thein. An Efficient Indexing Mechanism for Data Deduplication[J].International Conference on Current Trends in Information Technology，2009：1-15.

[16] 徐照，廣域網(wǎng)重復(fù)數(shù)據(jù)消除方法的研究與實(shí)現(xiàn)[D]. 南京：南京郵電大學(xué)，2013.2