The Price of Cheap Writes: How does RocksDB read?

How does RocksDB read a key?

A read in RocksDB proceeds from the newest data to the oldest, stopping at the first version of the key it finds. That's it; everything else makes the process faster.

The search order is fixed and mirrors the write path outlined in the previous article, but in reverse: it traverses the active memtable, immutable memtables, SST files in level 0, and sorted SST files from level 1 down.

RocksDB first checks the active memtable since it holds the most recent writes, lives in memory, and uses a skiplist. As a result, a lookup is a sorted, in-memory search that costs almost no I/O. The search stops as soon as it finds the key.

After the active memtable, RocksDB checks any immutable memtables that have filled up but haven’t been flushed to disk yet. It checks them next, newest to oldest.

Disk is then checked. Level 0 files must each be checked individually, newest to oldest, because their key ranges overlap. This is because each one is a snapshot of whatever a memtable happened to absorb so that the same key can be in two level 0 files at once.

Every level 0 is a separate place where a key might hide, which is precisely why the level 0 file count taxes reads and why RocksDB stalls writes to keep it bounded.

From level 1 down, SST files within a given level are sorted and non-overlapping, so at most one file per level can contain the key. Finding that file is a binary search over file metadata, and then the search descends into the file itself. The index block locates the right data block, and the data block either holds the key or shows that this level doesn’t have it.

Sequence numbers are important to RocksDB’s read path because they stop a search at the first version it finds. This guarantees that this version is the newest. If a read finds a tombstone, for example, it succeeds and returns that the key was deleted. Thus, the search ends at the tombstone and leaves the older value on disk.

What read operations does RocksDB offer?

RocksDB exposes four ways to read, each using the read path differently: Get, MultiGet, Iterators, and Snapshots.

Get

Get is the point lookup we traced in the previous section. That is, finding one key in a newest-to-oldest search where the first version wins.

MultiGet

MultiGet batches point lookups. A read can give RocksDB a set of keys, which it sorts and groups by the files they might touch.

Effectively, this helps RocksDB open a single SST and consult its index and filter blocks once, and batches the I/O. This is the same read path as Get, but the costs are fixed and amortized across the batch.

Iterators

Iterators scan ranges, meaning that they seek to a key and walk forward or backward in sorted order.

Effectively, an iterator is a k-way merge (i.e., it combines k different sorted lists into a single, fully sorted sequence). Every live data source—the memtable, any immutable memtable, every L0 file, and one file per deeper level—contributes its own sorted cursor, and a heap repeatedly yields whichever cursor holds the next smallest key.

This newest-version-first rule applies at every step, so if several sources offer the same key, the newest version wins and the rest are discarded.

Shadowed values and tombstones are skipped as the iterator advances, which means a range full of deleted keys is a range the iterator must silently traverse without returning anything. A heavily deleted keyspace makes scans slow in ways point lookups never seem to notice.

Snapshot

A Snapshot is a sequence number, captured at a moment in time. Any read that carries it simply ignores versions newer than that number and returns the newest version at or below it. This allows for consistent point-in-time reads, implemented as an integer comparison.

Taking a snapshot is effectively free because the cost accrues later; a live snapshot can still see versions that can't be reclaimed, no matter how old they are.

Both Get and MultiGet know exactly which key they want, which means the search can ask a cheaper question than “where is this key?” Namely, “which files definitely don’t have it?” Iterators never get that shortcut. Answering the cheaper question is the bloom filter’s entire job.

What is a bloom filter?

A bloom filter answers one question about a set: is this element definitely not in it? The answer is either definitely not or maybe, never a confident yes. A file that definitely does not have a key is one the search never opens, saving I/O.

When an SST is built, it runs every key through a handful of hash functions, and each hash sets a bit in a compact bit array (the filter block).

At read time, the lookup hashes the sought key the same way and checks those bits. If any bit is unset, the key was never inserted, meaning the key is definitely not here.

If all bits are set, the key is probably present—probably because other keys’ hashes can happen to cover the same bits.

