1、引言
　基于LAN或WAN的網(wǎng)絡(luò)應(yīng)用之間進行數(shù)據(jù)傳輸或者同步非常普遍,，比如遠程數(shù)據(jù)鏡像,、備份、復(fù)制,、同步,，數(shù)據(jù)下載、上傳,、共享等等,，最為簡單的做法自然就是對數(shù)據(jù)進行完全復(fù)制,。然而，數(shù)據(jù)在網(wǎng)絡(luò)上來回被復(fù)制多次后就會存在大量副本,，很多情形下這些文件副本之間僅有很小的差異,，很可能是從同一個文件版本演化而來。如果對文件進行完全復(fù)制,，在文件較大的情況下,，會占用大量網(wǎng)絡(luò)帶寬，同步時間也會較長,。目前,，廣域網(wǎng)WAN的帶寬與訪問延遲仍然是急需解決的問題，完全復(fù)制使得很多網(wǎng)絡(luò)應(yīng)用無法提供良好的服務(wù)質(zhì)量,，比如分布式文件系統(tǒng)(DFS),、云存儲(Cloud Storage)。Rsync與RDC(Remote Differential Compression)是兩種最為常見的數(shù)據(jù)同步算法,，它們僅傳輸差異數(shù)據(jù),，從而節(jié)省網(wǎng)絡(luò)帶寬并提高效率。本文基于這兩種算法思想并借助重復(fù)數(shù)據(jù)刪除(De-duplication)技術(shù),，對數(shù)據(jù)同步算法進行深入研究與分析,，并研發(fā)了原型系統(tǒng)。首先介紹rsync與RDC算法,，然后詳細描述算法設(shè)計與相應(yīng)的數(shù)據(jù)結(jié)構(gòu),，并重點分析文件分塊、差異編碼,、文件同步算法,，最后簡介推拉兩種應(yīng)用模式。

2,、相關(guān)工作
　Rsync是類Unix環(huán)境下的一個高效的遠程文件復(fù)制(同步)工具,，它通過著名的Rsync算法來優(yōu)化流程，減少了數(shù)據(jù)通信量并提高文件傳輸效率,。假設(shè)現(xiàn)在有兩臺計算機Alpha和Beta ,計算機Alpha能夠訪問A文件,計算機Beta能夠訪問B文件,，文件A和B非常相似，計算機Alpha和Beta通過低速網(wǎng)絡(luò)互聯(lián),。它的大致流程如下(詳細過程請參考Rsync作者Andrew Tridgell的tech_report.ps)：
　1,、Beta將文件B分割成連續(xù)不重疊的固定大小數(shù)據(jù)塊S，最后一個數(shù)據(jù)塊上可能會小于S字節(jié),；
　2,、Beta對于每一個數(shù)據(jù)塊,計算出兩個校驗值，一個32位的弱滾動校驗和一個128位的MD4校驗,；
　3,、Beta將校驗值發(fā)送給Alpha,；
　4、Alpha通過搜索文件A的所有大小為S的數(shù)據(jù)塊(偏移量可以任意,，不一定非要是S的倍數(shù)),，來尋找與文件B的某一塊有著相同的弱校驗碼和強校驗碼的數(shù)據(jù)塊。這主要由滾動校驗Rolling checksum快速完成,；
　5、Alpha給Beta發(fā)送重構(gòu)A文件的指令,，每一條指令是一個文件B數(shù)據(jù)塊引用（匹配）或者是文件A數(shù)據(jù)塊（未匹配）,。
　　Rsync是一個非常優(yōu)秀的工具，但它仍然存在一些不足之處,。
　1,、Rolling checksum雖然可以節(jié)省大量checksum校驗計算量，也對checksum搜索作了優(yōu)化,，但多出一倍以上的hash查找,，這個消耗不小,；
　2,、Rsync算法中，Alpha和Beta計算量是不對等的,，Alpha計算量非常大,，而Bete計算量非常小。通常Alpha是服務(wù)器,，因此壓力較大,；
　3、Rsync中數(shù)據(jù)塊大小是固定的,，對數(shù)據(jù)變化的適應(yīng)能力有限,。
　RDC算法的典型代表是微軟DFS中的DFSR(Distributed File System Replication)，它與Rsync不同之處在于采用一致的分塊規(guī)則對復(fù)制的源文件和目標文件進行切分,。因此,，RDC對于源端和目標端的計算量是對等的。RDC和RSync算法在設(shè)重點上有所不同,，Rsync追求更高的重復(fù)數(shù)據(jù)發(fā)現(xiàn)而不惜計算量,；RDC在兩者之間作了一個折衷，目標是以少量的計算快速發(fā)現(xiàn)數(shù)據(jù)差異,，當然重復(fù)數(shù)據(jù)發(fā)現(xiàn)不及Rsync,。另外，Rsync是定長分塊策略,，而RDC是變長分塊策略,。

