CSE Roadmap

Common tier · about 2 hours · 5 parts

Part 4 of 5 · 2 min read

SSTables and compaction

Each flush creates an immutable sorted file; compaction later merges these files together.

SSTables and compaction

Think of a filing cabinet where every finished drawer is sealed and labeled. It is never reopened or edited, only eventually combined with other sealed drawers into one new, sorted drawer.

In plain words: each file an LSM-tree flushes to disk is called a sorted-string table, or SSTable, and it is never modified after being written. A lookup may therefore need to check several SSTables, newest first, to find the most recent version of a key, which gets slower as more SSTables accumulate. Compaction solves this by periodically merging several SSTables into one new, larger sorted SSTable, discarding outdated or deleted entries along the way and keeping the total number of files a lookup must check manageable.

A worked example. After many flushes, the sensor-logging system's storage engine merges a batch of older SSTables into one larger SSTable during compaction, removing superseded readings and shrinking the number of files future lookups must check.

The key lines. No new SQL; compaction is a background process internal to the storage engine.

SSTable, compaction

An SSTable is an immutable, sorted file produced by one LSM-tree flush; compaction periodically merges several SSTables into fewer, larger ones, discarding outdated entries and keeping lookup costs manageable.

Example: sealed filing drawers that are never reopened individually, but are later merged together into one newly sorted drawer, mirror SSTables being compacted.

Remember this

An LSM-tree trades read simplicity for write speed: writes become cheap, sequential flushes, while reads may need to check several SSTables until compaction catches up. This is why write-heavy systems, such as time-series and logging databases, often prefer LSM-trees over B+-trees.

Quick notes

  • A B+-tree's in-place updates scatter many small random writes across disk under heavy write load.
  • An LSM-tree buffers writes in memory, then flushes them to disk as one large sequential sorted file.
  • Each flush produces an immutable SSTable, which is never modified after being written.
  • A lookup may need to check several SSTables, newest first, before compaction merges them.
  • Compaction periodically merges SSTables together, discarding outdated entries and keeping reads manageable.