問題：

如何增量同步文件，例如一個(gè)文本文件有10M，分別存放在A，B兩個(gè)地方，現(xiàn)在兩個(gè)文件是完全一樣的，但是我馬上要在A上對(duì)這個(gè)文件進(jìn)行修改，B如何實(shí)現(xiàn)自動(dòng)和A上的文件保持一致，并且網(wǎng)絡(luò)的傳輸量最少。

?

應(yīng)用場(chǎng)景：

這樣的使用場(chǎng)景太多，這里隨便列舉幾個(gè)

1.A機(jī)器為線上運(yùn)營的機(jī)器，現(xiàn)在需要一臺(tái)備份的機(jī)器B，當(dāng)A發(fā)生宕機(jī)的時(shí)候，或者硬盤損壞等各種認(rèn)為非人為原因?qū)е聰?shù)據(jù)不可用時(shí)，可以很快從B恢復(fù)

2.SVN這樣的應(yīng)用場(chǎng)景，不需要每次修改都向服務(wù)器發(fā)送并替換掉一個(gè)文件，而是只發(fā)送被修改的部分

3.手機(jī)客戶端對(duì)一個(gè)文本修改，如果那個(gè)文本有2M，難道我每次更新都需要上傳整個(gè)文件嗎？每次2M，傻子才用!?

等等....?

?

解決方案：

一.分而治之

計(jì)算機(jī)最重要的基本算法思路就是分而治之，在我們眼里，一個(gè)文件不是一個(gè)文件，而是一堆存儲(chǔ)塊，每個(gè)存儲(chǔ)塊可能20Byte大小，至于這個(gè)值具體多大，你可以自己設(shè)定,這里的20Byte僅提供參考。通過這樣的方法，一個(gè)文件被分成了很多個(gè)塊，我們只需要比對(duì)塊是否相同就可以得出哪個(gè)部分做了相應(yīng)修改。

?

二.快速校驗(yàn)

剛上面提到如何比對(duì)文件，當(dāng)然這里肯定不會(huì)把文件的每個(gè)塊上傳去比對(duì)，那樣做就沒有意義了。快速比對(duì)這不禁讓我想起了哈希規(guī)則，哈希表可以通過O（1）的復(fù)雜度查找某個(gè)key，為什么？ ?因?yàn)樗ㄟ^計(jì)算hash值來初步驗(yàn)證key，一個(gè)key的hash值是唯一的。但是僅僅驗(yàn)證hash值是不可靠的，因?yàn)閔ash值有可能會(huì)沖突，所以在驗(yàn)證完hash值后，我們?cè)谶M(jìn)行key的比較來確定要找的值...

通過哈希的思路，我們可以使用類似的方法來實(shí)現(xiàn)文件增量同步，把每一個(gè)存儲(chǔ)塊，通過MD5計(jì)算其值，然后傳遞MD5值到服務(wù)器，讓服務(wù)器比對(duì)MD5來確定有沒有被修改，如若MD5值不相等，則判定這個(gè)文件塊有被修改過

為什么是MD5？

1）能夠?qū)⑷我忾L度的字符串轉(zhuǎn)換為128位定長字符串（MD5 16)?

2）MD5能夠保證絕大部分情況下不同的值hash之后其hash值不一樣，哈希沖突比較少

這樣就可以了嗎？

No,MD5的生成需要占用比較長的CPU時(shí)間，所以我們需要尋找一種更簡潔的校驗(yàn)方式，這里選用Alder32?是一個(gè)比較通用的解決方案

?

Alder32有兩個(gè)優(yōu)點(diǎn)：? 1、計(jì)算非常快，比MD5快多了，成本小； 2、當(dāng)我們有了從0-k長度的校驗(yàn)和后，計(jì)算出1-k或者2-k等其他校驗(yàn)和非常方便，只要少量運(yùn)算即可。(k可以理解為上面的20Byte)

?

當(dāng)然，它的缺點(diǎn)也很明顯，就是碰撞率比MD5高多了，所以，我們客戶端需要同時(shí)計(jì)算出Alder32校驗(yàn)和與MD5值，傳給服務(wù)器，而服務(wù)器，為了節(jié)省CPU時(shí)間，第一步只生成Alder32進(jìn)行校驗(yàn)，當(dāng)值相等時(shí)，在進(jìn)行MD5校驗(yàn)，這樣服務(wù)器就節(jié)省了很大的開支。

Alder32算法實(shí)現(xiàn)：

?A?=?1?+?D1?+?D2?+?...?+?Dn?(mod?65521)
?B?=?(1?+?D1)?+?(1?+?D1?+?D2)?+?...?+?(1?+?D1?+?D2?+?...?+?Dn)?(mod?65521)
???=?n×D1?+?(n?1)×D2?+?(n?2)×D3?+?...?+?Dn?+?n?(mod?65521)

?Adler-32(D)?=?B?×?65536?+?A

C實(shí)現(xiàn)版本

const?int?MOD_ADLER?=?65521;
?
unsigned?long?adler32(unsigned?char?*data,?int?len)?/*?where?data?is?the?location?of?the?data?in?physical?memory?and?
???????????????????????????????????????????????????????len?is?the?length?of?the?data?in?bytes?*/
{
????unsigned?long?a?=?1,?b?=?0;
????int?index;
?
????/*?Process?each?byte?of?the?data?in?order?*/
????for?(index?=?0;?index?<?len;?++index)
????{
????????a?=?(a?+?data[index])?%?MOD_ADLER;
????????b?=?(b?+?a)?%?MOD_ADLER;
????}
?
????return?(b?<<?16)?|?a;
}

?

三.實(shí)現(xiàn)更改

因?yàn)橐呀?jīng)找出來了文件不同的地方，所以只需要按需上傳更改的部分到服務(wù)器，然后服務(wù)器做更改就可以了。?

?

?

實(shí)例分析：?

理論概述完畢，來點(diǎn)小例子子

客戶端文件內(nèi)容是：?

?taohuiissoman

而服務(wù)器的文件內(nèi)容是：

itaohuiamsoman

?

首先，客戶端開始分塊并計(jì)算出MD5和Alder32值。

如上圖，像taoh是一塊，對(duì)taoh分別計(jì)算出MD5和alder32值。以此類推，最后一個(gè)n字母不足4位保留。于是，客戶端把計(jì)算出的MD5和alder32按順序發(fā)出，最后發(fā)出字符n。

?

服務(wù)器收到后，先把自己保存的File.2的內(nèi)容按4字節(jié)劃分。

劃分出itao、huia、msom、an，當(dāng)然，這些串的Alder32值肯定無法從File.1里劃分出的：taoh、uiis、soma、n找出相同的。于是向后移一個(gè)字節(jié)，從t開始繼續(xù)按4字節(jié)劃分。

從taoh上找到了alder32相同的塊，接著再比較MD5值，也相同！于是記下來，跳過taoh這4個(gè)字符，看uiam，又找不到File.1上相同的塊了。繼續(xù)向后跳1個(gè)字節(jié)從i開始看。還是沒有找到Alder32相同，繼續(xù)向后移，以此類推。

到了soma，又找到相同的塊了。

?

重復(fù)上面的步驟，直到File.2文件結(jié)束。

?

通過這個(gè)簡單的例子，可以設(shè)想一下其他任何的增刪查改功能?

?

參考資料：http://cs.anu.edu.au/techreports/1996/TR-CS-96-05.pdf?

?

---

博客地址：Zealot Yin

歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)注明出處[http://creator.cnblogs.com/]

總結(jié)

以上是生活随笔為你收集整理的如何实现文件增量同步——算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。