千亿文本单机bloom去重实战

前言

消除重复数据是我们在实际业务中经常遇到的一类问题。在大数据领域，重复数据的删除有助于减少存储所需要的存储容量、避免重复的任务。例如，对爬虫库的海量url进行去重，对rapid7的dns数据集进行去重等。

需求分析

首先可以确定的是，数据是不断增加的，这是一个增量时去重的问题，接下来估算一下数据量，一期fdns数据集的数量在19亿条左右，所有dns数据集汇总可达千亿，爬虫url也可达这个数量级。

其次是设备限制，使用一台32gb内存、8t ssd、搭载wsl子系统的windows10服务器，最好用python。

去重方案调研

从实际需求出发，从读写速度、内存硬盘等硬件占用、是否支持内存映射文件、是否可扩展、是否可复用、os系统、错误率等指标进行调研。

读写速度：

文本加入过滤器的单/多进程速度、和判断文本是否在过滤器中的单/多进程速度。

内存映射文件(mmap)：

是否支持将内存映射到硬盘上，突破内存大小方面的限制，用读写速度和硬盘换内存。

可扩展(Scalable):

首次指定过滤器数据量大小之后保存，后续复用过滤器受到硬件限制时，更换硬件后过滤器是否可以自动扩展大小。

复用：

数据是不断增加的，去重容器必须是可以快速复用的，避免重复工作。

错误率：

硬件限制下降低对去重精准度的要求，换读写速度等其他方面的性能。

我们目前常用的去重方法有：

基于 BitMap

Bit-Map 的基本思想是用一个 bit 位来标记某个元素对应的 Value，而 Key 即是该元素。由于采用了 Bit 为单位来存储数据，因此可以大大节省存储空间。

如果每个数字用 int 存储，那就是 20 亿个 int，因而占用的空间约为 (2000000000*4/1024/1024/1024)≈7.45G

适用于亿级数字精准去重，不适用url、dns等数据。

基于布隆过滤器（BloomFilter）

BloomFilter（布隆过滤器）实际的数据结构就是一个大型的位数组和几个无偏hash函数，文本数据经过hash缩小体积后存入过滤器，其典型的应用场景就是能够快速判断一个 key 是否存在于某容器，不存在就直接返回。适用于url、dns等数据。

误判率是由于hash碰撞导致的。随着存入的元素数量增加，误判率随之增加。

它的优点是空间效率和查询时间都远远超过一般的算法，布隆过滤器存储空间和插入 / 查询时间都是常数O(k)。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

github上找下开源的python BloomFilter模块:

pybloom_live

https://pypi.org/project/pybloom-live/

pybloomfilter

https://github.com/prashnts/pybloomfiltermmap3

mmap-bloom-filter

https://github.com/dream2333/mmap-bloom-filter

方案评估与选择

在设置数据量为100w/1kw、错误率百万分之一、单进程/10进程这些变量后，3个模块的指标表现如下表：

pybloom_live 基于内存读写速度最快，写1kw数据/10进程需26.12s，可复用，100亿数据仅占17g内存，1000亿数据占170g内存，超过了32g硬件限制。

pybloomfilter 复用时丢key，不考虑。

mmap-bloom-filter 基于内存映射硬盘读写，写1kw数据/10进程需106.93s，可复用，100亿数据仅占33g硬盘，1000亿数据仅占330g硬盘。

结论

在32gb内存、8t ssd硬件限制下，

当去重后数据量级在100亿以内时，使用pybloom_live模块，首次去重100亿数据需7.26小时。

26.12s * (100e/1kw) /3600 = 7.26h

当去重后数据量级超过100亿时，使用mmap-bloom-filter模块，首次去重1000亿数据需12.38天。

106.93s * (1ke/1kw) /3600 /24 = 12.38d

为降低hash碰撞率，去重后数据量级达到20亿就该换mmap-bloom-filter模块了。

公众号后台消息基本不看，有事滴滴

原文始发于微信公众号（流浪猫收容所）：千亿文本单机bloom去重实战