3,、重復(fù)數(shù)據(jù)刪除技術(shù)
　De-duplication，即重復(fù)數(shù)據(jù)刪除,，它是一種非常新的且流行度很高的存儲技術(shù),，可以大大減少數(shù)據(jù)的數(shù)量。重復(fù)數(shù)據(jù)刪除技術(shù),，通過數(shù)據(jù)集中重復(fù)的數(shù)據(jù),，從而消除冗余數(shù)據(jù)。借助dedup技術(shù),，可以提高存儲系統(tǒng)的效率,，有效節(jié)約成本、減少傳輸過程中的網(wǎng)絡(luò)帶寬,。同時它也是一種綠色存儲技術(shù),，能有效降低能耗。
　Dedupe按照消重的粒度可以分為文件級和數(shù)據(jù)塊級,。文件級的dedup技術(shù)也稱為單一實例存儲(SIS, Single Instance Store),，數(shù)據(jù)塊級的重復(fù)數(shù)據(jù)刪除，其消重粒度更小,，可以達到4-24KB之間,。顯然，數(shù)據(jù)塊級的可以提供更高的數(shù)據(jù)消重率,，因此目前主流的 dedup產(chǎn)品都是數(shù)據(jù)塊級的,。將文件都分割成數(shù)據(jù)塊(定長或變長的數(shù)據(jù)塊)，采用MD5或SHA1等Hash算法 (可以同時使用兩種或以上hash算法或CRC校驗等,，以獲得非常小概率的數(shù)據(jù)碰撞發(fā)生)為數(shù)據(jù)塊計算指紋(FP, Fingerprint),。具有相同F(xiàn)P指紋的數(shù)據(jù)塊即可認為是相同的數(shù)據(jù)塊，存儲系統(tǒng)中僅需要保留一份,。這樣,，一個物理文件在存儲系統(tǒng)就對應(yīng)一個邏輯表示，由一組FP組成的元數(shù)據(jù),。當進行讀取文件時,，先讀取邏輯文件，然后根據(jù)FP序列,，從存儲系統(tǒng)中取出相應(yīng)數(shù)據(jù)塊,，還原物理文件副本。
　Dedupe技術(shù)目前主要應(yīng)用于數(shù)據(jù)備份,，因此對數(shù)據(jù)進行多次備份后,，存在大量重復(fù)數(shù)據(jù)，非常適合這種技術(shù)。事實上,，dedupe技術(shù)可以用于很多場合,，包括在線數(shù)據(jù)、近線數(shù)據(jù),、離線數(shù)據(jù)存儲系統(tǒng),，甚至可以在文件系統(tǒng)、卷管理器,、NAS,、SAN中實施。也可以用于網(wǎng)絡(luò)數(shù)據(jù)傳輸,，當然也可以應(yīng)用于數(shù)據(jù)打包技術(shù),。Dedupe技術(shù)可以幫助眾多應(yīng)用降低數(shù)據(jù)存儲量，節(jié)省網(wǎng)絡(luò)帶寬,，提高存儲效率、減小備份窗口,，綠色節(jié)能,。

