BloomFilter(布隆过滤器)学习笔记

看到一个集合查找的面试题，想起这个算法。

前言

一个面试题

现在有一个非常庞大的数据，假设全是 int 类型。现在我给你一个数，你需要告诉我它是否存在其中(尽量高效)。

如果int是32位或以下，这个题目只需要使用BitMap即可。

分析

1. 我们可以将数据存放到BitMap中，共需要空间(2^64)=0.5G，目前的计算机可以存放。
2. 计算效率是O(1)可满足性能。

以上办法可以解决32位int的场景。但别高兴得太早，此时，面试官会加大难度，如果int是64位，或元素是不是int，是字符串，怎么办呢？
此时，面试官想要得到的答案，就是BloomFilter。

算法

BloomFilter使用BitMap保存Hash计算出的校验和。为了降低冲突概率，使用不同Hash算法进行多次Hash。
在实际生产中，通常还是会用同一个Hash算法，但会对数据进行不同的处理，比如末尾添加些字符等。

特点

优点

算法简单

整个算法只需要使用多次Hash算法，单机即可完成。

使用空间小

由于使用BitMap，相比树状存储或HashMap等需要存储数据本身的算法而言。空间效率远优于一般算法。

由于BloomFilter计算简单，所需存储空间小，单机就能完成计算，可以很方便的扩展，是个非常精干的算法。但由于并未保存数据本身，因此也存在一些缺陷。

缺点

存在误判

BloomFilter存在假阳性，但不存在假阴性。不过误判概率极小。
如果BloomFilter判断元素不存在，则元素一定不存在，如果判断元素存在，则大概率存在。

不能删除元素

BloomFilter不允许删除元素，只允许添加。
由于BloomFilter不保存数据本身，所以
此外，由于存在假阳性的可能，因此即便在数组中使用计数的方式，也是存在问题。

使用场景

防止缓存被击穿

现在的系统，可以说在每个环节都会存在缓存。无论是加速静态数据的CDN，应用缓存tair，memcache，还是数据库内部，都存在缓存的设计。
如果是正常的查询，缓存通常有很高的命中率，即便存在一些未命中的情况，缓存也会更新，使得下次请求命中。但如果请求的数据本身就是不存在的呢。

可以预料到:

1. 缓存会被全部击穿。
2. 最终数据库中也查询不到。
3. 缓存并不会更新。
   这种情况下。可以使用BloomFilter来过滤掉不存在的元素。因为BloomFilter中不存在的元素，数据库里一定不存在。

另一个面试题

系统遇到大量的请求，这些请求一定会击穿缓存，应该怎么办？
答案就是BloomFilter。

用于黑名单

同样，由于所需存储空间小，也很适用于黑名单。用于过滤危险网址，垃圾邮件等。
因为存在误判，所以还需要一个白名单。

问题

为什么LevelDB中使用BloomFilter但MySQL没有？

1. MySQL的Innodb的数据本地更新的，BloomFilter并不支持删除。
2. 通常MySQL的数据量不会非常巨大。
3. LevelDB中，已经生成的SSTable数据是不会删除的，BloomFilter正好满足。
4. LevelDB的数据结构就和缓存金字塔一样，如果数据不存在，或在较底层，就需要一层层往下查找，要没有用BloomFilter跳不存在数据的层，就要每一层进去找，查询的成本会被放大的很厉害。
5. 在B+tree中查找不存在的数据，查询成本不会像LevelDB那样放大。

总结

1. BloomFilter存在极低概率的假阳性，但不存在假阴性。
2. 用于保护缓存击穿，或存放过滤网址，黑名单等，BloomFilter通常是一个不错的选择，也可能是目前唯一的选择。