LSM trees

Why some databases never edit a row where it lives on disk

A log-structured merge tree (LSM tree) never updates data in place. New writes go into a sorted table in memory called the memtable, and are also appended to the write-ahead log so a crash can't lose them.

When the memtable fills (say 64 MB), it is written out in one go as an SSTable (sorted string table): an immutable file of sorted keys. Change user:42 three times and three files may hold it; the newest wins.

Over time, a background job called compaction merges SSTables like merge sort does, keeping only the newest version of each key and dropping deleted ones. Files are arranged in levels, each about T times bigger than the one above.

LSM trees

Discord stored billions of chat messages in Cassandra

Apache Cassandra, and ScyllaDB which Discord later moved to, store data in LSM trees. Chat is write-heavy: millions of messages arrive every minute and are rarely edited, which is exactly the load LSM trees suit.

The same design sits under RocksDB and LevelDB (made at Facebook and Google), Google's Bigtable and Apache HBase. Meta built MyRocks, a MySQL storage engine on RocksDB, to store data more compactly than the usual B-tree engine.

LSM trees

The database saves up changes and writes one big sorted file

A B-tree rewrites each changed page in place, so updates to random keys become small writes scattered across the disk. Disks are far faster at long sequential writes: a hard drive skips a multi-millisecond seek per write.

An LSM tree sorts thousands of random writes in memory, then writes them as one sequential file, so each write costs far less. The price: reads check the memtable, then files newest first, and compaction rewrites data several times.

To keep reads quick, each SSTable has a Bloom filter that says "this key is definitely not here", so most files are skipped without reading them, and the levels formula keeps the number of files to check small.