寫程式是良心事業: 關於 rsync algorithm 演算法

因為專案需要, 我希望能夠稍微了解真正底層用到的rsync技術, 所以我選讀的這篇文章就是位於澳洲首都特區坎培拉的研究型國立大學, 由 Andrew Tridgell 和 Paul Mackerras 在 1996 年6月所發表 The rsync algorithm [1]這篇技術報告. 而 Andrew Tridgell 在 1999年的2月發表了博士論文 Efficient Algorithms for Sorting and Synchronization [2]. 而目前在 Linux/Unix 底下使用的 rsync [4] 指令是由 Wayne Davison 所維護. 而知名的 Dropbox 服務底層則是改良自 librsync [5].

而這篇文章, 我主要是著重在於技術報告中提到的 Rolling Checksum 和 Checksum searching 的部份. 由於我並不是資工系畢業的, 也沒學過工程數學或是一些高深的數學演算法, 因此看這篇技術報告時, 只能搭配程式碼來研讀. 網路上其實有不少介紹 Rolling Checksum的文章, 也有對岸簡體文章在說明這部份. 但, 後來找到一個網站是 Jakob Jenkov 所寫的 RSync - Remote Synchronization Protocol [3] 中的 Checkums 章節. 才能比較理解 Rolling checksum 作法的好處, 以及如果要實作 Rolling Checksum 應該怎樣實作. 接著陸續找到一些網路上實作 Rolling checksum 的程式碼研讀後, 對於 Rolling Checksum 就比較能夠掌握.

The rsync algorithm:

假設有兩台分別為 α 和 ß 的電腦. α 電腦存取一個檔案 A, 且 ß 電腦存取一個檔案 B. 當檔案 A和檔案 B 具有類似的相同內容時. 在 α 和 ß 電腦之間要同步這個檔案時,可以透過 rsync 演算法來解決每次都要完整傳送整份檔案的困擾. rsync 演算法包含 5 個步驟

ß 將檔案 B 分割成一系列不重疊的固定大小的區塊(Block), 區塊大小(Block size)的為 S bytes. 最後一個區塊的大小可能會小於 S bytes.
ß 會把每一個區塊計算出兩個 checksums: 一個稱作 weak "rolling" 32-bits checksum. 另一個是 strong 128-bit MD4 checksum.
接著 ß 將這些 checksums 都送給 α .
α 會對於檔案 A 中尋找在任何 offset 上所有大小 S bytes的區塊是否有相同的 weak and strong checksum 和 ß 所提供的相同. 這是透過 rolling checksum 的特性, 所以速度相當快.
最後, α 會傳送一連串的intructions給 ß 來建構出檔案A的複製版本. 每一個 instruction 都會是參照到檔案 B的一個區塊或是 literal data. Literal data 指的是那些在檔案 A 中出現, 但是不符合檔案 B中任何一個區塊的資料.

最後, ß 將會得到一個完整的檔案A的複製, 但是 α 只需要傳送部份檔案A中不存在於檔案B的資料 literal data 給 ß 就可以了.

Rolling checksum:

基本上, 如果你是學數學或是資工背景的, 看技術報告 Rolling checksum 章節的定義, 應該就完全能夠理解它所提的 weak rolling checksum 是怎樣運作的.

在開始解釋它之前, 我們先回到前面 rsync algorithm 的第4個步驟, α 必須對於檔案A 中在任何 offset 上所有大小 S bytes 的區塊, 尋找是否有和 ß 所提供的區塊有相同的 weak and strong checksum. 假設, 檔案 A 的大小為 10 個 bytes, 而 ß 所提供的區塊大小 S 為 4 bytes 的資料給 α . 這時 α 必須從第 0 個 byte 開始比對且必須依序移動每一個 byte 後抓4個bytes的資料來比對, 最差的情況要6次才能比對完一個 ß 所提供第一個區塊資料. 請參考如下圖:

透過前面這一個簡單的圖示, 我們可以知道, 如果檔案Ａ的資料很大時候,要比對完 ß 所提供的不同區塊, 它會是一個大量的資料運算.

