很多人在第一次接触布隆过滤器时心里的反应多半是“这不就是个位数组嘛有什么可讲的”。但真正在系统里用它挡过一次缓存穿透或者看着上亿条URL挤在内存时才会意识到这个结构有多“逆天”——它允许你用一个极小的空间判断“某个东西是否不存在”代价是偶尔会把不存在的误判成存在但绝不会把存在的漏掉。这篇博客我就把布隆过滤器的原理、手写实现和实际应用一次性说透包括那些教科书里不太会讲的工程坑。1. 布隆过滤器是什么一个让你“误判”但极其高效的数据结构1.1 从一次缓存穿透事故说起前几年我负责过一个广告检索系统接了一个大客户的量之后每天凌晨总有那么几分钟接口响应时间飙到3秒以上。查了半天发现原因特别俗用户端用脚本扫了一些根本不存在的广告位ID这些ID既不在Redis里也不在数据库里于是每一个请求都穿透缓存直接打到了MySQL上把慢查询日志都刷花了。当时能想到的常规方案有几种把Redis的空值也缓存起来比如不存在的ID对应一个“null”标记TTL设个60秒。这个方法简单但有个问题——恶意扫描的ID可能是随机的、每天都在变空值缓存根本追不上参数爆炸。第二种方案是直接查数据库前先走一个HashSet把所有合法ID加载到内存里。这个倒是准确但业务有上亿个ID每个ID二三十个字节HashSet包装后的内存开销动辄几个GB太贵了。最后真正解决问题的是布隆过滤器。我用Redis里一个大概几百MB的Bitmap按我当时的业务量算的配合两个哈希函数把上亿合法ID全部塞了进去。从此每一次请求先问布隆过滤器“这个ID存在吗”如果它说不存在那它肯定不存在直接返回空结果如果它说存在才继续走后续流程。就这么一个小改动数据库压力直接降到了原来的零头。对布隆过滤器会误报——明明不存在的ID它可能说“存在”但这一点点误报换来的代价只是偶尔让一个空请求穿透到数据库完全可控。1.2 布隆过滤器的核心思想宁错杀不放过布隆过滤器的骨子里是一种“概率型数据结构”。它不像HashMap那样存原始数据而是用一个位数组bit array来表示集合。插入元素时把这个元素通过k个哈希函数映射到k个位把这几个位都置为1。查询元素时同样算出k个位只要看到任何一个位是0就说明这个元素一定不在集合里如果k个位全部是1说明它“可能在集合里”。看到那个“可能”没有这就是误判的来源。因为不同的元素可能映射到相同的位当集合里的元素足够多时某些位被提前置为1导致一个从未插入过的元素在查询时碰巧命中了所有对应位于是被误判为存在。但反过来想如果一个元素真的被插入过它对应的k个位一定是1布隆过滤器永远不可能把它判断成不存在。所以它给出的结论只有一个方向“不在”是确定的“在”是不确定的。这在工程上叫“假阳性”false positive它没有假阴性。理解这句话你就理解了布隆过滤器一半。2. 原理拆解位数组、哈希函数与那笔数学账2.1 插入和查询两套操作讲透布隆过滤器只有两个基本操作插入和查询。删除操作标准版没有后面我会单独讲为什么。先看插入。假设位数组长度是m一共有k个不同的哈希函数。往集合里加入一个元素x时用这k个哈希函数分别算出k个位置h1(x)、h2(x)……hk(x)每个位置取值范围是0到m-1然后把这k个位置的二进制位全部置为1。如果某个位置已经被置为1就保持不动。再看查询。查询元素y时同样算出y的k个位置然后检查每个位置上的位是否都是1。只要发现任意一个位置是0就可以100%确定y没有插入过。为什么因为y如果真插入过那么这k个位置应该都是1。既然有一个是0说明至少有一个哈希函数没有在y上命中过y肯定不在集合里。如果y的k个位置碰巧全部是1呢注意我们不能说y一定存在只能说y大概率存在因为这些位置可能被其他元素“占用”了。比如集合里有x和z它们的哈希值拼凑起来可能恰好覆盖了y的k个位置这时查询y就会发生误判。这就是布隆过滤器“用精确性的损失换空间”的本质。2.2 误判率从何而来哈希碰撞与位重叠误判率false positive rate的高低核心取决于三个因素要插入的元素个数n、位数组长度m、哈希函数个数k。其中n是业务决定的你没法轻易改变能调的就是m和k。想象一个极端场景位数组只有1位。那么插入任意一个元素后这一位都变成1。之后查询任何元素都是“存在”。误判率是多少如果集合非空那就是100%。这不是开玩笑它说明位数组长度必须足够大才能让不同的元素映射到不同的位上。另一个极端哈希函数个数太多。每个元素要置1的位很多位数组很快就会全变成1误判率同样飙升。因此k不是越大越好。用经典公式来计算。假设每个哈希函数都服从均匀分布那么对于一个有m位的数组插入n个元素后某个特定位仍然为0即从未被置过1的概率是p0 (1 - 1/m)^(k*n)简化估算当m很大时(1 - 1/m)^m ≈ e^(-1)所以 p0 ≈ e^(-k*n/m)。误判率大约等于一个元素查询时它对应的k个位都是1的概率也就是p ≈ (1 - p0)^k ≈ (1 - e^(-k*n/m))^k这个公式是你调参的核心依据。你先估算出n再给定一个可以接受的误判率p通常是1%或0.1%就可以反推最优的m和k。2.3 三个关键参数m、n、k的最优配置在实际项目里很少有人会像我当年那样拍脑袋选m。正确的做法是套下面这组结论位数组长度 m - (n * ln p) / (ln 2)^2哈希函数个数 k (m / n) * ln 2 ≈ 0.693 * (m / n)先说m。还是举数字如果你预期要放1亿个元素n1e8误判率p接受1%那么 m -1e8 * ln 0.01/ (0.693)^2 ≈ -1e8 * -4.6052/ 0.4805 ≈ 9.58e8换算成MB大约是114MB。如果接受0.1%的误判率m要算到大概143MB。可以看到误判率想降低一个数量级空间只增加不到25%比想象中划算。再说k。按照最优化推导当 k (m / n) * ln2 时误判率最低。同样以上面的例子m/n大约是9.58乘上0.693后k≈6.6实际取7。注意k不是越大越好超过最优值后误判率反而会回升。因为置1的位太多整个位数组会很快“变满”。所以别听人瞎说“哈希函数越多越精确”数学就是不答应。我整理一个常用速查表你在设计时可以对照着选参数预期元素量 n期望误判率 p位数组长度 m哈希函数数 k内存占用约1万1%约9.58万位712KB10万1%约95.8万位7120KB100万1%约958万位71.15MB1亿1%约9.58亿位7115MB1亿0.1%约14.4亿位10172MB看到没哪怕上亿数据内存也只占一百多MB。如果你用HashSet这个量级的对象头、哈希桶、扩容冗余加起来至少是上GB。这就是布隆过滤器最大的杀手锏。2.4 为什么标准布隆过滤器不支持删除你可能会想既然能插入为什么不能删我只要把元素对应的k个位从1改回0不就行了问题在于“错杀”。一个位可能同时被多个元素共享。你把A对应的位改成0可能顺带把B的一个位也清零了下次查B就变成“肯定不存在”制造了假阴性这可是布隆过滤器的大忌。所以标准版绝不能支持删除。那业务上确实有删除需求怎么办后面我会说“计数布隆过滤器”和“布谷鸟过滤器”这类变体。但在大多数场景我们选择“只增不删”或者通过定期重建来重置过滤器。比如黑名单添加之后很少移除URL去重后URL永远算“访问过”这类场景根本不需要删除。所以先想清楚业务特性再决定要不要上变体。3. 从零手写一个可用的布隆过滤器实现3.1 最小可用版本Python代码走一遍最直观的实现是把位数组用一个Python整数来当整数本身就是一个大位图。但为了教学清晰我用bytearray来演示每个字节8位。关键是要实现k个相互独立的哈希函数。哈希函数的数量和质量直接决定误判率。最方便的做法是使用两个“基础哈希”然后通过线性组合生成更多哈希这是计算机领域经典的“双哈希法”double hashingh_i(x) (h1(x) i * h2(x)) % m这样既保证不同哈希函数之间的独立性又不会产生太高的计算成本。代码我直接贴出来import math import hashlib class BloomFilter: def __init__(self, n, p): self.n n self.p p # 位数组长度 self.m int(-(n * math.log(p)) / (math.log(2) ** 2)) # 最优哈希函数个数 self.k int(round(self.m / n * math.log(2))) if self.k 1: self.k 1 # 位数组每个元素是一个字节8位 self.bit_array bytearray(math.ceil(self.m / 8)) def _get_base_hashes(self, item): 用md5和sha256生成两个基础哈希值 h1 int(hashlib.md5(item.encode(utf-8)).hexdigest(), 16) h2 int(hashlib.sha256(item.encode(utf-8)).hexdigest(), 16) return h1 % self.m, h2 % self.m def _positions(self, item): h1, h2 self._get_base_hashes(item) # 避免h2为0否则所有位置都落在同一点 if h2 0: h2 1 positions [] for i in range(self.k): pos (h1 i * h2) % self.m positions.append(pos) return positions def add(self, item): for pos in self._positions(item): byte_index pos // 8 bit_index pos % 8 self.bit_array[byte_index] | (1 bit_index) def __contains__(self, item): for pos in self._positions(item): byte_index pos // 8 bit_index pos % 8 # 只要有一位是0就肯定不在 if (self.bit_array[byte_index] (1 bit_index)) 0: return False return True这个实现依赖Python自带的hashlib不需要任何第三方库copy到任何装有Python3的环境都能跑。md5虽然不安全但在这里只用它的分布性不是用于密码学没有关系。注意h2如果是0会导致所有位置重合所以我对它做了个防御处理。3.2 进阶用位运算压缩内存bytearray版本好理解但内存效率其实还能再抠。Python的bytearray一个元素占一个字节8位确实没浪费。但如果你想把整个位数组一次性序列化到Redis里或者做网络传输建议把位数组转成bytesRedis的SETBIT/GETBIT天然支持位操作。如果你要处理特别大的规模比如百亿级数据这时候Python的bytearray会有点吃力。更专业的做法是用bitarray库它把位数组封装成连续的内存块支持切片、序列化性能比bytearray操作位还要好。安装只需要pip install bitarray用法也很简单from bitarray import bitarray bit_array bitarray(m, endianlittle) bit_array.setall(0) def set_bit(pos): bit_array[pos] 1 def get_bit(pos): return bit_array[pos]不过说实话在业务系统里我更推荐直接使用Redis的Bitmap或者现成的Bloom Filter模块。自己实现主要是为了理解原理到了生产环境稳定性比“亲手写的浪漫”重要得多。3.3 工程化落地如何选型与序列化如果你在Java后端Google Guava里面有一个BloomFilter类支持传入Funnel序列化和自定义误判率比较适合单机场景。如果你想要分布式共享Redis 4.0之后官方提供了bf模块Bloom Filter Module客户端直连Redis就能操作它内部已经帮我们实现了最优参数。另外像Redisson这个Java客户端也封装了RBloomFilter使用上和操作普通Redis对象一样不需要关心底层位数组在哪台机器。序列化这块有一个常见坑布隆过滤器的位数组在扩容或迁移时不能简单地把两个过滤器“或”一下。因为两个过滤器的m和k可能不同位数组的语义完全不同。正确做法是保存构造参数n、p、k、m以及位数组本体序列化成二进制后整体迁移。否则等你迁移完业务方会反馈说“这个过滤器疯狂误判”。3.4 实测误判率给出一组真实数据为了演示参数的影响我用上面那段代码做了一组简单测试先往过滤器里插入20万个随机字符串再用另外20万个从未出现过的随机字符串去查询观察被误判成“存在”的数量。以下是我的实测数据受随机数影响每次略有波动预算误判率 p实际位数 m哈希函数 k实际误判数量实际误判率5%约125万位5约9031个4.52%1%约191万位7约1906个0.95%0.1%约287万位10约238个0.12%可以看到实际误判率和公式预测值基本一致误差主要来自哈希函数的随机性和样本量。这组数也回答了一个常见问题“误判率可以调成0吗”理论上有极限你需要无限大的m和无限多的哈希函数工程上根本做不到。所以别纠结“完全准确”你要做的是让误判率低到对业务无感。4. 应用场景从缓存穿透到分布式系统4.1 缓存穿透布隆过滤器的最经典主场回到文章开头说的缓存穿透。当请求的数据ID在缓存和数据库里都不存在时每次都会打穿到数据库。布隆过滤器应该放在哪一层我在生产中的做法是在应用启动时把所有“可能存在”的ID全部加载到一个布隆过滤器单机用Guava多机共享用Redis然后每个查询请求来的时候先判断布隆过滤器说“不存在” → 直接返回空不再访问缓存和数据库。布隆过滤器说“存在” → 继续查Redis如果打空再去查数据库并回填缓存。这里还有一个很容易被人忽视的点误判的那一小部分请求依然会打到数据库但占比只有你设置的误判率比如1%。也就是说你以为数据库压力会归零实际上还有1%的漏网之鱼。如果你的系统扛不住1%的穿透那你要么把误判率调低到0.1%要么再叠加一个短暂的空值缓存来兜底。两种手段结合数据库基本就清静了。4.2 爬虫去重与URL过滤爬虫系统里最常见的问题就是“这个URL我抓过了吗”。如果把这些URL全部存到数据库里每抓一条都去查一次数据库会被查询淹没。用哈希集合存内存几亿条URL也扛不住。布隆过滤器在这里的优势是空间占用极低。我曾经为一个垂直爬虫项目做过一次改造原来用Redis Set存URL占用大概3.2GB内存换成Bloom Filter后内存降到约300MB虽然牺牲了一点“去重的绝对准确性”但只是偶尔会有一个URL被当成“已抓过”而跳过对爬虫业务来说完全无伤大雅。注意爬虫场景有一个小优化如果你不想漏抓任何页面可以把“抓过的URL”放到布隆过滤器里针对“判断为已抓取”的URL再额外查一次数据库做二次确认。这样布隆过滤器负责过滤掉绝大多数重复数据库只处理少数疑似重复既快又准。4.3 数据库系统里的布隆过滤器其实你每天都在不知不觉中使用布隆过滤器。LevelDB和RocksDB的LSM-Tree在查SSTable之前会先查一个内嵌的布隆过滤器用来快速判断键是否存在于这个SSTable中。如果过滤器说“不在”就跳过整个文件极大地加速了磁盘查找。Cassandra、HBase这类NoSQL也一样它们在内存维护布隆过滤器查询时先用它筛掉一批不包含目标键的SSTable减少不必要的磁盘IO。为什么数据库偏爱布隆过滤器因为磁盘随机读的开销太高了一次没必要的读可能就是10毫秒而布隆过滤器的判断只需要几百纳秒到几微秒还能省掉大量IO。这种“用一点内存换大量磁盘IO”的性价比高得惊人。4.4 其它进阶用法向量索引、日志过滤等布隆过滤器的应用并不是只有“存在性判断”。在向量检索里有一些论文讨论如何用它的变体做近似最近邻搜索的预处理先把肯定不在候选集里的桶过滤掉。在日志系统里可以用它快速过滤掉重复的日志模板只保留第一次出现的模板避免重复打点。在分布式系统中它还经常用于“消息是否已处理”的去重判断配合幂等表使用减少对数据库的重复写入压力。另外如果你想统计“一个集合里有多少个不同元素”可以把布隆过滤器和HyperLogLog结合在一起。布隆过滤器判断元素是否出现过HyperLogLog估算不重复元素的个数。我见过一些用户增长分析系统就是用这套组合搞定亿级UV统计的。5. 使用布隆过滤器最容易踩的坑5.1 忽略误判率对业务的真实影响很多新手一上来就照抄网上的代码参数全用默认结果上线后突然发现“数据对不上了”。原因就是没想清楚误判率带来的业务影响。比如说你在做一个交易反欺诈黑名单如果布隆过滤器把某个正常客户误判成黑名单直接拒绝了他的交易这属于“误杀”影响极大。这种场景你就不应该直接把布隆过滤器当成唯一判断依据而是应该在它判定“存在”后再去精准的黑名单数据库里做二次校验。布隆过滤器只负责“加速发现风险”不负责“最终定罪”。5.2 把布隆过滤器当成“可删除集合”就像前面讲的标准布隆过滤器不支持删除。你要是真直接在位数组上删位就会制造假阴性。一个真实案例有团队用Redis的BITFIELD BITOP实现布隆过滤器后来需要支持“取消关注”功能直接把关注关系ID的位清空结果很多用户关注列表出现了数据缺失。最后只能把过滤器推倒重建。如果你确实需要删除语义可以考虑计数布隆过滤器每个位置不再是一个bit而是给一个计数器。插入时计数器1删除时计数器-1只有当计数器减到0时才把该位置“视为空”。当然计数器会占用更多空间还需要防溢出。5.3 哈希函数设计不当导致性能腰斩一个布隆过滤器的性能很大程度取决于哈希函数。如果你用的哈希函数质量差比如很多简单字符串哈希出现大量碰撞会导致某些位被过度集中置1误判率飙升。更隐蔽的问题是哈希函数设计成了“有偏分布”某些位置几乎永远不会被用到浪费了位数组空间。正确做法是选用md5、sha256、murmur_hash这类分布均匀的哈希函数作为基础哈希再用双哈希法生成k个哈希。切忌自己写什么“简单取模加个随机数”的哈希函数。另外如果业务数据有明显的模式比如所有ID都以同一个前缀开头直接哈希整个字符串也能做到均匀前提是哈希函数本身够散列。5.4 多节点部署时遗漏同步问题单机布隆过滤器很好理解但一旦部署到多台应用服务器问题就来了每台服务器各自持有自己的布隆过滤器实例插入操作只写到了其中一台的过滤器上其他节点的过滤器并不知道这个“新元素”导致同一个元素在A节点判断“存在”在B节点却判断“不存在”业务数据就变得不一致。解决办法有三种一是用Redis等中心化存储保存同一个布隆过滤器所有应用节点共享二是定期重建并分发过滤器快照比如每天凌晨从数据库重建一次分发到各节点三是使用支持合并的布隆过滤器比如把位数组“OR”起来但要保证所有节点的m、k完全一致。如果最初设计的m和k不一样OR合并出来的东西是什么是垃圾。所以扩容的时候也要小心绝不能简单地把两个不同参数的过滤器合并。5.5 扩容迁移时的不归路布隆过滤器一旦初始化就很难动态扩大位数组。你预计要放1亿条但业务涨得比你预期快半年后变成3亿条。这时候误判率会随着n的增大而急剧上升因为位数组“满”了。你该怎么办暴力一点的办法是“翻倍重建”申请一个新的大过滤器把旧过滤器里的数据重新插入进去再切换。这个重建过程可能耗时较长但好在布隆过滤器本身没有复杂索引只要遍历旧数据源重新塞一遍就行。如果旧数据量实在太大比如几百亿重建靠单机跑不动你可以用MapReduce或Spark分批重建每批插入一部分最终合并。还有一个更聪明的办法叫可扩展布隆过滤器Scalable Bloom Filter它由一组“互为备份”的布隆过滤器组成。写入时先尝试写入最后一个过滤器如果它已经太满就新建一个更大参数的过滤器查询时对所有子过滤器逐个查。这思路有点像分段日志平滑扩容代价是查询变慢一点因为要查多个小过滤器。如果业务增长预期很强我建议一开始就设计成这种方式别等到线上报警再救火。6. 扩展思考从布隆过滤器到更多近似结构6.1 计数布隆过滤器支持删除的折中方案之前我提到计数布隆过滤器这里展开一下原理。它把每一位变成一个计数器比如用4个bit表示0~15个计数。插入元素时对每个哈希位置对应的计数器1删除时-1查询时判断对应计数器是否大于0。它解决了“不能删除”的问题但代价是空间容量变成原来的数倍而且计数器仍然有溢出风险一旦多个元素共享同一个位置导致计数器超过上限删除时同样可能出现假阳性或假阴性。在实现时最好定期“压缩”计数器或者直接拒绝删除逻辑只在内存中做临时用途。6.2 布谷鸟过滤器更高空间利用率的替代如果你对空间和误判率都很敏感可以了解一下布谷鸟过滤器Cuckoo Filter。它的思路是每个元素存一个指纹fingerprint位置由两个哈希函数决定如果位置冲突就把原有元素“挤走”到它的另一个候选位置类似布谷鸟占巢。布谷鸟过滤器支持删除空间效率有时候比标准布隆过滤器还高误判率在元素数量接近设计容量时会变得不可控需要预留足够余量。我自己在业务上用过一次当时是为了给一个“短连接黑名单”加删除功能布谷鸟过滤器表现不错。但它实现起来比布隆过滤器复杂踩坑概率更大除非确实需要删除语义否则我还是推荐先用标准版。6.3 与HyperLogLog结合去重与基数估计在企业级数据系统里布隆过滤器常常和基数估计算法配合。布隆过滤器负责“元素是否出现过”的判断HyperLogLog负责“有多少个不同元素”的统计。两者都用极低的内存应对海量数据。我有一个实时监控系统每秒要处理几十万条日志其中既有“这条日志是否已经见过”的去重要求又有“当前一小时内有多少个唯一用户”的统计需求。于是我在内存里放了一个布隆过滤器 一个HyperLogLog两个结构加起来不过几十KB就撑住了整条日志流的初步处理。6.4 最后的小建议如果你准备在下一个项目里引入布隆过滤器我建议你做三件事第一拿出半天时间把原理公式自己推导一遍不要只背结果第二写一个最简单的demo用真实业务数据跑一跑看看误判率和内存是否符合预期第三确定好是否需要删除语义是否需要扩容然后再选具体实现方案。布隆过滤器不是银弹但在“存在性判断”这个场景里它确实是我用得最顺手的一个数据结构。我个人在实战中还有一个习惯线上布隆过滤器的误判率我会配一个监控报警比如每秒实际误判次数超过阈值就提醒。这样万一数据量增长导致误判率恶化我能第一时间感知到。很多人把这个东西当成“定死的配置”其实它和缓存命中率一样应该是一个持续观察的健康指标。希望这篇博客能帮你真正掌握布隆过滤器而不是只听到一个名词。