基于數據去重的廣域網絡傳輸優化系統研究
2016-11-03 08:34:32時立鋒劉海客包翰榕
中國新通信 2016年19期
時立鋒 劉海客 包翰榕
【摘要】 信息技術不斷的更新和發展推動全球進入大數據時代。傳統型廣域網傳輸方案伴隨通信量的急劇增長已經很難滿足用戶的數據傳輸要求。面對廣域網遇到的現狀，主要研究了一種數據去重算法，并將其用于廣域網優化系統中。重點研究了數據分塊算法，采用一種新型的滑動塊檢測技術，并利用時間淘汰算法選出重復的數據塊，從而提高重復數據削減率，可以有效節約網絡帶寬并加快廣域網傳輸速率。
【關鍵詞】 數據去重 數據分塊算法 廣域網優化 時間淘汰算法
隨著信息技術產業的飛速發展，當前已涌現出各種新型網絡應用，致使廣域網上的帶寬流量迅猛增加，網絡也因此出現帶寬緊缺、延時高等問題。
面對上述問題，廣域網加速隨即成為討論的熱點。數據去重技術脫穎而出，它能夠對網絡中的數據實施全面的、不間斷的重復數據檢測，而且其壓縮效率明顯優于傳統概念的壓縮技術。調查顯示，廣域網中有接近60%的流量數據都是重復的[1]。例如，網絡中同一文件可能在某些時間段內分發給多個人，因此便造成相同數據反復傳送[2]。郵件群發也會導致大量冗余[3]；互聯網上的web頁面同樣也會造成大量重復數據[4]。在廣域網流量中約48%的網頁內容幾乎相同[5]；如果能在廣域網加速系統中結合去重技術，將極大限度提升整個帶寬的利用率。
在這個以用戶體驗為主導的時代，去重優化系統能夠為個人和企業提供優質的網絡體驗。其原理是：采用數據去重技術對TCP流進行去重處理，采用雙向緩存存儲字段，并以非常小的代價消除重復數據，確保冗余流量不會重復發送，該方法有效減少了不必要的帶寬浪費，此舉可以達到提高傳輸速率和帶寬利用的目的。通常情況下，廣域網加速系統會同時部署在客戶端和服務端，因此可以保證對通過的TCP流進行雙向數據優化。系統示意圖如圖1所示。
數據去重系統一般由TCP透明代理和去重處理兩部分構成。TCP透明代理的主要功能是截取數據流交給去重模塊，處理完冗余后再將去重之后的數據進行發送，另外一端數據去重系統負責將接收的數據作還原處理。
目前，思科已經率先在網絡優化領域展開了研究工作。它推出一款名為WAAS設備，在傳輸協議環境內消除重復數據并采用雙向模式，有效地消除了網絡中的冗余流量，為其它應用預留出更多的空間。
一、數據去重原理和方法
1.1 數據去重的定義及分類
數據去重是一種消除重復數據[6]的方法，又稱之為智能壓縮、單實例存儲或冗余數據刪除[7]，根據粗粒度消除冗余，此技術不僅支持文件級去重功能，而且對數據塊也能起到很好去重效果。
第一類：相同數據檢測技術：完全文件檢測技術使用hash算法以整個文件為單元進行去重處理；數據塊級重復數據去重技術通常采用固定快算法[8]、基于內容的邊長分塊算法[9]、滑動塊檢測技術[10]來分析查找出重復的數據塊。
第二類：相似數據檢測技術：該技術一般采用模式匹配技術、shingle技術[11]以及bloom filter技術[12]尋找出數據的相似點，然后對相似部分使用delta編碼技術[13]實現編碼壓縮。
1.2 數據去重的原理及流程
數據去重的原理是利用算法查找數據流中的重復數據，隨后用短小標簽來替代那些重復值，以此避免大量相同數據反復傳送于網絡中，從而可以提升帶寬利用效率。數據去重基本流程如圖2所示。
圖2中數據去重技術主要分為三步：
（1）協議棧將符合規則的數據流傳送到數據去重模塊中，并采用適當的數據塊劃分算法處理數據流。常用的數據塊劃分算法有固定分塊算法、可變分塊算法、滑動塊檢測技術。
（2）當數據流被劃分成數據塊之后，就需要判斷其是不是重復數據塊了，為了解決這個問題，可以利用hash值來作為區別不同數據塊的指紋。通常使用SHA-1、MD5等函數來計算數據塊hash值。
（3）通過計算數據塊的hash值去搜索數據指紋庫，如果在數據指紋庫中匹配到該指紋，則需要對該數據塊進行去重操作。反之，則需要將此數據塊對應的指紋添加到數據指紋庫中，與此同時記錄該數據塊。
二、數據去重關鍵技術的研究與改進
2.1 數據塊劃分算法
（1）固定分塊檢測算法
固定分塊檢測技術是一種用于處理數據塊級的簡單重復檢測技術，它采用預設的固定分塊將原始數據集切分為等長且互不重疊的數據塊，然后再計算其每個數據塊的指紋值。
（2）基于內容的變長分塊（CDC）檢測算法
變長分塊檢測機制則按照數據所包含的內容來確定塊長。該方法采用滑動塊窗口的方式讀取數據流，然后將窗口內數據塊通過Rabin滾動哈希算法計算其特征值，假如特征值未能滿足設定要求，則將窗口向后偏移一字節，以此類推，直到特征值滿足設定的要求，此時將上一個分塊的邊界到窗口右邊沿所包括的數據作為一個新的分塊。
（3）滑動塊檢測算法
滑動塊檢測技術[14]則有效利用上述兩種算法的特點，該算法采用固定大小的滑動窗口來讀取數據流，并使用弱hash算法計算窗口內數據塊的指紋，如果在數據指紋庫中匹配，則再次計算此數據塊的強hash指紋值并在數據指紋庫中匹配，匹配成功則認為滑動窗口內所有的數據內容為一個有效數據塊，否則將窗口向后挪動一個字節重新利用弱hash算法計算。如果滑過一個塊大小的距離依然沒能找到對應的指紋，則認定此滑動窗口內的數據為一個數據塊邊界。
2.2 改進的滑動塊檢測算法
即使滑動塊檢測算法是一種結合弱hash校驗和強hash校驗分塊算法，不過該方法依然無法百分百保證準確性。有可能弱hash和強hash同時發生碰撞導致發送了錯誤的索引，從而引起數據傳輸錯誤。針對該問題我們提出了一種新的方法。在滑動塊檢測算法的基礎上，將原來計算滑動窗口內數據指紋的弱hash算法，用滾動哈希算法來替換。而二次匹配數據指紋的強hash算法，利用逐個字節比較的方法進行替換，這樣就可以避0免將兩個不同的數據塊劃分為重復數據塊而發送錯誤的數據塊索引，引起的傳輸錯誤問題。
2.3 數據塊指紋及其檢索
數據指紋如果能作為數據塊的唯一標識將可以很好地用于檢索方面。而目前比較適合計算數據指紋的是hash算法。hash算法以不定長度的數據作為入參，然后利用hash函數計算出定長的輸出值，該輸出就是hash值，或稱之為數據指紋。Hash算法的數學表達式為key=hash（content），主要的hash算法有MD5、sha-1等。
對于大存儲容量的數據去重系統來說，尋找一個數量巨大的指紋庫，性能往往會成為一種制約。不過Hash以O（1）的時間復雜度超過其它諸多信息檢索方式成為廣泛認可的高性能查找算法。
三、基于數據去重的廣域網加速優化系統的設計與實現
3.1 方案設計與實現
廣域網數據優化系統是一個對等的雙邊系統，系統兩端同時支持數據壓縮和恢復功能。如圖3所示，該系統主要由TCP透明代理和數據去重兩部分構成，工作過程中需要先確認收發兩端是否部署了該系統，如果存在，則對TCP流進行數據去重優化；否則，不做任何處理將該TCP報文轉發出去。數據發送時，TCP透明代理模塊將符合規則的TCP數據流截取下來，隨后進行重組，當滿足一定條件時，就將該數據段交付給去重模塊處理，最終將處理過的新數據發到廣域網上；接收端，TCP透明代理監測數據流中的索引號，當發現有重復數據的索引值時則將其發送給去重模塊進行還原，最終將還原后的數據送往目的端。對于客戶端而言，整個過程無需進行任何配置操作，Linux操作系統提供的netfilter框架可以很好地實現代理功能。數據經過廣域網數據去重優化系統時協議棧會自動將符合規則的數據報文截獲并交給自定義的用戶空間協議棧處理[16]。
系統工作過程中，接收線程通過IPQueue機制將符合條件的IP數據包截取并放入用戶空間的預處理隊列。TCP_ prep報文預處理線程主要對的數據報文的排序、重組和TCP連接管理，TCP_prep線程將預處理后的控制報文直接放入發送隊列，同時將重組后的數據報文放到待處理數據隊列中。Data_proc數據處理線程封裝了重復數據消除模塊，當待處理隊列中的數據滿足一定條件觸發定時器時線程TCP_timer時，Data_proc作為處理數據的線程從待處理隊列中讀取數據并交給去重模塊處理，將處理過后的數據放入發送隊列中。TCP_sender發送線程讀取待發送隊列信息，然后根據端口和ip調用Raw Socket將這些信息發到指定的終端上，圖4是報文在TCP處理中的處理流程。
3.2 改進的滑動塊檢測算法的實現
本系統采用改進的滑動塊檢測算法，改進后的滑動塊檢測算法（滑動窗口2KB）如圖5所示。
改進的滑動塊檢測算法具體流程如下：
Step 1：數據分塊開始時如圖6所示，首先利用滾動哈希函數計算圖6滑動塊窗口里面2KB個字節的數據塊哈希值，然后在數據指紋庫里面進行索引，若未能索引到則將窗口向后挪動一個字節如圖7所示，如果索引到了則把這個數據塊和在數據指紋庫里面索引到的hash值對應的數據塊進行逐個字節比較。如果這兩個數據塊逐個字節比較完全一樣則說明索引成功，此時我們就將滑動窗口內的字節劃分數據塊1，并且將前一個數據塊后邊界和此時滑動窗口前邊界之間的數據劃分為數據塊2，同時還將滑動窗口向后移動2KB個字節如圖8所示，如果逐個字節比較不完全一樣則發生hash沖突索引失敗，這說明這個數據塊不是一個重復的數據塊，這時需要將滑動窗口向后移動一個字節如圖7所示。對于數據塊2來說，如果大小小于2KB則不能將這數據塊加入到數據指紋庫當中，如果等于2KB則把這個數據塊（segment）和其hash值一起加入到數據指紋庫當中。對于1數據塊，由于是重復的，所以不需要將其加入到數據指紋庫當中。
Step 2：有一種特殊的情況即連續滑動了2KB個字節，此時不管滑動窗口內的數據有沒有在數據指紋庫里面索引成功，直接將滑動塊前面的2KB個字節劃分為一個數據塊，并且將其hash值和數據塊都加入到數據指紋庫當中。
3.3 數據傳輸編解碼協議
在TCP數據流通過去重模塊之后就要開始進行廣域網傳輸了，在傳輸之前需要自己制定一套編解碼協議，以便收發雙方可以更好的對去重后的TCP數據流進行接收和發送。
XCODEC_PIPE_OP_HELLO：主站或者小站發送的第一個數據，表示數據傳輸即將開始，后面跟著發送數據者的UUID，接收者收到此UUID，據此UUID找到對應的接收數據指紋庫（以下都稱為Cache）。
XCODEC_PIPE_OP_ASK：小站收到主站發來的索引，但是自己的Cache中沒有此索引，因此不能得到真實數據，這時發送這個消息，向主站請求真實數據。這個消息中包含有此索引（hash值）。
XCODEC_PIPE_OP_LEARN：主站收到XCODEC_PIPE_OP_ASK消息后，從中解析出HASH值，從自己的Cache中取出數據，發給小站，這個數據包的格式就采用這個類型。如果主站Cache中沒有此hash值，則發生致命錯誤，需要斷開連接。
XCODEC_PIPE_OP_FRAME：正常數據都放入到FRAME中。數據也是有格式的。FRAME的最大長度是XCODEC_PIPE_MAX_FRAME，為32768。
XCODEC_MAGIC：是個標記，遇到此標記，表明隨后緊挨的一個字節是一種操作類型。這種操作類型有以下幾種。
操作類型：
XCODEC_OP_ESCAPE：表示這是原始數據，而且XCODEC_MAGIC本身也是原始數據的一部分。發送者，對于原始數據，在ESCAPE時，要逐個字節尋找數據中的XCODEC_MAGIC，如果找到，就在后面插入一個XCODEC_ OP_ESCAPE。
XCODEC_OP_EXTRACT：表示后面的2k數據應該存入Cache，接收者收到這種操作，需要計算后面2k數據的HASH值，并存入自己的Cache。
XCODEC_OP_BACKREF：表示后面的一個字節是個索引號，接收者需要根據此索引號在自己的window中找到對應的HASH值，再由HASH從cache中找到真實數據。
XCODEC_OP_REF：表示后面的8個字節是個HASH值，接收都需要根據此HASH值在自己的cache中找到真實數據。
如果不能依據XCODEC_OP_BACKREF找到相對應的數據，則會導致致命錯誤的發生。如果不能根據XCODEC_OP_ REF找到對應數據，則需要發送XCODEC_PIPE_OP_ASK向發送者要真實的數據。
3.4 數據指紋庫Cache管理
Cache數據都放在內存中，基本數據結構是一個基于hash的Map
二、測試及結果分析
4.1 測試方法
評價指標：數據去重技術旨在加速收發雙方的通信速度，所以可以用速度提升百分比來作為評價指標。
測試環境：采用兩個普通電腦當作數據傳輸的收發兩端，在另外兩個雙網卡機器上運行廣域網數據優化軟件，延遲為600ms，丟包率為0.005%的條件下對數據傳輸進行加速測試，測試網絡結構圖如圖12。
測試方法：
4.2 測試結果及分析
從以上測試結果我們可以得出如下結論：
（1）結論1：方案一和方案二的對比可以看出廣域網的延遲對于數據傳輸產生了很大的影響，使得傳輸速率下降非常明顯。
（2）結論2：方案二和方案三的對比可以得出透明代理可以加速有巨大延遲的廣域網的傳輸速度，加速效果非常明顯。
（3）結論3：方案四的兩次測試對比可以看出在透明代理的基礎上，數據去重技術的加速效果異常明顯，第一次由于數據去重的開銷，速率相比透明代理有小幅下降，但是第二次的測試充分說明了數據去重對于廣域網傳輸優化有著極大的改善，速率提升很明顯。
從方案一、二、三、四的對比可以看出來透明代理和數據去重對數據傳輸加速都起到了很大的加速效果。尤其是數據去重功能將原來的速度提升了很多，這不但加速數據傳輸，而且減少了在網絡上傳輸的數據量，減少了對帶寬的占用。極大的改善了廣域網絡傳輸的環境，提升了傳輸速率。
五、結束語
本文首先對數據去重技術的研究背景和現況進行了介紹，然后對數據去重涉及到的關鍵技術進行了研究和改進，并在這些理論的基礎上設計出一種帶有數據去重的廣域網優化加速系統。并且經過實例測試這個系統工作正常，性能達到了預期加速的目的，改善了廣域網傳輸的環境。但還是可以在如下幾個方面進行改進：
（1）對重復數據的檢索是限制重復數據消除性能的瓶頸，在內存資源有限的情況下就只能存儲有限的數據塊和hash值，這就會引起重復數據檢索成功率的降低。所以平衡數據指紋庫和和內存之間的關系可以最優化檢索效率，這也是以后研究的重點。
（2）兩邊的數據指紋庫即Cache同步也是一個很大的問題，同步機制是在假設網絡條件理想的情況下才可以的，但是真實的網絡環境條件很差，這就為cache同步機制帶來了極大的挑戰，如何解決這個問題變得很迫切。
參 考 文 獻
[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] 敖莉，舒繼武，李明強.重復數據消除技術[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] 徐照，廣域網重復數據消除方法的研究與實現[D]. 南京：南京郵電大學，2013.2