This means that there can be false positives—the search opens the file, checks, and finds nothing, having burned the I/O the filter exists to save.

At RocksDB’s conventional setting of ten bits per key, the false-positive rate is roughly one percent. Ten bits buys a 99% chance of skipping a file that lacks the key. A filter for a million-key SST is a bit over a megabyte, lives in memory alongside the index, and is consulted without touching the disk it protects. Only a handful of structures in systems engineering buy more for less.

This is also why the previous article in this series found a filter block size of zero. Bloom filters are opt-in, configured via the filter_policy, at a bits-per-key of the application’s choosing, and the default sets none.

This default is defensible for a library that cannot know its workload, but is indefensible in production where the filter is the difference between a missing key costing one memory check per file and costing an index-block read per file.

One limitation that exists is that bloom filters only help when the search knows the exact key. A bloom filter can answer whether key:0301 is in this file, but it cannot answer whether this file contains anything between key:0090 and key:0110 because hashes destroy the order.

Iterators, which never know their next key in advance, get no help from this structure. Bloom filters are a point-lookup technology; range-heavy workloads must look elsewhere for relief.

What about RocksDB prefix seeks?

RocksDB’s partial remedy for the scan problem is to change what gets hashed. A prefix extractor tells RocksDB that keys have meaningful structure (i.e., the first eight bytes, say, or everything before a separator). Once RocksDB knows what a prefix is, it can build bloom filters over prefixes instead of, or alongside, whole keys. A filter that answers whether a file contains a key that starts with a certain prefix can help an iterator.

However, this shortcut only works with one prefix.

A scan for a given prefix can skip files and blocks the same way that point lookups do. A scan that crosses from one prefix into the next does not get the same help. How to maintain iteration-order guarantees across prefixes warrants its own deep dive into the configurational fine print that makes it possible.

Prefix seek does not make range scans cheap in general.

Rather, it makes one specific, extremely common shape of range scan cheap for a given prefix.

What is the RocksDB block cache?

The block cache is an in-memory cache of uncompressed blocks. When a data block is read from an SST, it is decompressed and kept, so the next read that needs the same block finds it without touching disk. This means hot key cluster in hot blocks, and hot blocks stop costing I/O.

Thus, bloom filters try to keep searches out of files, while the block cache makes the files it must enter cheap to revisit.

One subtlety is that there are two caches.

The block cache is RocksDB’s own, which holds uncompressed blocks it manages explicitly. Beneath it is the operating system’s page cache, which holds the raw, compressed file pages that RocksDB has recently read. The same data can occupy both at once (i.e., uncompressed in the block cache, and compressed in the page cache), which is why RocksDB’s true memory footprint is chronically underestimated, and why cache-sizing discussions that ignore the page cache are only reasoning about half of the system.

Index and filter blocks get special treatment. They are small, consulted on nearly every read that reaches their file, and are catastrophically expensive to miss, so keeping them resident is almost non-negotiable.

Whether they live inside the block cache’s budget or outside it in the table readers’ own memory is a configuration choice (i.e., cache_index_and_filter_blocks).

What do tombstones and merge chains cost readers?

Tombstones and merge chains are record types from the write path that impacts the read path, but can only be settled by compaction. Tombstones accumulate until compaction drops them and the corpses they shadow, and merge chains grow until compaction folds them into settled values.

A tombstone is cheap for the point lookup that finds it. That is, the search stops and delivers the answer since “deleted” is a valid result. However, an iterator can't stop at a tombstone. Rather, it must resolve the tombstone, skip the versions it shadows, and keep advancing until it finds the next live key. A heavily deleted keyspace is a minefield of entries that must be traversed and discarded while returning nothing; scans over it can do a lot of arbitrary work to produce little output. Point lookups never notice this, while range scans are defenseless against it.

Merge operands run the same bill, but in the other direction. A read of a merged key cannot stop at the newest record because an operand is a description of a change and not a value. So, the search must keep collecting operands until it reaches a full value, a tombstone, or the bottom of the tree, and then fold the chain through the merge operator.

