SSTables: The Sorted String Table

4 min read

An SSTable (Sorted String Table) is an immutable, ordered file format commonly used in Log-Structured Merge-tree (LSM-tree) key-value storage engines.

Core Concept of an SSTable

• Sorted Key-Value Pairs: At its most fundamental level, an SSTable is simply a file containing key-value pairs sorted sequentially by key.
• Immutability: Once an SSTable file is written to storage, it is never modified in-place. Because the file is immutable, multiple CPU threads or queries can read it concurrently without lock contention or corruption risks.

How SSTables Work in an LSM Engine

In a standard Log-Structured Merge-tree architecture:

1. The Write Path (WAL & Memory Buffer): Incoming writes are appended to a Write-Ahead Log (WAL) and stored in a memory buffer.
2. Flushing to SSTables: When the memory buffer fills up, the engine sorts the accumulated entries and flushes them to storage as a new SSTable file.
3. Background Compaction: Over time, many small SSTable files accumulate, containing overlapping key ranges or updated/deleted records. Background compactor nodes execute compaction — reading multiple SSTable files, merging and re-sorting their keys, discarding obsolete data, and writing out consolidated SSTable files.

A Worked Example: From Writes to Compaction

Let's trace a small dataset through the full lifecycle. Each write carries a sequence number (seq) so the engine knows which version of a key is newest.

Step 1: Writes Land in the Memtable

seq 1:  put("anna", 1)
seq 2:  put("bob", 2)
seq 3:  put("carol", 5)
seq 4:  put("anna", 7)    # overwrite
seq 5:  delete("bob")     # tombstone

        ... memtable fills up: FLUSH ...

seq 6:  put("bob", 9)     # re-insert
seq 7:  put("dana", 6)

        ... memtable fills up: FLUSH ...

Step 2: Each Flush Produces One SSTable

At flush time, the memtable is sorted by key and written as an immutable file. Obsolete versions within one memtable are already collapsed (e.g., anna=1 is simply overwritten in memory before it ever hits disk):

SSTable-001.sst          SSTable-002.sst
  anna  = 7   (seq 4)      bob  = 9   (seq 6)
  bob   = DEL  (seq 5)      dana = 6   (seq 7)
  carol = 5   (seq 3)

Note the problem: bob exists in both files — a live value in SSTable-002 and a tombstone in SSTable-001. A lookup must check the newest file first, which works, but the overlapping files keep piling up as writes continue.

Step 3: Compaction Merges the Files

Compaction performs a k-way merge: since each input file is already sorted by key, a single pass over both files walks all keys in order. For each key, the entry with the highest sequence number wins, and tombstones are dropped once no older versions of that key remain:

Merge SSTable-001 + SSTable-002, newest seq wins:

  anna  : only in 001            → keep anna  = 7
  bob   : DEL (seq 5) vs 9 (seq 6) → keep bob = 9, drop tombstone
  carol : only in 001            → keep carol = 5
  dana  : only in 002            → keep dana = 6

Step 4: One Consolidated SSTable

SSTable-merged.sst (Level 1)
  anna  = 7
  bob   = 9
  carol = 5
  dana  = 6

The result is a single, fully sorted, deduplicated file with no wasted space — and every key lookup now needs to probe only one SSTable instead of two. This same merge runs recursively in the background across levels of the LSM-tree, keeping the number of files (and read amplification) bounded forever.

The K-Way Merge Algorithm

The k-way merge solves a classic problem: given $k$ sorted lists, produce one sorted list in a single pass over the data — without loading everything into memory and re-sorting. It's the same primitive used for external sorting and merging sorted runs, and it's exactly what an LSM compactor runs over its input SSTables.

The Algorithm, Step by Step

1. Initialize $k$ cursors: one per sorted input, each pointing at the first entry. Each cursor only ever moves forward.
2. Find the smallest head: among all non-exhausted cursors, find the entry with the smallest key. When two heads share the same key (the same record updated in different SSTables), the entry with the highest sequence number wins.
3. Emit and advance: append the winner to the output — but if it's an older duplicate of a key already emitted, simply discard it — then advance only that cursor by one.
4. Repeat: until every cursor has walked off the end of its input.

Because every input is already sorted, the merge touches each of the $N$ total entries exactly once. Finding the smallest head costs $O(k)$ with a linear scan, or $O(\log k)$ with a min-heap of the $k$ current heads — giving $O(N \cdot k)$ or $O(N \log k)$ total, with only $O(k)$ memory for the cursors regardless of data size.

TypeScript Implementation

interface Entry {
  key: string;
  seq: number; // higher = newer
  value?: string; // undefined = tombstone
}
 
function kWayMerge(tables: Entry[][]): Entry[] {
  // One cursor per input SSTable, each starting at index 0
  const cursors = tables.map(() => 0);
  const merged: Entry[] = [];
  const total = tables.reduce((sum, t) => sum + t.length, 0);
 
  while (merged.length < total) {
    // Step 2: find the cursor with the smallest current key
    let best = -1;
    for (let i = 0; i < tables.length; i++) {
      const entry = tables[i][cursors[i]];
      if (!entry) continue; // this table is exhausted
      if (best === -1) {
        best = i;
        continue;
      }
      const current = tables[best][cursors[best]];
      const smallerKey = entry.key < current.key;
      const sameKeyNewer =
        entry.key === current.key && entry.seq > current.seq;
      if (smallerKey || sameKeyNewer) best = i;
    }
 
    // Step 3: emit the winner, advance only its cursor
    const winner = tables[best][cursors[best]++];
    const last = merged[merged.length - 1];
    if (!last || last.key !== winner.key) {
      merged.push(winner); // older duplicates are dropped
    }
  }
 
  return merged;
}
 
// The two SSTables from the worked example above:
const sstable001: Entry[] = [
  { key: "anna", seq: 4, value: "7" },
  { key: "bob", seq: 5 }, // tombstone
  { key: "carol", seq: 3, value: "5" },
];
 
const sstable002: Entry[] = [
  { key: "bob", seq: 6, value: "9" },
  { key: "dana", seq: 7, value: "6" },
];
 
console.log(kWayMerge([sstable001, sstable002]));
// [ {anna, 7}, {bob, 9}, {carol, 5}, {dana, 6} ]

Note what the merge did for free: bob's tombstone (seq 5) lost to the newer bob = 9 (seq 6) and was discarded — no garbage left in the output file.

Related reads

• The Log Structured Merge Tree — the architecture SSTables were invented for
• How WALs became a thing — the log that precedes every memtable write