一文讲透布隆过滤器

关注

发布于: 2020 年 08 月 24 日

1、什么是布隆过滤器？布隆过滤器本质上就是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。
相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。
2、为什么需要布隆过滤器？2.1 缓存穿透我们经常会把一部分数据放在Redis中缓存，比如文章详情内容。
这样有查询请求进来，我们可以根据文章Id直接去缓存中取数据，而不用读取数据库，这是提升性能最简单，最普遍，也是最有效的做法。
﻿
一般的查询请求流程是这样的：先查缓存（有缓存的话直接返回）-> 如果缓存中没有，再去数据库查询（把数据库取出来的数据放入缓存）-> 返回数据。
﻿
一切看起来很美好。但是如果现在有大量请求进来，而且都在请求一个不存在的文章Id，会发生什么？
既然文章Id都不存在，那么肯定没有对应的缓存信息，没有缓存，那么大量的请求都堆积到数据库，数据库的压力一下子就上来了，甚至可能把数据库打满跑死。
2.2 大范围查询查询近1亿用户手机号系统中是否存在其交易信息，如何做到判断的准确快速？
方案一：通过数据库查询
查询压力好像有点大，做不到高效而且还存在数据库服务被压垮的风险。
方案二：通过Redis缓存（存在交易单的用户手机号放入Set）
可能会产生大Key造成慢查询，同时内存资源会造成浪费。
﻿
以上例子有一个共同的特点： 如何判断一个元素是否存在一个集合中。这些问题用其他方式可能都会解决，但“布隆过滤器”就能够有效的解决。
3、布隆过滤器实现原理3.1 哈希函数哈希函数的概念：将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码。示意图如下所示：
可以明显的看到，原始数据经过哈希函数的映射后成为了一个个的哈希编码，数据得到压缩。
哈希函数是实现哈希表和布隆过滤器的基础。
3.2 数据结构布隆过滤器是一个 bit 向量或者说 bit 数组，示意图如下所示：
布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。
假设我们要将x、y、z三元素放入布隆过滤器再去检索w，示意图如下所示：​
﻿
以上图为例，具体的操作流程：
﻿
假设集合里面有3个元素{x, y, z}，哈希函数的个数为3。将位数组进行初始化，将里面每个位都设置为0。
﻿
设置：对于集合{x, y, z}里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1（这样位置2、4、5、6、12、14、17均为1）。
查询：判断W元素是否存在集合中的时候，同样的方法将W通过哈希映射到位数组上的3个点（位置：5、14、16）。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。反之，如果3个点都为1，则该元素可能存在集合中。
﻿
注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。
假设某个元素通过映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。
4、布隆过滤器操作4.1 添加元素
语法：[bf.add  key  options]
﻿
127.0.0.1:6379> bf.add users 15012345678
(integer) 1
﻿
将要添加的元素给k个哈希函数
得到对应于位数组上的k个位置
将这k个位置设为1
4.2 查询元素
语法：[bf.exists  key  options]
﻿
127.0.0.1:6379> bf.exists users 15012345678
(integer) 1
127.0.0.1:6379> bf.exists users 15012345679
(integer) 0
﻿
将要查询的元素给k个哈希函数
得到对应于位数组上的k个位置
如果k个位置有一个为0，则肯定不在集合中
如果k个位置全部为1，则可能在集合中
4.3 删除元素传统的布隆过滤器并不支持删除操作。
但是名为 Counting Bloom filter 的变种可以用来测试元素计数个数是否绝对小于某个阈值，它支持元素删除。可以参考文章 Counting Bloom Filter 的原理和实现
5、最佳实践5.1 应用场景常见的使用常见有，利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续更昂贵的查询请求。
既然你使用布隆过滤器来加速查找和判断是否存在，那么性能很低的哈希函数不是个好选择，推荐 MurmurHash、Fnv 这些。
5.2 设置哈希函数个数和布隆过滤器长度假如布隆过滤器长度过小的话，那很快所有的 bit 位均会被置为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。
哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置为 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。
﻿