海量数据去重

起因

有个哥们，有 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 的目的是降低内存占用

然而

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

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