《大规模分布式计算深入解析》4.2 布隆过滤器与 Puffin 统计

zone map 对高基数等值查询无能为力,布隆过滤器补上这一层:1 万行、1% 误判率需要 95851 位与 7 个哈希函数,1000 次不存在键查询约误判 10 次。本节推导 m/k 公式,并说明 Puffin 中 NDV 与 theta sketch 如何为优化器服务。

4.2 布隆过滤器与 Puffin 统计

4.1 的 zone map 对范围查询很有效,但遇到高基数等值查询就失灵:一列有 100 万个不同 ID,每个 page 的 min/max 都覆盖全表值域,id = 12345 这种查询一个 page 都跳不过。min/max 描述的是「值域」,不是「成员」,而等值查询关心的恰恰是成员。

布隆过滤器补的正是这一层:它用位数组回答「这个值一定不在」,用少量误判换取大幅跳过。本节先推 m/k 公式,再算误判账,最后把 Puffin 这类 sidecar 统计放进同一张图。

布隆过滤器:只回答「一定不在」

布隆过滤器是一个 m 位的位数组,加 k 个哈希函数。插入一个值,用 k 个哈希算出 k 个位置,全部置 1;查询一个值,同样算 k 个位置:

若 k 个位置中有任意一个为 0 → 该值一定不在集合中
若 k 个位置全为 1         → 该值可能在集合中(也可能不在)

这个不对称是布隆的全部价值:它不会漏掉真正存在的值(无假阴性),但会把一些不存在的值误判为存在(有假阳性)。用在数据裁剪上,假阳性只意味着「多读一块」,不会漏数据;正确性安全,代价是误判率。

查询结果含义裁剪动作
任一位为 0一定不存在可跳过该块
全为 1可能存在必须读该块
真正存在的值全为 1一定会读,不会漏

布隆不能删除元素。把某位置 0 会影响其他元素的判断,所以它只适合「写入后不再删除」的块级统计。数据更新只能重写块或重建过滤器,这与列式文件「块不可变」的假设一致。

m 与 k:公式与用例 33 的 95851 位

给定预期元素个数 n 和目标误判率 p,最优位数组长度 m 与哈希函数个数 k 由两个公式给出:

m = -n × ln(p) / (ln 2)^2
k = (m / n) × ln 2

lab 的用例 33 代入 n = 10,000、p = 0.01:

ln(0.01) = -4.60517
(ln 2)^2 = 0.480453
m = -10000 × (-4.60517) / 0.480453 ≈ 95850.5 位,向上取整 95851 位
k = (95851 / 10000) × 0.693147 ≈ 6.64,四舍五入 7 个
字节数 = 95851 / 8 ≈ 11981 字节 ≈ 12KB
参数值说明
n10,000预期插入的元素数
p1%目标误判率
m95,851 位位数组长度,约 12KB
k7哈希函数个数
每元素位数9.59 位m / n

m/n 约为 9.59 位/元素,这是 1% 误判率的代价。误判率每降一个数量级,位数大约要增加 4.8 位/元素;想把 1% 降到 0.1%,位数组要从 12KB 涨到约 18KB。误判率不是免费的,它直接用空间换。

k 也不是越大越好。k 增大,每次查询的哈希次数增加,CPU 成本上升;同时位数组被填得更满,误判率反而可能回升。最优 k 由 m/n 决定,公式给出的 7 就是平衡点。盲目加哈希函数,既慢又不一定更准。

误判率:1000 次查询约 10 次误判

误判率的定义是「不存在的元素被误判为存在」的概率。lab 的用例 34 把它折算成次数:

不存在键查询次数 = 1000
误判率 = 1%
期望误判次数 = 1000 × 1% = 10 次
查询次数误判率期望误判实际影响
10001%1010 次多读块
10000.1%11 次多读块
100010%100100 次多读块

误判的代价是「多读」,不是「读错」。被误判的块会被读进来,再由上层谓词过滤掉,结果仍然正确。所以布隆的账要按「多读的块数 × 单块成本」算,而不是按「错误率」算。10 次误判在 1000 次查询里,可能只多读 10 个块;若每个块 1MiB,就是多读 10MiB。

误判率会随插入量漂移。公式里的 p 是按预期 n 算的;如果实际插入量超过 n,位数组被填得更满,真实误判率会高于设计值。写入时低估基数,是布隆失效的常见原因;要么按上限预留,要么在基数超阈值时重建。

布隆过滤器的格式与粒度

Parquet 规范的 split-block Bloom filter 由 256 bit 的块组成,每块含八个 32 bit word。用列值散列选块,再在块内按规范的位操作测试成员关系。它与通用位数组公式的 7 次独立哈希是两个模型。Parquet 在列块元数据记录相应 Bloom 的位置;ORC 等格式有自己的索引粒度。读端是否利用 Bloom 也取决于 reader 和谓词。缺失索引、NULL 谓词或类型不兼容时,应按适用规则保留候选。 Parquet Bloom 规范

布隆的成本:12KB 与 7 次哈希

一份 1% 误判率、1 万元素的布隆约 12KB。把它放进整张表:

单个 column chunk 的布隆 ≈ 12KB
10GiB 表、80 个 row group、10 列 → 800 个 column chunk
若每列都建布隆:800 × 12KB = 9600KB ≈ 9.6MB
成本项量级说明
存储约 12KB / chunk只对高基数列建,实际远小于 9.6MB
读取每次查询读过滤器点查只读命中的 chunk 过滤器
CPU每键 k=7 次哈希相对解压可忽略
构建写入时逐值哈希写入吞吐的小幅下降

