廉价写入的代价：RocksDB 如何读取？

RocksDB 如何读取一个键？

RocksDB 的读取会从最新数据查到最旧数据，并在找到键的第一个版本时停止。仅此而已；其他一切机制都只是为了加速这个过程。

搜索顺序固定不变，与上一篇文章介绍的写入路径方向相反：依次遍历活跃内存表、不可变内存表、0 层中的 SST 文件，以及从第 1 层开始逐层向下的已排序 SST 文件。

RocksDB 首先检查活跃内存表，因为它保存着最新写入的数据，位于内存中，并使用跳表。因此，查找是在内存中执行的有序搜索，几乎不产生 I/O。一旦找到键，搜索就会停止。

检查完活跃内存表后，RocksDB 会检查所有已经写满、但尚未刷入磁盘的不可变内存表。检查顺序同样是从最新到最旧。

接下来检查磁盘。由于 0 层文件的键范围相互重叠，因此必须从最新到最旧逐个检查。这是因为每个文件都是某个内存表所吸收数据的快照，所以同一个键可能同时存在于两个 0 层文件中。

每个 0 层文件都可能藏着目标键，这正是 0 层文件数量会增加读取负担、而 RocksDB 会暂停写入以限制其数量的原因。

从第 1 层开始，同一层级内的 SST 文件已排序且互不重叠，因此每层最多只有一个文件可能包含目标键。系统通过二分搜索文件元数据找到该文件，然后进入文件内部继续搜索。索引块定位正确的数据块，而数据块要么包含目标键，要么表明该层没有这个键。

序列号对 RocksDB 的读取路径很重要，因为它让搜索在找到第一个版本时停止，并保证该版本是最新版本。例如，如果读取找到了一个墓碑标记，读取就算成功，并返回该键已被删除。因此，搜索会在墓碑标记处结束，而更旧的值仍留在磁盘上。

RocksDB 提供哪些读取操作？

RocksDB 提供四种读取方式，每种方式使用读取路径的方式都不同：Get、MultiGet、Iterators 和 Snapshots。

Get

Get 就是上一节追踪的点查找。也就是在从最新到最旧的搜索中查找一个键，并以找到的第一个版本为准。

MultiGet

MultiGet 会批量执行点查找。一次读取可以向 RocksDB 提供一组键，RocksDB 会对它们排序，并按它们可能访问的文件进行分组。

实际上，这让 RocksDB 可以只打开一次 SST、只查询一次其索引块和过滤器块，并批量执行 I/O。它与 Get 使用相同的读取路径，但成本固定，并由整个批次分摊。

迭代器

Iterators 用于扫描范围，即先定位到一个键，再按排序顺序向前或向后遍历。

实际上，迭代器执行的是 k 路归并（即把 k 个不同的有序列表合并成一个完全有序的序列）。每个活跃数据源——内存表、所有不可变内存表、每个 L0 文件，以及每个更深层级中的一个文件——都会提供自己的有序游标，而堆会不断取出持有下一个最小键的游标。

优先采用最新版本的规则适用于每一步。因此，如果多个数据源都提供了同一个键，最新版本胜出，其余版本则被丢弃。

迭代器前进时会跳过被遮蔽的值和墓碑标记。这意味着，对于一个充满已删除键的范围，迭代器必须默默遍历整个范围，却不返回任何内容。大量删除的键空间会让扫描变慢，而点查找似乎永远不会注意到这一问题。

快照

Snapshot 是在某一时刻捕获的序列号。任何携带它的读取都会直接忽略序列号更大的版本，并返回序列号小于或等于它的最新版本。这样只需进行整数比较，就能实现一致的时间点读取。

创建快照几乎没有即时成本，因为成本会在之后累积；只要快照仍然有效，它能看到的版本就无法被回收，无论这些版本有多旧。

Get 和 MultiGet 都确切知道自己要查找哪个键，因此可以提出一个比“这个键在哪里？”成本更低的问题，即“哪些文件肯定没有这个键？”Iterators 永远无法利用这一捷径。回答这个成本更低的问题，就是布隆过滤器的全部职责。

什么是布隆过滤器？

布隆过滤器只回答一个关于集合的问题：这个元素确定不在其中吗？ 答案要么是确定不在，要么是可能在，绝不会给出确定在的回答。如果一个文件确定不包含某个键，搜索就完全不必打开它，从而节省 I/O。

