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

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

問題描述

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

解決方案

聽過 Rsync 這個 Linux 檔案同步工具的讀者, 應該知道它能有效率的處理檔案同步的問題。對於 Rsync 的演算法有興趣的讀者,可以參考 < sup class="footnote-ref">[1] 跟 < sup class="footnote-ref">[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. 改變的資料在於兩個切割點之間,但沒有覆蓋到切割點使用的位元組資料。雖然改變了一個區塊內容,但不影響切割點 < sup class="footnote-ref">[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 做的包裝:

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