The previous article’s walkthrough folded a chain of three, but note that nothing in the design bounds the chain at three. A counter merged ten thousand times between compactions is a read that gathers and folds ten thousand operands, and the write path did nothing to prevent it.

The Amplification Triangle

The amplification triangle is a three-way trade-off that governs every LSM tree: write amplification, read amplification, and space amplification. Improving any two worsens the third.

Athanassoulis et al. formalized these trade-offs as the RUM conjecture (2016), which holds that an access method can minimize at most two of read overhead, update overhead, and memory or space overhead, with the third absorbing the cost. B-trees sit at one position (i.e., cheap reads, expensive updates), while LSM trees sit at another (i.e., cheap updates, expensive reads), and the triangle maps the territory in between.

Everything in this article has been one corner of the triangle defending itself.

Write amplification is the ratio of bytes physically written to disk to bytes the application logically writes. A single Put is written once to the WAL, once when flushed to L0, and every time compaction carries it down a level. This means that one logical write could routinely become ten to thirty physical writes over its lifetime in a leveled LSM with a dozen levels. While the previous article celebrates that every one of those writes is sequential, this article laments it.

Read amplification refers to the number of places a query must check to find its answer. For a point lookup, the worst case is every memtable, L0 file, and one file per deeper level (i.e., the search traced at the top of this article), and the realized cost is whatever survives the bloom filters and the block cache. For a range scan, it is the k-way merge holding every source open at once. Read amplification is largely what this article covers: filters, caches, and prefix extractors acting as the machinery to pay it down.

Space amplification is the ratio of disk consumed to logical data stored. Old versions awaiting compaction, tombstones and the corpses they shadow, unfolded merge chains, and every version a live snapshot pins all consume disk space for data the application can no longer read or no longer wants. Well-tuned leveled compaction holds this near 1.1x, while other arrangements trade considerably more.

The triangle holds that improving any two corners worsens the third. That is,

• Compact aggressively: reads get faster and space gets tighter, but every key is rewritten constantly, and write amplification climbs
• Compact lazily: writes glide, but files pile up for reads to check and dead data lingers on disk
• Spend memory on filters: caches and reads recover, but memory is the quiet fourth resource the triangle’s corners all bid on

There is no setting marked “fast.” There are only positions on the triangle that match, or fail to match, a given workload.

A Walkthrough of the Read Path

The following reuses the project from the previous article’s walkthrough, with statistics enabled.

Replace the contents of src/main.rs with:

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);
			}
		}
	}
}

Above, we have three flushed L0 files whose key ranges fully overlap, so no file can be excluded by range metadata alone because every file is a place that both keys might hide.

The hit (i.e., key:0404) lives only in the oldest file, forcing the newest-first search to deal with two files that don’t have it before reaching the one that does.

The miss (i.e., key:0303) sits inside every file’s range and inside no file, meaning nothing but a bloom filter could save that read.

Run it as is, and then with the argument bloom.

Without filters, the output is:

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

We have six data-block accesses to answer two lookups. The hit read a data block from each of the three files, two of which weren’t helpful, costing three disk reads. The miss then checked the same three files, and its three data-block accesses were cache hits only because the first lookup had just warmed the cache. The block cache did its job, and it’s the only thing that did.

With filters, the output is:

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

We have one data-block access in total. We can verify the arithmetic for useful being 5 by hand:

• The hit consulted the newest file’s filter and the second file’s filter, and both returned no. The oldest file’s filter returned the one full.positive, which proved a true positive. This gives us two skips
• The miss consulted all three filters and got three no’s, which means we have three skips and zero files opened

Sum the hit and the miss, and we get five file checks. The five file-checks that filtered answered from memory are the five data-block reads the no-filter run had to perform. So, ten bits per key turned six block accesses into one.

This is effectively the amplification triangle on a smaller scale. The no-filter run paid read amplification in full, the filtered run paid for it in memory (i.e., a few hundred bytes of filter per file), and the write path paid nothing either way. Every tuning decision in RocksDB is this trade at a larger scale.

How does Solana stress the read path?

