⏱️ Lectura: 12 min
Facebook, Netflix, and LinkedIn run their highest write-volume databases on the same idea: never modify a file that has already been written to disk. That rule, seemingly simple, is the core of LSM trees (Log-Structured Merge-Tree), the data structure behind RocksDB, Cassandra, LevelDB, and dozens of systems that need to accept a high volume of concurrent writes without blocking whoever comes next.
📑 En este artículo
The memtable in RAM, the write-ahead log, the immutable SSTables on disk, and the compaction process determine whether that promise of speed holds over time or degrades.
TL;DR
- You’ll understand why an LSM tree writes faster than a traditional B-tree.
- You’ll be able to distinguish memtable, write-ahead log (WAL), and SSTable in any LSM-based database.
- You’ll know what compaction is and why it determines long-term performance.
- You’ll be able to install and try RocksDB in Python with a working example.
- You’ll identify when it’s NOT a good idea to use an LSM-based database.
- You’ll learn the exact commands to check compaction status in RocksDB and Cassandra.
- You’ll compare LSM trees against B-trees with a practical decision table.
What Is an LSM Tree and Why It Matters
An LSM tree (Log-Structured Merge-Tree) is a data structure designed for databases that need to absorb many writes without paying the cost of rewriting an entire file each time. The idea originated in a 1996 paper by Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil, which proposed separating the write (fast, sequential, in memory) from the final organization of the data, which happens later, in the background.
A B-tree, the structure Postgres or MySQL/InnoDB use by default, updates data in place: it finds the exact page where the key lives and rewrites it. That operation is cheap for reads but expensive for writes under heavy concurrency, because every write requires locating a page on disk and modifying it. An LSM tree flips that logic: it never looks up or modifies an existing page. Everything new gets appended, in order, to files that get merged later. Writing to RocksDB or Cassandra is, essentially, an append: there’s no prior lookup, no locking of a shared page.
This architecture matters because it determines which engine fits each scenario: IoT sensors, event logs, time series, and activity feeds, in other words, anything that writes far more than it deletes.
How an LSM Tree Works Internally
When an application writes a key to a database built on LSM trees, two things happen almost simultaneously. First, the engine records the operation in the write-ahead log (WAL), an append-only file on disk that guarantees the write survives a power outage. Second, the same key gets inserted into the memtable, an ordered structure in RAM (usually a skip list or a red-black tree) that keeps recent keys available for immediate reads.
The memtable has a size limit. Once it fills up, the engine flushes it to disk as an SSTable (Sorted String Table): an immutable file, sorted by key, that never gets modified again. That never modified part is the key to the entire design: once written, an SSTable is only read or deleted, never edited in place.
flowchart LR
A["Write (SET key)"] --> B["WAL (write-ahead log)"]
A --> C["Memtable (in-memory tree)"]
C -->|"memtable full"| D["Flush to SSTable"]
D --> E[("Disk: immutable SSTables")]Over time, dozens of SSTables pile up at the shallowest level (L0). Reading a key would then mean checking the memtable and, in the worst case, every L0 SSTable one by one. To avoid that degradation, a background process called compaction merges several SSTables into one new, larger one, discarding the old versions of each key and the tombstones (deletion markers) that have already served their purpose. The result of a compaction gets promoted to a deeper level: L1, L2, and so on, each one larger and colder than the previous.
sequenceDiagram
participant M as Memtable
participant L0 as SSTable L0
participant L1 as SSTable L1
M->>L0: flush when the memtable fills up
L0->>L1: compaction merges and sorts
Note over L0,L1: duplicate keys and tombstones are discardedEach SSTable also keeps a bloom filter per key, a probabilistic structure that can quickly answer whether a key is definitely not in that file, without needing to open it. That combination of sorted SSTables, levels, and bloom filters is what lets a read avoid checking every file on disk.
Practical Examples
The behavior of an LSM tree is easier to understand in code. The first example simulates, in a few lines, the bare minimum any LSM-based engine does: accumulate writes in memory and flush them, sorted, to a file.
class MemTable:
def __init__(self):
self.data = {}
def put(self, key, value):
self.data[key] = value
def flush_to_sstable(self, path):
with open(path, 'w') as f:
for key in sorted(self.data):
f.write(key)
f.write('=')
f.write(self.data[key])
f.write(chr(10))
self.data = {}
memtable = MemTable()
memtable.put('user:42', 'ana')
memtable.put('user:7', 'beto')
memtable.flush_to_sstable('sstable_0001.txt')Running this script leaves memtable.data empty after flush_to_sstable, and the file sstable_0001.txt contains the two keys sorted alphabetically (user:42 before user:7, because the comparison is textual, not numeric). That detail (the order is lexicographic, unless the application controls it) is a common source of surprises when designing keys for production.
The second example uses actual RocksDB, through the official Python binding, to show what the same idea looks like in a production engine.
import rocksdb
opts = rocksdb.Options()
opts.create_if_missing = True
db = rocksdb.DB('tienda.db', opts)
db.put(b'product:1001', b'mechanical keyboard')
db.put(b'product:1002', b'wireless mouse')
valor = db.get(b'product:1001')
print(valor)
stats = db.get_property(b'rocksdb.num-files-at-level0')
print(stats)This code creates or opens a database in the tienda.db directory, writes two keys, and reads them back. The call to get_property with the rocksdb.num-files-at-level0 property returns how many SSTables currently exist at level L0; it’s the most direct way to confirm, from code, that the engine is generating files and not just accumulating everything in the memtable.
Getting Started
To try an LSM tree without writing your own engine, it’s enough to install RocksDB or spin up a Cassandra node. Both expose, through different commands, exactly the same concepts: memtable, SSTable, and compaction.
On Linux, installing the RocksDB Python binding first requires the native library:
sudo apt-get install librocksdb-dev
pip install python-rocksdbWith that installed, the second code block from the previous section runs as-is. To force a manual compaction and see the effect on the levels, you can call the binding’s compaction method directly:
db.compact_range()💡 Tip: Forcing a full compaction with compact_range() is meant for testing or one-off maintenance. Calling it on every write in production cancels out the advantage of background writes.
That call merges the pending SSTables and updates the per-level counters. Reading rocksdb.num-files-at-level0 again after compact_range() should return a lower number, or zero, than before.
If the interest is Cassandra instead of RocksDB, the equivalent command to inspect compaction status is:
nodetool compactionstatsThat command, run on any Cassandra node, shows compactions in progress, how many bytes each has processed, and how many are pending in the queue. It’s the first place to check when write latency starts climbing for no apparent reason.
Real-World Use Cases
RocksDB, developed by Facebook based on LevelDB, is today the embedded storage engine behind MyRocks (the alternative engine to InnoDB for MySQL), CockroachDB, and Kafka Streams for local task state.
Apache Cassandra has used LSM trees since its original design, inspired by Google’s Bigtable paper and Amazon’s Dynamo paper. Each Cassandra node keeps its own memtable, its own commit log (the equivalent of the WAL), and its own SSTables on disk, which lets it scale horizontally without coordinating every write between nodes.
LevelDB, the foundation on which Google built RocksDB, runs embedded inside Chrome for IndexedDB and inside Bitcoin Core for the block index. In both cases the access pattern is the same one that drove the original design: many sequential writes, lookups by key, and tolerance for an occasional read being a bit slower in exchange for consistently fast writes.
Common Mistakes and Best Practices
The most common mistake when operating an LSM database is failing to watch write amplification: every compaction rewrites data that was already on disk, so a key can end up being physically written several times before reaching its final level. Ignoring this metric leads to a system that consumes far more disk bandwidth than its logical writes should justify.
⚠️ Watch out: if the write rate exceeds compaction speed, L0 SSTables pile up uncontrollably. This is known as a compaction storm, and it ends up blocking new writes until compaction catches up.
Another common mistake is designing keys that always grow at the end of the range, like ascending timestamps or auto-incrementing IDs. That concentrates all writes in the same range of SSTables and reduces the parallelism compaction could otherwise take advantage of. The recommended practice is to distribute the key prefix, for example with a short hash, when write volume is high.
Tombstones in Cassandra are another typical source of problems: if an application frequently deletes and rewrites the same key, tombstones pile up between compactions and a read can end up discarding hundreds of dead versions before finding the current value. Cassandra exposes the tombstone threshold per read in its warning logs, and raising it without understanding the cause only postpones the problem.
Comparison with Alternatives
The question of whether an LSM tree or a B-tree is the better fit doesn’t have a single answer: it depends on the access pattern.
| Structure | Best for | Main advantage | Limitation |
|---|---|---|---|
| B-tree (Postgres, InnoDB) | Workloads with many reads and point updates | Highly predictable single-record reads | Expensive writes: every update rewrites a page in place |
| LSM tree (RocksDB, Cassandra, LevelDB) | Write-intensive workloads: logs, time series, events | Sequential writes, almost always an append | Write amplification from compaction, and costlier reads without bloom filters |
| Hash index (Redis, memcached) | Exact-key access, no ranges or ordering | Constant-time reads and writes | Doesn’t support range queries or key ordering |
Going Deeper
The most important design decision inside an LSM engine is the compaction strategy: leveled compaction versus size-tiered compaction, also called tiered.
In leveled compaction, each level has a fixed maximum size and keys within a level don’t overlap between SSTables at that same level. When a level exceeds its limit, an SSTable gets merged with the SSTables in the next level that cover the same key range. RocksDB uses leveled compaction by default because it minimizes disk space and bounds read amplification, at the cost of more background compaction work.
In size-tiered compaction, the engine groups SSTables of similar size and merges them once enough of the same size have accumulated, without guaranteeing that keys within a level don’t overlap. Cassandra offers both strategies, configurable per table: SizeTieredCompactionStrategy, the original one, and LeveledCompactionStrategy, designed for tables with more reads than writes.
flowchart TD
A["Memtable (RAM)"] --> B["Level L0 (recent SSTables)"]
B --> C["Level L1"]
C --> D["Level L2"]
D --> E["Level LN (colder, larger)"]
subgraph Compaction
B
C
D
endThe table also reveals another design tension: bloom filters. Each SSTable keeps one to be able to answer that a key isn’t there without opening the file. The more levels a read has to check, the more filters get consulted before touching disk; tuning the false-positive rate of those filters, at the cost of more RAM, is the most direct lever for lowering read latency in a mature LSM engine.
📖 Summary on Telegram: View summary
Your next step: install python-rocksdb, run the second code example in this article, and compare the value of rocksdb.num-files-at-level0 before and after calling compact_range().
Frequently Asked Questions
What does LSM stand for in LSM tree?
LSM stands for Log-Structured Merge-Tree: a structure organized as an append-only log that merges in the background to stay sorted.
Why do LSM trees write faster than a B-tree?
Because every write is an append in memory and in the write-ahead log, with no need to locate or modify an existing page on disk, unlike a B-tree.
Which databases use LSM trees?
RocksDB, Cassandra, LevelDB, ScyllaDB, HBase, and MyRocks, the alternative storage engine for MySQL, are all built on LSM trees.
What is write amplification?
It’s the ratio between the bytes the application requested to write and the bytes the engine ends up physically writing to disk due to successive compactions.
When is an LSM-based database not a good fit?
When the workload is mostly point reads over data that rarely changes: there, a B-tree offers more predictable read latency without paying the cost of background compaction.
How do SSTables relate to LSM trees?
An SSTable is the immutable storage unit on disk that results from flushing a full memtable; the succession of SSTable levels, merged through compaction, is what constitutes the LSM tree.
References
- Official RocksDB repository: source code, design documentation, and the Python binding used in the examples.
- Official LevelDB repository: Google’s original implementation that RocksDB was based on.
- Apache Cassandra documentation: nodetool reference, compaction strategies, and internal architecture.
- Log-structured merge-tree, Wikipedia: history of the original 1996 paper and design variants.
📱 Enjoying this content? Follow @programacion on Telegram for daily tech content in Spanish: quick summaries, fresh content every day.
Imagen destacada: Foto de William Warby en Unsplash
0 Comments