前言

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

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

問題描述

假設有兩個檔案 , A 跟 B, 不管這兩個檔案是不是代表同一個文件的不同版本 , 問題是我們需要一個比將檔案 A 拷貝 (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/bupbup 專案是 LGPL 授權 , 但這兩個檔案除外 , 採用 BSD 授權 。

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

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 授權 ):

# 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


[1]http://ijecorp.blogspot.tw/2014/02/rsync-algorithm.html
[2]http://www.coctec.com/docs/linux/show-post-68616.html
[3] 同樣區塊切割點 , 但內容不同的區塊 , 跟 Rsync 一樣是透過強檢查碼 ( 如 MD5) 偵測出來 。