rsync 的核心算法
rsync 是 unix/linux 下同步文件的一個高效算法，它能同步更新兩處計算機的文件與目錄，并適當利用查找文件中的不同塊以減少數據傳輸。rsync 中一項與其他大部分類似程序或協定中所未見的重要特性是鏡像是只對有變更的部分進行傳送。rsync 可拷貝／顯示目錄屬性，以及拷貝文件，并可選擇性的壓縮以及遞歸拷貝。rsync 利用由 Andrew Tridgell 發明的算法。這里不介紹其使用方法，只介紹其核心算法。我們可以看到，Unix 下的東西，一個命令，一個工具都有很多很精妙的東西，怎么學也學不完，這就是 Unix 的文化啊。
本來不想寫這篇文章的，因為原先發現有很多中文 blog 都說了這個算法，但是看了一下，發現這些中文 blog 要么翻譯國外文章翻譯地非常爛，要么就是介紹這個算法介紹得很亂讓人看不懂，還有錯誤，誤人不淺，所以讓我覺得有必要寫篇 rsync 算法介紹的文章。（當然，我成文比較倉促，可能會有一些錯誤，請指正）
問題
首先， 我們先來想一下 rsync 要解決的問題，如果我們要同步的文件只想傳不同的部分，我們就需要對兩邊的文件做 diff，但是這兩個問題在兩臺不同的機器上，無法做 diff。如果我們做 diff，就要把一個文件傳到另一臺機器上做 diff，但這樣一來，我們就傳了整個文件，這與我們只想傳輸不同部的初衷相背。
于是我們就要想一個辦法，讓這兩邊的文件見不到面，但還能知道它們間有什么不同。這就出現了 rsync 的算法。
算法
rsync 的算法如下：（假設我們同步源文件名為 fileSrc，同步目的文件叫 fileDst）
1）分塊 Checksum 算法。首先，我們會把 fileDst 的文件平均切分成若干個小塊，比如每塊 512 個字節（最后一塊會小于這個數），然后對每塊計算兩個 checksum，
- 一個叫 rolling checksum，是弱 checksum，32位的 checksum，其使用的是 Mark Adler 發明的 adler-32算法，
- 另一個是強 checksum，128位的，以前用 md4，現在用 md5 hash 算法。 </ul>
- 如果我 fileSrc 這邊在文件中間加了一個字符，這樣后面的文件塊都會位移一個字符，這樣就完全和 fileDst 這邊的不一樣了，但理論上來說，我應該只需要傳一個字符就好了。這個怎么解決？ </ul>
- 如果這個 checksum 列表特別長，而我的兩邊的相同的文件塊可能并不是一樣的順序，那就需要查找，線性的查找起來應該特別慢吧。這個怎么解決？ </ul>
為什么要這樣？因為若干年前的硬件上跑 md4 的算法太慢了，所以，我們需要一個快算法來鑒別文件塊的不同，但是弱的 adler32 算法碰撞概率太高了，所以我們還要引入強的 checksum 算法以保證兩文件塊是相同的。也就是說，弱的 checksum 是用來區別不同，而強的是用來確認相同。（checksum 的具體公式可能看這篇文章）
2）傳輸算法。同步目標端會把 fileDst 的一個 checksum 列表傳給同步源，這個列表里包括了三個東西，rolling checksum (32bits)，md5 checksume (128bits)，文件塊編號。
我估計你猜到了同步源機器拿到了這個列表后，會對 fileSrc 做同樣的 checksum，然后和 fileDst 的 checksum 做對比，這樣就知道哪些文件塊改變了。
但是，聰明的你一定會有以下兩個疑問：
很好，讓我們來看一下同步源端的算法。
3）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 中，當然會發生碰撞，把碰撞的做成一個鏈接就好了。這就是原文中所說的第二步。
4）比對算法。這是最關鍵的算法，細節如下：
4. 1）取 fileSrc 的第一個文件塊（我們假設的是 512 個長度），也就是從 fileSrc 的第 1 個字節到第 512 個字節，取出來后做 rolling checksum 計算。計算好的值到 hash 表中查。
4. 2）如果查到了，說明發現在 fileDst 中有潛在相同的文件塊，于是就再比較 md5 的 checksum，因為 rolling checksume 太弱了，可能發生碰撞。于是還要算 md5 的 128bits 的 checksum，這樣一來，我們就有 2^-(32+128) = 2^-160的概率發生碰撞，這太小了可以忽略。如果 rolling checksum 和 md5 checksum 都相同，這說明在 fileDst 中有相同的塊，我們需要記下這一塊在 fileDst 下的文件編號。
4. 3）如果 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 了吧。
4. 4）這樣，我們就可以找出 fileSrc 相鄰兩次匹配中的那些文本字符，這些就是我們要往同步目標端傳的文件內容了。
圖示
怎么，你沒看懂？ 好吧，我送佛送上西，畫個示意圖給你看看（對圖中的東西我就不再解釋了）。
這樣，最終，在同步源這端，我們的 rsync 算法可能會得到下面這個樣子的一個數據數組，圖中，紅色塊表示在目標端已匹配上，不用傳輸（注：我專門在其中顯示了兩塊 chunk #5，相信你會懂的），而白色的地方就是需要傳輸的內容（注意：這些白色的塊是不定長的），這樣，同步源這端把這個數組（白色的就是實際內容，紅色的就放 一個標號）壓縮傳到目的端，在目的端的 rsync 會根據這個表重新生成文件，這樣，同步完成。
最后想說一下，對于某些壓縮文件使用 rsync 傳輸可能會傳得更多，因為被壓縮后的文件可能會非常的不同。對此，對于 gzip 和 bzip2 這樣的命令，記得開啟 “rsyncalbe” 模式。