9.6MB 是「全列都建」的上界,不是典型值。实际只给少数过滤列建布隆,统计开销通常远小于数据本身。布隆的性价比取决于「过滤器字节 / 被跳过块的字节」:跳过一块 1MiB 的数据,只花 12KB 统计,比例约 1:87,非常划算;若过滤器比数据还大,就不值得。

布隆的读取也有代价。点查时要先读过滤器、再算哈希、再判断;如果查询命中的块很多,过滤器的读取与哈希会成为额外开销。布隆适合「高选择性点查」,不适合「低选择性扫描」。

Puffin Theta sketch 与目录统计

Iceberg Puffin 单独保存带类型的 blob。规范定义的 Theta sketch 带字段 ID、快照 ID 和序号,可用于估计 NDV,典型消费者是查询优化器。Parquet 列块 Bloom 的成员判断走 Parquet 规范。Puffin 在 Iceberg 表元数据中定位,按需读取,无固定顺序要求先扫描 Parquet footer 再读取它。合并不同 sketch 前还要满足相同的值编码、字段和兼容性约束。 Puffin 规范

NDV 与 theta sketch:给优化器用的统计

布隆回答「某个值在不在」,但优化器还需要另一个问题:「这一列有多少个不同值」。这就是 NDV(Number of Distinct Values)。精确 NDV 要存全部值,代价太高;Puffin 里常用 theta sketch 这类可合并的近似结构。

统计回答的问题典型结构服务对象
min/max值域范围两个值裁剪、范围选择率
布隆某值是否存在位数组等值裁剪
NDV有多少不同值theta sketch / HLL优化器基数估计

NDV 的主要用途不是裁剪,而是代价估算。join 的顺序、聚合的哈希表大小、等值谓词的选择率,都依赖「这一列有多少不同值」。NDV 估错,优化器可能选错 join 顺序,代价比多读几个块大得多。

theta sketch 的优势是可合并。每个文件维护一个 sketch,扫描计划可以把多个文件的 sketch 合并,估计全局 NDV,而不必读全部数据。可合并性让「文件级统计」能升级成「表级统计」,这是 Puffin 相比普通 footer 统计的另一个价值。

近似统计要接受误差。theta sketch 的误差随精度参数变化,NDV 是一个估计值而不是精确值;优化器用它做决策,不拿它做正确性判断。统计可以错,结果不能错,这是所有近似统计的共同边界。

组合使用:三种统计的分工

把 min/max、布隆、NDV 放在一起,各自的位置很清楚:

查询形态首选统计原因
范围查询 x > 95min/max区间比较最便宜
等值点查 id = 12345布隆min/max 对高基数无效
join 顺序选择NDV需要基数而不是成员
分区裁剪分区值目录级,零文件打开
低基数枚举字典 + min/max布隆空间不划算

没有一种统计能覆盖所有查询。范围查询靠 min/max,等值点查靠布隆,优化器决策靠 NDV;三者组合,才构成完整的统计层。统计的选型应该跟着查询形态走,而不是跟着格式默认走。

组合的顺序也有讲究。先做便宜的 min/max,再做布隆,最后才读数据;如果布隆的过滤率很高,也可以先布隆再 min/max,但前提是布隆的读取成本低于 min/max 的收益。顺序由成本与过滤率共同决定,4.3 会把这两级组合成一个跳过率总账。

三个常见误解

误解一:布隆过滤器有误判,所以查询结果可能出错。 真相:布隆只有假阳性、没有假阴性;误判只会让不该读的块被读进来,再由上层谓词过滤,结果仍然正确。

误解二:哈希函数越多,布隆越准。 真相:k 由 m/n 决定,用例 33 的最优值是 7;盲目增加哈希次数只会提高 CPU 成本,还可能因位数组过满而推高误判率。

误解三:NDV 统计是用来跳过数据块的。 真相:NDV 主要服务优化器的基数估计与 join 顺序,不是成员判断;跳过数据靠的是 min/max 与布隆。

一句话总结本节

通用 Bloom 公式用来理解空间与误判的取舍。Parquet 用自己的 split-block 布局排除一定不存在的列块。Puffin 的 Theta sketch 提供近似基数,消费路径和用途各自独立。

统计结构及消费者

表级基数估计、列块成员测试和页级范围分别影响计划选择或扫描。缺失统计时保留正确性。

flowchart LR
    A[快照元数据] --> B[定位 Puffin Theta sketch]
    B --> C[NDV 估计]
    C --> D[优化器基数与计划]
    E[Parquet 列块元数据] --> F[定位 split-block Bloom]
    E --> G[定位 Page Index]
    F --> H[用等值条件排除确定不存在的列块]
    G --> I[用范围和偏移定位候选页]
    H --> J[Reader 扫描候选]
    I --> J

本节 lab

下载卷五 Java 8 实验 · 实验运行与版本说明

在 bd-engine-lab 中验证布隆参数与误判账:

  • 源码:src/format/Format.java 与 src/format/FormatSuite.java。
  • 运行:cd bd-engine-lab && mkdir -p out && javac -d out $(find src -name '*.java') && java -cp out lab.RunAll。
  • 断言:用例 33 验证「1 万行、1% 误判率需要 95851 位、7 个哈希函数」;用例 34 验证「1000 次不存在键查询、1% 误判率,约 10 次误判」。
  • 整卷 runner 的预期汇总为 TOTAL: 116 passed, 0 failed。

对应本节判断链:先确认 min/max 对高基数等值查询失效 → 用布隆的「一定不在」补位 → 由 n 与 p 推出 m=95851 位、k=7 → 把 1% 误判率折算成 1000 次查询约 10 次多读 → 对照 Parquet split-block Bloom → 以 Puffin Theta sketch 的 NDV 服务优化器。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图