4、數(shù)據(jù)同步算法
　如Rsync假設(shè)現(xiàn)在有兩臺計算機Alpha和Beta ,計算機Alpha能夠訪問A文件,計算機Beta能夠訪問B文件,，文件A和B非常相似,，計算機Alpha和Beta通過低速網(wǎng)絡(luò)互聯(lián)?；赿edupe技術(shù)的數(shù)據(jù)同步算法大致流程與Rsync相似,，簡單描述如下：
　1、Beta采用數(shù)據(jù)切分算法,，如FSP(fixed-size partition),、CDC(content-defined chuking)，將文件B分割成大小相等或不等的數(shù)據(jù)塊,；
　2,、Beta對于每一個數(shù)據(jù)塊,計算一個類似rsync弱校驗值和md5強校驗值，并記錄數(shù)據(jù)塊長度len和在文件B中的偏移量offset,；
　3,、Beta將這將數(shù)據(jù)塊信息發(fā)送給Alpha；
　4,、Alpha采用同樣的數(shù)據(jù)塊切分技術(shù)將文件A切成大小相等或不等的數(shù)據(jù)塊,，并與Beta發(fā)過來的數(shù)據(jù)信息進行搜索匹配，生成差異編碼信息,；
　5,、Alpha將差異編碼信息發(fā)送給Beta，并同時發(fā)送重構(gòu)文件A的指令；
　6,、Beta根據(jù)差異編碼信息和文件B重構(gòu)文件A,。
　上面算法描述中，有幾個關(guān)鍵問題需要解決,，即文件切分,、切分數(shù)據(jù)塊信息描述、差異編碼,、差異編碼信息描述,、文件同步。文件切分,、差異編碼,、文件同步將在后續(xù)部分介紹，這里對切分數(shù)據(jù)塊信息描述和差異編碼信息描述作說明,。
　切分數(shù)據(jù)塊信息的數(shù)據(jù)文件布局由文件頭(chunk_file_header)和數(shù)據(jù)塊描述(chunk_block_entry)實體集組成,，具體定義如下。其中,，文件頭定義了文件B的數(shù)據(jù)塊大小,、數(shù)據(jù)塊總數(shù)。文件頭后緊隨一組數(shù)據(jù)塊描述實體,，每個實體代表一個數(shù)據(jù)塊,，定義了塊長度、塊在文件B中的偏移,、弱校驗值和強md5校驗值,。　

5,、文件切分
　Dedupe技術(shù)中，數(shù)據(jù)分塊算法主要有三種,，即定長切分(fixed-size partition),、CDC切分(content-defined chunking)和滑動塊(sliding
block)切分。定長分塊算法采用預(yù)先定義好的塊大小對文件進行切分,，并進行弱校驗值和md5強校驗值,。弱校驗值主要是為了提升差異編碼的性能，先計算弱校驗值并進行hash查找,，如果發(fā)現(xiàn)則計算md5強校驗值并作進一步hash查找,。由于弱校驗值計算量要比md5小很多，因此可以有效提高編碼性能,。定長分塊算法的優(yōu)點是簡單,、性能高，但它對數(shù)據(jù)插入和刪除非常敏感,，處理十分低效，不能根據(jù)內(nèi)容變化作調(diào)整和優(yōu)化,。
　CDC算法是一種變長分塊算法,，它應(yīng)用數(shù)據(jù)指紋(如Rabin指紋)將文件分割成長度大小不等的分塊策略。與定長分塊算法不同,，它是基于文件內(nèi)容進行數(shù)據(jù)塊切分的,，因此數(shù)據(jù)塊大小是可變化的。算法執(zhí)行過程中,，CDC使用一個固定大小(如48字節(jié))的滑動窗口對文件數(shù)據(jù)計算數(shù)據(jù)指紋,。如果指紋滿足某個條件，如當它的值模特定的整數(shù)等于預(yù)先設(shè)定的數(shù)時,，則把窗口位置作為塊的邊界,。CDC算法可能會出現(xiàn)病態(tài)現(xiàn)象，即指紋條件不能滿足,，塊邊界不能確定,，導(dǎo)致數(shù)據(jù)塊過大。實現(xiàn)中可以對數(shù)據(jù)塊的大小進行限定,，設(shè)定上下限,，解決這種問題。CDC算法對文件內(nèi)容變化不敏感，插入或刪除數(shù)據(jù)只會影響到檢少的數(shù)據(jù)塊,，其余數(shù)據(jù)塊不受影響,。CDC算法也是有缺陷的，數(shù)據(jù)塊大小的確定比較困難,，粒度太細則開銷太大,，粒度過粗則dedup效果不佳。如何兩者之間權(quán)衡折衷,，這是一個難點,。
　滑動塊算法結(jié)合了定長切分和CDC切分的優(yōu)點，塊大小固定,。它對定長數(shù)據(jù)塊先計算弱校驗值,，如果匹配則再計算md5強校驗值，兩者都匹配則認為是一個數(shù)據(jù)塊邊界,。該數(shù)據(jù)塊前面的數(shù)據(jù)碎片也是一個數(shù)據(jù)塊,，它是不定長的。如果滑動窗口移過一個塊大小的距離仍無法匹配,，則也認定為一個數(shù)據(jù)塊邊界,。滑動塊算法對插入和刪除問題處理非常高效,，并且能夠檢測到比CDC更多的冗余數(shù)據(jù),，它的不足是容易產(chǎn)生數(shù)據(jù)碎片。

