Demystifying LSM Trees and SSTables: The Engine Behind Modern Databases

If you are diving into the world of database internals, or reading Martin Kleppmann’s Designing Data-Intensive Applications, you’ll inevitably run into two massive concepts: SSTables and LSM Trees.

These are the backbone of modern, high-write-volume databases like Cassandra, RocksDB, and DynamoDB. But how do they actually work together?

Let’s break it down from scratch, starting with the absolute foundation: the log data structure.

Dont worry, LSM trees are not even minutely like trees but i didn’t name any of it

Part 1: The Append-Only Log

First, we need to understand the log data structure. It is nothing but a process by which we can append information to a storage file. Imagine this: the log data structure is based on a Key-Value store. The key is the specific item we are tracking, the value is the information (like a count), and the system usually tags a timestamp on it behind the scenes.

Let’s take an example. Say I have a button on my screen which says “Cat”, and adjacent to it I have a count number. When I click the button, it triggers a feature that tracks the number of times I’ve clicked it. Likewise, I have multiple buttons associated with different animals, like “Dog” and “Monkey”.

Every time I increment anything, I send a payload to my log data structure that looks like this:

{
  "cat": 12,
  "dog": 14,
  "monkey": 17,
  "timestamp": 1698745200
}

When this hits the database, my log on the disk looks like this: cat: 12, dog: 14, monkey: 17

If I send more payloads, since log data structures follow strictly append-only operations, the new payload just gets slapped at the end.

{
  "cat": 16,
  "dog": 19,
  "monkey": 20,
  "timestamp": 1698745245
}

Now my log DB becomes:

cat: 12, dog: 14, monkey: 17, cat: 16, dog: 19, monkey: 20

This is important to understand. In log databases, we only perform append operations. We never jump around the disk to overwrite old data. Because we just write sequentially, writes are incredibly fast! But reading that data to find the newest value for “cat” is a nightmare because we have to scan the whole file thereby causing a O(n) time complexity

Part 2: Data Segments and Compaction

Now get this, since we have an append-only log, it will eventually grow infinitely and fill up the entire memory. To fix this, the database writes to data segments.

What we mean by that is, when a log reaches a specific bucket size or time duration, the database closes it and makes it read-only. New writes go to a new segment. Because we are appending in real-time, each segment can have duplicate keys.

Segment 1 (Older)

cat: 12, dog: 13, monkey: 16, cat: 16, dog: 56, monkey: 30

Segment 2 (Newer)

cat: 14, dog: 78, monkey: 34, cat: 16, dog: 86, monkey: 90

To prevent running out of space, these segments periodically get compacted. The database looks at the segments, realizes that the previous value of any key doesn’t matter anymore, and only keeps the most recent value based on the timestamp.

After compaction, those two bulky segments become one highly efficient segment: cat: 16, dog: 86, monkey: 90

Get Sanshray’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

This concept of segments is the major foundation we need for SSTables.

Part 3: Enter the SSTable (Sorted String Table)

Now, let’s extend this to SSTables. SSTables are essentially these compacted segments, but with two very strict rules:

1. Keys are arranged in alphabetical (or numerical) order.
2. No key can be repeated in a single segment.

To give you an example of what this actually looks like on the disk, imagine we have two different SSTable segments. Notice how the animals are in alphabetical order, and there are no duplicates inside each individual segment:

SSTable Segment 1 (Older segment)

cat: 16
dog: 86
elephant: 10
monkey: 90
zebra: 5

SSTable Segment 2 (Newer segment)

cat: 22
dog: 91
penguin: 4
zebra: 8

When it’s time to compact these two SSTables together, we don’t need to load the whole massive file into RAM. Because they are already sorted, we can use a simple Merge Sort algorithm.

The Final Merged SSTable

cat: 22
dog: 91
elephant: 10
monkey: 90
penguin: 4
zebra: 8

We compare the first keys of the two segments (cat and cat). Since they are the exact same key, we just pick the value from the newer segment (cat: 22), drop the old one, and write it to a brand new file. Then, we move our pointer down. We compare dog and dog. Keep the newer one (dog: 91). Then we compare elephant and penguin. elephant comes first alphabetically, so we write elephant: 10 to the new file and move the pointer down on Segment 1.

By doing this, we can effortlessly compact massive SSTables using almost zero memory, keeping everything perfectly sorted!

Part 4: The Missing Link — The Memtable

But wait, how do we construct the SSTable by sorting the keys in the first place? Our original append-only data segments didn’t have any sorting!

We do it as an in-memory operation. In the RAM of the system, we use a balanced tree (like a Red-Black tree). This is called a Memtable.

When a write comes in, it doesn’t go straight to a sorted disk file. It goes directly into the Memtable in memory. Because it’s a balanced tree, as data is written, it automatically sorts itself alphabetically. Once the Memtable gets full, we perform a simple read operation on the tree and flush it to the disk. Boom — we now have a perfectly sorted SSTable segment!

(Note: Because RAM is volatile, we also simultaneously write incoming data to an unsorted Write-Ahead Log (WAL) on the disk. This can be a space, like a normal disk space. This dont need to be sorted, we are just taking care of an edge case here, if we do need to use the data from WAL, we can worry about the sorting of it then. That way, if the power goes out, we don’t lose the data currently sitting in the Memtable).

Part 5: Bringing it together, The LSM Tree

Now finally, how do we use all these prerequisites together?

Here is the secret: An LSM Tree (Log-Structured Merge-Tree) is not a single tree structure. It is the entire system we just built.

Here is the lifecycle of an LSM Tree in action:

• The Write: You click “cat”. The DB appends it to the WAL for safety, and inserts it into the sorted Memtable in RAM.
• The Flush: The Memtable gets full. The DB freezes it and writes it to the disk as a perfectly sorted SSTable.
• The Read: If a user asks for the “cat” count, the DB checks the Memtable first. If it’s not there, it checks the newest SSTable on disk. Because the SSTable is sorted alphabetically, it can find “cat” almost instantly without reading the whole file. If it’s not there, it checks the next newest SSTable, and so on.
• The Merge: In the background, the DB constantly runs our Merge Sort compaction algorithm, taking smaller, newer SSTables and merging them down into larger, older SSTables.

This cascading, merging process of pushing data from memory down through layers of SSTables on disk is exactly why we call it a Log-Structured Merge-Tree. And that is how modern databases handle massive, real-time data loads!

Thanks for making it to the end, i hope you understood most of it, but if you want further explanations or want to be explain some other topics to you guys, drop us a comment, would also appreciate if you could let me know how you guys liked it and ill catch up with you guys next week!

Writer: Sanshray Langeh
SDE 1