存储基础（2）：读放大、布隆过滤器与缓存

1 分钟阅读

发布于：

本文是「存储基础系列」的第 2 篇，聊三个经常一起出现的概念：读放大（Read Amplification）、布隆过滤器（Bloom Filter）、以及 缓存（Cache / Page Cache / Block Cache）。它们本质上都在回答一个问题：“我为一次读取，付出了多少额外成本？”

读放大如何被 Bloom + Cache 降下来（以 LSM/RocksDB 为例）

1. 什么是读放大

读放大可以粗略理解为：

  • 逻辑读取 1 个 key/范围
  • 实际上却需要 读取更多的 block / page / 文件 / 层级 / 远端请求

常见来源：

  • 索引层级多：比如 LSM 的多层 SST 文件，需要多次查找。
  • 数据局部性差：随机 IO 多，导致每次读都要带出很多无用数据。
  • 远端存储：对象存储/网络盘，每次读的固定开销更高，放大更明显。

衡量方式没有唯一标准，但可以用“为完成一次查询需要触碰多少个数据块/文件”来直觉理解。

1.1 更工程化的度量：用“触碰次数”近似

对存储引擎/数据库来说，最常用的读放大直觉是：

  • 触碰多少个文件（SST/page/segment）
  • 触碰多少个 block/page（实际 IO 单元）

比如一次点查最理想是：1 次索引定位 + 1 个 data block；最糟的是：跨多层、多个文件都要查一遍，甚至还要回表/远端读。

2. 布隆过滤器：减少“读不存在”的成本

在 KV/LSM 场景里，一个非常典型的痛点是：读一个不存在的 key。

如果没有 Bloom Filter，往往需要：

  • 查 memtable
  • 再查多层 SST（每层可能多个文件）
  • 最后才能确认“不存在”

Bloom Filter 的作用：

  • 用很小的内存，给出一个快速判断：
    • 一定不存在（直接返回，避免走 IO）
    • 可能存在（再去真正查找）

关键点：

  • Bloom Filter 有假阳性（false positive），但没有假阴性。
  • 假阳性率取决于：位数组大小、哈希函数个数、元素数量。

工程上一般会把 Bloom Filter 按 SST 文件 / data block 粒度存储并加载到内存。

Bloom Filter：参数与假阳性如何影响“白跑一趟”

2.1 核心要点一句话

Bloom Filter 对读放大最直接的贡献是：把大量“负查”挡在内存里，避免它们把读路径拖进多层多文件的 IO 地狱。

它的代价是：

  • 需要内存（或把 filter block 常驻 cache）
  • 有假阳性（会“白跑一趟”），假阳性越高，收益越差

2.2 一个“可估算”的经验公式（不用依赖公式渲染）

Bloom Filter 常用的近似关系是：

假阳性率 p 近似 ≈ (0.6185)^(bits_per_key)
最优哈希数 k ≈ 0.693 * bits_per_key

工程上你可以这样用：

  • 先根据“负查比例 + 可接受的白跑成本”选一个 bits_per_key
  • 再用压测/线上指标验证：负查是否真的不触盘了、尾延迟是否下降

2.3 一个更直观的“参数感”例子

如果你选 bits_per_key = 10，用上面的近似可以得到：

p ≈ 0.6185^10 ≈ 0.008  （约 0.8%）

直觉上就是：负查里大约千分之几会“白跑一趟”去触盘（具体还会被层数/文件数/缓存命中影响）。

这类估算的意义不是精确，而是帮你回答：我愿意用多少内存，换多少“负查不触盘”的概率。

3. 缓存：把热点从“慢介质”挪到“快介质”

存储系统里常见的缓存分三类：

  • OS Page Cache：文件系统层面的缓存，默认就有（读文件受益很大）。
  • Block Cache：比如 RocksDB 的 block cache，缓存压缩后的 data block / index block。
  • 应用级缓存：在服务端实现的 key/value 缓存（通常在业务层或代理层）。

常见误区：

  • “有了 Page Cache 就不需要 Block Cache”：不一定。比如压缩、校验、block 组织方式都会影响命中收益；另外 block cache 更可控。
  • “缓存越大越好”：不一定。缓存会挤占 memtable、compaction buffer、写入 buffer 等资源，可能反而让系统更抖。

3.1 Page Cache vs Block Cache：什么时候谁更有用

  • Page Cache（OS）更擅长：文件层面的热数据复用（尤其顺序读/重复读）。
  • Block Cache（引擎）更擅长：
    • 缓存“压缩后的 block”（节省内存）
    • 精确控制缓存对象（data/index/filter）
    • 配合 Bloom/index 把读路径变得更可预测

很多线上系统会同时开两层缓存，但需要注意“同一份数据被缓存两次”造成的浪费，以及 scan 对 cache 的污染。

3.2 一个很现实的坑：范围扫描把 cache 冲掉

如果你的系统既有点查热点，又有大量 scan（例如全量导出/后台任务），很容易出现：

  • scan 触发大量顺序读，把 page cache / block cache 的热点挤掉
  • 点查的 P99 突然变差（看起来像“cache 失效”）

工程上常见的处理方式是：把 scan 和在线读隔离（资源隔离/单独实例），或者让 scan “不进 cache/低优先级”。

4. 一个实用的排查思路

当你发现“读变慢了”，可以按这个顺序定位：

  • 命中率：block cache / page cache 命中率是否下降？
  • 读路径触碰次数：一次读要查多少层/多少文件？
  • IO 形态：随机读多还是顺序读多？是否被压缩/解压 CPU 卡住？
  • 假阳性率：Bloom Filter 是否配置过小导致无效？

4.1 一个更贴近落地的排查顺序（建议照着做）

  1. 拆开看命中率：不要只看总体命中率，至少区分 data/index/filter（很多“命中率很高但还是慢”的根因在这里）。
  2. 看触碰次数：一次点查要查多少层？多少文件？是否存在大量负查？
  3. 看 IO 形态：是否随机读为主？是否被 compaction/flush 抢带宽？
  4. 看 CPU：是否被解压/校验/迭代器合并吃满（NVMe 上更常见）？

下一篇我们会把这些概念放到 LSM 的结构里看：为什么 compaction 会影响读写放大，以及如何做权衡。