布隆过滤器这名字听着唬人我第一次遇见它是在处理用户注册防重的场景。当时线上 MySQL 用唯一索引兜底但架不住每次注册都先查一次库高峰期数据库的读压力肉眼可见地往上飙。后来用 PHP Redis 的 Bitmap 折腾了一套布隆过滤器几行代码就把大部分无效查询挡在了数据库前面。这篇文章我不打算讲太玄的数学推导而是把这套东西从原理到代码、从参数计算到踩坑经验一层层拆开像庖丁解牛一样让你看完能直接在自己项目里用起来。1. 布隆过滤器到底在解决什么问题1.1 缓存穿透这个让人头大的坑先聊一个很多做后端的朋友都撞过的场景你的业务里有一个热点数据接口用户请求进来先查 Redis 缓存缓存没有再去查 MySQL查到了回填缓存。正常情况下这套流程没问题缓存命中率也高。但如果有大量请求带着根本不存在的 ID 打进来比如说恶意刷接口、或者传参被遍历缓存里永远查不到MySQL 每次都得白扛一次查询这就是典型的缓存穿透。缓存穿透最恶心的点在于“查询的是不存在的数据”这类数据没法提前写进缓存也不可能要求上游先把参数校验做好。你可以在接口层做参数校验、做限流但总有一些场景防不住。这时候布隆过滤器就能派上用场先问它“这个东西是否存在”它说“不存在”那就直接返回连缓存都不查它说“可能存在”才继续往下走。这里的关键词是“可能存在”布隆过滤器的核心特性就是判断不存在是绝对的判断存在是有误差的。听起来好像很不靠谱但正是这种“宁可错杀、绝不放过”的特性让它特别适合挡掉那些“肯定不存在”的请求。1.2 布隆过滤器的原理一个位数组和几个哈希函数布隆过滤器的实体数据结构极其简单一个很长的位数组一串 0 和 1外加 K 个哈希函数。你可以把它想象成一个巨大的格子本每个格子只能写 0 或 1一开始全是 0。要往里面加一个元素就拿这个元素分别喂给 K 个哈希函数算出 K 个位置然后把对应格子从 0 改成 1。查询某个元素是否存在时同样拿它算 K 个位置检查这些位置的格子是不是都为 1。只要有一个格子是 0说明这个元素肯定没被添加过如果 K 个格子全部都是 1那只能说“有可能被添加过”因为存在哈希碰撞——两个不同元素可能把某些同样的格子涂成了 1。这个设计最大的好处是省空间。一个元素只占用 K 个 bit和存储原始数据动辄几十上百字节相比几乎可以忽略不计。而且无论集合里已经有多少元素每个元素占用的空间永远只有 K 个 bit。代价就是误判率会随着元素越来越多而上升并且你没法删除元素——因为把某个格子从 1 改回 0会影响其他可能落在同一位置上的元素。1.3 误判率到底怎么来的很多人第一次接触布隆过滤器都会问误判率能不能做到 0理论上可以只要位数组无限长或者哈希函数无限多但现实中不可能。误判的本质就是哈希碰撞当位数组里 1 越来越多新元素算出的 K 个位置大概率早就被其他元素涂成 1 了这时候它就会被“误认为”存在。误判率的影响因素主要有三个位数组长度 m、哈希函数个数 K、已经插入的元素数量 n。固定 n 的前提下m 越大1 的密度越低碰撞概率越小K 越多判断越严格但太多之后反而会加速位数组变满。这里有一个最优 K 值的公式后面我会给出具体计算方法和推导过程。实际使用中你要做的就是接受这个误判率然后把误判率控制在一个可接受的范围比如 1% 或者 0.1%。毕竟我们用它来挡的是“绝对不存在”的请求就算误判了代价也无非是多查一次缓存、多查一次数据库不会造成数据错误。2. 为什么用 PHP Redis 组合实现2.1 Redis Bitmap 就是天然的位数组布隆过滤器的核心是一个位数组。如果你自己用 PHP 的字符串来模拟也能写但内存完全扛不住一个亿的位就是 1.25MB 的字符串这倒还好真正的问题是你没法跨进程共享每个 PHP-FPM 进程各存一份根本没法在集群里用。Redis 的 String 类型底层是字节数组配合 SETBIT 和 GETBIT 命令完全可以当成一个跨进程共享的位数组来用。SETBIT key offset value 就是把某个 offset 的位改成 0 或 1GETBIT 就是读取指定位的值这两个操作的时间复杂度都是 O(1)。Redis 官方文档里也明确说过用 Bitmap 存储 1 亿个用户的在线状态只需要 12.5MB 内存这个量级非常可观。举个直观的例子假设你要存 1000 万个手机号如果不做任何压缩直接存字符串每个手机号至少 11 个字符一个 Redis key 都装不下得多说几个 G。但布隆过滤器只需要约 958 万个 bit也就是大约 1.15MB差了上千倍。这就是为什么布隆过滤器在 Redis 上可以实现得如此优雅。2.2 方案选型对比为什么不是 MySQL 也不是本地数组我见过有人用 MySQL 建一张表来模拟布隆过滤器字段就是 offset 和 value查询走索引。这种方案在数据量小的时候也能跑但每判断一个元素是否存在都要走一次 SQL 查询网络开销和数据库连接开销全堆上去了。假设每秒要过滤 1 万个请求就算 MySQL 扛得住 1 万 QPS连接数也会成为瓶颈完全背离了布隆过滤器“轻量级挡请求”的初衷。本地数组方案就更不用说了单机内存有限而且数据不能共享多台服务器各自为政布隆过滤器就失去了全局一致性的意义。Redis 的好处是天然支持分布式部署所有 PHP-FPM 进程访问同一个 key数据一致性由 Redis 保证你只需要把 Redis 连接池做好就够了。对比一下三种方案的取舍方案内存/存储开销跨进程共享性能适用场景PHP 本地数组大每进程一份不支持最快单进程测试MySQL 表大还要索引支持慢有 SQL 开销不推荐除非数据量极小Redis Bitmap极小约 n/8 字节支持极快O(1) 位操作生产环境首选2.3 参数设计位数组长度 m 和哈希函数个数 K 的计算这里要给出一套可以直接套用的公式。假设我们预估最多要存储的元素数量是 n可接受的误判率是 p那么最优位数组长度 m 和哈希函数个数 K 分别是位数组长度m - (n * ln(p)) / (ln(2) * ln(2))哈希函数个数K (m / n) * ln(2)拿一个具体例子算一下假设要存储 100 万条数据误判率控制在 1%也就是 p0.01。先算 m m - (1000000 * ln(0.01)) / (ln2 * ln2) ln(0.01) 约等于 -4.60517ln2 约等于 0.693147ln2 的平方约等于 0.480453。 m - (1000000 * -4.60517) / 0.480453 ≈ 9585058 bit换算成字节就是 9585058 / 8 ≈ 1.14MB。再算 K K (9585058 / 1000000) * 0.693147 ≈ 6.64向上取整为 7。也就是说对于 100 万条数据、1% 误判率的目标我们需要一个约 958 万位约 1.14MB的位数组7 个哈希函数。你可以用这个公式反推各种组合比如数据量大到 1 亿条误判率同样 1%那 m 大约是 9.58 亿位约 114MBK 还是 7 左右。这也是为什么布隆过滤器适合海量数据场景但前提是你得能接受这类内存开销。3. 完整实现从零写一个 BloomFilter 类3.1 类的整体设计与构造函数接下来直接上代码。我这里用 PHP 实现一个可复用的 BloomFilter 类底层依赖 Redis 的 SETBIT 和 GETBIT。为了让类更通用我在构造函数里只接收 Redis 连接、key 名称、位数组长度 m 和哈希函数个数 K另外封装一个静态工厂方法让调用方只需要传预期元素量和期望误判率就能自动算出 m 和 K。?php class BloomFilter { private Redis $redis; private string $key; private int $m; private int $k; // 两个基础哈希的种子实际上我们通过这两个种子派生 K 个哈希位置 private const SEED_1 31; private const SEED_2 131; public function __construct(Redis $redis, string $key, int $m, int $k) { $this-redis $redis; $this-key $key; $this-m $m; $this-k $k; } public static function create(Redis $redis, string $key, int $expectedItems, float $falsePositiveRate): self { $m (int) ceil(- ($expectedItems * log($falsePositiveRate)) / (log(2) ** 2)); $k (int) ceil(($m / $expectedItems) * log(2)); return new self($redis, $key, $m, $k); } }构造函数里把 m 和 K 存下来后续所有位置计算都依赖它们。这里做了参数化处理的好处是你可以随时通过调整 m 和 K 来改变空间与误判率的平衡。如果元素量预估偏少导致误判率飙升你还可以直接换一个 key 重建旧 key 留着或者删掉都行。3.2 核心功能添加元素与查询元素位置计算是整个实现的灵魂。标准的布隆过滤器要求 K 个哈希函数尽量相互独立但在工程实践中我们通常只用两个基础哈希函数然后用双重哈希公式派生 K 个位置。这样做既避免了实现 K 个不同哈希函数的麻烦也能保证分布足够均匀。我先实现一个基于 CRC32 的哈希函数。CRC32 是 PHP 内置的速度快返回一个 32 位整数。需要注意在 32 位系统上crc32()可能返回负数所以这里做一次 0x7FFFFFFF的位运算强制转成正数。private function hash(string $item, int $seed): int { $hash crc32($item . : . $seed); return $hash 0x7FFFFFFF; } private function positions(string $item): array { $h1 $this-hash($item, self::SEED_1); $h2 $this-hash($item, self::SEED_2); $positions []; for ($i 0; $i $this-k; $i) { $positions[] ($h1 $i * $h2) % $this-m; } return $positions; }注意一个细节$i从 0 开始也就是说positions[0]实际就是h1 % m后面每个位置按照等差数列递增公差是 h2。这种双重哈希的好处是K 个位置对同一个元素来说是确定性的、可重复的查询的时候能还原出同样的一组位置不同元素由于 h1 和 h2 不同分布也不会严重扎堆。有了位置数组之后添加和查询就非常直白了。添加是把每个位置都 SETBIT 为 1查询是依次 GETBIT只要有一个位是 0就立即返回“不存在”。public function add(string $item): void { foreach ($this-positions($item) as $offset) { $this-redis-setBit($this-key, $offset, 1); } } public function exists(string $item): bool { foreach ($this-positions($item) as $offset) { if ($this-redis-getBit($this-key, $offset) 0) { return false; } } return true; }代码只有十几行但已经能跑通一个完整的布隆过滤器了。我建议你在写业务代码前先用这套最基础的版本打印几条测试数据验证一下“可信的不存在”和“可能的存在”各自的行为是否符合预期再继续做优化。3.3 Pipeline 和 Lua 脚本优化上面的基础版本有个性能隐患每添加一个元素要执行 K 次 Redis 网络往返。假设 K7添加 1 万个元素就是 7 万次请求即便 Redis 很快网络 RTT 也扛不住。解决方法是使用 Redis Pipeline把多个 SETBIT 合并成一次请求发送Redis 依次执行后一次性返回结果。public function add(array $items): void { foreach (array_chunk($items, 500) as $chunk) { $pipe $this-redis-pipeline(); foreach ($chunk as $item) { foreach ($this-positions($item) as $offset) { $pipe-setBit($this-key, $offset, 1); } } $pipe-exec(); } } public function exists(string $item): bool { $positions $this-positions($item); $pipe $this-redis-pipeline(); foreach ($positions as $offset) { $pipe-getBit($this-key, $offset); } $results $pipe-exec(); foreach ($results as $bit) { if ($bit 0) { return false; } } return true; }注意批量添加时我用array_chunk把元素切成每批 500 个避免单条 Pipeline 命令太多导致 Redis 请求缓冲区过大。这里有个经验值一个 Pipeline 里塞 2000 到 5000 条命令是安全的太多反而会拖慢 Redis 处理速度甚至引发慢查询日志。如果你不想在 PHP 和 Redis 之间来回传 offset 数组可以把“算位置 写位”的逻辑都塞进 Lua 脚本。缺点是 Lua 里也得实现同样的哈希逻辑PHP 和 Lua 两边要保持完全一致维护成本高所以我一般只在简单场景这么做。Pipeline 方案已经能覆盖绝大多数业务需求。3.4 预留位数组空间的技巧还有一个容易被忽略的问题Redis 的字符串是动态扩容的。你要写入一个很大的 offsetRedis 会先把字符串扩容到那个长度再写。虽然 SETBIT 本身会自动扩容但频繁扩容会产生内存碎片和性能抖动。如果你能预估到 m 的大小比如前面算出来的 958 万位约等于 1.14MB建议在应用启动时一次性把位数组的空间占好。public function initSpace(): void { $byteLen (int) ceil($this-m / 8); // 在字符串尾部写入一个 \0触发 Redis 一次分配好整个字符串空间 $this-redis-setRange($this-key, $byteLen - 1, \0); }setRange这个命令平时用得不多它可以在指定偏移位置写入内容自动创建中间的空字节。把偏移设到byteLen - 1写入一个\0Redis 就会一次把字符串分配成我们期望的长度。后续所有 SETBIT 都不会再触发扩容性能更稳定。4. 真实业务场景怎么用4.1 缓存穿透防护的完整示例布隆过滤器在缓存穿透防护里的位置非常清晰放在 Redis 缓存和 MySQL 之间或者说放在请求进入任何昂贵数据源之前。我用一个典型的用户详情查询场景来演示完整链路。假设用户数据在 MySQL用户 ID 是自增主键我们不希望恶意请求带着一堆不存在的 ID 来刷 MySQL那么流程应该是这样的先查布隆过滤器如果 ID 不存在直接返回空如果 ID 可能存在再查 Redis 缓存缓存也没有才允许查 MySQL。$bloom BloomFilter::create($redis, bf:user:detail, 1000000, 0.01); function getUserDetail(Redis $redis, BloomFilter $bloom, int $userId) { // 第一步布隆过滤器判断 if (!$bloom-exists(user: . $userId)) { return null; // 这个 ID 绝对不在库里直接返回 } // 第二步查缓存 $cacheKey user:detail: . $userId; $cached $redis-get($cacheKey); if ($cached ! false) { return json_decode($cached, true); } // 第三步查数据库走到这里才有 MySQL 压力 $user queryUserFromDb($userId); if ($user null) { // 如果布隆过滤器误判了这里会多查一次空库但是概率很低 return null; } $redis-setex($cacheKey, 3600, json_encode($user)); return $user; }这里有个重要的取舍布隆过滤器的初始化。你不能在用户查询时才把 ID 写进布隆过滤器而应该在数据写入 MySQL 的同时同步写入布隆过滤器。最简单的方式是在用户注册、导入等写操作的地方同一事务里既写库又写布隆过滤器。如果担心漏写可以启动一个离线脚本全量扫描一次 MySQL 里的用户 ID批量重建布隆过滤器。4.2 用户名和手机号唯一性预检另一个非常典型的场景是唯一性预检。比如用户注册的时候要检查手机号是不是已经被占用。常规做法是直接查 MySQL但如果在注册入口就放一个布隆过滤器就能把 99% 的“已被占用”请求拦截在数据库之外。这里要注意一个反向的思维布隆过滤器判断“可能不存在”是可信的判断“可能存在”是不可信的。所以在做唯一性校验时流程要反过来布隆过滤器说“这个手机号已存在”不能直接拒绝因为可能是误判还需要查 MySQL 确认。布隆过滤器说“这个手机号不存在”那就可以放心让用户走注册流程不需要查库。这样做的收益是把“查库确认存在”这个低频动作留给了真正可能存在的请求把“肯定不存在的手机号”全部挡掉了。对注册场景来说大部分新用户想用的手机号本来就不在库里所以拦截效果非常明显。类似的应用还有昵称占用预检、Email 去重、活动防重复领取、黑名单过滤。本质都是一样的核心全在于理解“宁可错杀、绝不放过”以及它的反面“宁可放过、必须确认”。4.3 哪些场景不适合用布隆过滤器我见过有人把布隆过滤器当成万能的判重工具这就会踩坑。先说不能用于精确判重比如订单号是否已支付这种必须 100% 准确一个误判都可能导致用户重复支付或者漏发凭证布隆过滤器不适用。再说删除场景。布隆过滤器不支持删除元素因为删掉某个位可能会误伤其他落到同一位置的元素。如果你的业务有频繁删除的需求要么定期重建布隆过滤器要么改用计数布隆过滤器Counting Bloom Filter但实现复杂度会高很多。最后是数据量特别小的场景。如果集合只有几百条数据直接把 ID 放进 Redis Set 或者 MySQL 查一下也许更简单布隆过滤器的数学优势体现不出来反而要多维护一套 key、多管理 K 个哈希函数一言以蔽之就是杀鸡焉用牛刀。5. 踩过的坑与排查经验5.1 PHP 整数溢出与负数偏移第一个坑是 PHP 的整数溢出问题。crc32()函数在 64 位系统上返回 0 到 4294967295 之间的整数没问题但在 32 位 PHP 进程上它可能返回负数。如果你直接拿负数去算偏移量最终位置可能变成负数传给 Redis 的 SETBIT 直接报错。解决方法是统一在哈希结果上执行 0x7FFFFFFF确保结果永远是非负整数。这个操作把 32 位哈希值最高位的符号位直接抹掉相当于把范围收敛到 0 到 2147483647。对于布隆过滤器来说这 31 位精度完全够用分布也不会明显变差。另一个坑是 offset 超过 Redis 的限制。Redis 的 SETBIT offset 参数不能超过 2^32 - 1也就是位数组最多 512MB约 42.9 亿 bit。如果你预估的数据量超过 5 亿条且误判率 1%那么 m 会超过 2^32 bit单个 key 就放不下了。这个时候你需要做分片把位数组按区间切分成多个 key比如bf:user:0、bf:user:1每个 key 负责一段 offset 范围。5.2 误判率飙升的排查思路有一次我在生产环境发现误判率高得离谱随手一查发现有个定时任务把布隆过滤器的 key 给清掉了然后系统自动用新的 key 重建。问题是新 key 建完之后数据还没来得及全量重新写入很多原本存在的 ID 在布隆过滤器里被判定为“不存在”而更糟糕的是由于部分 ID 已经写入了整个位数组又稀稀拉拉误判率反而比正常高不少。排查这种问题要从两个维度看。第一个维度是 m 和 K 是否符合当前数据量如果存储的元素数量 n 远超当初设计值误判率会按指数级上升。第二个维度是位数组的“密度”你可以用 Redis 命令统计这个 key 里有多少个位是 1SETBIT bf:user:detail 100 1 BITCOUNT bf:user:detailBITCOUNT返回的是位数组中值为 1 的数量。如果你能知道当前已经插入的元素数量 n就可以算一个理论上的“期望密度”(1 - e^(-K*n/m))。如果实际 BITCOUNT 远高于这个值说明有重复写入或者哈希函数分布不均的问题。5.3 批量写入时的性能调优刚才提到的 Pipeline 方案已经大幅降低了网络开销但我在实际压测时还发现几个性能点。一个是 Redis 的 maxmemory 策略如果 Redis 实例设置了 allkeys-lru 淘汰策略布隆过滤器的 key 可能在内存紧张时被淘汰掉一旦被淘汰所有查询都会变成重新创建的空 key误判率直接变成 100%。所以布隆过滤器这类重要 key 要设置persistent或者用 noeviction 策略单独保护。另一个性能点是 Redis 连接池。PHP-FPM 每个 worker 进程维护一个 Redis 连接这是最常用的方式。但如果你用了 swoole 这类常驻内存框架要特别注意 redis 连接在协程间不能共享否则并发写同一个连接会导致命令交叉错乱。最后提一下批量的粒度。我在测试中发现一个 Pipeline 里塞 3000 条 SETBIT 命令Redis 端处理时间大概在几毫秒到十几毫秒之间但如果塞到 1 万条以上Redis 的请求缓冲区会明显变大反而可能触发客户端超时。所以批量操作要控制单次数量分批写入时每批停留极短的时间给其他请求一些喘息空间。5.4 进阶玩法计数布隆过滤器与分片如果你的业务确实需要删除功能标准布隆过滤器无能为力这时候可以升级为计数布隆过滤器。原理很简单把每个位从 0/1 变成一个计数器插入元素时就给对应位置的计数器加 1删除元素时就减 1。查询时只要发现任何一个计数器的值为 0就说明元素不存在。用 Redis 实现计数布隆过滤器可以利用 BITFIELD 命令它可以对字符串里的任意 bit 区间做自增自减操作。比如给每个位置分配 4 bit 作为计数器那么 m 位数组实际占用的空间就是 m * 4 bit。代价是空间翻了 4 倍但换来的是删除能力适合需要频繁有进有出的场景。分片则是为了解决单 key 容量上限的问题。你可以实现一个简易的分片逻辑把所有 offset 均匀映射到多个分片 key 上比如$shardId floor($offset / (2**32))然后$offsetInShard $offset % (2**32)。这样理论上数据量可以横向扩展只要分片 key 足够多。这属于大规模场景下的工程化方案了一般业务体量用不上但提前了解总没有坏处。6. 最后的体会我用了布隆过滤器很长时间最大的体会是它的价值不在于“精确”而在于“用极低的成本把绝对不存在的请求挡在外面”。理解这一点之后你会发现它在系统架构里的位置其实非常明确它不是一个查数据的工具而是一个前置闸门。设计布隆过滤器方案时最需要花心思的不是代码本身而是预估数据量、控制误判率、以及设计数据同步机制。只要这三个点想清楚了代码反而是最简单的部分。以后如果你在处理类似缓存穿透、判重、过滤的场景时希望这篇拆解能帮你少走一些弯路。