腾讯 | 布隆过滤器原理与应用

导语 | 开通微信时，系统如何判断你输入的手机号没被注册？如何使用更少的存储空间、更快的速度解决这个问题？对于这个问题，腾讯微信支付数据开发工程师杭天梦带来了她利用 Bloom 过滤器解决此类问题的思考，向大家分享。本文分享的主要内容为 Bloom 过滤器的简介、原理、应用和结论等。

“开通微信时，系统如何判断你输入的手机号没被注册？如何使用更少的存储空间、更快的速度解决这个问题？”

对于这个问题，最暴力的方法为：
通过遍历来判断是否被注册。那么时间复杂度为 O(n)，空间复杂度也是 O(n)。

稍微学过算法的同学会说：
使用 HashMap，时间复杂度瞬间降到 O(1)。

精通算法的同学可能会说：
使用 Bitmap，因为 Bitmap 只需要存储数据的状态信息（0 和 1），这样空间复杂度为 O(max_value)。

下面问题又来了：

如果 n=10 亿，将会占据多少内存？

假设整数为 64bit=8Byte，

Hashmap：10 亿整数需要 8G 的内存

Bitmap:

虽然速度提上去了，内存占有量无法想象的…大！

那如何既保证查询效率，又保证低内存占用？

下面我们的主角闪亮登场——布隆过滤器。

一、Bloom 过滤器的简介

Bloom 过滤器（Bloom Filter）是由布隆（Burton Howard Bloom）在 1970 年提出的。

它实际上是由一个很长的二进制向量和一系列随机映射函数组成。

它的目标是——占用更小的空间的前提下，检索一个元素是否在一个集合中。

二、原理介绍

下面我从三个方面来介绍布隆过滤器：构造、检索、效果。

1.构造

构造主要包括以下三个步骤：

选择 k 个哈希函数
将待检索字符串分别做 Hash 映射
每个映射的值对应的 bit 数组置为“1”

我举一个简单的例子：
假设我们有 3 个哈希函数，有两个待检索字符串"jimboooo"和"luckyyyyy"。

对于字符串"jimboooo"，经过三个哈希函数映射后，将 1,4,8 的位置置为“1”。

同理，对于字符串“luckyyyyy"，我们经过哈希函数映射后，将位置 2,4,7 置为“1”。

那么，我们的布隆过滤器已经构造完毕了。

2.检索

将待检索的字符串通过 k 个哈希函数映射；
查看映射的整数对应的位置是否 1，如果都为 1，说明待检索字符串是存在的。

下图是我们构造过程得到的数组，如果要检索"jimbooo"，哈希映射后是 2,4,7，这三个位置都为 1，说明此字符串是存在的。如果要检索"fukuoka"，映射后是 1,3,4，因为 3 的位置为 0，很明显它是不存在的。

3.效果

布隆过滤器的原理已介绍完毕，看起来十分简单。那可能会出现什么问题呢？

如果要检索的字符串（原本不存在）映射后数组每个位置恰好都为 1，那就出现了误判！

我们来通过公式了解下它的误判率、布隆过滤器长度以及哈希函数个数之间的关系吧。

先上公式（推理见附录）：
k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数（待检索元素总数），p 为误报率，
当且仅当：

误报率 p 取得最优解：

本文地址：腾讯 | 布隆过滤器原理与应用
本文版权归作者和AIQ共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出

根据公式就可以得到布隆过滤器的长度、误识率、待插入元素个数（待检索元素总数）的关系了。

如下图所示，x 轴为 m/n，含义为每个元素占有的 bit 数，y 轴为误识率。

得出的结论是，对于一个拥有最优 k 值且误判率在 1% 的布隆过滤器，每个元素只需要 9.6bits（与元素的大小无关）。若给每个元素增加 4.8bits 左右，误判率将会减少十倍。

三、应用

可应用于很多方面：

1.网页爬虫对 URL 的去重

避免爬取相同的 URL 地址。

2.缓存击穿

将已存在的缓存放到布隆中，当黑客访问不存在的缓存时迅速返回避免缓存及 DB 挂掉。

3.HTTP 缓存服务器

当本地局域网中的 PC 发起一条 HTTP 请求时，缓存服务器会先查看一下这个 URL 是否已经存在于缓存之中，如果存在的话就没有必要去原始的服务器拉取数据了(为了简单起见，我们假设数据没有发生变化)，这样既能节省流量，还能加快访问速度，以提高用户体验。

4.黑/白名单

类似反垃圾邮件。

四、结论

布隆过滤器用于判断一个元素是否在一个集合中，不会有假负例（将在集合中的元素误判不在集合中），但会有一定的误识率（将不在集合中的元素误判为在集合中）。

方案对比结论：

五、附录

1.公式推导

（1）k 次哈希函数某一 bit(长度为 m）未被置为 1 的概率为：

（2）插入 n 个元素后依旧为 0 的概率和为 1 的概率分别是：

（3）k 个位置均被设为 1 的概率：

2.如何让误识率降到最低？

3.哈希函数怎么设计？

要点：

Independent 相互独立
Uniformly distributed.离散型均匀分布（概率相同）
They should also be as fast as possible. 要快

案例分享：

Chromium uses HashMix
python-bloomfilter uses cryptographic hashes（cryptographic hashes）
Plan9 uses a simple hash as proposed in Mitzenmacher 2005
Sdroege Bloom filter uses fnv1a (included just because I wanted to show one that uses fnv.)Squid uses MD5

4.参考文章

（1）布隆过滤器应用：

https://www.pdai.tech/md/algorithm/alg-domain-bigdata-bloom-filter.html

（2）Hash 函数设计：

https://llimllib.github.io/bloomfilter-tutorial/

（3）函数推导参考：

https://blog.csdn.net/quiet_girl/article/details/88523974