Bloom Filter

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于快速判断一个元素是否可能属于某个集合。它允许一定的误判率（False Positive），即可能将不在集合中的元素误判为存在；对于已成功插入且状态未被破坏的元素，不会产生假阴性（False Negative）。这项保证针对过滤器内部记录的集合，不代表它天然与数据库实时一致。

布隆过滤器广泛应用于需要在海量数据中快速排除“绝对不存在”情况的场景，例如：缓存穿透防护、URL 去重、数据库查询优化、恶意请求拦截等。

⚙️ 基本原理

布隆过滤器的核心思想是：把元素映射到位数组中的多个位置，通过这些位置的状态判断它是否可能属于集合。

数据结构组成

• 位数组（Bit Array）：长度为 m 的二进制数组，初始所有位都为 0
• 哈希映射：每个元素对应 k 个哈希位置，通常通过基础哈希值派生，位置范围为 [0, m-1]；理论分析假设映射独立且均匀

工作流程

Mermaid 对照图：以 10 位数组、3 个哈希位置为例，下面的位置为演示指定值。

两个已插入元素共享第 5 位；cherry 的三个位置由其他元素共同覆盖，因此只能判断“可能存在”。

1. 添加元素（Insert）

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

• 使用 k 个哈希函数分别计算该元素的 k 个哈希值
• 将位数组中对应 k 个位置的值设为 1

注意：多个元素可能共享同一位，因此位只能从 0 → 1，不可逆。

2. 查询元素（Lookup）

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

• 使用相同的 k 个哈希函数计算该元素的 k 个哈希值
• 检查位数组中对应的 k 个位置是否都为 1
  • 如果全部为 1：元素可能存在（有误判可能）
  • 如果任意一个为 0：元素一定不存在

关键特性：为什么返回“不存在”时可以排除元素？

✅ 不会漏报（False Negative）

• 如果元素已经成功插入当前过滤器，查询结果一定是“可能存在”
• 因为添加元素时已经将对应的位设为 1，后续查询时这些位仍为 1

❌ 可能误报（False Positive），假阳性

• 如果元素不存在于集合中，但查询结果显示"存在"
• 原因：其他元素的哈希映射恰好覆盖了该元素的所有哈希位置

哈希位置的独立性与工程实现

理论模型假设各次映射独立且均匀，以便估算位数组的占用与误判率；工程上不必分别计算 k 次完整哈希。Kirsch 与 Mitzenmacher 的双重哈希研究表明，使用两个基础哈希派生多个位置，可以保持相同的渐近误判率。

应关注位置分布和实际误判率，不能仅凭“用了多个哈希函数”判断实现质量。

时间复杂度和空间复杂度

• 时间复杂度：插入和查询的时间复杂度均为 O(k)（k 为哈希位置数量）；若计入变长输入的哈希成本，还取决于输入长度。
• 空间复杂度：O(m)，位数组大小

其中 k 通常很小（如 3～7），因此实际性能接近常数时间。

不可逆，不可删除元素

传统布隆过滤器不支持删除操作，因为：

• 多个元素可能共享同一位；
• 若将某位置 1 → 0，可能清除其他元素仍需要的标记，造成假阴性。

变种方案：计数布隆过滤器（Counting Bloom Filter）使用计数器替代位，支持删除，但空间开销更大。

位数组没有保存元素本身，因此也不能从过滤器还原或枚举原始元素。

数学分析

误判率计算

假设：位数组长度：m，哈希函数数量：k，已插入元素数量：n

在独立、均匀映射的近似模型下，最优参数和误判率估算如下，推导放在文末：

最优哈希函数数量：

$$k_{\text{opt}}=\frac{m}{n}\ln (2)$$

连续最优参数下的误判率估算：

$$p_{min}\approx {\left(0.5\right)}^{k_{\text{opt}}}\approx {\left(0.6185\right)}^{\frac{m}{n}}$$

对于给定的 m、k、n，常用的误判率近似公式为：

$$p\approx {(1-e^{-\frac{kn}{m}})}^k$$

给定预估的不同元素数量 n 和目标误判率 p，可以反推位数组长度 m：

$$m=-\frac{n\ln p}{(\ln 2{)}^2}$$

m 需要向上取整，k 应取相邻正整数比较误判率；下面的容量表使用连续最优值估算。重复插入同一个元素不会增加新的标记，容量规划中的 n 指不同元素数量。

可以看出：m 与 n 成正比（线性关系），但比例系数由 p（误判率）决定

