rsync 的核心算法
作者：陳皓
rsync是unix/linux下同步文件的一個(gè)高效算法，它能同步更新兩處計(jì)算機(jī)的文件與目錄，并適當(dāng)利用查找文件中的不同塊以減少數(shù)據(jù)傳輸。rsync中一項(xiàng)與其他大部分類似程序或協(xié)定中所未見的重要特性是鏡像是只對(duì)有變更的部分進(jìn)行傳送。rsync可拷貝／顯示目錄屬性，以及拷貝文件，并可選擇性的壓縮以及遞歸拷貝。
rsync是unix/linux下同步文件的一個(gè)高效算法，它能同步更新兩處計(jì)算機(jī)的文件與目錄，并適當(dāng)利用查找文件中的不同塊以減少數(shù)據(jù)傳輸。rsync中一項(xiàng)與其他大部分類似程序或協(xié)定中所未見的重要特性是鏡像是只對(duì)有變更的部分進(jìn)行傳送。rsync可拷貝／顯示目錄屬性，以及拷貝文件，并可選擇性的壓縮以及遞歸拷貝。rsync利用由Andrew Tridgell發(fā)明的算法。這里不介紹其使用方法，只介紹其核心算法。我們可以看到，Unix下的東西，一個(gè)命令，一個(gè)工具都有很多很精妙的東西，怎么學(xué)也學(xué)不完，這就是Unix的文化啊。
本來不想寫這篇文章的，因?yàn)樵劝l(fā)現(xiàn)有很多中文blog都說了這個(gè)算法，但是看了一下，發(fā)現(xiàn)這些中文blog要么翻譯國外文章翻譯地非常爛，要么就是介紹這個(gè)算法介紹得很亂讓人看不懂，還有錯(cuò)誤，誤人不淺，所以讓我覺得有必要寫篇rsync算法介紹的文章。（當(dāng)然，我成文比較倉促，可能會(huì)有一些錯(cuò)誤，請(qǐng)指正）
問題
首先， 我們先來想一下rsync要解決的問題，如果我們要同步的文件只想傳不同的部分，我們就需要對(duì)兩邊的文件做diff，但是這兩個(gè)問題在兩臺(tái)不同的機(jī)器上，無法做diff。如果我們做diff，就要把一個(gè)文件傳到另一臺(tái)機(jī)器上做diff，但這樣一來，我們就傳了整個(gè)文件，這與我們只想傳輸不同部的初衷相背。
于是我們就要想一個(gè)辦法，讓這兩邊的文件見不到面，但還能知道它們間有什么不同。這就出現(xiàn)了rsync的算法。
算法
rsync的算法如下：（假設(shè)我們同步源文件名為fileSrc，同步目的文件叫fileDst）
1）分塊Checksum算法。首先，我們會(huì)把fileDst的文件平均切分成若干個(gè)小塊，比如每塊512個(gè)字節(jié)（最后一塊會(huì)小于這個(gè)數(shù)），然后對(duì)每塊計(jì)算兩個(gè)checksum，
一個(gè)叫rolling checksum，是弱checksum，32位的checksum，其使用的是Mark Adler發(fā)明的adler-32算法，
另一個(gè)是強(qiáng)checksum，128位的，以前用md4，現(xiàn)在用md5 hash算法。
為什么要這樣？因?yàn)槿舾赡昵暗挠布吓躮d4的算法太慢了，所以，我們需要一個(gè)快算法來鑒別文件塊的不同，但是弱的adler32算法碰撞概率太高了，所以我們還要引入強(qiáng)的checksum算法以保證兩文件塊是相同的。也就是說，弱的checksum是用來區(qū)別不同，而強(qiáng)的是用來確認(rèn)相同。（checksum的具體公式可能看這篇文章）
2）傳輸算法。同步目標(biāo)端會(huì)把fileDst的一個(gè)checksum列表傳給同步源，這個(gè)列表里包括了三個(gè)東西，rolling checksum(32bits)，md5 checksume(128bits)，文件塊編號(hào)。
我估計(jì)你猜到了同步源機(jī)器拿到了這個(gè)列表后，會(huì)對(duì)fileSrc做同樣的checksum，然后和fileDst的checksum做對(duì)比，這樣就知道哪些文件塊改變了。
但是，聰明的你一定會(huì)有以下兩個(gè)疑問：
如果我fileSrc這邊在文件中間加了一個(gè)字符，這樣后面的文件塊都會(huì)位移一個(gè)字符，這樣就完全和fileDst這邊的不一樣了，但理論上來說，我應(yīng)該只需要傳一個(gè)字符就好了。這個(gè)怎么解決？
如果這個(gè)checksum列表特別長(zhǎng)，而我的兩邊的相同的文件塊可能并不是一樣的順序，那就需要查找，線性的查找起來應(yīng)該特別慢吧。這個(gè)怎么解決？
很好，讓我們來看一下同步源端的算法。
3）checksum查找算法。同步源端拿到fileDst的checksum數(shù)組后，會(huì)把這個(gè)數(shù)據(jù)存到一個(gè)hash table中，用rolling checksum做hash，以便獲得O(1)時(shí)間復(fù)雜度的查找性能。這個(gè)hash table是16bits的，所以，hash table的尺寸是2的16次方，對(duì)rolling checksum的hash會(huì)被散列到0 – 2^16 – 1中的某個(gè)值。（對(duì)于hash table，如果你不清楚，請(qǐng)回去看你大學(xué)時(shí)的數(shù)據(jù)結(jié)構(gòu)那本教科書）
順便說一下，我在網(wǎng)上看到很多文章說，“要對(duì)rolling checksum做排序”（比如這篇和這篇），這兩篇文章都引用并翻譯了原版的這篇文章，但是他們都理解錯(cuò)了，不是排序，就只是把fileDst的checksum數(shù)據(jù)，按rolling checksum做存到2^16的hash table中，當(dāng)然會(huì)發(fā)生碰撞，把碰撞的做成一個(gè)鏈接就好了。這就是原文中所說的第二步。
4）比對(duì)算法。這是最關(guān)鍵的算法，細(xì)節(jié)如下：
4.1）取fileSrc的第一個(gè)文件塊（我們假設(shè)的是512個(gè)長(zhǎng)度），也就是從fileSrc的第1個(gè)字節(jié)到第512個(gè)字節(jié)，取出來后做rolling checksum計(jì)算。計(jì)算好的值到hash表中查。
4.2）如果查到了，說明發(fā)現(xiàn)在fileDst中有潛在相同的文件塊，于是就再比較md5的checksum，因?yàn)閞olling checksume太弱了，可能發(fā)生碰撞。于是還要算md5的128bits的checksum，這樣一來，我們就有 2^-(32+128) = 2^-160的概率發(fā)生碰撞，這太小了可以忽略。如果rolling checksum和md5 checksum都相同，這說明在fileDst中有相同的塊，我們需要記下這一塊在fileDst下的文件編號(hào)。
4.3）如果fileSrc的rolling checksum 沒有在hash table中找到，那就不用算md5 checksum了。表示這一塊中有不同的信息?？傊灰猺olling checksum 或 md5 checksum 其中有一個(gè)在fileDst的checksum hash表中找不到匹配項(xiàng)，那么就會(huì)觸發(fā)算法對(duì)fileSrc的rolling動(dòng)作。于是，算法會(huì)住后step 1個(gè)字節(jié)，取fileSrc中字節(jié)2-513的文件塊要做checksum，go to (4.1) - 現(xiàn)在你明白什么叫rolling checksum了吧。
4.4）這樣，我們就可以找出fileSrc相鄰兩次匹配中的那些文本字符，這些就是我們要往同步目標(biāo)端傳的文件內(nèi)容了。
圖示
怎么，你沒看懂？ 好吧，我送佛送上西，畫個(gè)示意圖給你看看（對(duì)圖中的東西我就不再解釋了）。
這樣，最終，在同步源這端，我們的rsync算法可能會(huì)得到下面這個(gè)樣子的一個(gè)數(shù)據(jù)數(shù)組，圖中，紅色塊表示在目標(biāo)端已匹配上，不用傳輸（注：我專門在其中顯示了兩塊chunk #5，相信你會(huì)懂的），而白色的地方就是需要傳輸?shù)膬?nèi)容（注意：這些白色的塊是不定長(zhǎng)的），這樣，同步源這端把這個(gè)數(shù)組（白色的就是實(shí)際內(nèi)容，紅色的就放一個(gè)標(biāo)號(hào)）壓縮傳到目的端，在目的端的rsync會(huì)根據(jù)這個(gè)表重新生成文件，這樣，同步完成。
最后想說一下，對(duì)于某些壓縮文件使用rsync傳輸可能會(huì)傳得更多，因?yàn)楸粔嚎s后的文件可能會(huì)非常的不同。對(duì)此，對(duì)于gzip和bzip2這樣的命令，記得開啟 “rsyncalbe” 模式。
【編輯推薦】
責(zé)任編輯：趙寧寧
