wire / wire-format / lsm-tree
An LSM tree is a data structure for write-heavy workloads. Writes go to an in-memory memtable (sorted). When full, the memtable is flushed to disk as an immutable SSTable (sorted string table). Background compaction merges SSTables to reduce read amplification. Used in LevelDB, RocksDB, Cassandra, HBase, and SQLite (LSM variant).
aka: LSM tree (Log-Structured Merge tree)
spec: LSM tree (Patrick O'Neil, 1996)
An LSM tree is a data structure for write-heavy workloads. Writes go to an in-memory memtable (sorted). When full, the memtable is flushed to disk as an immutable SSTable (sorted string table). Background compaction merges SSTables to reduce read amplification. Used in LevelDB, RocksDB, Cassandra, HBase, and SQLite (LSM variant).
| field | size | meaning |
|---|---|---|
| Memtable | in-memory | Sorted in-memory structure (skip list or red-black tree). All writes go here first. Also written to WAL for durability. |
| WAL (Write-Ahead Log) | disk | Append-only log of writes. Used for recovery if memtable is lost. |
| SSTable (Level 0) | disk | Flushed memtable. Multiple SSTables per level (overlapping key ranges). Bloom filter per SSTable. |
| SSTable (Level 1+) | disk | Compacted SSTables. Non-overlapping key ranges within a level. Sorted. |
| Compaction | background | Merge SSTables from one level to the next. Strategies: size-tiered (Cassandra), leveled (LevelDB/RocksDB), time-window (time-series). |
| Read amplification | metric | Number of SSTables checked per read. Bloom filters reduce this. |
| Write amplification | metric | Number of times a key is rewritten during compaction. Leveled compaction has high write amplification. |
| Space amplification | metric | Ratio of total data size to logical data size. Size-tiered has high space amplification. |
example:
00 00 00 00
LSM tree (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/lsm-tree
or /wire-format/lsm-tree.json