Notesstorage🌱 seedling

SSTable

Also: Sorted String Table · SST · SST File

An immutable file of key-value pairs sorted by key, split into blocks, with an index of where each block starts. It is the on-disk unit of an [[LSM-Tree]]: written once in one sequential pass, never modified, eventually merged away by [[Compaction]].

Why it exists

Sorting the data makes range scans cheap and lets the index be sparse: one entry per block instead of one per key. Immutability makes writing, caching and concurrent reading simple.

How it works

  • Produced by flushing a Memtable or by compaction, always written start to finish.
  • Data blocks (RocksDB's default is 4 KB, usually compressed) hold sorted entries.
  • An index block maps each block's first or last key to its offset, so a lookup is: binary-search the index in memory, read one block.
  • A per-file Bloom Filter answers "could this key be in this file?" without touching disk.
  • Updates and deletes never edit an SSTable. A newer file shadows older values, and tombstones mark deletions.

Trade-offs

Gains Costs
sequential writes; trivially safe concurrent reads a key can exist in several files until compaction
sparse index fits in memory reads may check many files (read amplification)
whole blocks compress well dead values occupy space until merged

In practice

  • RocksDB SSTables carry data, index and filter blocks, and a properties block with key ranges and counts.
  • Cassandra stores each table as a set of SSTables plus its own partition index (and, in the classic BIG format, a summary file).

Pitfalls

  • "Immutable" means deletes add data: a mass delete writes a tombstone per key, and range scans must wade through them until compaction.

Recall

These cards are also in your review deck, scheduled with spaced repetition.