|
滑動(dòng)塊算法結(jié)合了定長(zhǎng)切分和CDC切分的優(yōu)點(diǎn)，塊大小固定。它對(duì)定長(zhǎng)數(shù)據(jù)塊先計(jì)算弱校驗(yàn)值，如果匹配則再計(jì)算md5強(qiáng)校驗(yàn)值，兩者都匹配則認(rèn)為是一個(gè)數(shù)據(jù)塊邊界。該數(shù)據(jù)塊前面的數(shù)據(jù)碎片也是一個(gè)數(shù)據(jù)塊，它是不定長(zhǎng)的。如果滑動(dòng)窗口移過(guò)一個(gè)塊大小的距離仍無(wú)法匹配，則也認(rèn)定為一個(gè)數(shù)據(jù)塊邊界。滑動(dòng)塊算法對(duì)插入和刪除問(wèn)題處理非常高效，并且能夠檢測(cè)到比CDC更多的冗余數(shù)據(jù)，它的不足是容易產(chǎn)生數(shù)據(jù)碎片。
6、差異編碼
差異編碼的基礎(chǔ)是文件B數(shù)據(jù)分塊信息和文件A，它首先對(duì)文件A進(jìn)行對(duì)等數(shù)據(jù)分塊(滑動(dòng)塊算法除外，它對(duì)文件B的切分是定長(zhǎng)算法，而對(duì)文件A是滑動(dòng)塊算法)，然后匹配文件B數(shù)據(jù)分塊信息。如果數(shù)據(jù)塊匹配，則用數(shù)據(jù)塊索引表示，達(dá)到重復(fù)數(shù)據(jù)刪除效果。否則，則將對(duì)應(yīng)的文件A數(shù)據(jù)塊寫入差異編碼文件中。數(shù)據(jù)塊匹配算法方面，定長(zhǎng)切分和CDC切分是基本相同，文件A采用和文件B對(duì)等的切分算法進(jìn)行數(shù)據(jù)塊切分。滑動(dòng)塊算法與其他兩種算法不同，它與rsync類似，它對(duì)文件B的切分是定長(zhǎng)算法，而對(duì)文件A的切分是滑動(dòng)塊算法。因此，這種算法切分是不對(duì)等的。
然后根據(jù)文件B構(gòu)造hashtable，通過(guò)hash查找進(jìn)行匹配，并按照差異編碼數(shù)據(jù)布局構(gòu)造相應(yīng)數(shù)據(jù)文件。
7、文件同步
Beta得到差異編碼文件delta，再結(jié)合已有的文件B，即可以將文件B同步成文件A的副本。同步算法遍歷delta文件，讀取每一個(gè)數(shù)據(jù)塊描述實(shí)體，根據(jù)embeded標(biāo)志分別從delta和文件B中讀取相應(yīng)的數(shù)據(jù)塊，重新構(gòu)造出文件A。
8、PULL與PUSH模式
數(shù)據(jù)同步有PULL和PUSH兩種應(yīng)用模式，PULL是將遠(yuǎn)程數(shù)據(jù)同步到本地，而PUSH是將本地?cái)?shù)據(jù)同步到遠(yuǎn)程。對(duì)應(yīng)到同步算法，主要區(qū)別在于數(shù)據(jù)分塊和差異編碼位置不同。PULL和PUSH同步模式步驟分別如下所述。
PULL同步模式流程：
1、本地對(duì)文件A進(jìn)行數(shù)據(jù)切分，生成數(shù)據(jù)塊描述文件chunk；
2、上傳chunk文件至遠(yuǎn)程服務(wù)器；
3、遠(yuǎn)程服務(wù)器對(duì)文件B進(jìn)行差異編碼，生成差異編碼文件delta；
4、下載delta文件至本地；
5、本地同步文件A至文件B，相當(dāng)于下載文件B到本地文件A。
PUSH同步模式流程：
1、遠(yuǎn)程服務(wù)器對(duì)文件B進(jìn)行數(shù)據(jù)切分，生成數(shù)據(jù)塊描述文件chunk；
2、下載chunk文件至本地；
3、本地對(duì)文件A進(jìn)行差異編碼，生成差異編碼文件delta；
4、上傳delta文件至遠(yuǎn)程服務(wù)器；
5、遠(yuǎn)程同步文件B到A，相當(dāng)于上傳文件A到遠(yuǎn)程文件B。
轉(zhuǎn)載：http://blog.csdn.net/liuben/archive/2010/08/06/5793706.aspx
本文鏈接：http://m.95time.cn/tech/program/2010/7878.asp 
出處：CSDN
責(zé)任編輯：bluehearts
上一頁(yè) 數(shù)據(jù)同步算法研究 [3] 下一頁(yè)
◎進(jìn)入論壇網(wǎng)絡(luò)編程版塊參加討論
|
第 1 頁(yè) 
第 4 頁(yè) 數(shù)據(jù)同步算法研究 [4]