The previous article cast the validator as the write path’s stress test. That is, shreds coming in at line rate, forever. The read side is the other half of the bargain because a ledger nobody can read back is just an expensive way to warm a data center.

Every claim this article has made about search order, filters, and key design shows up in how Solana’s data actually gets queried.

Inside the validator, the Blockstore’s reads come in two different shapes: serving repair requests, and replaying or streaming a block.

Serving repair requests means other validators are asking for shreds that they missed. This is a point lookup by (slot, index). Replaying or streaming a block’s worth of ledger is a range scan over a given slot.

Because shred keys lead with the slot number, every shred of a slot sits contiguously on disk, so “give me slot n” is a tight, sequential iterator walk rather than a scatter of point reads.

The key design from the write path is the read path optimization. That is, the same slot-first layout that made flushes produce barely overlapping L0 files makes block reads a single contiguous sweep.

The RPC layer asks harder questions. getTransaction is a point lookup by signature into the transaction-status data. This is the case that bloom filters exist for, since a signature absent from a given SST should cost one memory check to rule out instead of an index read.

getSignaturesForAddress is the prefix-shaped scan from earlier in this article—the address-to-signature index leads with the address, so one account’s entire history occupies one contiguous key range, and an entire address’s activity becomes the shape of range scan that the structure handles well.

The questions that applications actually ask, however, sit on top of both. There is no primitive for “Give me all the transactions for this address.” This type of question becomes a prefix scan for the signatures, then a point lookup per signature for the transactions.

Effectively, one range query fans out into hundreds or thousands of Gets, which is precisely the workload that MultiGet’s batching exists for. That is, sort the signatures, group them by files they touch, and consult each file’s index and filters once.

A query that looks like one API call from the outside is, on the read path, every mechanism this article has described firing in sequence: iterator, prefix ordering, bloom filters, batch amortization, and block cache.

We built that API call.

Historically, developers had to run a client-side loop of getSignaturesForAddress and n getTransaction calls, with the retry logic that n+1 patterns always end up needing.

getTransactionsForAddress collapses that loop into a single method with a variety of features that match the read path mechanics discussed in this article.

Ascending and descending sort order are the iterator’s two directions. Cursor-based pagination hands back a token of the form slot:position, which is a key position, so resuming a paginated query is re-seeking a scan to where the last one stopped. Slot and time filters bound the work rather than discard it afterward.

The archival system serving that method holds Solana’s full transaction history in RocksDB—hundreds of terabytes. We migrated it from ClickHouse to RocksDB, and it is the reason that this series exists: the storage engine described across these articles is the one we tuned, column family by column family, to make an account’s entire lifetime a contiguous scan and a signature lookup a single memory check. This is why we have the most performant archival system in all of Solana.

Conclusion

The read path is the LSM tree’s repayment schedule, and this article presents it as an itemized bill. A lookup traverses newest to oldest, through the memtable, L0, and all sorted levels, and stops at the first version it finds. Every other feature and piece of tooling exists to minimize the number of touches that search requires: Bloom filters answer whether a key is definitely not in a file from memory, so that file stays closed; the block cache makes it so files that must be open are cheap to reopen; and prefix design turns the one affordable shape of the range scan into the shape applications actually need.

The amplification triangle is the ledger that records all of this in: read cost paid down with memory, write cost paid earlier in sequential installments. Space cost quietly accruing in every tombstone and shadowed version the search steps over.

Note that every structure in this article merely manages the cost of accumulated files, dead versions, and unfolded merge chains. Nothing covered in this article actually removes it. The thing that removes it runs in the background, continuously, and deciding how aggressively it runs is the single most consequential tuning decision in RocksDB. The next article in this series is compaction: what it does, the three styles RocksDB offers, and why Solana’s Blockstore famously switched styles and then switched back.

If spending your afternoon reading a walkthrough about a database’s read path sounds like your cup of tea, build with us. The read path described here is the one we operate against Solana’s full history, where the difference between a bloom filter consulted and a file opened is measured in real hardware and real money. We’re hiring across our engineering team. See all open roles at helius.dev/careers