布隆过滤器（Bloom Filter）：如何在海量数据中轻松找到你要的答案？

一、背景

无论是红黑树、平衡二叉树、散列表，结点都是存储的key-value对。而有些场景，内存是有限的，仅需要了解key是否存在，不想知道具体内容（value）。

这时就需要布隆过滤器。布隆过滤器是一种概率型数据结构，它的特点是高效的插入和查询，能确定某个字符串一定存在或者可能存在。

布隆过滤器不存储具体数据，所以占用空间小，查询结果存在误差，但误差可控，同时不支持删除操作。

（1）一个巨大的数据文件，需要知道是否存在某个key，如果把整个文件读取进行查找，这个效率就比较低。那么可以添加一个布隆过滤器，插入数据时对key做标识，查询key是否存在时直接查询布隆过滤器。

（2）一个数据库查询，想要查询数据库中是否存在key，可以添加一个布隆过滤器，查询key时直接查询布隆过滤器，不需要IO操作，大大提升查询效率。

二、布隆过滤器的构成

布隆过滤器的原理本质上和散列表是一样的。但布隆过滤器为了节约内存，不是使用的数组，而是使用的位图。

（1）位图。

bit的数组，实现方式有多种。

// 例如
vector<char> bitmap;
uint64_t bitmap;

（2）n个hash函数。

举例： 使用byte buf[8]构建64bit的位图，那么n=i*8+j；假设hash(key)=173，n=173%64=173&63=45，j=n%8=45%8=5，i=n/8=45/8=5。因此将（5，5）位置置 1。

三、原理

当一个元素加入位图时，通过k个hash函数将元素映射到位图的k个点，并把它们置1；当检索时，再通过k个hash函数运算检查位图的k个点是否都为1；如果有不为1的点，那么认为该key不存在；如果全部为1，则可能存在。

布隆过滤器是不支持删除操作的，原因在于：在位图中每个槽位只有两种状态（0或者1），一个槽位被置为1，但不确定它被设置了多少次；也不知道被多少个key hash映射而来；以及具体被哪个hash函数映射而来。

值得注意的是，只要有一个槽位为0，则key一定不存在；如果key映射的所有槽位都为1，不能说明一定存在，只能说明可能存在（假阳率）。

图片

四、应用场景

布隆过滤器通常用于判断某个key一定不存在的情况。同时允许判断存在时有误差的情况。

常见处理场景：

（1）缓存穿透的解决。

（2）热key限流。

缓存场景：为了减轻数据库（MySQL）的访问压力，在数据库（MySQL）和服务端（server）直接加入缓存用来存储热点数据。

缓存穿透：服务端（server）请求数据时，缓存和数据库都不包含数据，最终请求压力全部涌向数据库。

数据请求步骤：

先访问redis，如果存在则直接返回，如果不存在则走2访问数据库；

访问数据库，如果不存在直接返回，如果存在则将MySQL存在的key写回redis。

发生原因：黑客利用漏洞伪造数据攻击或内部业务bug造成大量重复请求不存在的数据。

解决方案：

（1）在redis设置<key，null>键值对，依次避免访问数据库；缺点是<key，null>过多会占用过多内存，可以给key设置过期expire key 600ms，停止攻击后最终由redis自动清除无用的key。

（2）在服务端（server）存储一个布隆过滤器，将MySQL存在的key放入布隆过滤器中，布隆过滤器可以过滤一定不存在的数据。

五、应用分析

在实际应用中，该选择多少个 hash 函数？要分配多少空间的位图？预期存储多少元素？如何控制误差？

可以使用如下公式计算：

n = ceil(m / (-k / log(1 - exp(log(p) / k))))

p = pow(1 - exp(-k / (m / n)), k)

m = ceil((n * log(p)) / log(1 / pow(2, log(2))));

k = round((m / n) * log(2));

其中

n -- 预期布隆过滤器中元素的个数，如上图 只有str1和str2 两元素 那么 n=2

p -- 假阳率，在0-1之间 0.000000

m -- 位图所占空间

k -- hash函数的个数

数学公式：

图片

5.1、变量关系

假设：

n = 6000

p = 0.000000001

m = 258797 (31.59KiB)

k = 30

得到如下关系图：

图片

（1）假阳率p会随着插入元素的增多而逐渐变高。

（2）假阳率p会随着位图所占空间的增大而减小。

（3）假阳率p会随着hash函数个数增多，呈现快速减小后缓慢增长的趋势。hash函数个数在31时假阳率最低。

5.2、确定n和p

在实际使用布隆过滤器时，首先需要确定 n 和 p，通过上面的运算得出 m 和 k；推荐一个布隆过滤器计算器可以选出合适的值。

5.3、选择hash函数

选择一个 hash 函数，通过给 hash 传递不同的种子偏移值，采用**线性探寻**的方式构造多个 hash 函数；

#define MIX_UINT64(v) ((uint32_t)((v>>32)^(v)))

uint64_t hash1 = MurmurHash2_x64(key, len, Seed);
uint64_t hash2 = MurmurHash2_x64(key, len,MIX_UINT64(hash1));
for (i = 0; i < k; i++) // k 是hash函数的个数
{
     Pos[i] = (hash1 + i*hash2) % m; // m 是位图的⼤⼩
}

六、总结

1. 布隆过滤器由位图和n个hash函数构成。布隆过滤器的操作是一个key经过多个hash函数，然后对位图大小进行取余等到多个槽位并对应置为1。判断时只要有一个槽位为0就一定不存在该key。
2. 布隆过滤器能确定一个key一定不存在，不能判断key一定存在，但可控假阳率确定存在。
3. 布隆过滤器不支持删除操作，可以通过两个布隆过滤器解决（依然存在假阳率，但会低一些），添加放在第一个布隆过滤器，删除放在第二个布隆过滤器。即要判断key是否存在，首先检查第二个布隆过滤器是否删除过，如果删除过就往第一个布隆过滤器插入。
4. 布隆过滤器根据n和p算出m和k，hash函数个数是利用开放寻址法来计算的。