一個有創意的檔案切割演算法

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

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

問題描述

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

解決方案

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

Rsync 與 Hashsplitting 的相同點：

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

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

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

首先，來看看 Hashsplitting 的步驟：

從檔案開頭，每連續 64 個位元組(byte)計算一個 32-bit rolling checksum。
如果 checksum 的最低 13 位元(bit)都是 1，且與上個切割點距離超過 2K 的話，則最後一個位元組的位移(offset)是一個分割點。
如果與上一個分割點過大，如超過 32KB，則強制最後一個位元組的位移作為一個分割點。
重複步驟 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 只是為了避免單一區塊大小出現暴走所做的人為限制。

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

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

從第 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 做的包裝：

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 ⎘

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

一個有創意的檔案切割演算法

問題描述

解決方案

程式範例

結語

參考資料

郭信義 (Sam Kuo)

如何實作簡單的持久性訊息佇列?

簡單的插件框架 - 使用 pkg_resources

想要學習 MCollective? 試試 vagrant-mcollective

用 Python 實作混合式邏輯時鐘

一個有創意的檔案切割演算法

問題描述

解決方案

程式範例

結語

參考資料

Footnotes

郭信義 (Sam Kuo)

如何實作簡單的持久性訊息佇列?

簡單的插件框架 - 使用 pkg_resources

想要學習 MCollective? 試試 vagrant-mcollective

用 Python 實作混合式邏輯時鐘