布隆过滤器介绍

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。
所以布隆过滤器有错判的可能，称为错误率

utils

布隆过滤器作为一个工具，已经收录进collie包中，路径：collie_common/utils/bloom_filter.py

bloom_filter.PyBloomFilter类

init(capacity=10000000, error_rate=0.000001, redis_conf=None, key="", overwrite=False)

• capacity: 预先估计去重后的数量
• error_rate: 期望的错误率
• redis_conf: dict，redis链接参数，默认为None，即默认通过内存存放过滤器
• key: str, 通过redis存放过滤器时键的名字
• overwrite: 布尔, 通过redis存放过滤器时，是否要删除已经放入过滤器的数据

add(value)

将value加入过滤器中

• value: str

is_exist(value)

判断value是否在过滤器中

• value: str
• return: 布尔值

del_key()

删除redis中的布隆过滤器

属性

• m: 布隆过滤器的总位数（长度）
• k: 需要hash的次数
• p: 实际错误率
• mem: 需要使用的内存（M）

BloomFilter(BaseDocFilter)

init(self, name, value_field, redis_conf=None, redis_key=None, capacity=10000000, error_rate=0.0000001, overwrite=False)

• name: data_pump的filter的名字
• value_field: data中需要过滤的字段，如：“company_name_digest”,即根据数据中的comapny_name_digest字段去重
• redis_conf: redis链接参数,默认None, 为None时，通过内存存放过滤器，此时不支持多进程
• redis_key: 通过redis存放过滤器时键的名字
• capacity: 预先估计去重后的数量
• error_rate: 期望的错误率
• overwrite: 布尔, 通过redis存放过滤器时，是否要删除已经放入过滤器的数据

使用帮助

• 去重后的数量（capacity）与错误率（error_rate）关系到需要hash的次数以及需要使用多少内存，使用前可以先查看相关指标，即PyBloomFilter.mem, PyBloomFilter.k等
• 如果是一次性任务，且通过redis存放布隆过滤器，在任务结束后记得删除redis中的过滤器释放内存（del_key方法）
• 如果是单进程任务，所需的内存可接受，可不设置redis_conf，即通过本地内存过滤，这样速度更快