构建 SST 时，系统会让每个键经过若干个哈希函数，每个哈希值都会在一个紧凑的位数组（即过滤器块）中设置一个位。

读取时，查找过程会以相同方式对目标键进行哈希，并检查这些位。如果任何一位未设置，就表示这个键从未被插入，因此可以确定它不在这里。

如果所有位都已设置，这个键就可能存在——之所以只是可能，是因为其他键的哈希值可能恰好覆盖了相同的位。

这意味着可能出现假阳性：搜索打开文件并进行检查，却什么也没找到，白白消耗了过滤器原本要节省的 I/O。

按照 RocksDB 通常采用的每个键十位配置，假阳性率约为百分之一。十位空间可以带来 99% 的概率，跳过不含目标键的文件。一个包含百万个键的 SST，其过滤器略大于一兆字节，与索引一起驻留在内存中，查询时无需访问它所保护的磁盘。在系统工程中，很少有结构能以如此低的成本换来如此高的收益。

这也解释了为什么本系列上一篇文章中看到的过滤器块大小为零。布隆过滤器需要主动启用，通过 filter_policy 配置，并由应用选择每个键使用多少位；默认配置不会设置过滤器。

对于无法预知工作负载的库来说，这一默认值无可厚非；但在生产环境中却站不住脚，因为过滤器决定了缺失键的查询成本是每个文件一次内存检查，还是每个文件一次索引块读取。

布隆过滤器的一个限制是，它只在搜索确切知道目标键时才有帮助。布隆过滤器可以回答 key:0301 是否在该文件中，却无法回答该文件是否包含 key:0090 与 key:0110 之间的任何内容，因为哈希会破坏顺序。

Iterators 无法提前知道下一个键，因此得不到这一结构的帮助。布隆过滤器是一种点查找技术；以范围查询为主的工作负载必须另寻优化方案。

RocksDB 前缀查找呢？

RocksDB 对扫描问题的部分补救方案是改变哈希对象。前缀提取器会告诉 RocksDB，键具有有意义的结构（例如前八个字节，或分隔符之前的所有内容）。RocksDB 知道前缀是什么后，就可以针对前缀构建布隆过滤器，而不是只针对完整键构建，或同时为两者构建。能够回答文件是否包含以特定前缀开头的键的过滤器，可以帮助迭代器。

不过，这条捷径只适用于单个前缀。

针对给定前缀的扫描可以像点查找一样跳过文件和块。但从一个前缀跨越到下一个前缀的扫描得不到同样的帮助。如何在不同前缀之间维持迭代顺序保证，涉及大量配置细节，值得另文深入讨论。

前缀查找并不能普遍降低范围扫描的成本。

它只是让一种特定且极为常见的范围扫描形式——针对给定前缀的扫描——变得低成本。

什么是 RocksDB 块缓存？

块缓存是未压缩数据块的内存缓存。从 SST 读取数据块时，系统会解压并保留它。下一次读取需要同一个块时，就无需访问磁盘。这意味着热门键会聚集在热门块中，而热门块不再产生 I/O 成本。

因此，布隆过滤器会尽量阻止搜索进入文件，而块缓存则降低必须进入的文件再次访问时的成本。

这里有一个细节：实际上存在两层缓存。

块缓存由 RocksDB 自己管理，保存其明确控制的未压缩块。在其下方是操作系统的页缓存，保存 RocksDB 最近读取的原始压缩文件页。同一份数据可以同时占用两者的空间（即在块缓存中以未压缩形式存在，在页缓存中以压缩形式存在）。这就是 RocksDB 的真实内存占用总是被低估的原因，也说明忽略页缓存的缓存容量讨论只考虑了系统的一半。

索引块和过滤器块会得到特殊处理。它们体积小，几乎每次读取进入对应文件时都会查询，而且缓存未命中的代价极其高昂，因此让它们常驻内存几乎是必选项。

它们是计入块缓存预算，还是放在预算之外、由表读取器自己的内存保存，是一个配置选择（即 cache_index_and_filter_blocks）。

墓碑标记和归并链会给读取带来什么成本？

墓碑标记和归并链是写入路径中的记录类型，会影响读取路径，但只能通过压实来解决。墓碑标记会持续累积，直到压实将其与它们遮蔽的旧记录一起丢弃；归并链也会不断增长，直到压实将其折叠为最终值。

