What I Self-Host
Concept of the day · databases
LSM Trees
Trade read amplification for write throughput by never updating in place.
The mechanism. Writes go to an in-memory table (the memtable) plus a write-ahead log, and nothing else. When the memtable fills, it is flushed to disk as an immutable sorted file (an SSTable). Reads check the memtable, then each level of SSTables, newest first. Background compaction merges SSTables to bound how many a read must consult and to discard overwritten keys.
Why it is fast to write. Every write is sequential. A B-tree, by contrast, must find and modify the right page, which is a random write, and it writes a whole page to change one row. LSM trees turn random writes into sequential ones at the cost of making reads check several places.
The three amplifications. Write amplification: compaction rewrites the same data repeatedly. Read amplification: one logical read touches many files (mitigated with bloom filters per SSTable). Space amplification: obsolete versions live until compaction. Leveled compaction minimises space and read amplification; size-tiered minimises write amplification. You cannot minimise all three — that is the RUM conjecture.
Where you meet them. RocksDB, LevelDB, Cassandra, ScyllaDB, HBase, and the storage engines under ClickHouse and InfluxDB.
Takeaway. If your workload is write-heavy with range scans, this is the shape. If it is read-heavy point lookups on a small dataset, a B-tree still wins.