SSTable Anatomy: Sorted Strings on Disk

An SSTable (Sorted Strings Table) is an immutable file containing key/value pairs in sorted key order. The format was introduced by Google's Bigtable paper (2006) and adopted by LevelDB, RocksDB, Cassandra, HBase, ScyllaDB, and BadgerDB.

Why Immutable?

Once written, an SSTable is never modified. This single rule unlocks everything that makes an LSM tree work:

• No locking — readers can stream through any SSTable without coordination.
• Page cache friendly — the OS can cache aggressively; nothing invalidates.
• Crash safe — you cannot half-corrupt a file you never write to.
• Trivial backups — copy the file. Done.
• Snapshots are free — a snapshot is just a list of which SSTables are live.

File Layout

A minimal SSTable looks like this:

+---------------------------+
| Block 0 (sorted KV pairs) |
+---------------------------+
| Block 1                   |
+---------------------------+
|        ...                |
+---------------------------+
| Block N                   |
+---------------------------+
| Index (first key + offset |
|        for every block)   |
+---------------------------+
| Bloom filter (Ch 4)       |
+---------------------------+
| Footer                    |
| - index_offset            |
| - bloom_offset            |
| - num_entries             |
| - smallest_key            |
| - largest_key             |
| - magic / version         |
+---------------------------+

Real engines add: per-block compression, per-block checksums, statistics, properties blocks, restart-point arrays for prefix compression. We'll add those features in later lessons.

Block-Oriented for a Reason

Why split into blocks instead of one giant sorted array? Two reasons:

1. Compression. Compressing a 4 KiB block with snappy/zstd yields 60-80% size reduction. The block becomes the unit of I/O — read one block, decompress, search.
2. Index size. An index entry per key would explode memory. An index entry per block (typically 4-64 KiB) is 1000x smaller and still gives O(log N) lookup.

LevelDB defaults to 4 KiB blocks. RocksDB defaults to 4 KiB but commonly tunes up to 32-128 KiB for cold data.

Reading a Key

1. Load the footer (last few bytes of the file).
2. Read the index. Binary search by first-key for the block that could contain the target.
3. Read that block from disk.
4. Linear (or binary) search within the block.

For ~1 GiB SSTables with 4 KiB blocks, the index has ~256K entries. Memory: a few MiB. One disk seek per point lookup.

Why "Strings"?

In Bigtable everything is bytes. "Sorted Strings" is the historical name, not a type constraint. Keys are byte arrays compared lexicographically. Values are opaque byte arrays. The same format encodes numeric keys (big-endian) or composite keys (row_key + column + timestamp).