時立鋒 劉海客 包翰榕

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）固定分塊檢測算法

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

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

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

（3）滑動塊檢測算法

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

2.2 改進的滑動塊檢測算法

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

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

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

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

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

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

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

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

3.2 改進的滑動塊檢測算法的實現(xiàn)

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

改進的滑動塊檢測算法具體流程如下：

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

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

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

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

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

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

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

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

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

操作類型：

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

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

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

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

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

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

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

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

4.1 測試方法

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

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

測試方法：

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

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

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

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

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

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

五、結(jié)束語

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

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

（2）兩邊的數(shù)據(jù)指紋庫即Cache同步也是一個很大的問題，同步機制是在假設(shè)網(wǎng)絡(luò)條件理想的情況下才可以的，但是真實的網(wǎng)絡(luò)環(huán)境條件很差，這就為cache同步機制帶來了極大的挑戰(zhà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] 敖莉，舒繼武，李明強.重復數(shù)據(jù)消除技術(shù)[J].軟件學報.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)重復數(shù)據(jù)消除方法的研究與實現(xiàn)[D]. 南京：南京郵電大學，2013.2