先抛一个问题高并发接口有人用一批不存在的ID疯狂刷请求每次都绕过缓存直接打数据库连接池瞬间被榨干或者你负责的爬虫系统每天要抓几百万URL用Redis的Set去重内存看着往下掉。我当时遇到这两类需求第一反应都是找一种能省内存、判断又够快的数据结构。布隆过滤器就是这么个小家伙它用极小的内存告诉你“这个值一定不存在”对于“可能存在”只敢说大概率。这篇内容我会把布隆过滤器的原理、手写实现、Redis集成方式以及两个真实场景的落地案例完整捋一遍最后聊聊参数和排坑。不管你是后端开发、数据工程师还是架构师只要碰到大量去重或者缓存穿透这篇应该能给你一个可以直接开干的方案。1. 布隆过滤器到底解决了什么问题1.1 先从缓存穿透说起缓存穿透这个词后端同学应该不陌生。正常情况下请求先查Redis缓存命中了就返回没命中再查数据库查完回填缓存。但有一类请求特别阴险它查的数据压根就不存在。比如攻击者构造一批随机用户ID这些ID在系统里没有任何记录。缓存里没有数据库里也没有于是每次请求都得实打实打到数据库。数据库要做的是一次全表或者聚簇索引查找查完发现没有然后什么也不返回。这种“查一次空一次”的流量如果被放大再大的数据库集群也扛不住。布隆过滤器在这里的作用就是一道低成本的前置关卡。系统把所有合法ID先写入布隆过滤器请求进来先问它这个ID存在吗如果回答“不存在”那太好了直接返回数据不存在连缓存都不用查更不用去碰数据库。只有当它回答“可能存在”时才继续往下走缓存和数据库的链路。由于布隆过滤器能保证“不存在”这个结论是百分百正确的所以合法ID永远不会被误杀被拦下来的都是非法流量。1.2 内存量级和延迟的博弈除了防穿透布隆过滤器最常见的用途是海量数据去重。举个具体例子假设你的爬虫系统要记录1000万条已经抓过的URL。用HashSet存每个URL按50字节算光内存就要500MB左右这还只是对象开销比较理想的情况下。如果URL更长一些或者Java里加上了指针对齐1GB都很正常。更麻烦的是这1000万条数据放入Redis的Set里网络开销、序列化开销都会让事情变复杂。布隆过滤器的内存占用则是另一个量级。按误判率1%来算1000万条URL大约只要1200万比特换算下来只有大概1.4MB。就算是误判率压到0.1%也才不到18MB。这就是它的核心价值用可控的误判换几十甚至几百倍的内存节省。而且布隆过滤器的查询只涉及几次位运算不像HashSet那样可能存在拉链遍历所以平均延迟也极其稳定。1.3 那个“宁漏勿错”的性质我刚接触布隆过滤器时最困惑的是“误判”到底怎么理解。后来发现一句话就能说清楚布隆过滤器只能说“不在”不能说“一定在”。它给出的“在”是概率性的可能把不在集合里的元素误判成存在这叫假阳性但它永远不会把真正存在判断成不存在也就是不会发生假阴性。这个特性决定了它能用在哪些地方。防缓存穿透场景里假阳性只会让少数非法请求继续下探到数据库影响有限而假阴性则会直接挡住合法数据那是不可接受的。布隆过滤器正好没有假阴性所以适合做这种“宁可错杀不宁可不杀也不能漏杀”的场景。等到后面讲爬虫去重你会发现假阳性可能导致“漏抓”这是它的另一面需要业务上单独兜底。2. 核心原理位数组和哈希函数的组合2.1 底料就是个巨型位数组不用把布隆过滤器想得太玄乎它的底层就是一个很长的位数组每个位置只能存0或1。一开始所有位都置成0。往里添加元素的时候把这个元素喂给若干个哈希函数得到若干个位置把这些位置上的0改成1。查询的时候也一样算出位置检查这些位置上是否全部为1。这里的关键点在于“若干个哈希函数”。哈希函数的作用是把任意长度的输入映射到一个固定范围内的整数也就是位数组的下标。布隆过滤器要求这些哈希函数彼此独立、分布均匀这样元素被映射到的每个位置都尽量没有关联能最大程度降低不同元素之间的位重叠概率。2.2 添加和查询的完整动作看一个具体例子。初始化一个长度为16的位数组初始状态是16个0。现在要添加字符串apple我们用了3个哈希函数分别算出下标1、5、9那么就把这三个位置全部置为1。再添加banana哈希算出的下标是2、5、13把2和13置为15本来就是1保持不变。查询apple时重新计算1、5、9三个位置全是1于是布隆过滤器回答“可能存在”。查询cherry时算出下标3、7、11位置3是0立刻就能断定cherry不在集合里。这就是它的工作原理。值得留意的是为什么不能根据位置全为1就断定一定存在因为不同的元素经过不同的哈希函数可能映射到同一个位置。比如某个元素grape的三个哈希值恰好是1、5、9但它从来没有被添加过布隆过滤器也会认为它存在这就是假阳性。位数组越短、元素越多这种碰撞概率越大。2.3 误判率怎么算出来误判率并不是拍脑袋定出来的。假设位数组长度为m元素数量是n哈希函数个数是k。添加完n个元素后任意一个位还是0的概率约等于(1 - 1/m)^(k*n)。查询一个不存在元素时要能得到“可能存在”需要它对应的k个位置全部是1所以误判率大约为(1 - (1 - 1/m)^(k*n))^k。工程上一般用两个公式反过来推算参数。已知预估元素数量n和能接受的误判率p位数组长度m - (n * ln p) / (ln 2)^2哈希函数个数k (m / n) * ln 2举个例子想要容纳1亿个元素误判率控制在0.1%计算得m大约是14.3亿比特约179MBk大概是7。也就是说分配179MB内存用7个哈希函数就能支撑1亿元素的去重需求。2.4 为什么删除操作这么棘手布隆过滤器最大的痛点是“不能删除”。原因很直观一个位可能同时被多个元素标记为1删除某个元素时如果把它对应的几个位清零可能把其他元素标记过的位也清了导致其他元素被误判为不存在。有人会想到计数布隆过滤器也就是把每个位从0/1换成计数器删除时对应位置计数减一减到0才置空。这个思路可行但代价是内存占用成倍增加而且计数溢出需要额外处理。实际生产里我更推荐用“定期重建”或者“按时间分片”的思路来解决数据淘汰问题后面排坑部分会细说。3. 手写一个布隆过滤器并验证3.1 动手前的思路理论讲得再多不如手撸一把。我实现了一个纯Python版本的布隆过滤器不依赖第三方位数组库只用了标准库的hashlib和math。整体思路很简单用一个bytearray当位数组哈希函数从md5的摘要里拆出两个独立值再用双哈希方式生成k个可复现的下标。这样做的好处是单文件、零依赖用来学习原理或者做小规模验证非常方便。生产环境建议直接用Redis或者RedisBloom模块毕竟纯Python的位运算性能一般但逻辑是完全一致的。3.2 核心代码实现import hashlib import math class BloomFilter: def __init__(self, expected_items, error_rate): self.expected_items int(expected_items) self.error_rate error_rate # 计算位数组长度和哈希函数个数 self.bit_array_size self._calculate_bit_array_size() self.hash_count self._calculate_hash_count() # 用bytearray存位, 每个字节8个位 self.bit_array bytearray(self.bit_array_size // 8 1) def _calculate_bit_array_size(self): return int(- (self.expected_items * math.log(self.error_rate)) / (math.log(2) ** 2)) def _calculate_hash_count(self): return int((self.bit_array_size / self.expected_items) * math.log(2)) def _hashes(self, item): # 用md5摘要拆出两个64位整数作为独立哈希的基础 digest hashlib.md5(item.encode(utf-8)).hexdigest() h1 int(digest[:16], 16) h2 int(digest[16:32], 16) if h2 0: h2 1 # 双哈希生成第i个哈希位置 return [(h1 i * h2) % self.bit_array_size for i in range(self.hash_count)] def _get_bit(self, offset): byte_index offset // 8 bit_offset offset % 8 return (self.bit_array[byte_index] bit_offset) 1 def _set_bit(self, offset): byte_index offset // 8 bit_offset offset % 8 self.bit_array[byte_index] | (1 bit_offset) def add(self, item): for position in self._hashes(item): self._set_bit(position) def contains(self, item): for position in self._hashes(item): if self._get_bit(position) 0: return False return True这段代码里_hashes用了双哈希公式(h1 i * h2) % m。h1和h2由md5的摘要拆开得到可以认为相互独立。生产级实现通常会直接用MurmurHash3或者别的非加密哈希但用md5做示例足够好用了。3.3 实测一下误判率代码写完就得跑数据验证。我做了个小实验往过滤器里添加1万个元素然后用另外1万个不存在的元素做检测统计被误判为存在的比例。def test_error_rate(): bf BloomFilter(expected_items10000, error_rate0.001) # 添加1万个元素 for i in range(10000): bf.add(fitem-{i}) # 检查1万个不存在的元素 false_positive 0 for i in range(10000, 20000): if bf.contains(fitem-{i}): false_positive 1 print(f实际误判率: {false_positive / 10000:.4%}) test_error_rate()我自己跑了几次误判率基本都在0.08%到0.12%之间浮动和理论值接近。说明这套参数计算和哈希逻辑是靠谱的。如果你把error_rate改成0.0001位数组长度会变大实测误判率也会随之下降。3.4 用Redis bitmap做分布式版本单机版好理解但实际系统通常是多实例部署。共享一份布隆过滤器最省事的办法就是直接用Redis的bitmap。Redis天然支持SETBIT和GETBIT一个键就是完整位数组所有服务实例共用。import redis import hashlib import math class RedisBloomFilter: def __init__(self, client, key, expected_items, error_rate): self.client client self.key key self.expected_items expected_items self.error_rate error_rate self.bit_array_size int(- (expected_items * math.log(error_rate)) / (math.log(2) ** 2)) self.hash_count int((self.bit_array_size / expected_items) * math.log(2)) def _hashes(self, item): digest hashlib.md5(item.encode(utf-8)).hexdigest() h1 int(digest[:16], 16) h2 int(digest[16:32], 16) if h2 0: h2 1 return [(h1 i * h2) % self.bit_array_size for i in range(self.hash_count)] def add(self, item): for pos in self._hashes(item): self.client.setbit(self.key, pos, 1) def contains(self, item): for pos in self._hashes(item): if self.client.getbit(self.key, pos) 0: return False return True这段代码里bit_array_size直接作为Redis bitmap的偏移量上限取决于Redis单个字符串键的最大长度默认512MB足够支持几十亿位的位数组。如果使用Redis的RedisBloom模块还有BF.RESERVE和BF.ADD这些命令底层都差不多不需要重复造轮子。4. 两个能直接落地的实战案例4.1 案例一高并发接口防缓存穿透我参与过的一个商品详情系统商品ID是大整数总量接近亿级。当时接口偶然会被恶意流量打穿每次几百个不存在的商品ID请求直接把数据库的读负载拉满。当时的解决方案就是布隆过滤器。流程设计不复杂。系统启动时先从商品表把所有商品ID扫一遍写入一个Redis布隆过滤器大概消耗几十MB内存。之后请求路径变成请求带商品ID进来。先用布隆过滤器判断ID是否存在。如果不存在直接返回“商品不存在”。如果可能存在继续查Redis缓存。缓存未命中再查数据库回填缓存并返回结果。新商品上架时需要注意同步问题。我的做法是先写入数据库成功再调用add方法把新ID加入布隆过滤器。这里存在一个极窄的时间窗口商品已经写库但过滤器还没更新此时查询这个新ID会被判定为不存在。这样的情况很少见而且只会返回一次“不存在”客户端重试后就能正常。如果你对这个时间窗口容忍不了可以改成先更新布隆过滤器再落库代价是数据库写失败时过滤器里会残留一个假ID影响也不大。加了这层过滤之后非法流量的请求基本都止步于第一步数据库的无效查询比例下降了99%以上。对于合法数据里的热点和冷门数据原本的缓存逻辑没有任何改动这就是布隆过滤器的魅力侵入性低收益明确。4.2 案例二爬虫URL去重告别内存爆炸另一个典型的场景是爬虫。当年我们有个定向抓取任务每天要处理几十万条新URL累计的去重集合很快到了一个分钟级就要查重几十万次的状态。早期用Redis的Set存已抓URL跑了两个星期内存就吃掉了好几个GB而且成员数量越大判断耗时也在增加。后来把去重结构换成了布隆过滤器。URL先做一次归一化只保留规范格式然后按10亿条URL、0.01%误判率初始化过滤器。抓取前先contains一下如果返回False就抓抓完立刻add。内存占用从几个GB降到了几百MB查询耗时更是稳定。但这里有个必须正视的问题假阳性会导致部分未抓取URL被当成“已抓过”而漏抓。对于严谨的爬虫业务漏抓的代价可能比较大。我的做法是对重要URL不做布隆过滤器的唯一性裁决而是用一个极小的白名单Set辅助。具体逻辑是先查白名单Set再查布隆过滤器两者只要有任何一个判定为“不存在”就去抓取。这个白名单Set只保存那些绝对不允许漏掉的URL比如种子页、首页、高价值页面。这样布隆过滤器承担绝大部分去重压力白名单补足确定性两者搭配很顺手。5. 参数调优和排坑指南5.1 容量和误判率估算先别拍脑袋很多人在初始化布隆过滤器时直接用“大概”乘以“随便”来定参数结果上线后误判率高得离谱。正确做法是先结合业务实际情况估算元素总量n和可接受误判率p再用公式算出位数组长度m和哈希函数个数k。这里我列出几个常用配置的参考值预估元素数量 n误判率 p位数组长度 m占用内存哈希函数 k1千万1%约9580万比特约11.4MB71千万0.1%约1.43亿比特约17.1MB101亿0.1%约14.3亿比特约170MB710亿0.01%约191.7亿比特约2.2GB13可以看出来误判率要求越严格内存开销越大。实际项目里我一般选0.1%作为默认值既能把假阳性控制在很低水平又不会让内存暴涨。如果业务场景对漏抓零容忍那么0.01%甚至0.001%也是可以考虑的先估算再定参数。5.2 误判率高了怎么调如果运行一段时间后发现误判率明显高于设定值排查顺序通常是这几步第一检查实际元素数量是不是远超预估。布隆过滤器的误判率会随着插入元素数量增加而上升而且是指数级恶化。如果业务增长速度超出预期就需要扩容。第二检查哈希函数个数k是否合理。k太小位被置1的概率变大k太大位数组很快就会被全部置1。这两个极端都会让误判率升高。第三检查位数组是否因为Redis持久化或者进程重启导致部分位被重置。这个问题比较隐蔽如果Redis没有开启持久化重启后位数组会重新归零那么所有已添加元素都会被判断为不存在这不是误判率问题而是数据丢失问题。解决思路要么开启AOF或RDB持久化要么在启动时从数据源重建过滤器。5.3 过滤器不能删业务上怎么兜底正如前面说的标准布隆过滤器不支持删除。业务上如果有元素需要过期淘汰比如URL在一段时间后不再需要去重怎么办我最常用的方案是“时间分片”。以天为单位生成独立的布隆过滤器键比如url_filter_20250601、url_filter_20250602。查询时先查当天的过滤器再查昨天的最多查最近N天写入时只写当天。这样历史数据自然过期只需要定期删除若干天前的键就实现了伪删除。另外一个方案是“定期重建 双缓冲”。凌晨初始化一个新的布隆过滤器把源数据重新灌入然后切换查询入口旧的过滤器延迟删除。这个方案适合源数据量可控的场景而且能顺便调整参数。双缓冲期间要保证写入只能落到新过滤器否则数据会丢。5.4 容易被忽略的几个坑布隆过滤器用久了有几个坑值得单独提出来。第一个坑是哈希函数的选择。直接用各个语言自带的hashCode或者hash()是危险的因为不同进程、不同版本的哈希种子可能不同而且分布质量参差不齐。跨服务实例时如果A实例和B实例用不同的哈希函数同一个元素会生成不同的位位置过滤器的判断就会错乱。必须保证所有实例使用完全相同且稳定的哈希函数组合。第二个坑是位数组偏移量和Redis的字符串编码。当Redis的字符串长度比较小时内部编码可能是embstr或raw不影响SETBIT和GETBIT但如果你自己拼接位数组要注意大小端和偏移转换否则数据全会错位。第三个坑是高并发写入时的Redis性能。如果每添加一个元素就要执行多次SETBIT在超高QPS下会产生很多次RTT。一个优化思路是使用Lua脚本把多次位操作合并成一次原子脚本或者使用RedisBloom模块的BF.ADD、BF.MADD命令。第四个坑是布隆过滤器误判的“放大器”作用。在防穿透场景里假阳性意味着仍有少量非法请求会穿透到数据库。如果攻击流量特别大即使1%的假阳性也可能对应大量请求。如果观测到数据库仍然偶尔被打就要把误判率和非法请求总量相加评估必要时再加一层参数校验。我在实际使用中还有一个习惯无论参数算得多准都会在系统里保留一个布隆过滤器位数组快照的监控指标比如当前元素数量、位数组置1的比例。当置1比例超过一定阈值就自动告警提醒我该评估扩容了。这种数据驱动的方式比我最初靠感觉维护过滤器可靠得多。布隆过滤器是个非常成熟的数据结构但它的“概率性”决定了我们不能只关注它省了多少内存更要关注它每个参数背后对应的业务风险。只要你把容量估算、哈希一致性和数据重建这些细节处理好它在生产环境里是真的又省又稳。