6,、差異編碼
　差異編碼的基礎(chǔ)是文件B數(shù)據(jù)分塊信息和文件A,，它首先對文件A進行對等數(shù)據(jù)分塊(滑動塊算法除外，它對文件B的切分是定長算法,，而對文件A是滑動塊算法),，然后匹配文件B數(shù)據(jù)分塊信息。如果數(shù)據(jù)塊匹配,，則用數(shù)據(jù)塊索引表示,，達到重復(fù)數(shù)據(jù)刪除效果。否則,，則將對應(yīng)的文件A數(shù)據(jù)塊寫入差異編碼文件中,。數(shù)據(jù)塊匹配算法方面，定長切分和CDC切分是基本相同,，文件A采用和文件B對等的切分算法進行數(shù)據(jù)塊切分,。滑動塊算法與其他兩種算法不同,，它與rsync類似,，它對文件B的切分是定長算法,，而對文件A的切分是滑動塊算法。因此,，這種算法切分是不對等的,。然后根據(jù)文件B構(gòu)造hashtable，通過hash查找進行匹配,，并按照差異編碼數(shù)據(jù)布局構(gòu)造相應(yīng)數(shù)據(jù)文件,。

7、文件同步
　Beta得到差異編碼文件delta,，再結(jié)合已有的文件B,，即可以將文件B同步成文件A的副本。同步算法遍歷delta文件,，讀取每一個數(shù)據(jù)塊描述實體,，根據(jù)embeded標志分別從delta和文件B中讀取相應(yīng)的數(shù)據(jù)塊，重新構(gòu)造出文件A,。

8,、PULL與PUSH模式
　數(shù)據(jù)同步有PULL和PUSH兩種應(yīng)用模式，PULL是將遠程數(shù)據(jù)同步到本地,，而PUSH是將本地數(shù)據(jù)同步到遠程,。對應(yīng)到同步算法，主要區(qū)別在于數(shù)據(jù)分塊和差異編碼位置不同,。PULL和PUSH同步模式步驟分別如下所述,。
　PULL同步模式流程：
　1、本地對文件A進行數(shù)據(jù)切分,，生成數(shù)據(jù)塊描述文件chunk,；
　2、上傳chunk文件至遠程服務(wù)器,；
　3、遠程服務(wù)器對文件B進行差異編碼,，生成差異編碼文件delta,；
　4、下載delta文件至本地,；
　5,、本地同步文件A至文件B，相當于下載文件B到本地文件A,。

　PUSH同步模式流程：
　1,、遠程服務(wù)器對文件B進行數(shù)據(jù)切分，生成數(shù)據(jù)塊描述文件chunk,；
　2,、下載chunk文件至本地,；
　3、本地對文件A進行差異編碼,，生成差異編碼文件delta,；
　4、上傳delta文件至遠程服務(wù)器,；
　5,、遠程同步文件B到A，相當于上傳文件A到遠程文件B,。