LSM-Tree
A B-tree updates a record where it lives, which means finding the page and writing it back. An LSM-tree refuses to do that. Writes go into memory, memory is flushed out as a whole sorted file, and files are merged into bigger files behind you. Every write into this model becomes sequential, which is the point, and the price is that the same data is written down more than once: once when it is flushed, and again every time a merge sweeps past it. This page runs a workload and counts both numbers, so the trade is a figure rather than a claim. It also keeps a plain dictionary alongside and checks every read against it after every operation, because a store that is fast at being wrong is not a store.
Write it again, and again, and count
1 Keys written into a memtable that has a size and therefore fills
Pick a workload and drag to run part of it. Everything below is recounted from the store as it stands at that point.
| key | value in memory |
|---|---|
| empty, because it has just been flushed | |
every write is a key nobody has written before, which is the case the paper is about. After 88 operations the memtable holds 0 of the 8 entries it takes before it flushes.
2 Each full memtable flushed as a sorted file, and files merged level by level
Flushed, then merged, then merged again
| where | entries | note |
|---|---|---|
| level 0, file 0 | 8 | newest |
| level 1 | 0 | holds up to 32 |
| level 2 | 80 | holds up to 128 |
11 flushes and 4 compactions so far. Level 0 is allowed 4 files before it is merged down, and every level below holds 4 times what the one above it does.
3 The bytes actually written divided by the bytes handed in, counted as it runs
MeasuredBytes in, bytes written
Bytes actually written, divided by bytes handed in. That ratio is what the whole design trades away, and it is counted while the workload runs rather than worked out afterwards.
3.27x written per byte in
Handed 1408 bytes, wrote 4608. Every entry goes down once at the flush and again at every compaction that catches it.
| # | what happened | entries | bytes |
|---|---|---|---|
| 1 | flush to level 0 | 8 | 128 |
| 2 | flush to level 0 | 8 | 128 |
| 3 | flush to level 0 | 8 | 128 |
| 4 | flush to level 0 | 8 | 128 |
| 5 | flush to level 0 | 8 | 128 |
| 6 | compact into level 1 | 40 | 640 |
| 7 | compact into level 2 | 40 | 640 |
| 8 | flush to level 0 | 8 | 128 |
| 9 | flush to level 0 | 8 | 128 |
| 10 | flush to level 0 | 8 | 128 |
| 11 | flush to level 0 | 8 | 128 |
| 12 | flush to level 0 | 8 | 128 |
| 13 | compact into level 1 | 40 | 640 |
| 14 | compact into level 2 | 80 | 1280 |
| 15 | flush to level 0 | 8 | 128 |
4 What a read costs afterwards, and what a delete costs before the space comes back
What a read costs, and what a delete costs
| key | reads back | places searched | found in |
|---|---|---|---|
| 0 | 0 | 2 | level 2 |
| 1 | 3 | 2 | level 2 |
| 2 | 6 | 2 | level 2 |
| 3 | 9 | 2 | level 2 |
| 4 | 12 | 2 | level 2 |
| 5 | 15 | 2 | level 2 |
| 6 | 18 | 2 | level 2 |
| 7 | 21 | 2 | level 2 |
| 8 | 24 | 2 | level 2 |
| 9 | 27 | 2 | level 2 |
| 10 | 30 | 2 | level 2 |
| 11 | 33 | 2 | level 2 |
Worst read on this store looks in 2 places, and the average is 1.9. There are 88 entries on disk for 88 live keys, so 0 of them are older versions or delete markers still taking up room. 0 of those are markers.
A delete does not remove anything. It writes a marker saying the key is gone, and the marker costs exactly what a value costs, so deleting makes the store bigger and slower until a merge catches up with it. The marker cannot be thrown away early either: an older copy of that key may still be sitting in a deeper level, and forgetting the marker before the merge reaches the bottom would bring the deleted value back. Try the workload with deletes and watch the entry count climb above the number of keys that are actually there.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| every read agrees with a plain dictionary, after every single operation | yes | 4 workloads of 96 operations, every known key checked after each one |
| on fresh keys the store writes several times what it was handed | yes | 1536 bytes in, 4736 bytes written, an amplification of 3.08 over 12 flushes and 4 compactions |
| and that cost is the design, not a bug: most entries are written more than once | yes | each entry is written once at the flush and again at every compaction that catches it, and the ones flushed since the last compaction have been written exactly once so far; a dictionary that overwrote in place would write 1536 bytes and pay for it in seeks instead |
| deleting costs a write, so the same 96 operations hand in the same bytes | yes | 1536 bytes either way, and after the workload with deletes the store is holding 51 entries for 32 live keys: removing things made it bigger |
| most of what is on disk is out of date and still occupying it | yes | 24 entries on disk for 8 keys that are actually live, so 16 of them are older versions waiting for a compaction to notice |
| a read never looks in more places than there are files and levels | yes | checked for every key of every workload, against the number of level zero files plus the number of deeper levels |
| every live key is readable, by name, out of the memtable or a level | yes | each live key of each workload asked for individually and found with the value it was last written with, which is membership rather than a count that happens to match |
| a delete marker sits on disk until a merge reaches the bottom, then goes | yes | 14 markers still stored at the end of the workload, and 0 at operation 60, which is immediately after a compaction reached the deepest level. Every deleted key reads as absent in both states. |
| and a key written twice before a flush only reaches disk once | yes | the same 96 operations over eight keys amplify 1.17 against 3.08 over 96 fresh ones, because the memtable absorbs the overwrites before anything is written |
What is real here, and what is not
An entry is sixteen bytes because something had to be
Key and value are eight bytes each, and that constant is invented. It cancels out of the ratio the page reports, which is bytes written over bytes handed in, so the amplification figure does not depend on it. The absolute byte counts do, and they are there to make the ratio readable rather than to describe any real record.
Leveled compaction, and only one shape of it
Level zero collects whole flushed files and is allowed four of them, so the merge happens when a fifth arrives; every level below holds four times the one above and is merged when it overflows. Real implementations differ in almost every particular: partitioned levels, size-tiered compaction, per-file key ranges so a merge touches only the overlapping part. What is here is the shape that makes the counting legible, not RocksDB.
The dictionary is the witness, and it checks after every operation
A plain map is updated alongside the store, and every key that has ever been written is read back and compared after each of the 96 operations. Not at the end: a structure that settles to the right answer and is wrong in between is wrong. That check is what would catch a merge keeping the older of two versions, which is the bug that looks like nothing until a specific key is asked for at a specific moment.
Reads are counted in places searched, not in seeks
Each level zero file and each level below counts as one place a lookup may have to go. A real implementation would skip most of them with a Bloom filter per file and with per-file key ranges, which is what the Bloom Filter machine on this site is for. None of that is here, so the read cost shown is the worst case rather than the usual one.
The tombstone count was wrong once, and the sentence gave it away
The claim that markers stay until a merge reaches the bottom was first checked by counting markers in the deeper levels only, and it reported zero markers stored while fourteen were sitting in level zero. Every check was green and the printed sentence contradicted its own number. Counting level zero as well is the fix; noticing that a claim and its evidence disagreed is what caught it.
It can write less than it was handed, and that is real
The workload that rewrites eight keys over and over amplifies less than one, because the memtable absorbs repeated writes to a key before anything reaches disk. That is not a modelling error and it is not the usual case; it is what happens when the working set is smaller than the memtable. It is on the page because the honest version of a cost figure includes the case where the amplification falls below one. The cost is still positive; it is smaller than the data handed in.
Sound: no
What this page measures is a ratio of byte counts and a number of files searched. Neither is a duration, and a merge does not have a rhythm anybody could hear at true scale.
Sequential here means this model, and a real store writes more
What is counted is the bytes a flush and a compaction write. A production store also writes a write-ahead log before the memtable is safe, plus manifests, snapshots and filesystem metadata, and the device below it writes more again. The amplification figure on this page is modelled output bytes over logical bytes handed in, and it is a lower bound on what a real disk would see.
Sources
- O'Neil, Cheng, Gawlick and O'Neil, The Log-Structured Merge-Tree, hosted by the first author — the paper that names the structure and argues it from the cost of keeping an index on a fast-growing history table.
- RocksDB's own description of the compaction styles it implements, which is where the difference between the shape modelled here and a production one can be read.
- Logical Art, the studio this belongs to.