儲存中的檔案合併策略優化
問題
系統中的所有資料以block 存放: 每個block裡:
n l
2個block中可能包含大量的重複檔案, 這時我們需要找出這2個block, 將其合併, 以節省空間.
問題: 如何高效的(在時間上和空間上) 找出具有大量重複檔案的block對.
問題包含2個部分:
- 建立資料結構儲存在block中, 作為簽名
- 在需要時對比2個block的簽名以得出相似度
常規方法
1. 檔案列表
因為block內的檔名是排序的, 可以直接對比2個block各自的檔案列表, 走一遍歸併, 這樣,
建立簽名的開銷:
-
時間和空間開銷:
O(n x l)
, 每個block需要儲存: 5G 資料: 1000萬 x 512
計算相似度的開銷:
-
總的時間複雜度是
O(n x l)
, 需要讀取5G x 2的資料
這種方法可以非常準確的得出重複檔案數量. 但空間開銷和時間開銷都比較大.
2. hash-bitmap
另外一個直接的, 近似的方案是使用hash-bitmap:
建立簽名:
對每個block, 將所有檔名做1次hash,
例如:int(sha1(fn)) % b
,
這裡b 是bitmap的大小, 如果取b=64 * 10^6, 這個hash 表是比較稀疏的(n/b=0.16),
衝突率也就比較低, 大約有7%的衝突率, 參考:hash-collision
計算相似度:
然後再對比2個block的時候, 可以通過將2個bitmap取AND
操作,
找到存在於2個block中的bit有幾個, 來確定重複的檔案數.
這種方法是粗略的估計:
-
其一是hash時, 在同一個block中, 2個fn的hash可能落到1個bit上, 導致不準確.
-
其二是2個block中把不同的fn也可能hash到1個bit上, 導致估算時增加重複檔案的統計.
建立簽名的開銷:
-
空間複雜度:
O(n)
, 實際儲存空間開銷是 8MB, 因為不同的block的bitmap大小必須一致, 所以要取最大可能的大小. -
時間複雜度是
O(n x l)
計算相似度的開銷:
-
時間複雜度是
O(n/64)
, 因為目標機器是64位的, 位AND操作一次可以對比64個bit(1個int64_t
)
但這2個方案都不是最好的, 雖然hash-bitmap的方案空間開銷已經很小了.
接下來我們看看這個思路: min-hash
方案: min-hash
ofollow,noindex" target="_blank">min-hash 實現了使用常量的空間開銷對2個集合進行相似度的比較.
原理
-
A, B 是2個集合, 我們定義一個相似度的函式: Jaccard-similarity:
J(A, B) = len(A ∩ B) / len(A ∪ B)
-
假設有1個hash函式, 它不會對不同的輸入得出相同的hash值, 即: 如果
x != y
, 那麼hash(x) != hash(y)
, 這裡我們在測試演示的時候就選擇用sha1
了, 而且將sha1的輸出結果按照16進位制40位整數處理. -
最小hash值: 一個集合S中所有元素的hash值最小的那個(hash值, 不是原始元素), 對我們的場景來說:
min_a = min([ sha1(x) for x in A ]) min_b = min([ sha1(x) for x in B ])
顯然如果A和B的元素一樣, 那麼min_a == min_b
;
如果A和B的元素有很多重複, 那麼min_a
和min_b
有很大概率相同;
更精確的, 對A, B兩個集合,min_a == min_b 的概率是 J = len(A ∩ B) / len(A ∪ B)
解釋下上面的結論的推導過程
-
對有n個元素的集合S, 假設S集合未知, 也就是說它裡面的元素都是隨機的, 那麼, 對其中所有元素做一次hash後, 其中的一個元素e, 成為最小hash的概率是
1/n
, 也就是:P(sha1(e) == min([ sha1(x) for x in S ])) = 1/n
因為假設hash函式均勻, 每個元素成為最小元素的機率都是相等的.
-
對於要對比的2個集合A和B, 元素共有:
A ∪ B
, 取min_ab = min([ hash(x) for x in (A ∪ B) ])
,A ∪ B
中每個元素成為min_ab
的機率是1 / len(A ∪ B)
因此
A ∩ B
裡的一個元素e 成為min_ab
的機率是len(A ∩ B) / len(A ∪ B)
. -
而
A ∩ B
裡的一個元素e 成為min_ab
, 是min_a == min_b
的充要條件.所以有 P(min_a == min_b) = J = len(A ∩ B) / len(A ∪ B)
所以我們的問題就轉化成:求出P, 我們就知道的2個block中重複檔案的比例J
使用 min-hash 求相似度的步驟也是2個:
生成簽名:
-
確定一個hash函式, 測試中就用
sha1
了. -
分別為A 和 B準備
b
個bucket:bucket_a
和bucket_b
. -
對A中所有元素計算sha1, 按照
sha1(a) % b
拆分A中的元素到b個bucket中:bucket_a[sha1(a) % b].append(sha1(a))
對B也做同樣的操作.
-
記錄A, B中每個bucket中的最小hash值:
for i in range(0, b): bucket_a[i] = min(bucket_a[i]) bucket_b[i] = min(bucket_b[i])
將元素分散到b個bucket中, 是為了通過概率的均值來估算概率P.
這裡也暗含了一個假設: bucket_a[i] 中的元素與bucket_b[i]的元素相似度與len(A ∩ B) / len(A ∪ B)
相近
因為假設認為sha1 非常隨機地分散了A或B中的元素, 子集相似度接近全集相似度.
計算相似度:
對比2個block, 統計min_a == min_b
的個數:
eq = 0.0 for i in range(0, b): if bucket_a[i] == bucket_b[i]: eq += 1 P = eq / b
因為P == J, 所以我們就得到了2個block的相似度.
min-hash 實現
實現時, 要求對比的2個block的使用的bucket數量b
相同.
-
空間複雜度
O(b)
:1KB = sizeof(int64) * b
b=128
-
時間複雜度:
O(b)
: 128次int 比較
通過min-hash 計算相似度 和 對比真實統計相似度的python程式碼:min-hash.py
通過這個程式模擬的結果如下:
模擬驗證
NO. bucket: 128
Hash length: int64
總數 | a總數 | b總數 | 實際重複率(A∩B)/(A∪B)% | 估算重複% | 誤差% |
---|---|---|---|---|---|
1000 | 360 | 840 | 20.00% | 21.88% | 1.87% |
1000 | 520 | 880 | 40.00% | 38.28% | -1.72% |
1000 | 680 | 920 | 60.00% | 60.94% | 0.94% |
1000 | 839 | 959 | 80.16% | 78.91% | -1.25% |
1000 | 1000 | 1000 | 100.00% | 100.00% | 0.00% |
10000 | 3600 | 8400 | 20.00% | 15.62% | -4.38% |
10000 | 5200 | 8800 | 40.00% | 35.16% | -4.84% |
10000 | 6800 | 9200 | 60.00% | 60.94% | 0.94% |
10000 | 8399 | 9599 | 80.02% | 85.16% | 5.14% |
10000 | 10000 | 10000 | 100.00% | 100.00% | 0.00% |
100000 | 36000 | 84000 | 20.00% | 21.88% | 1.87% |
100000 | 52000 | 88000 | 40.00% | 47.66% | 7.66% |
100000 | 68000 | 92000 | 60.00% | 62.50% | 2.50% |
100000 | 83999 | 95999 | 80.00% | 80.47% | 0.47% |
100000 | 100000 | 100000 | 100.00% | 100.00% | 0.00% |
1000000 | 360000 | 840000 | 20.00% | 19.53% | -0.47% |
1000000 | 520000 | 880000 | 40.00% | 40.62% | 0.62% |
1000000 | 680000 | 920000 | 60.00% | 58.59% | -1.41% |
1000000 | 839999 | 959999 | 80.00% | 75.78% | -4.22% |
1000000 | 1000000 | 1000000 | 100.00% | 100.00% | 0.00% |
結論
系統中的所有資料以block 存放, 2個block中可能包含大量的重複檔案, 這時我們需要找出這2個block, 將其合併,
問題: 如何高效的(在時間上和空間上) 找出具有大量重複檔案的block對.
假設:
n = 1000萬 l = 512 位元組 64 * 10^6 = 8MB b = 128
各種演算法的開銷如下
演算法\開銷 | 空間開銷 | 實際空間 | 時間開銷 |
---|---|---|---|
fn-list | O(n x l) | 5GB | O(n x l) |
hash-bitmap | O(n) | 8MB | O(n) |
min-hash | O(1) | 1KB | O(1) |