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 (next section) 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). Below: an illustrative dictionary index maps first words to sorted pages. The dragon entry leads to page 202, which contains draw.

Figure 1. An SSTable is one immutable on-disk file with three sections: a Bloom filter cached in RAM for fast not-exists checks, a sparse index block that binary-searches to the target data block, and sorted, compressed data blocks. Think of an Oxford English Dictionary: the sparse index records the first word on each page, while the pages contain sorted words and their definitions. To find draw, follow the dragon → Page 202 entry. These illustrative page numbers stand for data-block offsets in an SSTable. Multiple SSTables can coexist, each with its own index and sorted data.

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. (periodically) 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)

Where SSTables Run in Production

The same file format powers Google's Bigtable and Spanner, Amazon DynamoDB, Apache Cassandra, and RocksDB. RocksDB is the storage engine underneath Kafka Streams, CockroachDB and many other systems. If you've used a modern key-value store, you've almost certainly written an SSTable.