of drdr.xp Blog drdrxp @weibo.com

存储中的文件合并策略优化

问题

系统中的所有数据以block 存放: 每个block里:

  • n=1000万个文件, 已经排序好,
  • 每个文件名长度平均l=512 Byte.

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

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_amin_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_abucket_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对.

假设:

  • 每个block的文件数 n = 1000万
  • 单个文件名长度: l = 512 字节
  • hash-bitmap 大小 64 * 10^6 = 8MB
  • min-hash bucket数量 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)

参考:

Archive