Storage engines / Lsm trees
How to Build an LSM Tree
Follow one account from an in-memory map to logs, sorted tables, compaction, and crash recovery.
On this page07 sections
As engineers, we’ve all used different databases; we call APIs, store data, and it feels magical. I used to feel the same way and wanted to see how the storage engine actually works.
Oh boy! I didn’t expect to go down the rabbit hole, and it’s hella exciting.
Imagine we’re building a payment service and hand-rolling the storage engine ourselves.
Just Put It in Memory
Assume we have a user, Maya, and we want to save her account balance. It has an ID of 101 and a balance of 5,000. The easiest solution we can think of is to simply put everything in memory.
accounts = {
101 → ("Maya Sen", 5000)
}To read the account, we look up key 101. With a hash map, create, read, update, and delete take constant time on average.
Account 101 has a balance of ₹5,000.
You may be wondering, what if the server goes down? If the server crashes or we redeploy, Maya’s account is gone. So we need a way to persist the data even when the server crashes, some kind of a durable solution!
Append Every Change
As a durable storage solution, we have the next best thing: disk storage. In disk storage, we can have a log file, something like accounts.log maybe, and simply put the entries in it. We have found ourselves a solution!! For the sake of simplicity, we are assuming we are storing the data as it is, but actually the data are stored as encoded values.
Now you may be thinking, how do we update an existing value? We have to locate the value in accounts.log, then have to edit it.
But wait, if the updated record takes more bytes than the old one, it may no longer fit in the same space.
So the simplest solution is we just leave the old record as it is and append the updated account to the end, and this is what we call an append-only log. Creating an account and changing an existing one now use the same write path:
accounts.log
101, Maya Sen, 5000
205, Priya, 8000
310, Rahul, 2000
101, Maya Sen, 6000Okay, we’ve saved the records. But when Maya checks her balance, how do we find the latest one? We could read the whole log when the server starts and build our map again.
Every time we see another entry for Maya, we replace her previous balance. After that, lookups are fast again. That works, but we’re still keeping every account in memory. What if we leave the records on disk and read them when needed?
- 101 Maya Sen 5000
- 205 Priya 8000
- 310 Rahul 2000
Read the log to find it.
Three records. Maya’s starting balance is ₹5,000.
Now the duplicate entries become annoying. The first 101 we find says 5000, but there’s a newer one further down. We have to keep reading until the end to know we’ve found the latest balance. And if the account doesn’t exist, we’ve read the whole file for nothing.
Could we just remember where Maya’s latest record is?
Remember Where the Record Lives
The append-only log gives us a very crucial piece of information for free: the position of the new record, which is called the byte offset. What do we do with this byte offset? We store that position against the account ID in a map in memory, and a lookup can jump directly to it. This map is our index.
A byte offset counts bytes from the start of a file, beginning at 0. With UTF-8 encoding and a single newline after each record, the four record lines above occupy 20 bytes each. They start at offsets 0, 20, 40, and 60. Keeping the latest position for each account gives us:
beginning of file latest 101
│ │
0 ─────────────────────────────────── 60
latest_offset = {
101 → 60
205 → 20
310 → 40
}A request for account 101 now finds offset 60 in the index. We jump to that position in accounts.log and read the record, and return Maya’s 6,000 balance. Think of this as having an address for each record.
While we are looking up, a missing ID also gives us an answer immediately: there is no account to retrieve. Maya then deposits another 500. We append her updated account with a balance of 6,500 at offset 80, make the write durable, and change the index entry from 60 to 80 before confirming the update.
What does this give us? We never need to search for either of her older records.
- 0 101 Maya Sen 5000
- 20 205 Priya 8000
- 40 310 Rahul 2000
- 60 101 Maya Sen 6000
Account 101 points to byte 60, where Maya’s balance is ₹6,000.
The full account records stay in the file. RAM holds their IDs and offsets, which can save memory when the records are large.
On restart, the index disappears with the rest of the process’s memory. We can just rebuild it by scanning the log end to end and recording each complete, valid record’s starting offset.
Whenever an ID appears again, its newer offset replaces the previous one. For Maya, the entry moves through 0, 60, and 80, finishing at the record with her current balance. This moves the full scan from every lookup to startup. As the log grows, that startup scan becomes more expensive.
Split the Log into Segments
Everything is working, but the log keeps growing with every update. After millions of updates, we’re keeping old balances nobody needs, and scanning all of them during startup. How do we clean those up while new writes are still coming in?
We set a size limit on the active log. When it reaches the limit, we simply direct the new writes to a fresh new log file and leave the old one immutable. These files are called segments.
Now we have multiple files, aka segments, so the offset alone won’t help. Offset 0 in which file? Our index needs to remember the file name too.
Let’s say we close the first segment after those four records. Now Maya’s next update for 6,500 goes at the beginning of segment-02.log. The index entry becomes 101 → (segment-02.log, 0). So we know which file to open and where to read.
When that file reaches its limit, new writes are now added to segment-03.log. The two closed files aren’t changing anymore, so we can now clean them up without new writes being added halfway through.
Closed segments give compaction a stable input while a fresh segment accepts writes.
We combine the closed files into a new file, keeping the latest version of each account from those files. Combining files is merging; removing obsolete versions is compaction.
Okay, we’ve copied the records we need. Can we delete the old files now? To do that, we need to ensure the new file is safely saved on disk, the index must point to the new locations, and any reads still using the old files must finish.
For fetching one account by ID, we already have a useful design, similar to Bitcask. But what if we want all accounts from 100 through 300? Our hash index doesn’t keep IDs in order, so we have to check keys and fetch records scattered across files.
What if we kept the records sorted by account ID?
Sort the Records by Key
Good job so far! We really have come a long way. We have now solved the ever growing list problem with segments, and compacting them when needed. But you may have noticed a problem if you’re following along carefully. We are still storing the records based on their arrival order. What if we want to make a range query? Looks like we’ve got ourselves into another fine pickle.
But fear not, we’ve got it covered. Let us introduce a new rule that says:
Inside every completed segment, store key-value pairs in sorted key order.
And this sorted immutable segment is called a Sorted String Table, or SSTable. Point to remember: sorting a batch does not remove older versions in other files. An earlier batch and a later one might produce these tables:
Earlier writes Later writes
101 → Maya, 6500 101 → Maya, 7000
205 → Priya, 8000 150 → Ananya, 4000
310 → Rahul, 2000 205 → Priya, 9000Both inputs are sorted. Compare their next unread keys.
Now, when we are maintaining a sorted string table, we may not need to keep all the sorted indexes in memory.
Suppose we need key 205, and as the file is sorted, we know the key 205 definitely comes between 101 and 310. It jumps to byte 0 and scans only that small region:
101
150
205 ← found
310This is called a sparse index because it contains entries for selected keys rather than every key.
Find account 205. Start with the small block index.
Sort Live Writes in Memory
Now our closed segments are sorted, and our life is so much easier, but the new upcoming writes will hardly come in a sorted order, rather in a random order. Inserting every incoming record into the middle of an existing file would reintroduce the random disk updates we were trying to avoid.
So we clearly need somewhere to collect live writes and maintain them in sorted order before writing to the disk file. Let’s think through the properties we need this structure to have, shall we?
It needs to support four operations:
- It can handle random-order incoming writes
- Should be able to replace the current value with a new entry
- Be able to find a recent key efficiently
- Return every key in sorted order when it is time to write the file.
What data structure comes to mind which can support all of these? You guessed it right: A balanced search tree, such as a red-black tree or AVL tree, can provide these properties. And this in-memory sorted structure is what we call a memtable.
Just like we’ve seen before when the memtable grows a lot we can freeze it so it will become an immutable memtable. Now the final thing the engine needs to do, is to walk through the memtable and write it to a new file and this is what we call flushing the memtable
Point to remember: The engine does not insert records into an existing SSTable. It creates a complete new SSTable and then treats that file as immutable.
Priya’s 9500 update is in the active memtable; the installed table still holds 9000.
Protect Recent Writes with a WAL
We’re getting closer, but there’s one important problem left.
But wait, what if we have the active memtable that contains the newest changes, and updates have not yet been flushed into an SSTable and the machine crashes do we lose all our data then?
Writing every small update directly into its final sorted disk location would destroy the batching advantage of the memtable. But appending to the end of a file is simple. Therefore, we create a recovery log for the current memtable: the write-ahead log, or WAL.
But a file write can still sit in the operating system’s memory. Before confirming a durable update, we need a sync operation such as fsync to succeed.
Revisit the 9800 write before its flush. The previous flush holds 9500; earlier WAL history is omitted.
Now, even when a crash destroys the memtable, the WAL remains on disk. During restart, the engine reads it from beginning to end and reapplies every entry.
You might think: Why write the same data twice?
The writes serve different purposes:
- WAL: immediate and simple durability.
- Memtable: mutable, sorted working state.
- SSTable: durable, sorted long-term storage.
The WAL lets the engine safely acknowledge individual updates. The memtable then batches many updates into one sequential SSTable write.
Priya’s 10000 balance is in a frozen batch, protected by its retained WAL.
Congratulations! If you’ve come this far, We’ve made ourselves a Log-Structured Merge-tree storage engine. Production LSM engines have more tricks to handle all the different edge cases and quirks, like: tombstones, Bloom filters, caches, checksums, compression, multiple levels, and different compaction strategies which are beyond this first principle simpler derivation. Those are refinements built on top of the core design derived here, and maybe we can discuss them in a new post later