对于找到墓碑标记的点查找而言，它的成本很低。也就是说，由于“已删除”是一个有效结果，搜索会停止并返回答案。但迭代器不能在墓碑标记处停止。它必须解析墓碑标记、跳过被其遮蔽的版本，并继续前进，直到找到下一个有效键。大量删除的键空间就像一片雷区：迭代器必须遍历并丢弃其中的条目，却不返回任何内容；扫描可能执行大量不确定的工作，却只产生很少的输出。点查找永远不会注意到这一点，而范围扫描对此毫无防御能力。

归并操作数也会产生类似的账单，但方向相反。读取一个经过归并的键时，不能在最新记录处停止，因为操作数是对一次变化的描述，而不是值。因此，搜索必须不断收集操作数，直到遇到完整值、墓碑标记或树的底部，然后通过归并运算符折叠整条链。

上一篇文章的演示折叠了一条包含三个操作数的链，但设计中并没有任何机制将链长限制为三个。一个计数器如果在两次压实之间被归并一万次，一次读取就必须收集并折叠一万个操作数，而写入路径对此没有任何限制。

放大三角

放大三角是支配每棵 LSM 树的三方权衡：写放大、读放大和空间放大。改善其中任意两项都会恶化第三项。

Athanassoulis 等人通过 RUM 猜想（2016 年）形式化描述了这些权衡。该猜想认为，一种访问方法最多只能在读取开销、更新开销以及内存或空间开销中最小化两项，第三项必须承担代价。B 树位于一个位置（即读取便宜、更新昂贵），LSM 树位于另一个位置（即更新便宜、读取昂贵），而三角形则描绘了两者之间的整个空间。

本文介绍的一切，都是三角形的某个角在保护自己。

写放大是实际写入磁盘的字节数与应用逻辑写入字节数之比。单个 Put 会先写入 WAL 一次，刷入 L0 时再写一次，之后每次压实将其向下一层移动时都会再次写入。这意味着，在拥有十多个层级的分层 LSM 中，一次逻辑写入在整个生命周期内通常会变成十到三十次物理写入。上一篇文章称赞这些写入全都是顺序写入，而本文则为此叹息。

读放大是指查询必须检查多少个位置才能找到答案。对于点查找，最坏情况是检查每个内存表、每个 L0 文件，以及每个更深层级中的一个文件（即本文开头追踪的搜索过程），实际成本则取决于有多少检查未被布隆过滤器和块缓存消除。对于范围扫描，它是同时保持所有数据源打开的 k 路归并。读放大正是本文的主要内容：过滤器、缓存和前缀提取器共同构成降低其成本的机制。

空间放大是已占用磁盘空间与已存储逻辑数据量之比。等待压实的旧版本、墓碑标记及其遮蔽的旧记录、尚未折叠的归并链，以及有效快照固定的每个版本，都会为应用已无法读取或不再需要的数据占用磁盘空间。经过良好调优的分层压实可将该比例保持在约 1.1 倍，而其他方案则会牺牲更多空间。

这个三角形表明，改善任意两个角都会恶化第三个角。也就是说：

• 积极压实：读取更快，空间占用更紧凑，但每个键都会不断重写，写放大随之上升
• 延迟压实：写入顺畅，但文件不断堆积，读取时需要逐一检查，失效数据也会长期滞留在磁盘上
• 为过滤器投入内存：缓存和读取性能得到改善，但内存是三角形各个角都在争夺的隐性第四种资源

没有哪个设置叫作“快”。只有与给定工作负载匹配或不匹配的三角形位置。

读取路径演示

下面将复用上一篇文章演示中的项目，并启用统计信息。

将 src/main.rs 的内容替换为：

use rocksdb::{BlockBasedOptions, Options, DB};

