在日常开发中，我们经常会遇到这样的问题：如何快速判断一个元素是否在一个超大集合中？比如，如何判断一个用户ID是否在黑名单中？如何防止恶意请求查询不存在的key导致数据库压力过大？

这里我将介绍Redis中一个非常实用的数据结构——布隆过滤器，它能够以极小的空间成本解决这类问题。

什么是布隆过滤器？

布隆过滤器是1970年由布隆提出的一种空间效率极高的概率型数据结构，主要用于判断一个元素是否存在于一个集合中。

你可以把它理解为一个不太精确的Set集合：当它说某个元素不存在时，那这个元素肯定不存在；但当它说某个元素存在时，这个元素可能存在，也有一定概率不存在。

布隆过滤器解决了什么问题？

缓存穿透问题

这是布隆过滤器最经典的应用场景。什么是缓存穿透？当用户请求一个不存在的数据时，请求会绕过缓存直接查询数据库。如果有恶意攻击者大量请求这些不存在的数据，会导致数据库压力过大甚至崩溃。

布隆过滤器如何解决这个问题？

在Redis前设置一个布隆过滤器，将所有可能存在的key存入其中。请求到达时，先查询布隆过滤器：如果key不存在，直接返回；如果key存在，再去查询Redis和数据库。

通过这种机制，可以拦截绝大部分对不存在数据的查询请求，有效保护后端数据库。

其他应用场景

除了缓存穿透，布隆过滤器还广泛应用于：

  • 网页爬虫URL去重：快速判断URL是否已被爬取
  • 垃圾邮件过滤：判断邮件地址是否在黑名单中
  • 推荐系统去重：过滤用户已看过的内容
  • 数据库优化：HBase、LevelDB等数据库内置布隆过滤器减少磁盘IO

布隆过滤器的工作原理

数据结构

布隆过滤器的核心是两部分：一个很长的二进制位数组（初始值全为0）和多个无偏哈希函数（能把元素哈希值比较均匀地映射到位数组中）。

添加元素过程

当向布隆过滤器中添加一个元素时：

  1. 通过多个哈希函数对元素进行计算，得到多个哈希值
  2. 将这些哈希值对位数组长度取模，得到多个位置索引
  3. 将这些位置的值置为1

例如，添加元素X，经过两个哈希函数计算后，得到位置4和9，于是将位数组的第4位和第9位置为1。

查询元素过程

当查询一个元素是否存在时：

  1. 通过相同的哈希函数计算元素的多个哈希值
  2. 将这些哈希值对位数组长度取模，得到多个位置索引
  3. 检查这些位置的值是否都为1

如果都是1，元素可能存在；如果有任何一个位置为0，元素肯定不存在。

为什么会有误判？

假设有两个元素X和Y，X映射到位置4和9，Y映射到位置14和19。此时如果查询元素Z，而Z恰好映射到位置9和14（这些位置已被其他元素置为1），布隆过滤器就会误判Z存在。

这种误判是由于哈希冲突引起的。但布隆过滤器有一个重要特性：它不会漏判（即如果元素存在，一定会正确报告存在）。

如何降低误判率？

  1. 增加位数组大小：位数组越长，误判率越低
  2. 优化哈希函数数量：哈希函数过多或过少都会影响效率，需要找到平衡点
  3. 根据预期数据量调整参数：使用前预估元素数量，设置合适的错误率

Redis提供了bf.reserve命令，让我们可以自定义错误率和预计元素数量：bf.reserve myfilter 0.0001 10000（创建错误率为0.01%、容量10k的布隆过滤器）。

根据公开数据，当误判率为0.0001%时，每个元素仅占用28.8 bit，存储100万个元素只需约27.5MB空间，空间效率非常高。

布隆过滤器的优缺点

优点

  • 空间效率高：相比HashMap等数据结构，布隆过滤器非常节省空间
  • 查询速度快：插入和查询的时间复杂度都是O(k)（k为哈希函数个数，通常较小）
  • 保密性强：不存储元素本身，只存储存在与否的信息

缺点

  • 存在误判：可能将不存在的元素误判为存在（但不会相反）
  • 删除困难：不能直接删除元素，因为可能影响其他元素的判断

Redis中的布隆过滤器操作

Redis从4.0版本开始支持布隆过滤器（需安装相应插件），主要命令包括：

# 添加元素
bf.add filter_name element

# 检查元素是否存在
bf.exists filter_name element

# 批量添加元素
bf.madd filter_name element1 element2

# 批量检查元素
bf.mexists filter_name element1 element2

实际应用案例

假设我们有一个电商平台，需要防止恶意用户请求不存在的商品ID：

  1. 将所有存在的商品ID预先添加到布隆过滤器中
  2. 当有查询请求时，先检查布隆过滤器
  3. 如果商品ID不存在，直接返回"商品不存在"
  4. 如果商品ID存在，再查询Redis缓存和数据库

这样可以拦截绝大部分对不存在商品的查询请求，有效保护数据库。

总结

布隆过滤器是一个空间效率极高的概率型数据结构，虽然有一定误判率，但在很多场景下是完全可接受的。它特别适合解决缓存穿透等问题，能够有效保护后端存储系统。

当你的系统面临大量不存在的key的查询请求时，不妨考虑使用布隆过滤器这一小巧而强大的工具。它的简单实现和高效性能，可能会为你的系统带来意想不到的改善。