SSTables: Sorted String Tables

Concept. An SSTable is an immutable file of key-value pairs sorted by key. The system writes the file once and never modifies it. Write-heavy stores such as LSM trees use SSTables as their on-disk unit.

Intuition. Spotify can record 1 million listen events per second. A sorted on-disk B+Tree write triggers a rebalance, so per-event writes limit throughput. The system buffers writes in RAM, sorts the buffered keys, and flushes one 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: a bloom filter in RAM that answers "is key K here?" in O(1) and can skip a disk read on a miss, a sparse index block that binary-searches to the target data block, and sorted, compressed data blocks. Multiple SSTables can contain the same key; a read returns 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