The LSM Read Penalty (Read Amplification)
While LSM-trees achieve stellar write throughput, read operations face a significant challenge: a key may reside in the active Memtable, an immutable Memtable, or across multiple SSTables spanning several disk levels. Without optimizations, a single Get(key) could require dozens of random disk reads. To achieve sub-millisecond reads, modern LSM engines combine Sparse Indexes and Bloom Filters.
The Multi-Layer Read Pipeline
Under the Hood: Bloom Filter Mathematics
A Bloom filter is a space-efficient probabilistic data structure that tests set membership with zero false negatives (if it says the key is not in the SSTable, it is 100% guaranteed not to be there) and a tunable false positive rate p.
Given n keys and target false positive probability p, the optimal number of bits m and hash functions k are:
m = - (n * ln(p)) / (ln(2)^2)
k = (m / n) * ln(2)Allocating just 10 bits per key achieves a false positive rate of ~ 1%, allowing the engine to bypass physical disk reads for 99% of non-existent key lookups.
The Sparse Index
Rather than indexing every single key in the SSTable (which would consume excessive RAM), the engine creates a Sparse Index storing only one key for every 4KB data block (the first key of each block). To find key K, the engine performs a binary search in RAM over the sparse index to identify the single 4KB block that could contain K, and reads only that 4KB chunk from disk.
Worked example: sizing filters and indexes
One SSTable holds 1 million keys. With 10 bits per key the filter is 10 million bits, about 1.25 MB. The optimal number of hash functions is k = (m / n) x ln 2, which is about 6.9, so 7. The false positive rate is about (1 - e^(-k n / m))^k, roughly 0.8%.
| Bits per key | Best k | False positive rate |
|---|---|---|
| 5 | 3 | about 9% |
| 10 | 7 | about 0.8% |
| 15 | 10 | about 0.07% |
For a whole node holding 1 TB in 4 KB blocks, the index has about 268 million entries. At roughly 30 bytes per entry (separator key plus block handle), that is about 8 GB, too much to pin in RAM. RocksDB addresses this with partitioned index and filter blocks that are loaded on demand through the block cache, keeping only the top-level partition index resident.
A lookup for a missing key
A key absent from all 6 sorted runs it might be in: without filters, 6 block reads. With 1% false positive filters the expected cost is 6 x 0.01 = 0.06 block reads. That is why negative lookups, such as "does this username exist?", are nearly free in LSM engines.
Optimizations real engines use
- Prefix Bloom filters (RocksDB): hash a key prefix so bounded range scans within one prefix can skip files.
- Monkey-style allocation: giving smaller, upper levels lower false positive rates and the huge last level a higher one minimizes total expected I/O for the same memory.
- Ribbon filters (RocksDB): about 30% less memory than Bloom filters for the same false positive rate, at more CPU to build.
- Block cache: hot index, filter and data blocks stay in memory, so most reads never reach the device.