说一说你对布隆过滤器的理解

得分点

​ 布隆过滤器的原理

参考答案

标准回答

​ 布隆过滤器可以用很小的代价来估算出数据是否真实存在，相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

​ 布隆过滤器的数据结构是一个大型的位数组，而如果我们要映射一个值到布隆过滤器中，我们还需要使用多个不同的哈希函数来生成多个哈希值，并对每个生成的哈希值指向的位置设置为1。查询key是否存在时，每个哈希函数都利用这个key计算出一个哈希值，再根据哈希值计算一个位置。然后对比这些哈希函数在位数组中对应位置的数值，如果这几个位置中，有一个的位置值为0，则说明过滤器中不存在这个key。如果这几个位置中，所有位置的值都是1，就说明这个布隆过滤器中，极有可能存在这个key。之所以不是百分之百确定，是因为也可能是其他的key运算导致该位置为1。

加分回答

​ 过小的布隆过滤器bit位很快就会都被置为1，那么查询任何值都会返回“可能存在”，这就起不到过滤的目的了。这说明布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

​ 另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位为 1 的速度越快，且布隆过滤器的效率越低。但是如果太少的话，误报率会变高。

​ 布隆过滤器的典型应用有：

• 数据库防止穿库。 Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。
• 业务场景中判断用户是否阅读过某视频或文章，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。
• 缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回。
• WEB拦截器，如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率。Squid 网页代理缓存服务器在 cache digests 中就使用了布隆过滤器。Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。
• Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。
• SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。

​ Redis 因其支持 setbit 和 getbit 操作，且纯内存性能高等特点，因此天然就可以作为布隆过滤器来使用。但是布隆过滤器的不当使用极易产生大 Value这会增加 Redis 阻塞风险，因此实际使用中建议对体积庞大的布隆过滤器进行拆分。拆分的形式方法多种多样，但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上，而是应该拆分成多个小 bitmap 之后，对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。

延伸阅读

哈希函数的概念：

将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。

所有散列函数都有如下基本特性：

• 如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。
• 散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“散列碰撞（collision）”。