# 海量数据去重

起因
--

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

然而
--

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

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