Sort the Segments, Change Everything

Take the segmented log from the last lesson and add one requirement: within a segment, records are sorted by key.

That is the whole change. Both limits fall out of it.

A segment with this property is a Sorted String Table, universally abbreviated to SSTable.

Why sorting fixes the memory limit

If keys are sorted, the index no longer needs every key.

sparse index    handbag → 102400      handiwork → 104800

segment    ... handbag ... handful ... handicap ... handiwork ...
               102400                                104800

Looking up handicap: it sorts between handbag and handiwork, so it must live in the 2,400 bytes between those two offsets — if it exists at all. Seek there, scan that small block, done.

Since you are scanning a block anyway, that block can be compressed — which saves disk space and, more importantly, I/O bandwidth. The sparse index points at compressed blocks, so you decompress a few kilobytes rather than the file.

Why sorting fixes range queries

Keys near each other in sort order are near each other on disk. WHERE ts BETWEEN x AND y becomes: seek to x, read forward until you pass y. One seek, then sequential reading — the pattern storage devices are best at.

Every paginated list, every time-range chart, every ORDER BY ... LIMIT becomes cheap. This is why sorted structures, not hash tables, are the default index in general-purpose databases.

Merging sorted segments is easy

Compaction gets simpler too. Merging sorted files is the merge step of merge sort: look at the first key of each segment, take the smallest, advance that segment, repeat. When two segments hold the same key, keep the value from the newer one.

It never loads a whole segment into memory — it holds one position per segment and streams. You can merge files far larger than RAM, which is exactly what a storage engine needs to do.

But how do the writes get sorted?

Writes arrive in whatever order users produce them. You cannot append to a sorted file and keep it sorted.

The answer is to sort in memory, where it is cheap:

1. A write goes into an in-memory balanced tree — a memtable — which keeps keys sorted as they arrive.
2. When the memtable passes a size threshold, write it out to disk as a new SSTable. It is already sorted, so this is one sequential write.
3. Start a fresh memtable and carry on. The write path never blocks on disk ordering.
4. In the background, merge SSTables together, discarding superseded values and tombstones.

A read checks the memtable first, then the newest SSTable, then the next, and so on until the key is found.

This whole arrangement — memtable, flush, background merge — is a Log-Structured Merge-Tree. It is the engine underneath RocksDB, LevelDB, Cassandra, ScyllaDB, HBase, and the write path of many time-series databases.

The read that finds nothing

There is one bad case. Ask for a key that does not exist, and the read checks the memtable, then every SSTable, all the way down, finding nothing each time before it can report absence.

False positives cost you an unnecessary read. False negatives cannot happen, which is the property that makes the whole thing safe. Turn Bloom filters off in the simulator in the next lesson and watch read amplification climb with every level — they are not an optimisation, they are what makes LSM point lookups viable.

What compaction is really trading

Compaction is where LSM engines spend their character.

It reclaims space, reduces the number of levels a read must probe, and turns random logical updates into sequential physical writes. It also consumes disk bandwidth and CPU, and it does so on a schedule of its own choosing, competing with live traffic.

What to take away

Sorting is the change that makes the log-structured approach general-purpose. It buys a sparse index, cheap range scans, streaming merges, and block compression — at the cost of sorting in memory first, a write-ahead log for durability, and compaction running forever in the background.