SSTables: Sorted String Tables

Concept. An SSTable is an immutable file of key-value pairs sorted by key, written once and never modified. It's the building block for write-heavy stores like LSM trees.

Intuition. When Spotify needs to record 1 million listen events per second, writing each one to a sorted on-disk B+Tree is too slow, because every write triggers a rebalance. Instead, the system buffers writes in RAM until it has a chunk, then flushes a sorted immutable file to disk. That file is an SSTable.

Anatomy of an SSTable

SSTable structure. One file with three sections: the bloom filter (red, held in RAM) plus the index block and data blocks (green, on disk). Bottom: three SSTable files coexist on disk, with the user_100 key appearing as v1, v2, v3 across them in pastel purple. The newest wins on read.

Figure 1. An SSTable is one immutable on-disk file with three sections read in order: a bloom filter held in RAM (red) that answers "is key K here?" in O(1) and skips a wasted disk read on a miss, a sparse index block that binary-searches to the right data block, and the sorted, compressed data blocks themselves. Many SSTables coexist on disk, so the same key can live in several files; a read takes the newest version, here user₁₀₀'s v3 in sstable_3.db over v1 and v2.

Each SSTable is a single file with three sections laid out in order. (Recall Bloom filters from Module 2 for how they work and their false-positive behavior.)

Multiple SSTables coexist on disk. A background compaction process eventually merges older files together to throw away obsolete versions.

How Databases Use SSTables

Three operations show up in any system that uses SSTables:

Flush. Convert an in-memory buffer of pending writes into a sorted, immutable file on disk. One sequential write per flush.
Read. Consult the bloom filter, binary-search the sparse index, and read the target data block. Three steps, mostly from cache.
Compact. K-way merge a set of older SSTables into one larger file, keeping the newest version of each key and dropping deleted entries.

Some databases use SSTables as a standalone storage format (notably older versions of HBase and many analytics stores). Others layer them into a larger structure, which is where LSM trees come in on the next page.

Algorithm

Algorithm · SSTable: Flush, Read, Compact

Flush(memtable):                    // RAM buffer is full
    sorted = sort(memtable)         // sort by key
    write(bloom_filter)             // for quick "not exists"
    write(sparse_index)             // every Nth key → offset
    write(sorted_data)              // the actual key-values
    write(footer)                   // min_key, max_key, size

Read(sstable, key):
    if not bloom_filter.contains(key):
        return None                 // quick reject, no disk read
    offset = binary_search(index, key)
    block  = read_block(offset)
    return linear_search(block, key)

Compact(sstables):
    merged = k_way_merge(sstables)  // keep newest version per key
    return write_new_sstable(merged)

SSTables: Sorted String Tables

Anatomy of an SSTable

How Databases Use SSTables

Algorithm

Where SSTables Run in Production

Next