wire / wire-format / lsm-tree

LSM tree (Log-Structured Merge 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).

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: LSM tree (Log-Structured Merge tree)

wire format

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).

fieldsizemeaning
Memtablein-memorySorted in-memory structure (skip list or red-black tree). All writes go here first. Also written to WAL for durability.
WAL (Write-Ahead Log)diskAppend-only log of writes. Used for recovery if memtable is lost.
SSTable (Level 0)diskFlushed memtable. Multiple SSTables per level (overlapping key ranges). Bloom filter per SSTable.
SSTable (Level 1+)diskCompacted SSTables. Non-overlapping key ranges within a level. Sorted.
CompactionbackgroundMerge SSTables from one level to the next. Strategies: size-tiered (Cassandra), leveled (LevelDB/RocksDB), time-window (time-series).
Read amplificationmetricNumber of SSTables checked per read. Bloom filters reduce this.
Write amplificationmetricNumber of times a key is rewritten during compaction. Leveled compaction has high write amplification.
Space amplificationmetricRatio of total data size to logical data size. Size-tiered has high space amplification.

example:

00 00 00 00

LSM tree (placeholder)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/lsm-tree or /wire-format/lsm-tree.json