我是山姆鍋

版本控制與檔案同步軟體其中一個重要功能：讓來源 (source) 檔案的內容跟目標 (target) 檔案內容相同。
直覺來說，最簡單的方式：將來源檔案複製 (copy) 到目標檔案。
不過這種做法，對於像是同一個檔案的不同版本的同步，會耗用太多不必要的頻寬與儲存空間之外，
時間往往也是個造成這種方式不實際的因素之一。那有沒有更有效的作法呢？

在 [Dropbox
做到資料加密又避免重複儲存的秘密]
這篇文章中，山姆鍋提到會分享一個在網路上發現的有趣方法，來執行檔案切割的動作。
檔案切割其實只是找出兩個檔案差異的其中步驟之一，還是讓山姆鍋從頭說起。

問題描述

假設有兩個檔案，A 跟 B，
不管這兩個檔案是不是代表同一個文件的不同版本，問題是我們需要一個比將檔案
Ａ 拷貝 (copy) 並覆蓋 B 這種方式更有效的作法。
如果觀察檔案在不同時間點的修改，會發現通常只有少部分發生更動。
為了要快速有效的同步檔案，直覺可以找出來源檔案與目標檔案的差異，然後只需要在目標檔修改這些有差異的地方。
一個天真的方法是將來源檔案切割成多個固定大小的區塊，除了最後一個區塊可能比較小。
然後以同樣方式切割目標檔案後，再比對哪些區塊差異。這個方法只要在檔案開頭增加一個位元組，所有區塊的切割點跟內容就會全然不同。
顯然，我們需要更好的解決方案。

解決方案

聽過 Rsync 這個 Linux 檔案同步工具的讀者，
應該知道它能有效率的處理檔案同步的問題。對於 Rsync
的演算法有興趣的讀者，可以參考 [1] 跟 [2] 。 雖然 Rsync
使用的演算法可以解決上述問題，但山姆鍋所說有趣的方法是在參考 bup
這個 GitHub 專案時發現的，他們把他們的方法稱為「Hashsplitting」。

Rsync 與 Hashsplitting 的相同點：

  1. 都需要將檔案切割成區塊，以區塊做為比較單位。
  2. 為了計算快速，都使用 Rolling checksum。
  3. 同樣都使用強檢查碼來比對區塊內容是否相同。

除上述幾點外，Hashsplitting 可以說採用不同的思路來解決相同的問題。例如：

  • Rsync 使用固定區塊大小，Hashsplitting 的區塊邊界是動態決定。
  • Rsync 使用 rolling checksum 作為區塊內容的弱檢查碼，但 Hashsplitting
    則用它來做區塊邊界偵測。

首先，來看看 Hashsplitting 的步驟：

  1. 從檔案開頭，每連續 64 個位元組 (byte) 計算一個 32-bit rolling
    checksum。
  2. 如果 checksum 的最低 13 位元 (bit) 都是
    1，且與上個切割點距離超過 2K 的話，則最後一個位元組的位移 (offset) 是一個分割點。
  3. 如果與上一個分割點過大，如超過 32KB，則強制最後一個位元組的位移作為一個分割點。
  4. 重複步驟 2 到 3 直到檔案處理完畢。

Hashsplitting 表面上看起來好像很簡單，但其實要理解並不是那麼直覺。

步驟 1 為什麼要使用 64 個位元組來計算 rolling sum? bup
文件給了很率性的答案： 沒有理由，只是覺得剛好適合。

步驟 2 將步驟 1 得到的 checksum, 檢查最低 13 位的位元是不是都是
1，為什麼是 13 的位元？
這裡的原因是：這樣做的話，機率上大概每個區塊大小會接近 8K。
由於計算 rolling checksum 所使用的 64 個位元組不能預測，可以視同亂數。
從這個觀點，所計算的 checksum 最低的 13 的位元要同時為 1 的機率是
1/(2^13)，也就 1/8192。 所以，概率上，平均每 8KB 會產出一個區塊。
另外，2K 的限制是不希望出現過小的區塊。

步驟 3 只是為了避免單一區塊大小出現暴走所做的人為限制。

運用這樣簡單的步驟所產生的區塊切割點，不會因為檔案小部分的修改就造成大部分區塊的改變，為什麼？
下面按照幾個不同的情形說明：

  1. 改變的資料在於兩個切割點之間，但沒有覆蓋到切割點使用的位元組資料。雖然改變了一個區塊內容，但不影響切割點 [3]
    。
  2. 改變的資料覆蓋了某個切割點所使用的 64
    的位元組，則這個切割點前後的兩個區塊會受到影響。
  3. 在檔案新增小部分的資料，則此資料之後的所有區塊切割點都會改變，但內容不變。

從第 3 點可以看出來，Hashsplitting
仍然會因為小部分的資料插入而影響到切割點。
但跟固定切割點不同的是：相對於區塊資料來說，區塊切割點的資訊小很多。所以，即使許多區塊位移有所更動，
但區塊內容不變的結果，需要傳輸的資料量就小很多。

