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

栏目: 编程工具 · 发布时间: 6年前

内容简介:系统中的所有数据以block 存放: 每个block里:2个block中可能包含大量的重复文件, 这时我们需要找出这2个block, 将其合并, 以节省空间.问题: 如何高效的(在时间上和空间上) 找出具有大量重复文件的block对.

问题

系统中的所有数据以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

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

假设:

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)

参考:


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

未来版图

未来版图

麻省理工科技评论 / 人民邮电出版社 / 2018-5-1 / CNY 69.80

《麻省理工科技评论》作为世界上历史悠久、影响力极大的技术商业类杂志,每年都会依据公司的科技领军能力和商业敏感度这两个必要条件,从全球范围内选取50家未来可能会成为行业主导的聪明公司。 这些聪明公司,并非都是行业巨头,甚至专利数量、公司所在地以及资金规模都不在考察范围内。 这些公司是“高精尖科技创新”与“能够保证公司利益* 大化的商业模式”的完 美融合。无论公办私营,无关规模大小,这些遍布全球......一起来看看 《未来版图》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具