Rsync同步算法

rsync是unix/linux下同步檔案的一個高效算法，它能同步更新兩處計算機的檔案與目錄，并适當利用查找檔案中的不同塊以減少資料傳輸。rsync中一項與其他大部分類似程式或協定中所未見的重要特性是鏡像是隻對有變更的部分進行傳送。rsync可拷貝／顯示目錄屬性，以及拷貝檔案，并可選擇性的壓縮以及遞歸拷貝。rsync利用由澳洲電腦程式師Andrew Tridgell發明的算法。這裡不介紹其使用方法，隻介紹其核心算法。我們可以看到Unix下的東西，一個指令，一個工具都有很多很精妙的東西，怎麼學也學不完，這就是Unix的文化啊。

問題

首先， 我們先來想一下rsync要解決的問題，如果我們要同步的檔案隻想傳不同的部分，我們就需要對兩邊的檔案做diff，但是這兩個問題在兩台不同的機器上，無法做diff。如果我們做diff，就要把一個檔案傳到另一台機器上做diff，但這樣一來，我們就傳了整個檔案，這與我們隻想傳輸不同部的初衷相背。

于是我們就要想一個辦法，讓這兩邊的檔案見不到面，但還能知道它們間有什麼不同。這就出現了rsync的算法。

算法

rsync的算法如下（假設我們同步源檔案名為fileSrc，同步目的檔案叫fileDst）:

資料分塊

首先，我們會把fileDst的檔案平均切分成若幹個小塊，比如每塊512個位元組（最後一塊會小于這個數），然後對每塊計算兩個checksum，

• 一個叫rolling checksum，是弱checksum，32位的checksum，其使用的是Mark Adler發明的adler-32算法，
• 另一個是強checksum，128位的，以前用md4，現在用md5 hash算法。

為什麼要這樣？因為若幹年前的硬體上跑md4的算法太慢了，是以，我們需要一個快算法來鑒别檔案塊的不同，但是弱的adler32算法碰撞機率太高了，是以我們還要引入強的checksum算法。

CheckSum算法

同步目标端會把fileDst的一個checksum清單傳給同步源，這個清單裡包括了三個東西，rolling checksum(32bits)，md5 checksume(128bits)，檔案塊編号。

我估計你猜到了同步源機器拿到了這個清單後，會對fileSrc做同樣的checksum，然後和fileDst的checksum做對比，這樣就知道哪些檔案塊改變了。

但是，聰明的你一定會有以下兩個疑問：

• 如果我fileSrc這邊在檔案中間加了一個字元，這樣後面的檔案塊就完全和fileDst這邊的不一樣了，但理論上來說，我隻需要傳一個字元就好了。
• 如果這個checksum清單特别長，而我的兩邊的相同的檔案塊可能并不是一樣的順序，那就需要查找，線性的查找起來應該特别慢吧。

很好，讓我們來看一下同步源端的算法。

CheckSum查找算法

同步源端拿到fileDst的checksum數組後，會把這個資料存到一個 hash table中，用rolling checksum做hash，以便獲得O(1)時間複雜度的查找性能。這個hash table是16bits的，是以，hash table的尺寸是2的16次方，對rolling checksum的hash會被散列到0 – 2^16 – 1中的某個值。（對于hash table，如果你不清楚，請回去看你大學時的資料結構那本教科書）

順便說一下，我在網上看到很多文章說，“要對rolling checksum做排序”（比如這篇和這篇），這兩篇文章都引用并翻譯了原版的這篇文章，但是他們都了解錯了，不是排序，就是把fileDst的checksum資料，按rolling checksum做存到2^16的hash table中，當然會發生碰撞，把碰撞的做成一個連結就好了。這就是原文中所說的第二步。

比對算法

這是最關鍵的算法，細節如下:

• 取fileSrc的第一個檔案塊（我們假設的是512個長度），也就是從fileSrc的第1個位元組到第512個位元組，取出來後做rolling checksum計算。計算好的值到hash表中查。
• 如果查到了，說明發現在fileDst中有潛在相同的檔案塊，于是就再比較 md5的checksum，因為rolling checksume太弱了，可能發生碰撞。于是還要算md5的128bits的checksum，這樣一來，我們就有 2^-(32+128) = 2^-160的機率發生碰撞，這太小了可以忽略。如果rolling checksum和md5 checksum都相同，這說明在fileDst中有相同的塊，我們需要記下這一塊在fileDst下的檔案編号。
• 如果fileSrc的rolling checksum 沒有在hash table中找到，那就不用算md5 checksum了。表示這一塊中有不同的資訊。總之，隻要rolling checksum 或 md5 checksum 其中有一個在fileDst的checksum hash表中找不到比對項，那麼就會觸發算法對fileSrc的rolling動作。于是，算法會住後step 1個位元組，取fileSrc中位元組2-513的檔案塊要做checksum，go to (4.1) - 現在你明白什麼叫rolling checksum了吧。
• 這樣，我們就可以找出fileSrc相鄰兩次比對中的那些文本字元，這些就是我們要往同步目标端傳的檔案内容了。

總結

怎麼，你沒看懂？ 好吧，我送佛送上西，畫個圖給你看看。

這樣，最終，在同步源這端，我們的rsync算法可能會得到下面這個樣子的一個資料數組，圖中，紅色塊表示在目标端已比對上，不用傳輸（注：我專門在其中顯示了兩塊chunk #5），而白色的地方就是需要傳輸的内容（注意：這些白色的塊是不定長的），這樣，同步源這端把這個數組（白色的就是實際内容，紅色的就放一個标号）壓縮傳到目的端，在目的端的rsync會根據這個表重新生成檔案，這樣，同步完成。

最後想說一下，對于某些壓縮檔案使用rsync傳輸可能會傳得更多，因為被壓縮後的檔案可能會非常的不同。對此，對于gzip和bzip2這樣的指令，記得開啟 “rsyncalbe” 模式。

文章出自：酷殼網