Hashsplitting
最簡潔的地方在於：計算區塊切割點完全不需要目標檔案的額外資訊。 這點跟
Rsync 需要使用目標檔案的弱檢查碼來輔助找出相同區塊有很大的不同。

bup 設計文件
針對大檔案也有提供額外處理方法，有興趣的讀者請自行參考。
不想看程式碼的讀者，可以直接看 結語 。

程式範例

bup 中跟 Hashsplitting 最相關的程式檔案：`bupsplit.h’ 以及
bupsplit.c， 網址在
https://github.com/bup/bup/tree/master/lib/bup 。 bup
專案是 LGPL 授權，但這兩個檔案除外，採用 BSD 授權。

雖然 bup 有提供 Python 的綁定，但使用 C 擴充介面且有點難懂使用方式，
下面是山姆鍋另外使用 Cython 做的包裝：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from libc.stdlib cimport malloc, free
from cpython.buffer cimport PyBUF_SIMPLE
from cpython.buffer cimport Py_buffer
from cpython.buffer cimport PyObject_CheckBuffer
from cpython.buffer cimport PyObject_GetBuffer
from cpython.buffer cimport PyBuffer_Release


def find_separator(object buf):
    """ Searches the offset where a separator pattern found.
    :param buf: the buffer to search.
    :return: the offset value; or 0 if not found.
    """
    cdef Py_buffer gotdata
    cdef unsigned char* data

    if not PyObject_CheckBuffer(buf):
        raise TypeError(b'Buffer object expected.')

    try:
        PyObject_GetBuffer(buf, &gotdata, PyBUF_SIMPLE)
        data = <unsigned char*> gotdata.buf
        return bupsplit_find_ofs(data, gotdata.len)
    finally:
        PyBuffer_Release(&gotdata)

find_separator 接受一個 bytes
參數，然後回傳第一個切割點的位移值，假如沒找到的話則回傳 0。

下面的程式片段則提供高階一點的包裝，使用 find_separator
做整個檔案的切割 ( Buf 類別來自 bup 專案，所以請注意這個程式片段是 LGPL
授權)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# Note this file is released with LGPL 2.0.
CHUNK_BITS = 13
CHUNK_SIZE = 1 << CHUNK_BITS  # = 8192
CHUNK_MIN = CHUNK_SIZE // 4   # = 2048
CHUNK_MAX = CHUNK_SIZE * 4    # = 32768


class Buf(object):
    def __init__(self):
        self.data = bytearray()
        self.start = 0

    def put(self, s):
        if s:
            self.data = buffer(self.data, self.start) + s
            self.start = 0

    def peek(self, count):
        return buffer(self.data, self.start, count)

    def eat(self, count):
        self.start += count

    def get(self, count):
        v = buffer(self.data, self.start, count)
        self.start += count
        return v

    def used(self):
        return len(self.data) - self.start


class RollSumSplitter(object):
    def __init__(self):
        self.offset = 0
        self.buf = Buf()

    def feed(self, data):
        """
        :param data: the input data. must be greater than 64 in bytes.
        :return:
        """
        self.buf.put(data)
        chunks = []
        while True:
            b = self.buf.peek(self.buf.used())
            off = find_separator(b)
            if off:
                if off > CHUNK_MAX:
                    off = CHUNK_MAX
                self.buf.eat(off)
                chunks.append(buffer(b, 0, off))
            elif self.buf.used() > CHUNK_MAX:
                chunks.append(self.buf.get(CHUNK_MAX))
            else:
                break

        return chunks

    def final(self):
        return self.buf.get(self.buf.used())

使用方式大致是將檔案資料持續喂給 (feed) RollSumSplitter
物件，並取得產出的區塊，最後呼叫 final
取得剩餘的資料作為最後的區塊。山姆鍋這裡就不提供如何讀取檔案然後執行上述步驟的範例。

結語

檔案同步自然不是山姆鍋描述的那樣簡單，好像只需要知道分割檔案即可。事實上，就算只做檔案切割，
當把檔案數量跟檔案大小這樣的因素考量進來後，問題就變得複雜得多。
就檔案切割演算法來說，不知道您同不同意，但山姆鍋覺得 Hashsplitting 比
Rsync 的方法更簡潔。

參考資料

_`bup`: https://bup.github.io/

_`bup 設計文件`:
https://raw.githubusercontent.com/bup/bup/master/DESIGN

同樣區塊切割點，但內容不同的區塊，跟 Rsync 一樣是透過強檢查碼 (如
MD5) 偵測出來。

  1. http://ijecorp.blogspot.tw/2014/02/rsync-algorithm.html ↩︎

  2. http://www.coctec.com/docs/linux/show-post-68616.html ↩︎

  3. ↩︎