Part 5 of 8 · 3 min read
How an LSM-tree writes and reads
A memory table, a log, sorted files on disk and the search order for a key.
Think of a post room. New letters go into an in-tray on the desk. When the tray is full, the clerk sorts it and files it as a neat, sorted bundle. To find a letter, the clerk looks in the tray first, then in the newest bundle, then the next oldest, and so on.
An LSM-tree works the same way. The book builds it up in steps.
SSTable
A sorted string table (SSTable) is a file of key-value pairs sorted by key, in which each key appears once.
Example: a file holding apple=3, banana=7, cherry=1 in that order.
Sorted files have three advantages, as the book says. They are easy to merge, even if larger than memory, like the merge step of merge sort. They need only a sparse index in memory, since the sorted order tells where to look: knowing the positions of handbag and handsome, a reader can jump to handbag and scan forward to find handiwork. And blocks of records can be compressed.
Memtable
A memtable is a sorted structure kept in memory (such as a balanced tree) that collects the newest writes before they are written to disk as an SSTable.
Example: the memtable holds the last 64 MB of writes, sorted by key.
The steps in the book:
- Write. Add the write to the memtable. Also append it to a log on disk, only to rebuild the memtable after a crash.
- Flush. When the memtable grows past a threshold, typically a few megabytes or more, write it to disk as a new SSTable. This is a fast sequential write because the data is already sorted. Start a new memtable. The old log can be discarded.
- Read. Look in the memtable, then the newest SSTable, then the next older, until the key is found.
- Compact. In the background, merge SSTables into larger ones, keeping the newest value of each key and dropping overwritten and deleted values.
A worked example. Two SSTables, older first:
| Older file | Newer file |
|---|---|
| a=1, c=3, e=5 | a=9, d=4, e=DELETED |
Merging walks both files side by side and takes the smaller key each time:
- Key a: appears in both. The newer value wins: a=9.
- Key c: only in the older file: c=3.
- Key d: only in the newer file: d=4.
- Key e: the newer file holds a deletion marker, so e is dropped from the result.
Merged file: a=9, c=3, d=4.
The deletion marker is called a tombstone. A delete cannot remove the old value from older files straight away, since the files are never edited. So the delete is written like any other write, as a marker. The marker hides older values, and compaction removes both.
A read for key e before the merge finds the tombstone in the newer file, and returns "not found" without looking further.
This design suits writes. Every write is an append to a log and an insert in memory. The disk work is sequential. The book says the LSM-tree can support remarkably high write throughput.
The idea comes from the paper by Patrick O'Neil and colleagues that gave it the name Log-Structured Merge-Tree. LevelDB and RocksDB are storage engines built on it. Cassandra and HBase use similar engines, and they take the terms SSTable and memtable from Google's Bigtable paper. Lucene, the engine inside search systems, uses a similar scheme for its word list (module 3 of this level).
Common mistake
Forgetting that the log is not the database. The log has only the newest writes and exists to rebuild the memtable after a crash. It is thrown away after each flush.
Check yourself:
- In the merge example, what is the final value of
e, and why? - Why does an LSM-tree write a log as well as keeping a memtable?