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.
Connections
- Builds on this
- CompactionLSM-Tree
- Related
- Bloom FilterMemtable
Recall
These cards are also in your review deck, scheduled with spaced repetition.