海量数据去重

2021-04-21

起因

有个哥们,有 5000G 数据需要去重。

这么大数据其实挺不好处理的,尤其是超不注意就内存/磁盘炸裂。

所以,如何做到性能、内存、磁盘之间的平衡,就是这个问题的难题……

其实这个问题让我想起「编程珠玑」中的一篇内容……

方案

刚开始大家觉得使用使用 redis 的 hash 能力来处理,set/hash 都可以,但是不管是直接丢字符串,还是将字符串 hash 计算后存储,其实都会比较耗费内存。并且 hash 后的数据还会存在一定概率 hash 碰撞,此时更不好处理了。

于是在我们小群里面进行了一些讨论……

于是大家纷纷出招:

  • 磁盘换内存式的 kv 数据库(例如 leveldb、boltdb)
  • redis 布隆过滤器(布隆过滤器内部也是用的 bitmap,关键)
  • redis bitmap
  • mapReduce

其实都会有一些优缺点吧。

  • 磁盘式 kv db 性能不太行,同时读写磁盘可能会炸裂
  • redis 布隆过滤器的话 存在误差,毕竟 「存在的不一定存在,不存在的一定不存在……」
  • redis bitmap 如上,存在一定误差,毕竟还是会有撞库的可能
  • mapReduce 好像有大炮打蚊子的感觉……

ok,最终因为忙工作,也没细想这个问题了,反正也是嘴炮一番,这事就过了。

几天之后……

过了几天看到哥们发了几篇布隆过滤器的文章,然后怎么还在研究这事。

此时刚好在上班的路上,又重新想了想这个方案。

因为之前公司的产品中有同事提出使用布隆过滤器的「存在则可能存在」的特性做一个减少检索范围的筛选器。

所以恰好好像可以反过来想想,此时方案流程可以是这样:

  1. 利用布隆过滤器「不存在则一定不存在」的特性
  2. 例如
    1. 传入「张三」
      1. 不存在
        1. 并标记到「存储器」中(如果为了省内存,其实也可以使用安全 hash 算法进行计算后存入)
      2. 存在
        1. 从「存储器」中拿到撞库的字符串列表
          1. 进行暴力匹配
          2. 并将「张三」存入布隆过滤器,也就是上面撞库的字符串列表中
  3. 重复上面的步骤。

上面说的「存储器」是什么呢?

  • 可以是磁盘 kvdb
  • 可以是 redis 内存 set/hash
    • 如果重复字符串是低概率的事情才可以这么做,否内存炸裂

在「进行暴力匹配」这步骤中的问题

如果重复是大概率的事情,那么暴力匹配的耗时会非常多,变成一个 (O)n 的搜索,性能急剧下降。

此时有点像普通的二叉树,搜索匹配可能变成一个「链表」。

针对这种问题,可以做一些改进:

  1. 直接存入磁盘 kvdb
  2. 将字符串通过 安全 hash 算法计算成数字存入 redis bitmap/hash
    1. 对字符串进行 hash 的目的是降低内存占用

然而

然而哥们直接用了布隆过滤器的「不存在一定不存在」的特性直接「粗」过滤了。

所以……还是水一篇博客吧。