fn main() {
	let with_bloom = std::env::args().nth(1).as_deref() == Some("bloom");
	let path = if with_bloom { "/tmp/read-bloom" } else { "/tmp/read-nobloom" };

	let mut opts = Options::default();
	opts.create_if_missing(true);
	opts.enable_statistics();

	if with_bloom {
		let mut bbt = BlockBasedOptions::default();

		bbt.set_bloom_filter(10.0, false);
		opts.set_block_based_table_factory(&bbt);
	}

	let db = DB::open(&opts, path).unwrap();

	// Three L0 SSTs with fully overlapping ranges: file b holds keys where
	// key % 4 == b, all spanning 0..600. Keys where key % 4 == 3 exist nowhere
	for batch in 0..3u64 {
		let mut k = batch;

		while k < 600 {
			let key = format!("key:{:04}", k);
			db.put(key.as_bytes(), b"value").unwrap();
			k += 4;
		}

		db.flush().unwrap();
	}

	// key:0404 lives only in the oldest file, meaning the search must get past
	// the two newer files to reach it
	let hit = db.get(b"key:0404").unwrap();
	println!("get(key:0404) = {:?}", hit.map(|b| String::from_utf8(b).unwrap()));

	// key:0303 is inside every file's range and inside no file
	let miss = db.get(b"key:0303").unwrap();
	println!("get(key:0303) = {:?}", miss);

	if let Some(stats) = db.property_value("rocksdb.options-statistics").unwrap() {
		for line in stats.lines() {
			if line.contains("bloom.filter.useful")
				|| line.contains("bloom.filter.full.positive")
				|| line.contains("block.cache.data") {
				println!("{}", line);
			}
		}
	}
}

上面有三个已刷入的 L0 文件，其键范围完全重叠。因此，仅凭范围元数据无法排除任何文件，因为两个键都可能藏在任意文件中。

命中项（即 key:0404）只存在于最旧的文件中，迫使从最新开始的搜索先处理两个不包含它的文件，然后才能到达包含它的文件。

未命中项（即 key:0303）位于每个文件的范围内，却不存在于任何文件中。这意味着只有布隆过滤器才能节省这次读取。

先直接运行，然后使用参数 bloom 再运行一次。

不使用过滤器时，输出为：

get(key:0404) = Some("value")
get(key:0303) = None
rocksdb.block.cache.data.miss COUNT : 3
rocksdb.block.cache.data.hit COUNT : 3
rocksdb.bloom.filter.useful COUNT : 0

为了完成两次查找，我们访问了六次数据块。命中查询从三个文件各读取了一个数据块，其中两个毫无帮助，共产生三次磁盘读取。未命中查询随后又检查了相同的三个文件；它的三次数据块访问之所以都是缓存命中，只是因为第一次查找刚刚预热了缓存。块缓存完成了自己的任务，也是唯一发挥作用的机制。

使用过滤器时，输出为：

get(key:0404) = Some("value")
get(key:0303) = None
rocksdb.block.cache.data.miss COUNT : 1
rocksdb.block.cache.data.hit COUNT : 0
rocksdb.bloom.filter.useful COUNT : 5
rocksdb.bloom.filter.full.positive COUNT : 1

我们总共只访问了一次数据块。可以手动验证 useful 为 5 的计算过程：

• 命中查询先检查最新文件的过滤器，再检查第二个文件的过滤器，两者都返回否。最旧文件的过滤器返回唯一一个 full.positive，并被证明是真阳性。因此跳过了两个文件
• 未命中查询检查了全部三个过滤器，并得到三次否，意味着跳过三个文件，一个文件也没有打开

将命中和未命中相加，共有五次文件检查。过滤器在内存中回答的这五次文件检查，正是无过滤器运行时必须执行的五次数据块读取。因此，每个键十位的空间把六次块访问减少到一次。

这实际上是小规模的放大三角。无过滤器运行承担了全部读放大成本；使用过滤器的运行则用内存支付了这笔成本（即每个文件使用几百字节的过滤器）；无论哪种方式，写入路径都无需付出代价。RocksDB 中的每项调优决策，都是这种权衡的更大规模版本。

Solana 如何向读取路径施压？

上一篇文章将验证者视为写入路径的压力测试：分片持续以线速涌入。读取端则是这笔交易的另一半，因为一个无法读回数据的账本，只是给数据中心预热的一种昂贵方式。

本文关于搜索顺序、过滤器和键设计的每个观点，都体现在 Solana 数据的实际查询方式中。

在验证者内部，Blockstore 的读取分为两种不同形式：处理修复请求，以及重放或流式传输一个区块。

处理修复请求意味着其他验证者正在请求它们遗漏的分片。这是按 (slot, index) 执行的点查找。重放或流式传输一个区块的账本数据，则是在给定槽位上执行范围扫描。

