rsync 是 unix 上常常被用來同步兩臺主機資料的指令。而 rsync 令人稱道同步能力，不僅僅是把檔案抓下來到本機，而是厲害到可以只下載一個檔案中的差異部分，而非整份檔案抓下來。

如果自己想自製一個能夠比較兩份文件差異的程式，稍微想一下設計，大約還能以行爲單位來設計，找出差異。
但是如果檔案並非純文字，而是像照片這般的二進位檔案，可能一整份檔案都沒有任何換行符號，一比較差異就是讓伺服器把整份檔案重新抓下來了。

面對通用檔案的差異比較，其設計思路就會朝向將檔案切成一塊一塊的區塊來進行差異比較。但終究需要面對以下問題：

  • 不可能將每個區塊的內容下載下來讓客戶端進行比較，這樣等同下載整份檔案
  • 如果只是檔頭加了一點內容，切割區塊有機會造成每個區塊內容就不同，也等同要下載整份檔案

面對以上問題，rsync 採用了一些不錯的解決對策

校驗和 (Checksum)

校驗和不是 rsync 獨有的東西，很早就有利用校驗和來檢查檔案是否完整的流程存在。而校驗和其原理就只是利用檔案內的資料產生一個獨特的值，讓下載方與供應方用同樣的方法生出該值，稍加比較就知道兩個檔案是否相同。

舉個最簡單的校驗和的例子，假設檔案內容如下：

{5, 6, 7, 8}

最簡單的校驗和可以直接全部內容相加，其校驗和爲 26 ，只要下載方的校驗和也是 26 ，檔案下載完整的 可能性 就越高。

這裡的說明是用 可能性 是因為大家都知道直接相加的缺點。有太多可以產生相同校驗和的方法了。
例如以下內容皆有機會被視為相同檔案：

{3, 7, 8, 8}
{9, 2, 5, 11}

因此資訊界競相設計出各種校驗和的演算，例如 md4, md5 ，都宣稱高度可信，很難有不同的來源會產生相同的校驗和。但是越高度可信，所需要的計算時間越久，甚至需要產生一些質數出來輔助。

總結校驗和帶來的幫助，就是無需將伺服器上的每個區塊的內容都下載下來比較，只需要比較其校驗和便能得知是否有相同內容。

rsync 策略概述

rsync 接下來要面對的問題，就是如何避免檔案偏移，就造成下載整份檔案的狀況。其流程大概像下面的步驟：

  1. 將伺服器上的檔案 B 切成不重疊的區塊。
  2. 將檔案 B 的所有區塊分別算出一個弱校驗和(Rolling Checksum) 和 強校驗和 (md4)
  3. 客戶端將所有區塊的校驗和下載製表 (hash table)
  4. 客戶端從檔案 A 的檔頭開始切區塊，先只快速算出 弱校驗和，用其查表，查看是否存在
  5. 查表
    • 若無法用弱校驗和查出檔案 B 有該區塊，則區塊往下偏移繼續切並重複步驟 4 直至檔尾。
    • 若能查表查到才用強校驗和計算並比較，若符合代表有該區塊，並紀錄該區塊存在。反之則重複步驟 4

這個策略流程很簡單，但是要突破的瓶頸就是速度。不斷地將區塊偏移並且查詢比較非常耗時，因此其核心是快速的產生校驗和，快速的得知沒有相符的區塊，以避免每個區塊都用速度較慢的強校驗和檢查。在此 rsync 設計的 Rolling Checksum 佔了非常重要的位置。

而 Rolling Checksum 其速度跟前述的將所有資料相加的速度是一樣快的，但又沒有說弱到一下就產生碰撞 ，因此非常適合作初步檢驗。

Rolling Checksum

為了說明方便， Rolling Checksum 簡化算式如下

i 是 block 的開始位置，j 爲結束位置
bsize 則是一個 block 的大小

A = block[i] + block[i+1] + ... + block[j] // 從頭加到尾的意思
B = bsize * block[i] + (bsize - 1) * block[i+1] + ... + 1 * block[j] 

rolling_checksum = A + B

假設一個 block 的大小爲 4 個 byte ， 且 block 內容依然是

{5, 6, 7, 8}

其 Rolling Checksum 爲

 A = 5 + 6 + 7 + 8
 B = (4 * 5) + (3 * 6) + (2 * 7) + (1 * 8)

那為什麼說其速度跟全部加起來一樣快呢？ 觀察 A 部分的全部相加，大概會這樣設計一個迴圈

 A = 0;
 for (i = 0; i < bsize; i++) {
     A += block[i];
 }

將迴圈的流程稍微拆解一下，觀察一下 A 的內容

1.) A = 5
2.) A = 5 + 6
3.) A = 5 + 6 + 7
4.) A = 5 + 6 + 7 + 8

可以發現當中的 5 出現了 4 次，6 出現了 3 次，竟然跟算式 B 的要求吻合（這當然是有設計過的呀）。
所以要計算 B 的值只需要在同一個迴圈累加一下 A 便能同時算出 B 的值。稍微改寫如下

A = 0, B = 0;
for (i = 0; i < bsize; i++) {
    A += block[i]
    B += A;
}

最後補正為了說明而簡化的部分，其實這部分就只是為了 hash table 查詢所需要的取餘數的部分

完整定義：

A = (block[i] + block[i+1] + ... + block[j]) % M // 從頭加到尾的意思
B = (bsize * block[i] + (bsize - 1) * block[i+1] + ... + 1 * block[j]) % M 

rolling_checksum = A + (2^16) * B