Skip to content
The Log-Structured Merge-Tree (LSM-Tree) 4 min

Patrick O'Neil, Edward Cheng, Dieter Gawlick, Elizabeth O'Neil · Acta Informatica 1996

The Log-Structured Merge-Tree (LSM-Tree)

Why write-heavy databases like RocksDB and Cassandra keep data in memory and merge it to disk in batches. Play with a tiny LSM-tree and watch the merges.

Read the original paper

Databases · Black Belt · Pro · 4 min read

The Log-Structured Merge-Tree (LSM-Tree)

Every database index has the same chore: when a new row arrives, its entry has to land in the right place in a sorted structure. In a classic B-tree, that place is usually a leaf page somewhere on disk. If the index is too big for memory, each insert means reading and writing a random page. On a spinning disk, a random access is the slowest thing you can ask for.

In 1996, Patrick O'Neil and colleagues proposed a way out for write-heavy workloads such as logs and activity histories. Do not put each entry where it belongs right away. Collect entries, sort them in memory, and merge them into the disk structure in big sequential sweeps. The result is the log-structured merge-tree, the idea behind Bigtable, LevelDB, RocksDB and Cassandra.

An LSM-tree turns many small random writes into a few large sequential ones. It keeps recent entries in memory, merges them into bigger sorted structures on disk, and pays for it with slightly more work on reads.

The problem: random writes are expensive

The paper's running example is a transaction system that records every change in a History table. To find a customer's past activity quickly, you need an index on account and time. But every new History row needs a new index entry, and those entries land all over the index. Each one costs a random disk access.

The authors observe that the disk arm, not the disk's capacity, is the real cost. They estimate that the LSM-tree can do the frequent index inserts with much less disk arm use, at an order of magnitude lower cost for their example.

Imagine filing paper letters into a giant alphabetical cabinet. Walking to the right drawer for every letter is slow. A smarter clerk drops letters in an in-tray, and once an hour sorts the pile and files a whole batch in one trip down the aisle. Same cabinet, far fewer walks.

How an LSM-tree handles a write

An LSM-tree has components of increasing size. The smallest, C0, lives in memory. The next, C1, lives on disk and looks like a B-tree, but is packed full and laid out for sequential access.

  1. The write is first appended to a log file, so a crash cannot lose it.
  2. The entry is inserted into the C0 tree in memory. That costs no disk I/O.
  3. When C0 grows too big, a rolling merge takes a run of sorted entries out of C0 and merges them into C1, rewriting those C1 pages in large multi-page blocks.
The LSM-tree's two-step write path: record it in the log, put it in the in-memory tree, and later merge a whole run of entries into the disk tree in one large pass.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

1 more section, 1 more diagram and 2 interactive elements to play with

  • The price: reads and space

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.