現在, 回到技術報告中所節錄的 Rolling checksum 定義如下:

Rolling checksum 是由兩個值計算後所組成, 分別為 a (k, l) 和 b(k, l). 一個區塊的 block 的 Rolling checksum 可以用 s (k, l) 來表示. 而 s (k, l) = a (k, l) + (2^16)* b(k, l). 為了方便解釋, 這裡先會忽略掉 mod M 的部分. 此處我們可以節錄自 Jakob Jenkov 寫的 RSync - Remote Synchronization Protocol [3] 中的 Checkums 章節中 Rolling Checksum Algorithm 的解釋, 以下的 A 其實就是表示 a(k, l), 而 B 就是表示 b(k, l).

data = 是指一個區塊(block)的資料
i    = index 是區塊上表示每一個 byte 的位置. 如果區塊大小為 4 bytes, 即 blockSize = 4.
       則 i = 0, 1, 2, 3

a(k,l)即是 A = data[0] + data[1] + ... data[i];

b(k,l)即是 B = blockSize * data[0] + (blockSize-1) * data[1] + ... +
              (blockSize - i) * data[i] ... + 1 * data[blockSize-1];

假設有一個區塊大小 4 bytes 的資料如下, 這個區塊的每個byte的值分別為 3, 5, 7, 9. 根據定義計算 A = a(0, i) 和 B = b(0, i) 的方式分別如下：

而這個特性, 透過觀察可以得到 B 其實是每次的累加 A 所組成

A += data[i];
B += A;

在 Jakob Jenkov 所寫的 RSync - Remote Synchronization Protocol [3] 中的 Checkums 章節裡面有提到為什麼 A+= data[i] 後, 要算出 B只要用 B += A; 即可求出.

因此, 當我們要移動 1 個 byte 來計算下 1 個 4 bytes長度區塊的 Rolling checksum 時, 我們並不需要重新完整算一次. 只需要知道下 1 個 byte的值. 就可以求出來 A 和 B 的值. (以下節錄自Jakob Jenkov的文章 )

start = start index of new block.
end   = end index of new block.  

A -= data[start-1];   //remove old, first byte.
A += data[end];       // 算出新的 A

B -= blockSize * data[start-1];
B += A;               // 算出新的 B

Checksum searching:

根據技術報告中提到的 checksum searching, 它可以分為 3 個 Level 的 searching方式, 我用以下這張概念圖來解釋它.

當 α 收到 ß 傳送過來的 checksums 資料時候, 會建立一個大小為 2^16的 Hash Table , 而每個 key 所存的值就是表示一個區塊 32 bits長度 Rolling checksum 的 hash值, 長度為 16 bits. 而 Hash Table每個 key 對應的 entry 可能會指向 null 也可能會指向一個 list 的資料. 這個 list 中的 Node 包含 Rolling Checksum 以及一個 Strong Checksum. 比對的方式如下:

從A檔案中第 0 個byte開始, 抓出 block size大小的區塊算出 rolling checksum 以及 rolling checksum的 hash值. 如果 hash 值有符合就表示通過了 Level 1的 Check.
當 Level 1 Check 通過後, 開始找 list 中的node比較其 rolling checksum是否符合.若有則表示通過 Level2 Check.
一旦 Level2 Check通過, 就要把A檔案中的這個完整區塊的 strong checksum算出來和 node中的 Strong checksum 比對.

如果這個offset所取出的區塊在比對過程中有找到符合的, α 就要把目前 offset 以及對應到檔案 B 中的哪一個 block的資訊記錄下來, .如果完全都沒有比對到, 則繼續移動1個byte抓出相同 block size的區塊再比對一次.直到檔案A的所有區塊都比對過為止.

另外, 以上這張概念圖中 Hash Table 的 key值是排序過的, 這和我們一般所熟知的 Hash Table的是稍微不同的.在 Efficient Algorithms for Sorting and Synchronization [2]論文中的 3.2 章節有一張圖如下, 這才是原作者在 rsync 中所實作的方式.