《大规模分布式计算深入解析》3.1 Bloom 假阳性

按目标误差和键数选择过滤器预算。

按目标误差和键数选择过滤器预算。

实现机制

在哈希近似独立、经典位数组条件下,m/n 比特每键的近似最优 k 为 (m/n) ln 2。10 bit/key 约选 7 个哈希,算例假阳性约 0.8%。

1 亿键按 10 bit/key 是 125 MB 的理想位数组,额外空间包括分区、元数据和实现开销。

Bloom 假阳性的执行路径

flowchart TD
    N0["键与快照序号"]
    N1["按 min/max 选文件"]
    N0 --> N1
    N2["过滤器判断是否可能存在"]
    N1 --> N2
    N3["块索引定位偏移"]
    N2 --> N3
    N4["读缓存或设备并检查可见版本"]
    N3 --> N4
    N2 -- "过滤器返回不存在" --> F0["跳过该候选;范围查仍需核对过滤域"]

验证

复算空集合与不同负载下的误判率,确认查询键编码与过滤器生成一致。

下载实验包 · 本卷目录 · 系列导读

一手资料

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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