由于分片键以槽位编号开头，一个槽位的所有分片都会连续存放在磁盘上。因此，“给我槽位 n”是一次紧凑的顺序迭代器遍历，而不是一系列分散的点读取。

写入路径中的键设计就是读取路径的优化。也就是说，同一种槽位优先布局既让刷盘产生的 L0 文件几乎没有重叠，也让区块读取成为一次连续扫描。

RPC 层提出的问题更难。getTransaction 会按签名对交易状态数据执行点查找。这正是布隆过滤器适用的场景，因为当某个签名不存在于给定 SST 中时，应该只需一次内存检查就将其排除，而不是读取一次索引。

getSignaturesForAddress 就是本文前面提到的前缀型扫描——地址到签名的索引以地址开头，因此一个账户的全部历史记录会占据一段连续的键范围，而某个地址的全部活动也就形成了这种结构擅长处理的范围扫描。

然而，应用实际提出的问题建立在这两者之上。系统并没有“给我这个地址的所有交易”这样的原语。这类问题会先执行一次前缀扫描来获取签名，再按每个签名分别执行点查找来获取交易。

实际上，一个范围查询会扇出为数百或数千个 Get，而这正是 MultiGet 的批处理所针对的工作负载。也就是说，对签名排序，按它们会访问的文件分组，并且只查询一次每个文件的索引和过滤器。

一个从外部看只是一次 API 调用的查询，在读取路径上会依次触发本文介绍的所有机制：迭代器、前缀排序、布隆过滤器、批量摊销和块缓存。

我们构建了这个 API 调用。

过去，开发者必须在客户端循环调用 getSignaturesForAddress 和 n 次 getTransaction，并实现 n+1 模式最终总会需要的重试逻辑。

getTransactionsForAddress 将这个循环整合为一个方法，并提供多项与本文所述读取路径机制相匹配的功能。

升序和降序分别对应迭代器的两个方向。基于游标的分页会返回一个形如 slot:position 的令牌，它代表一个键位置。因此，继续分页查询就是重新将扫描定位到上一次停止的位置。槽位和时间过滤器会提前限制工作范围，而不是事后丢弃结果。

为该方法提供服务的归档系统在 RocksDB 中保存了 Solana 的完整交易历史——总计数百 TB。我们将其从 ClickHouse 迁移到了 RocksDB，这也是本系列文章诞生的原因：我们逐个列族调优这些文章介绍的存储引擎，让一个账户的全部生命周期成为一次连续扫描，让一次签名查找只需一次内存检查。正因如此，我们拥有整个 Solana 中性能最高的归档系统。

总结

读取路径是 LSM 树的还款计划，而本文将它呈现为一张明细账单。一次查找从最新版本遍历到最旧版本，依次经过内存表、L0 和所有已排序层级，并在找到第一个版本时停止。其他所有功能和工具都旨在尽量减少这次搜索所需的访问次数：布隆过滤器直接在内存中判断某个键是否确定不在文件中，从而让该文件保持关闭；块缓存降低必须打开的文件再次打开时的成本；前缀设计则把唯一成本可控的范围扫描形式，转化为应用实际需要的形式。

放大三角是记录这一切的账本：读取成本由内存偿还，写入成本则更早以连续写入的方式分期支付。空间成本则悄然累积在搜索越过的每个墓碑标记和被遮蔽版本中。

需要注意的是，本文介绍的每种结构都只是在管理文件累积、失效版本和未折叠归并链带来的成本。本文没有介绍任何真正消除这些成本的机制。真正负责消除它们的机制会在后台持续运行，而决定它运行得多积极，是 RocksDB 中影响最大的一项调优决策。本系列下一篇文章将介绍压实：它的作用、RocksDB 提供的三种压实风格，以及 Solana 的 Blockstore 为何曾以著名的方式切换风格，之后又切换回来。

如果花一下午阅读数据库读取路径的演示正合你意，欢迎加入我们一起构建。这里介绍的读取路径正是我们用来处理 Solana 完整历史记录的路径。在这一规模下，是查询布隆过滤器还是打开文件，都会转化为真实的硬件和资金成本。我们的工程团队正在招聘。前往 helius.dev/careers 查看所有空缺职位。