$$\frac{m}{n}=\frac{-\ln p}{(\ln 2{)}^2}\approx \{\begin{array}{ll}9.58& p=1\mathrm{\%}\\ 14.38& p=0.1\mathrm{\%}\\ 19.16& p=0.01\mathrm{\%}\\ 4.80& p=10\mathrm{\%}\end{array}$$

所以，每个元素平均占 ~9.6 个 bit（1% 误判率），可以近似为 10 bit/元素

1 亿个不同元素，$n=1\times {10}^8$，仅位数组的内存估算如下。本文 MB 按 ${10}^6$ 字节计算，MiB 按 $2^{20}$ 字节计算：

目标误判率 ($P$)	所需位数 $m$ (bit)	内存 (MB)
0.01% (0.0001)	$\approx 19.16\times {10}^8$	≈ 240 MB
0.1% (0.001)	$\approx 14.38\times {10}^8$	≈ 180 MB
1% (0.01)	$\approx 9.58\times {10}^8$	≈ 120 MB
10% (0.1)	$\approx 4.80\times {10}^8$	≈ 60 MB

✅ 实际工程取舍

• 误判率由后续操作成本决定：1% 可以作为估算起点；若一次误判需要昂贵的磁盘读或远程请求，应比较降低误判率增加的内存和减少的后端开销。
• 容量必须覆盖不同元素数量：按增长预留容量；固定过滤器超过预估容量后，误判率会上升，不能继续承诺初始目标。Go 库说明
• 理论位数组不等于实例总内存：还需计入字对齐、对象元数据，以及多层过滤器、重建副本等开销，实例总内存应以具体实现测量为准。

📌 固定过滤器按 100 万元素、1% 误判率配置，取 k = 7；插入量翻倍后，代入公式得到误判率约 15.7%。容量失控会直接放大后续查库或读盘压力。

示例演示

下面的位置是为演示手工指定的，不对应某个真实哈希函数的输出；数组从下标 0 开始。假设我们有：

• 位数组长度 m = 10
• 哈希函数数量 k = 3
• 初始状态：[0,0,0,0,0,0,0,0,0,0]

添加元素 "apple"：

• hash1("apple") = 2
• hash2("apple") = 5
• hash3("apple") = 8
• 更新后：[0,0,1,0,0,1,0,0,1,0]

添加元素 "banana"：

• hash1("banana") = 1
• hash2("banana") = 5
• hash3("banana") = 9
• 更新后：[0,1,1,0,0,1,0,0,1,1]

查询元素 "orange"：

• hash1("orange") = 2 → 位2 = 1 ✓
• hash2("orange") = 5 → 位5 = 1 ✓
• hash3("orange") = 7 → 位7 = 0 ✗
• 结论："orange" 一定不存在

查询元素 "cherry"：

• hash1("cherry") = 1 → 位1 = 1 ✓
• hash2("cherry") = 8 → 位8 = 1 ✓
• hash3("cherry") = 9 → 位9 = 1 ✓
• 结论："cherry" 可能存在（此例只插入了 apple 和 banana，cherry 没有被插入，因此这是一次假阳性）

优缺点

优点

• 空间效率高：相比存储实际元素，只需要位数组
• 查询速度快：O(k) 时间复杂度，k通常很小
• 支持大规模数据：适合处理海量数据的成员查询

缺点

• 存在误判率：无法完全避免假阳性
• 不支持删除操作：传统布隆过滤器无法安全删除元素（因为多个元素可能共享同一位）
• 无法获取元素列表：只能判断存在性，不能枚举所有元素

代码实现

Bloom Filter 与 BitSet 的分工

Bloom Filter 负责把元素映射为多个位下标，并解释查询结果；BitSet 负责紧凑、精确地存储和读写这些位。 BitSet 可以作为 Bloom Filter 的底层存储，两者不是并列的两道过滤步骤。

职责	Bloom Filter	BitSet
接收什么	原始元素，如 "apple"、用户 ID	非负整数位下标，如 2、5、8
参数与布局	根据预计元素数 n 和目标误判率 p 选择位数 m、哈希数量 k	将 m 个标记压入字节或机器字，如每个 uint64 保存 64 位
插入	计算元素的 k 个位置，调用底层置位操作	将指定位置设为 1，不关心这个位置来自哪个元素
查询	计算同一组位置；任一位为 0 则排除，全部为 1 则可能存在	精确回答“第 i 位是否为 1”，不解释原始元素是否存在
误判来源	不同元素的哈希位置发生重叠，可能产生假阳性	位下标读写本身没有概率误判

沿用前面的演示，插入 apple 时，Bloom Filter 算出 2、5、8，再调用 BitSet 的 Set(2)、Set(5)、Set(8)。查询 cherry 时，Bloom Filter 算出 1、8、9，调用对应的 Test；BitSet 精确返回三个 true，Bloom Filter 据此给出“可能存在”。假阳性发生在从这些位推断元素归属的过程中。

如果业务 ID 本身就是范围可控的非负整数，也可以直接用 BitSet 的第 id 位表示该 ID 是否存在，得到精确的成员判断。Bloom Filter 用哈希把更大、甚至非整数的键空间压缩到固定的 m 位中，以假阳性换取空间。 稀疏且跨度很大的 ID 直接作为位下标，可能需要很长的 BitSet。

两者的能力边界也不同：

• 删除：BitSet 通常提供 Clear(i)，但普通 Bloom Filter 不能用清位删除元素，因为该位可能仍被其他元素共享。
• 扩容：BitSet 即使支持增加位数，也不等于 Bloom Filter 可以直接扩容；修改映射范围 m 后，需要重新处理旧元素的位置。
• 并发：组合本身不提供线程安全。底层普通读写需要同步，并且锁或原子访问的设计还要覆盖一次 Bloom 操作的可见性要求。

本文 Go 库的 BloomFilter 结构及 Add、Test 实现就持有一个 *bitset.BitSet，在计算位置后调用其 Set、Test。Python 示例中的 bytearray 与位运算承担相同的存储职责，只是没有单独封装成 BitSet 类。

Go：使用成熟库

Go 示例使用 github.com/bits-and-blooms/bloom/v3，固定版本为 v3.7.0。它用位集合存储标记，但位数组只能表示成员关系，不能替代存储原始数据的数据库。

在独立示例目录初始化模块，再把下面代码保存为 main.go：

go mod init example.com/bloom-demo
go get github.com/bits-and-blooms/bloom/v3@v3.7.0
go run .

package main

import (
    "fmt"

    "github.com/bits-and-blooms/bloom/v3"
)

func main() {
    filter := bloom.NewWithEstimates(1_000_000, 0.01)
    filter.AddString("user:42")

    fmt.Println(filter.TestString("user:42")) // 已插入，必定为 true
    fmt.Println(filter.TestString("user:99")) // 未插入，仍可能为 true
    fmt.Printf("m=%d bits, k=%d\n", filter.Cap(), filter.K())
}

NewWithEstimates(n, p) 接收预计元素数量和误判率；New(m, k) 才接收位数和哈希数量。混用两组参数会得到与预期不同的容量。

Python：标准库实现

下面的固定容量实现适用于 Python 3.10+，使用 bytearray 存储位数组，无需安装第三方依赖。每个字节存储 8 个标记；n 和 p 分别表示预计不同元素数和目标误判率，实际误判率仍需结合输入验证。

使用 hashlib.blake2b 的 person 参数区分各次映射，便于对应前面的多哈希模型。这里每个位置计算一次完整哈希，侧重展示原理；哈希成本和全局锁都会影响吞吐。

import math
from hashlib import blake2b
from threading import Lock

class BloomFilter:
    def __init__(self, n: int, p: float = 0.01) -> None:
        if n <= 0 or not 0 < p < 1:
            raise ValueError("require n > 0 and 0 < p < 1")
        self._m = math.ceil(-n * math.log(p) / math.log(2) ** 2)
        self._k = max(1, round(self._m / n * math.log(2)))
        self._bits = bytearray((self._m + 7) // 8)
        self._lock = Lock()

    def _positions(self, value: str) -> tuple[int, ...]:
        data = value.encode("utf-8")
        positions = []
        for i in range(self._k):
            digest = blake2b(
                data, digest_size=8, person=i.to_bytes(16, "little")
            ).digest()
            positions.append(int.from_bytes(digest, "little") % self._m)
        return tuple(positions)

    def add(self, value: str) -> None:
        positions = self._positions(value)
        with self._lock:
            for pos in positions:
                self._bits[pos // 8] |= 1 << (pos % 8)

    def contains(self, value: str) -> bool:
        positions = self._positions(value)
        with self._lock:
            return all(
                self._bits[pos // 8] & (1 << (pos % 8))
                for pos in positions
            )

if __name__ == "__main__":
    bloom = BloomFilter(n=1_000_000, p=0.01)
    bloom.add("user:42")
    print(bloom.contains("user:42"))  # True：已插入
    print(bloom.contains("user:99"))  # 未插入，仍可能返回 True

保存为 bloom_demo.py，运行：

uv run --no-project --python 3.12 bloom_demo.py

插入和查询采用同一把锁，保护完整的多位置读写。 哈希计算在锁外完成，构造后的参数保持不变。它支持同一进程内多个线程共享实例，不提供跨进程共享，也不支持删除、自动扩容或持久化。

Python 对字符串和字节串的内置 hash() 默认带有进程随机化；如果后续要保存或跨进程交换过滤器，必须固定哈希算法、参数、编码和位序，并保存容量参数。这里的 Python 与前面的 Go 库采用不同哈希方案，位数组不能互换。

在同目录新建 bloom_threads.py，可验证共享实例的并发读写：

from concurrent.futures import ThreadPoolExecutor

from bloom_demo import BloomFilter

bloom = BloomFilter(n=20_000, p=0.01)

def insert_and_check(i: int) -> None:
    key = f"user:{i}"
    bloom.add(key)
    assert bloom.contains(key), f"missing inserted key: {key}"

with ThreadPoolExecutor(max_workers=8) as pool:
    list(pool.map(insert_and_check, range(10_000)))

assert all(bloom.contains(f"user:{i}") for i in range(10_000))
print("10,000 个已插入元素均可查到")

运行 uv run --no-project --python 3.12 bloom_threads.py。这个检查验证给定输入下已完成写入的可见性；多线程示例不代表吞吐提升，两个方法分别加锁也不保证“先查询再插入”的复合操作原子化。

🎯 应用场景

选型时应先确定过滤器记录的是哪个集合，以及误判会触发什么后果。假阳性是否可接受，取决于业务动作，不能仅凭误判率很低就忽略影响。

场景	过滤器记录的集合	返回“不存在”	返回“可能存在”
缓存穿透防护	已同步的合法 ID	状态可信时直接返回不存在	继续查缓存和数据库
URL 去重	已抓取或已调度的 URL	加入抓取流程	二次查重，或接受跳过新 URL 的风险
存储文件过滤	文件内的键或键组合	跳过当前文件	继续查索引或读取文件
注册预检查	已注册的手机号	可以尝试写入	查库确认，避免误拒新用户
黑名单预检查	已收录的风险标识	当前集合中没有记录	进入精确匹配或二次验证

缓存系统：Redis 缓存穿透防护

过滤器放在请求访问路径上，记录合法用户 ID。只有“过滤器覆盖当前可查询数据”这一条件成立时，负结果才可以直接结束请求。

容量算例：5000 万个不同 ID，目标误判率 0.1%，按前文公式，位数组约为 89.9 MB（85.7 MiB）。这只是容量估算，不代表某个线上系统的实测结果。

常见的读请求链路是 Bloom Filter → Redis 缓存 → 数据库：过滤器先排除不可能存在的 ID，缓存承接重复读取，数据库负责精确查询和最终数据。过滤器未就绪或同步状态不可信时，需旁路过滤器；下面将这条回退路径也画出。

“可能存在”只表示继续查询，不代表缓存或数据库一定有数据。 图中的空值标记需要与正常数据、缓存未命中区分；过滤器删除遗留的标记或假阳性，都可能使请求走到数据库后发现记录不存在。

图中只展开成功读取的分支：缓存超时或连接错误不能当作普通未命中，无条件回源会放大数据库压力；应按限流、熔断和降级策略处理。数据库查询失败也不能缓存为“不存在”。回填缓存失败时，可按策略返回已查到的数据并记录失败。

过滤器的 0.1% 误判率，表示未插入元素中预计约 0.1% 会命中，不表示总请求中只有 0.1% 会查库。 实际数据库请求还受有效 ID 比例、缓存命中率和流量分布影响。

• 新增同步：数据库记录可见、过滤器尚未更新的窗口内，负结果不能作为拒绝依据。单靠提交后异步更新无法消除这一窗口，需设计可见性协调、增量兜底或可信状态回退。
• 初始化：全量加载和增量追平完成后再标记就绪；空过滤器不能直接承接拦截请求。
• 删除：普通过滤器保留已删除 ID 的标记，只会增加无效查库；通过周期重建清理，不直接清位。
• 故障：过滤器丢失、读取失败或同步落后时，回退路径仍要受限流与并发上限保护，避免把流量全部压向数据库。
• 缓存错误：redis.Nil 表示未命中，连接错误与超时应单独处理；空值缓存也需要过期策略和新建数据后的失效处理。

爬虫系统：URL 去重

用 Bloom Filter 直接决定跳过 URL，会把假阳性转化为漏抓。 这不违反过滤器“没有假阴性”的性质：新 URL 被误判成“已抓取”，业务动作恰好是跳过它。

• 允许少量漏抓的探索性任务，可以用过滤器直接去重，但应说明接受的损失。
• 要求完整采集的任务，应在“可能存在”时查询精确集合；此时过滤器仅用于减少对新 URL 的无效查询。
• URL 规范化必须在插入和查询时保持一致，否则同一资源可能被当作不同输入。

定期重置只能清空历史记录，不能保证恢复之前漏抓的 URL；补抓还需要独立的来源列表与调度机制。并发调度还要处理“查询后再插入”的竞争，两个调用各自线程安全，也不等于整个去重决策原子化。

数据库：按存储文件过滤

不可变存储文件适合在写出时构建过滤器、读取时只查询。以 HBase 为例，BloomType支持按行键（ROW）或行键与列组合（列族、列限定符，ROWCOL）等方式构建过滤器。

过滤器排除的是当前文件中的候选键，不是直接跳过整个 Region。 某个文件返回“不存在”，只能省略该文件对应的后续读取；还需考虑其他文件及内存中的数据。

收益取决于负查询比例、候选文件数、过滤器命中缓存的情况，以及一次文件读取的成本，不能给出脱离负载条件的固定提速比例。

账号系统：注册预检查

过滤器记录已注册手机号。返回“不存在”时可尝试插入；返回“可能存在”时需要精确确认，不能直接拒绝。

1% 的误判率只作用于未插入的手机号；对已经插入的手机号，查询一定命中。 因此它减少的是新手机号的存在性预查询，已注册手机号仍会进入精确校验路径。最终并发唯一性由数据库唯一索引保证，即使过滤器同步滞后，也不能允许重复注册成功。

黑名单等风险场景同样应区分“已收录集合中不存在”和“现实中没有风险”，过滤器无法识别从未收录的恶意对象。

🛠️ 工程实践与选型

下面区分团队公开案例、产品文档和社区教程。案例说明当时的业务取舍，产品参数只适用于对应实现；不能把社区文章发布在某厂商平台上，等同于该厂商内部系统的实践。

vivo：推荐去重的写入汇聚与平滑迁移

vivo 团队 Zhang Wei 的《短视频推荐去重服务的设计实践》公开了比 API 调用更完整的工程过程。原方案用 Redis ZSet 保存观看历史，改造后用磁盘 KV 保存 Bloom 数据，并保留近期下发记录以弥补埋点上报延迟。

工程问题	案例中的处理
每条播放事件都读改写 Bloom，磁盘写入压力大	Redis 暂存播放记录，再通过分片定时任务汇聚写入
批处理之前，历史过滤器尚未覆盖新观看记录	查询同时使用尚未归档的暂存数据
普通 Bloom 无法逐条删除过期观看记录	按月保存，查询覆盖业务窗口的多个自然月，打散物理过期时间
首次请求触发历史迁移导致延迟不稳	将迁移纳入后台批处理；迁移期间增量双写以保留降级能力

这个案例值得借鉴的是把实时增量、归档数据和迁移任务分开处理。具体时间窗口与任务分片数依赖业务，不应当成通用默认值；有界历史以外的记录不再承诺去重。

MaxCompute：索引聚合失败时，保留低一层的过滤能力

阿里云MaxCompute Bloomfilter index 文档说明，新增数据先生成文件本地索引，再聚合为可供规划阶段裁剪文件的索引。聚合失败不阻断数据写入，本地索引仍可参与存储层过滤；需要时对受影响分区执行 REBUILD BLOOMFILTER INDEX。

索引维护失败时，丢失的是一部分加速能力，不能把新增数据直接排除。 在该产品支持范围内，可通过 Logview 的 BloomFilterAutoMergeTaskInfo 检查聚合状态，再用执行计划确认是否使用规划阶段裁剪。文档还提示，裁剪效果差时，多出来的索引任务可能拖慢查询。上线验证应同时看维护任务与查询总成本。

美团：用过滤器缓解空值缓存的空间压力

美团技术团队在 2017 年的《孵化业务快速落地与优化》中介绍，海外酒店列表需要查询酒店最低价，但部分酒店在某些时期没有可售产品。早期通过缓存无值结果防止反复回源，随着数据量增长，这些缓存占用了较多空间，后续引入 Bloom Filter 优化。

这类场景的起点是“无数据查询多、空值缓存贵”，不一定是恶意攻击。 对本文链路的启发是：先观察负查询的数量与分布，再决定是否引入过滤器。少量热点无效 ID 适合短 TTL 空值缓存；大量不同的无效 ID 才更需要比较过滤器的空间收益。后两项是基于机制的选型判断，不是原文给出的压测结论。

案例没有给出可直接复用的误判率、同步协议或收益比例，不能据此承诺固定的性能提升。酒店从无产品变为有产品时，仍需要解决过滤器更新和可见性问题。

阿里云 TairBloom：提前规划容量，减少多层扩容

阿里云开发者社区的《已经触碰到 Redis 的性能边缘？》介绍了 TairBloom 的产品用途；具体部署取舍应以TairBloom 官方文档为准。它采用可扩展结构，查询可能遍历多个子过滤器，自动扩容会增加内存与查询成本。

• 主动初始化：预计元素很多时，通过 BF.RESERVE 明确容量与误判率，避免从 BF.ADD 隐式创建的小容量实例不断扩容。
• 监控层数和内存：通过 BF.INFO 等实现提供的统计接口观察容量、插入量、层数及空间占用，把自动扩容作为兜底而非容量规划方式。
• 控制单键规模：必要时按业务域拆分或规划轮转；轮转时仍须覆盖业务要求保留的集合，不能直接丢弃旧过滤器而遗漏有效数据。

这些参数和命令应核对实际实例支持范围；TairBloom 的层容量、内存增长规则不能推广成所有 Bloom 实现的统一规则。

腾讯：按需求选择哈希方案与过滤器变种

腾讯技术工程官方号发布的《经典论文解读——布隆过滤器》由 PCG 工程师撰写，结合论文及 Go 组件讨论哈希派生、计数型和可扩展型结构。它适合作为设计分析资料，不应包装成带有业务收益指标的线上案例。

对实现的直接启发是：计算多个位置时，先考虑分布均匀、计算成本较低的哈希与派生策略；需要删除时评估计数结构，需要增长时评估多层结构。本文 Python 示例逐位置计算 BLAKE2 主要用于展示机制；若压测发现哈希成本占主导，可评估成熟实现或双重哈希，并重新验证误判率、并发语义和数据兼容性，而不是只替换函数名。

火山引擎：过滤器也可以部署在数据库内部

ByteHouse 高并发点查询调优最佳实践建议对高基数字符串查询键评估 Bloom 跳数索引；它用于排除不含目标值的数据颗粒，假阳性的代价是额外读取候选数据块，最终结果仍由精确查询决定。

这里优化的是读取的数据块数量，而不是替代业务层缓存。 从这一机制可以推断：应比较查询前后的读取行数、读取字节和耗时，并使用代表性的等值查询验证；范围查询不能机械照搬同一索引选择。索引粒度、数据分布和过滤率会共同影响收益。

火山引擎的ExBloomFilter 产品文档则描述了缓存侧可扩展过滤器，属于另一部署位置，需核对数据库、Proxy 和 Server 版本要求。开发者社区的Scrapy 分布式爬虫教程展示了 RabbitMQ 队列与 RedisBloom 去重的集成方式；它是作者的集成教程，不是字节内部生产规模的证明。是否允许假阳性导致漏抓，仍由采集完整性要求决定。

Join 运行时过滤：为一次查询临时构建集合

阿里云社区刊载的《Apache Doris Join 实现与调优实践》来自 Doris Contributor 的分享，介绍了将 Build 侧连接键生成的 Bloom Filter 下推到 Probe 侧扫描节点的做法。ByteHouse CDW 调优文档也介绍了这种运行时过滤方式。

例如，先筛出“参加本次活动的用户”，用这些用户 ID 构建过滤器；扫描订单表时，提前排除不可能属于这些用户的订单。通过过滤器的订单仍要执行精确 Join，假阳性只增加候选处理成本。 这是机制示例，不是上述厂商的具体业务案例。

TDSQL Boundless Runtime Filter 文档给出了更明确的实现边界：V21.6.4.0 起支持，要求满足其 Hash Join、连接类型及 TDStore 引擎等条件；估计收益不足时不启用，构建规模超出预估或探测效果过差时还会放弃过滤。外连接和反连接不能直接照搬内连接的提前丢弃规则。

实践中应核对执行计划是否出现 Runtime Filter、实际过滤行数和整体耗时。过滤器的构建、传输和等待也有成本；大部分记录都能匹配时，额外过滤可能得不偿失。不要把旧文章中的默认开关、阈值或左右表位置直接套用到其他产品和版本。

腾讯 TDStore：在固定总内存下调整各层过滤能力

腾讯云 2026 年的Monkey Bloom Filter 调优文档介绍了 TDStore/RocksDB 在 Leveled Compaction 下的分层内存分配：不同 LSM 层使用不同的 bits per key，而不是每层都分配相同的单位键内存。

优化目标是减少一次点查在各层累计产生的无效检查。 上层数据较少，可以用较少的总内存提高过滤能力；下层数据量更大，则需要控制其总预算。文档也指出，新增键写入前的主键存在性检查可能因此受益，但这不等于优化了所有写入路径或范围扫描。

对本文容量规划的启发是：有多个独立过滤器时，应按数据规模和后续读取代价分配预算，不能只追求每个过滤器都达到同一个误判率。该案例中的“LSM 层级”与可扩展 Bloom 的“子过滤器层数”含义不同，前者属于存储引擎结构，后者是集合增长的实现方式。

曝光去重：按需分块与有界历史

腾讯云社区作者 alieliu 的原创《曝光去重设计与实践》介绍了从明文曝光 ID 列表转向分块 Bloom 的过程：按用户逐步增加固定容量的数据块，到达块数上限后淘汰旧块。它是作者的实践记录，不能据发布平台认定为腾讯内部统一方案。

这类设计可以避免低活跃用户一开始就分配完整历史容量，同时限制长期增长。查询需要检查保留的各块，代价随块数增加；淘汰旧块后，旧曝光可能再次出现。因此它实现的是有界历史去重，不是永久去重，也不严格等价于“最近 N 个不同元素”的精确队列。

多块误判率需要合并评估。 若查询按“任一块命中即认为已曝光”判断，总误判率不超过各块误判率之和。例如 5 块各 0.1%，总误判率的上界为 0.5%；这是联合界估算，不要求各块独立，也不是该案例的实测结果。并发更新整个序列化数据块时，还需防止旧副本覆盖新写入；这一同步要求是从读改写机制推导的工程约束。

缓存穿透防护的参考上线方案

下面是针对本文读链路整理的实施建议，不是某家公司的内部发布流程。假设数据库为权威数据源，过滤器可以由其重建，且业务希望避免将可查询的新记录误判为不存在。

阶段	具体动作	进入下一阶段的条件
明确集合	确定租户、业务 ID、编码及合法范围；估算不同元素数量、增长量和内存	插入与查询采用相同的键规范，容量和误判率预算可解释
后台构建	建立可重放的增量通道，再读取与其位点匹配的快照；新版本保持未就绪	快照完成，快照期间及之后的增量无缺口地追平
影子验证	在线计算 Bloom 结果，但仍按原链路返回；受控抽样精确核对负结果	未发现同一可见性时点下的真实记录被负结果拦截
小流量启用	按固定用户或租户分组启用负结果短路；保留快速旁路开关	数据库回源量下降，端到端延迟改善，错误和同步积压可控
扩大流量	逐步增加覆盖范围，持续检查新增记录与负结果抽样	回退时的后端容量仍足以承接流量，旧路径未被过早撤除
重建切换	后台准备新版本，追平并安全发布；读请求固定使用一个版本	版本参数匹配，发布窗口内新增数据仍被覆盖

全量追平一次，不等于以后始终同步。 如果数据库提交后才异步写过滤器，新记录仍有一段漏同步窗口。严格避免漏查时，必须让可见性协议覆盖该窗口，例如在记录对读端可见前确认其已进入过滤器或可信的增量集合；否则该范围应旁路过滤器。单纯使用 MQ、定时任务或“双写”并不自动提供这种保证。

影子验证也要区分时点：先查过滤器、稍后查库时才刚创建的记录，不足以证明算法存在假阴性；需要结合提交时间、快照或版本核对。针对影子验证增加的精确查询，应控制采样率与并发。

故障演练与回退验收

演练场景	应检查的行为
新版本为空、加载未完成或恢复了旧快照	保持未就绪，走受限流保护的原查询链路
增量消费暂停、写入失败或积压超出可信范围	按可确认的范围旁路；无法确认范围时整体旁路，并检查数据库承载能力
消费者重复收到插入事件	普通 Bloom 重复置位不改变成员结果；不能据事件条数直接判断不同元素容量
两个任务同时更新同一序列化 Bloom 块	用单写者、版本比较或事务等机制避免后写旧副本覆盖新标记
新记录此前有空值缓存	按写入协议失效或更新空值标记，避免过滤器已放行但缓存仍返回不存在
过滤器远程调用超时、缓存也故障	限制回源并发，必要时拒绝或降级；不将系统错误伪装成“数据不存在”
切回旧过滤器版本	先确认旧版本仍接收完整增量；无法确认时回退原查询链路，而不是启用过期负结果

这些演练验证的是数据与服务行为；容量、误判率、吞吐和尾延迟还需使用代表性负载单独对照压测。

验证收益时应观察什么

结合以上机制，建议为实际部署记录以下指标，而不是只观察一个“命中率”：

指标	能回答的问题
负结果拦截率	实际省掉了多少后续缓存或数据库访问
已知不存在样本中的命中比例	当前负载下的观测误判率；分母不是所有查询
过滤器容量、层数、内存与查询延迟	扩容或过低误判率是否正在侵蚀收益
同步延迟、就绪状态和回退流量	能否安全使用负结果，旁路是否压垮后端
查库量、尾延迟与总资源消耗	增加过滤步骤后，端到端收益是否成立

本地过滤器与远端过滤器的成本不同。 后者会增加网络访问；如果负查询很少、后续查询已经很便宜，就应通过有无过滤器的对照压测确认净收益。对抽样查询做精确核对时，还应统一数据快照或可见性时点，避免把数据刚写入的同步窗口误算成算法误判。

🚀 布隆过滤器的优化

容量增长与重建

固定过滤器不会因为插入更多元素而自动降低误判率。不能简单扩大原位数组并沿用旧标记：如果定位采用对 m 取模，改变 m 会改变元素的位置，需要重新插入原始集合。

重建需要保留权威数据源。常见流程是读取快照、记录并回放快照期间的增量、追平后切换新实例。切换前后都要保证新增元素被覆盖，且为新旧两份过滤器同时驻留预留内存。若同步无法确认，应回退查询，不能以新过滤器的负结果直接拒绝。

Redis Bloom 文档介绍的可扩展实现通过增加子过滤器容纳增长；查询可能需要检查多个子过滤器，因此还要关注层数、总内存和查询成本。多个子过滤器合并判断时，总误判率需要整体规划，不能让每层各自消耗同一份误差预算。

变种和改进

• 计数布隆过滤器（Counting Bloom Filter）：用计数器替代位，插入递增、删除递减，空间开销增加。只有确认元素已插入、控制计数溢出和重复删除，才能避免错误减计数造成假阴性；不能仅凭“可能存在”就删除。
• 可扩展布隆过滤器（Scalable Bloom Filter）：通过增加子过滤器接纳更多元素，需要分配整体误判率预算。
• 分片布隆过滤器（Sharded Bloom Filter）：按稳定哈希把元素路由到独立过滤器，减少锁竞争；热点或分布不均仍可能让个别分片容量超限。

高并发场景下的优化策略

操作是 O(k)，不代表实现天然无锁或并发安全。 bits-and-blooms/bloom 的并发约束要求共享读写时由调用者同步；构建完成、安全发布且不再修改的实例才适合多个 goroutine 并发只读。

读写同步

底层置位通常是对一个 uint64 执行读、修改、写回。两个 goroutine 同时更新该整数中的不同位，可能互相覆盖，导致标记丢失。置位在逻辑上幂等，不能替代内存访问同步。

• 普通实现先用 Mutex 或 RWMutex 保护同一个过滤器的全部读写；只给 Add 加锁而让 Test 无锁，仍然存在数据竞争。
• 分片减少锁覆盖的范围，但每个可变分片仍需要读写同步；分片数量应根据压测选择，不能固定套用“CPU 核数 × 2”。
• 自定义原子位数组时，写入和查询都要使用正确的原子访问；只把 OR 改为原子操作、保留普通读取，并不能消除数据竞争。Go 内存模型

批量写入 + 版本切换（Copy-on-Write）

写少读多时，可以在后台构建新实例，完成快照与增量追平后，通过 atomic.Pointer 等方式安全发布；读者每次获取一个版本并完成查询。

旧实例和已发布的新实例都应保持不可变。复制可变实例本身也需要同步，多写者发布必须协调，避免后发布的旧副本覆盖前一个版本的更新。这种方式以重建 CPU、双份内存和增量管理换取只读路径的低同步开销。

内存与缓存优化

• 预分配容量，避免临时对象和不必要的输入转换；位数组底层按机器字存储，内存估算应考虑取整。
• 大数组的随机访问可能产生缓存未命中；是否使用块式布局、增加分片，应结合实际查询量和误判率测试。
• 将位数设为 64 的倍数只影响存储取整，不等于分配地址自动按缓存行对齐，也不能自动消除 false sharing。

CPU 缓存局部性与过滤器分区

RocksDB 官方说明提供了两种不同粒度的优化，能把“减少随机访问”落到具体实现上：

• 缓存行内探测：Full Filter 将同一个键的探测位置限制在同一 CPU 缓存行，减少每次查询触及的缓存行数量；这种局部布局会改变误判率模型，需要按实际实现评估。
• 按键范围分区：Partitioned Filter 把一个 SST 的过滤器拆成多个块，在相应缓存配置下，减少小查询一次装入 Block Cache 的过滤器数据；代价是额外的分区定位和 CPU 成本。

前者优化 CPU 缓存访问，后者优化过滤器块的加载和缓存占用；两者也不同于本文 Go 示例中为减少锁竞争而做的业务键分片。普通 BitSet 不会自动具备这些布局，不能仅把数组按 64 位对齐就宣称完成了优化。

典型高并发架构示例（Go）

下面是带输入校验的分片实现，可作为另一个独立的 main.go，使用前述模块和依赖运行。每个分片采用 RWMutex，查询和插入遵循同一套同步规则。

package main

import (
    "fmt"
    "hash/fnv"
    "math"
    "sync"

    "github.com/bits-and-blooms/bloom/v3"
)

type bloomShard struct {
    mu sync.RWMutex
    bf *bloom.BloomFilter
}

type ConcurrentBloomFilter struct {
    shards []bloomShard
}

// n 是总预估元素数；过滤器及其分片在首次使用后不得复制。
func NewConcurrentBloom(n uint, p float64, shardCount uint) (*ConcurrentBloomFilter, error) {
    if n == 0 || shardCount == 0 || shardCount > n || math.IsNaN(p) || p <= 0 || p >= 1 {
        return nil, fmt.Errorf("require n > 0, 0 < shards <= n, 0 < p < 1")
    }
    perShard := n / shardCount
    if n%shardCount != 0 {
        perShard++ // 向上取整，避免整数除法少分配容量
    }
    filter := &ConcurrentBloomFilter{shards: make([]bloomShard, shardCount)}
    for i := range filter.shards {
        filter.shards[i].bf = bloom.NewWithEstimates(perShard, p)
    }
    return filter, nil
}

func (f *ConcurrentBloomFilter) shard(data []byte) *bloomShard {
    h := fnv.New64a()
    _, _ = h.Write(data)
    return &f.shards[h.Sum64()%uint64(len(f.shards))]
}

func (f *ConcurrentBloomFilter) Add(data []byte) {
    shard := f.shard(data)
    shard.mu.Lock()
    defer shard.mu.Unlock()
    shard.bf.Add(data)
}

func (f *ConcurrentBloomFilter) Test(data []byte) bool {
    shard := f.shard(data)
    shard.mu.RLock()
    defer shard.mu.RUnlock()
    return shard.bf.Test(data)
}

func main() {
    filter, err := NewConcurrentBloom(100_000, 0.01, 16)
    if err != nil {
        panic(err)
    }
    var wg sync.WaitGroup
    for i := 0; i < 1_000; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            key := []byte(fmt.Sprintf("user:%d", id))
            filter.Add(key)
            if !filter.Test(key) {
                panic("inserted key was lost")
            }
        }(i)
    }
    wg.Wait()
    fmt.Println(filter.Test([]byte("user:42"))) // true
}

示例保证过滤器内存访问同步，不保证它与外部数据库的一致性，也不保证“先查再加”整体原子化。 输入字节在调用期间不能被其他 goroutine 修改；实例应由构造函数创建，不能使用零值。

每个元素只访问一个分片，因此 p 不需要简单除以分片数；但分片元素数只是均匀分布下的容量估计，生产中需预留余量并监控偏斜。修改分片数或路由哈希需要重建。验证并发访问时运行 go run -race . 或 Go race detector测试；没有报告数据竞争也不能替代业务一致性检查。

📐 公式推导

基本设定

• 位数组长度：$m$
• 插入元素个数：$n$
• 哈希函数个数：$k$
• 目标：求使误判率 $p$ 最小的 $k$

单个 bit 为 0 的概率

每次插入一个元素，会用 $k$ 个哈希函数将 $k$ 个位置置为 1。
总共进行 $kn$ 次独立哈希操作。

某一位在一次哈希中不被选中的概率是：

$$1-\frac{1}{m}$$

经过 $kn$ 次哈希后，该位仍为 0 的概率为：

$${(1-\frac{1}{m})}^{kn}$$

当 $m$ 很大时，利用极限公式 $\underset{m\to \mathrm{\infty }}{lim}{(1-\frac{1}{m})}^m=e^{-1}$，可近似为：

$${(1-\frac{1}{m})}^{kn}\approx e^{-kn/m}$$

因此，该位为 1 的概率为：

$$1-e^{-kn/m}$$

误判率（False Positive Rate）

查询一个不在集合中的元素时，若其 $k$ 个哈希位置全为 1，则发生误判。

假设各位置独立（近似成立），误判率为：

$$\begin{array}{}\text{(1)}& p\approx {(1-e^{-kn/m})}^k\end{array}$$

最小化误判率：求最优 $k$

以下等式针对式 (1) 的近似模型求解，并非有限位数组下的精确误判率。

我们希望选择 $k$ 使得 $p$ 最小。对式 (1) 取自然对数以简化求导：

$$\ln p=k\ln (1-e^{-kn/m})$$

令 $x=\frac{kn}{m}$，即 $k=\frac{mx}{n}$，代入得：

$$\ln p=\frac{mx}{n}\cdot \ln (1-e^{-x})$$

对 $x$ 求导并令导数为 0：

$$\frac{d}{dx}[\frac{mx}{n}\ln (1-e^{-x})]=\frac{m}{n}[\ln (1-e^{-x})+\frac{x{e}^{-x}}{1-e^{-x}}]=0$$

即：

$$\begin{array}{}\text{(2)}& \ln (1-e^{-x})+\frac{x{e}^{-x}}{1-e^{-x}}=0\end{array}$$

令 $y=e^{-x}$，则 $1-y=1-e^{-x}$，方程变为：

$$\ln (1-y)+\frac{-\ln y\cdot y}{1-y}=0$$

通过观察或数值验证，当$y=\frac{1}{2}$（即 $e^{-x}=\frac{1}{2}$）时满足方程：

• $x=\ln 2$
• 代入验证：$$\ln (1-\frac{1}{2})+\frac{\ln 2\cdot \frac{1}{2}}{1-\frac{1}{2}}=\ln \left(\frac{1}{2}\right)+\ln 2=-\ln 2+\ln 2=0$$

✅ 该驻点在连续近似模型中对应最小值；实际使用时仍需选择整数 k。

因此最优解为：

$$\begin{array}{}\text{(3)}& x=\frac{kn}{m}=\ln 2\Rightarrow k_{\text{opt}}=\frac{m}{n}\ln 2\end{array}$$

由于 $\ln 2\approx 0.6931$，常写作：

$$k_{\text{opt}}\approx 0.6931\cdot \frac{m}{n}$$

最小误判率

将 $k=\frac{m}{n}\ln 2$ 代回误判率公式 (1)：

首先计算指数部分：

$$e^{-kn/m}=e^{-\ln 2}=\frac{1}{2}$$

所以：

$$p_{min}={(1-\frac{1}{2})}^k={\left(\frac{1}{2}\right)}^k=2^{-k}$$

再将 $k=\frac{m}{n}\ln 2$ 代入：

$$\begin{array}{}\text{(4)}& p_{min}=2^{-\frac{m}{n}\ln 2}=e^{-\frac{m}{n}(\ln 2{)}^2}\end{array}$$

因为 $(\ln 2{)}^2\approx 0.48045$，也可写为：

$$p_{min}\approx {\left(0.6185\right)}^{m/n}$$

注：$0.6185=e^{-(\ln 2{)}^2}\approx e^{-0.48045}$

参考资料

• bits-and-blooms：Bloom v3.7.0、并发约束、实现源码
• bits-and-blooms：BitSet v1.10.0 位存储与操作实现
• Go：内存模型、数据竞争检测
• Redis：Bloom filter
• Apache HBase：BloomType
• Adam Kirsch、Michael Mitzenmacher：Less Hashing, Same Performance: Building a Better Bloom Filter
• Python：BLAKE2 哈希、Lock、hash 随机化
• 美团技术团队：孵化业务快速落地与优化
• 阿里云：Tair 社区介绍、TairBloom 文档
• 腾讯技术工程：经典论文解读——布隆过滤器
• 火山引擎：ByteHouse 点查询调优、ExBloomFilter
• 开发者阿橙：Scrapy 分布式爬虫、队列和布隆过滤器
• Apache Doris Contributor 分享：Apache Doris Join 实现与调优实践
• 腾讯云 TDSQL Boundless：Runtime Filter、Monkey Bloom Filter 调优
• 火山引擎：ByteHouse CDW query optimization best practices
• alieliu：曝光去重设计与实践
• RocksDB：Bloom Filter 与分区布局
• vivo 互联网服务器团队 Zhang Wei：短视频推荐去重服务的设计实践
• 阿里云 MaxCompute：Bloomfilter index（Beta）