|
1、引言
基于LAN或WAN的網(wǎng)絡(luò)應(yīng)用之間進(jìn)行數(shù)據(jù)傳輸或者同步非常普遍，比如遠(yuǎn)程數(shù)據(jù)鏡像、備份、復(fù)制、同步，數(shù)據(jù)下載、上傳、共享等等，最為簡(jiǎn)單的做法自然就是對(duì)數(shù)據(jù)進(jìn)行完全復(fù)制。然而，數(shù)據(jù)在網(wǎng)絡(luò)上來(lái)回被復(fù)制多次后就會(huì)存在大量副本，很多情形下這些文件副本之間僅有很小的差異，很可能是從同一個(gè)文件版本演化而來(lái)。如果對(duì)文件進(jìn)行完全復(fù)制，在文件較大的情況下，會(huì)占用大量網(wǎng)絡(luò)帶寬，同步時(shí)間也會(huì)較長(zhǎng)。
目前，廣域網(wǎng)WAN的帶寬與訪問(wèn)延遲仍然是急需解決的問(wèn)題，完全復(fù)制使得很多網(wǎng)絡(luò)應(yīng)用無(wú)法提供良好的服務(wù)質(zhì)量，比如分布式文件系統(tǒng)(DFS)、云存儲(chǔ)(Cloud Storage)。Rsync與RDC(Remote Differential Compression)是兩種最為常見(jiàn)的數(shù)據(jù)同步算法，它們僅傳輸差異數(shù)據(jù)，從而節(jié)省網(wǎng)絡(luò)帶寬并提高效率。本文基于這兩種算法思想并借助重復(fù)數(shù)據(jù)刪除(De-duplication)技術(shù)，對(duì)數(shù)據(jù)同步算法進(jìn)行深入研究與分析，并研發(fā)了原型系統(tǒng)。首先介紹rsync與RDC算法，然后詳細(xì)描述算法設(shè)計(jì)與相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，并重點(diǎn)分析文件分塊、差異編碼、文件同步算法，最后簡(jiǎn)介推拉兩種應(yīng)用模式。
2、相關(guān)工作
Rsync是類Unix環(huán)境下的一個(gè)高效的遠(yuǎn)程文件復(fù)制(同步)工具，它通過(guò)著名的Rsync算法來(lái)優(yōu)化流程，減少了數(shù)據(jù)通信量并提高文件傳輸效率。假設(shè)現(xiàn)在有兩臺(tái)計(jì)算機(jī)Alpha和Beta ,計(jì)算機(jī)Alpha能夠訪問(wèn)A文件,計(jì)算機(jī)Beta能夠訪問(wèn)B文件，文件A和B非常相似，計(jì)算機(jī)Alpha和Beta通過(guò)低速網(wǎng)絡(luò)互聯(lián)。它的大致流程如下(詳細(xì)過(guò)程請(qǐng)參考Rsync作者Andrew Tridgell的tech_report.ps)：
1、Beta將文件B分割成連續(xù)不重疊的固定大小數(shù)據(jù)塊S，最后一個(gè)數(shù)據(jù)塊上可能會(huì)小于S字節(jié)；
2、Beta對(duì)于每一個(gè)數(shù)據(jù)塊,計(jì)算出兩個(gè)校驗(yàn)值，一個(gè)32位的弱滾動(dòng)校驗(yàn)和一個(gè)128位的MD4校驗(yàn)；
3、Beta將校驗(yàn)值發(fā)送給Alpha；
4、Alpha通過(guò)搜索文件A的所有大小為S的數(shù)據(jù)塊(偏移量可以任意，不一定非要是S的倍數(shù))，來(lái)尋找與文件B的某一塊有著相同的弱校驗(yàn)碼和強(qiáng)校驗(yàn)碼的數(shù)據(jù)塊。這主要由滾動(dòng)校驗(yàn)Rolling checksum快速完成；
5、Alpha給Beta發(fā)送重構(gòu)A文件的指令，每一條指令是一個(gè)文件B數(shù)據(jù)塊引用（匹配）或者是文件A數(shù)據(jù)塊（未匹配）。
Rsync是一個(gè)非常優(yōu)秀的工具，但它仍然存在一些不足之處。
1、Rolling checksum雖然可以節(jié)省大量checksum校驗(yàn)計(jì)算量，也對(duì)checksum搜索作了優(yōu)化，但多出一倍以上的hash查找，這個(gè)消耗不小；
2、Rsync算法中，Alpha和Beta計(jì)算量是不對(duì)等的，Alpha計(jì)算量非常大，而Bete計(jì)算量非常小。通常Alpha是服務(wù)器，因此壓力較大；
3、Rsync中數(shù)據(jù)塊大小是固定的，對(duì)數(shù)據(jù)變化的適應(yīng)能力有限。
RDC算法的典型代表是微軟DFS中的DFSR(Distributed File System Replication)，它與Rsync不同之處在于采用一致的分塊規(guī)則對(duì)復(fù)制的源文件和目標(biāo)文件進(jìn)行切分。因此，RDC對(duì)于源端和目標(biāo)端的計(jì)算量是對(duì)等的。RDC和RSync算法在設(shè)重點(diǎn)上有所不同，Rsync追求更高的重復(fù)數(shù)據(jù)發(fā)現(xiàn)而不惜計(jì)算量；RDC在兩者之間作了一個(gè)折衷，目標(biāo)是以少量的計(jì)算快速發(fā)現(xiàn)數(shù)據(jù)差異，當(dāng)然重復(fù)數(shù)據(jù)發(fā)現(xiàn)不及Rsync。另外，Rsync是定長(zhǎng)分塊策略，而RDC是變長(zhǎng)分塊策略。
3、重復(fù)數(shù)據(jù)刪除技術(shù)
De-duplication，即重復(fù)數(shù)據(jù)刪除，它是一種非常新的且流行度很高的存儲(chǔ)技術(shù)，可以大大減少數(shù)據(jù)的數(shù)量。重復(fù)數(shù)據(jù)刪除技術(shù)，通過(guò)數(shù)據(jù)集中重復(fù)的數(shù)據(jù)，從而消除冗余數(shù)據(jù)。借助dedup技術(shù)，可以提高存儲(chǔ)系統(tǒng)的效率，有效節(jié)約成本、減少傳輸過(guò)程中的網(wǎng)絡(luò)帶寬。同時(shí)它也是一種綠色存儲(chǔ)技術(shù)，能有效降低能耗。
Dedupe按照消重的粒度可以分為文件級(jí)和數(shù)據(jù)塊級(jí)。文件級(jí)的dedup技術(shù)也稱為單一實(shí)例存儲(chǔ)(SIS, Single Instance Store)，數(shù)據(jù)塊級(jí)的重復(fù)數(shù)據(jù)刪除，其消重粒度更小，可以達(dá)到4-24KB之間。顯然，數(shù)據(jù)塊級(jí)的可以提供更高的數(shù)據(jù)消重率，因此目前主流的 dedup產(chǎn)品都是數(shù)據(jù)塊級(jí)的。將文件都分割成數(shù)據(jù)塊(定長(zhǎng)或變長(zhǎng)的數(shù)據(jù)塊)，采用MD5或SHA1等Hash算法 (可以同時(shí)使用兩種或以上hash算法或CRC校驗(yàn)等，以獲得非常小概率的數(shù)據(jù)碰撞發(fā)生)為數(shù)據(jù)塊計(jì)算指紋(FP, Fingerprint)。具有相同F(xiàn)P指紋的數(shù)據(jù)塊即可認(rèn)為是相同的數(shù)據(jù)塊，存儲(chǔ)系統(tǒng)中僅需要保留一份。這樣，一個(gè)物理文件在存儲(chǔ)系統(tǒng)就對(duì)應(yīng)一個(gè)邏輯表示，由一組FP組成的元數(shù)據(jù)。當(dāng)進(jìn)行讀取文件時(shí)，先讀取邏輯文件，然后根據(jù)FP序列，從存儲(chǔ)系統(tǒng)中取出相應(yīng)數(shù)據(jù)塊，還原物理文件副本。
出處：CSDN
責(zé)任編輯：bluehearts
上一頁(yè) 下一頁(yè) 數(shù)據(jù)同步算法研究 [2]
◎進(jìn)入論壇網(wǎng)絡(luò)編程版塊參加討論
|
第 1 頁(yè) 數(shù)據(jù)同步算法研究 [1]
第 2 頁(yè) 
