LSM trees and SSTables
A storage design that never changes a file once it is written, and why that makes writes cheap and reads more work.
5 minute lesson
Append and never overwrite
A B-tree changes its pages in place: every write lands somewhere else on the disk. An LSM tree takes the opposite approach. It collects writes in memory and writes them out together, as a sorted file that is never changed again.
- B-treeChanges pages in place
- LSM treeOnly adds new files
- LSM tree
- A storage structure that collects writes in memory and writes them to disk as sorted files that are never changed, merging the files later.
- SSTable
- A file of sorted keys and values that is written once and never changed.
- compaction
- Merging several sorted files into one, dropping values that were overwritten or deleted.
Key terms
The way of a write
- Log and memory
A write is appended to a log on disk, so that a crash cannot lose it. Then it goes into a sorted table in memory. That is all the write waits for.
- Log on diskappended
- Table in memorysorted
- Flush
When the table in memory is full, it is written to disk in one piece, as an SSTable: a file of sorted keys that will never be modified.
- Table in memoryfull
- SSTablewritten once
- Many files
Flush after flush, the files pile up. A key that was written three times now has three versions in three files. The newest one counts.
- File 1x = 1
- File 2x = 2
- File 3x = 3
What has to happen before an LSM tree confirms a write?
- An append to the log and an insert in memory
- A merge of the write into every file on disk
- A search for the old value in all the files
- A rewrite of the page that holds the old row
Show the answer
- An append to the log and an insert in memory
The log entry makes the write safe against a crash, and the table in memory makes it visible to reads. Both are fast: one sequential append and one insert in memory. Everything else, such as flushing and merging, happens later and in bulk, which is why this design handles very high write rates.
An LSM write is a log append plus a memory insert. The disk work is done later, in bulk.
Reading and tidying up
- A read looks in memory first, then in the files, newest first. A Bloom filter for each file says whether the key can be in it at all, so most files are skipped.
- Compaction runs in the background. It merges several files into one, keeps the newest version of every key and drops the rest. Without it the files and the stale versions would grow for ever.
Why does an LSM tree need compaction?
- To merge the files and discard outdated versions
- To make the writes safe against a sudden crash
- To copy the files onto the other machines
- To sort the keys inside the table in memory
Show the answer
- To merge the files and discard outdated versions
Files are only ever added, and an update does not remove the old value. It just adds a newer one. Left alone, the files would multiply and fill with versions that no read will ever return, and each read would have more files to check. Compaction merges them and keeps only the newest version of each key.
Compaction merges files and drops stale versions, so that reads stay fast and space is reclaimed.
Which engine for which load
B-tree
update in place
- A write
- Finds and changes a page
- A read
- One path down the tree
- Fits
- Read-heavy and mixed loads
LSM tree
append and merge
- A write
- An append and a memory insert
- A read
- May check several files
- Fits
- Write-heavy loads
How does an LSM tree store a write, and what does that cost when reading?
Show the answer
It appends the write to a log and puts it into a sorted table in memory. Full tables are flushed to disk as sorted files that are never changed. Writes are therefore cheap and sequential. A read may have to look in memory and in several files, newest first, helped by Bloom filters, and compaction must keep merging the files in the background.
Recap
- An LSM tree collects writes in memory and flushes them as sorted files that never change.
- Reads check memory and then files, newest first. Bloom filters skip files without the key.
- Compaction merges files and drops old versions. Writes are cheap, and reads and merging pay.