Internals · LSMsstablesorted string tablesparse indexblockimmutable

SSTables: The Immutable Sorted File

A memtable flush has to become a file that a reader can search without loading it, that compresses well, and that many readers can share without locks. The SSTable answers with sorted data blocks, a sparse index with one entry per block, a bloom filter and a footer that says where everything is — and it never changes after it is written.

▶ Interactive Interview question

Progress

Why this exists

The mechanism as the answer to a problem — read this before the name.

Problem
The memtable is full: 64 MB of sorted key/value pairs must go to disk in one sequential write, and afterwards a point read must find one key in that file without reading all 64 MB.
↓
Naive solution
Write the pairs one after another and, to find a key, read the file from the start until the key appears.
↓
Why it breaks
A lookup reads 32 MB on average; a miss reads all 64 MB. With ten such files, a single GET costs hundreds of megabytes of I/O.
↓
Better idea
The data is already sorted, so binary search would work — if we had an index of where keys are. A full index (one entry per key) is as big as the keys themselves; but one entry per fixed-size block is tiny and enough to narrow the search to one block.
↓
Internal mechanism
The file is a header, a sequence of 4–64 KB data blocks each holding sorted entries, a sparse index recording the first key and offset of every block, a bloom filter over all keys, and a fixed-size footer with the offsets of index and filter. A reader loads the footer once, keeps index and filter in memory, binary-searches the index to one block, reads and scans that block.
↓
Trade-offs
Immutability makes the file trivially safe to cache, share and replicate but means updates go elsewhere. Block-level compression cuts size 3–5× but forces whole-block decompression for one key. The sparse index costs one block read per lookup even when the key is absent — unless the bloom filter says no first.
↓
Real database
RocksDB's block-based table format (data blocks, index block, filter block, meta-index, footer with magic number), Cassandra's Data.db + Index.db + Filter.db + Summary.db files, HBase's HFile v3 with its trailer and bloom chunks.

Choose your depth

The same mechanism at four altitudes. Start where you are; come back deeper.

A sorted, write-once file

An SSTable is what a memtable becomes on disk: all its keys in order, with a small table of contents so a reader can jump close to any key, and a bloom filter so a reader can often skip the file entirely.

Because the file is never modified, every part of it can be cached forever, shared between threads without locks and copied to a replica while in use.

File layout

Every SSTable format is a variation on the same five parts, and their order is dictated by how the file is written: data first, because it streams straight out of the memtable in key order; index and filter after it, because they are complete only when the data is; the footer last, at a fixed size, because a reader must be able to find it without knowing anything else.

A 64 MB SSTable, block-based format

offset 0        ┌──────────────────────────────────────────────┐
                │ HEADER   magic, version, codec, comparator    │  ~16 B
                ├──────────────────────────────────────────────┤
                │ DATA BLOCK 0   apple → 7 · avocado → 14 · …   │  4 KB, compressed
                │ DATA BLOCK 1   cherry → 35 · date → 42 · …    │
                │ …                                            │
                │ DATA BLOCK 16383                              │
                ├──────────────────────────────────────────────┤
                │ SPARSE INDEX  block 0: "apple"  @ 16          │  one entry per block
                │               block 1: "cherry" @ 4112        │  ~16,000 × 20 B
                │               …                              │
                ├──────────────────────────────────────────────┤
                │ BLOOM FILTER  ~10 bits/key · k=7 hashes       │  ~1.2 MB for 1M keys
                ├──────────────────────────────────────────────┤
                │ META  min/max key, min/max seq, entries,      │
                │       tombstones, created-at, compaction level│
                ├──────────────────────────────────────────────┤
end − 48 B      │ FOOTER  index offset+len, filter offset+len,  │  fixed size
                │         meta offset, magic                   │
                └──────────────────────────────────────────────┘

Data blocks: the unit of I/O and compression

Entries are packed into blocks of a fixed target size — 4 KB in RocksDB by default, up to 64 KB where compression matters more than point-read latency. A block is read as a whole, decompressed as a whole and cached as a whole, so its size is a direct trade: small blocks make point reads cheap and the index large; big blocks compress better and make range scans cheap.

Inside a block, neighbouring keys share prefixes (user:00041, user:00042, …), so each key stores only the bytes that differ from the previous one plus a shared-prefix length. Every 16th entry is a restart point stored in full, so a reader can binary-search the restart points and then scan at most 16 entries. This is why sorted data compresses so much better than heap pages: the sort puts similar bytes next to each other.

The sparse index and the lookup

The index holds (first key of block, offset, length) for every block — sparse because it skips every key but one per block. A lookup for mango binary-searches the index for the last entry whose first key is ≤ mango, which pins down a single block; the key is either in that block or nowhere in the file. That is log₂(16,000) ≈ 14 comparisons in memory and one block read. Compare Binary Search: the same algorithm, applied to block boundaries instead of elements.

The consequence for absent keys is important: without more information, a miss still costs the block read, because only the block scan proves absence. That is the problem the Bloom Filters: Skipping Files That Cannot Contain the Key lesson solves — the filter is consulted before the index, and for a key not in the file it usually stops the lookup with no data I/O at all.

Point lookup in one SSTable

1get(file, key):
2  if not file.bloom.might_contain(key): return ABSENT        # ~1% of the time this lies
3  i = binary_search(file.index, key)                          # last block with first_key <= key
4  if i < 0: return ABSENT
5  block = block_cache.get(file.id, file.index[i].offset)      # read + decompress on miss
6  for entry in block.scan_from(restart_point(block, key)):
7      if entry.key == key: return entry                       # value or tombstone
8      if entry.key >  key: break
9  return ABSENT

Immutability: caching, concurrency, crash safety

A B+ tree page is shared mutable state and needs the whole apparatus of The Buffer Pool latches, dirty tracking and write-ahead logging to stay correct. An SSTable is written once and then only read, which dissolves those problems. Any number of threads can read it without locks. A cached block can never be stale. A crash during creation leaves an incomplete temporary file that is simply discarded; the file becomes visible atomically by rename after its final fsync, so it either exists whole or not at all.

Immutability also makes the operational side pleasant: a backup is a hard link to the current files, a replica bootstrap is a file copy, and a file is deleted only when the last reader that had it open finishes — a reference count, not a lock. The price is that an update to a row cannot touch its file; it produces a new version elsewhere, and Compaction: The Merge That Pays for Cheap Writes is the process that eventually reconciles the two.

Metadata that compaction and reads depend on

The meta block records the smallest and largest key, the smallest and largest sequence number, the entry and tombstone counts, and the level the file belongs to. Reads use the key range to skip files without touching bloom filter or index: a key outside [min, max] cannot be inside. Compaction uses the ranges to pick which level-1 files a level-0 file overlaps. Sequence ranges let a snapshot decide whether a file can contain anything it needs to see.

Cassandra keeps the same information across several sidecar files per table: Data.db, Index.db (the full per-partition index), Summary.db (the sparse sample of that index kept in memory), Filter.db (bloom), Statistics.db (min/max, tombstone histogram). RocksDB folds all of it into one .sst with named meta blocks. Same content, different packaging.

The parts and who reads them

Part	Size (64 MB file, 1M keys)	Read when	Kept in memory?
Footer	48 B	file opened	yes, once
Bloom filter	~1.2 MB (10 bits/key)	every point read	yes
Sparse index	~300 KB (16k entries)	every read that passes the filter	yes
One data block	4 KB	the block the key maps to	block cache (LRU)
Meta	~200 B	compaction planning, range pruning	yes

Key points

An SSTable is immutable and sorted: header, data blocks, sparse index (one entry per block), bloom filter, meta, footer.
Lookup = footer (once) → bloom filter → binary search the index → read one block → scan. Steady state: one block read per candidate file.
Blocks are the unit of I/O, compression and caching; prefix compression and restart points make sorted data 3–5× smaller.
Immutability removes locks, torn writes and cache invalidation, and makes backup and replication a file copy.
Min/max key and sequence metadata let reads and compaction skip files without opening them.

SSTable inspector

Inside one SSTable

An immutable, sorted file: header, data blocks, a sparse index with one entry per block, a bloom filter and a footer that points at the rest. Click a region, or find a key and watch which bytes a reader actually touches.

find key

Sparse index

One entry per data block, not per key: (first key of block, byte offset, block length). 16 keys in 4 blocks need 4 index entries. A real file with 64 MB of 4 KB blocks has ~16,000 entries — small enough to keep in memory for every open file.

first key apple      → block 0 @ offset   16   (74 B)
first key cherry     → block 1 @ offset   90   (66 B)
first key kiwi       → block 2 @ offset  156   (66 B)
first key melon      → block 3 @ offset  222   (69 B)

Immutability is what makes this file cheap to share: no locks (nobody writes), no torn pages (blocks are written once, sequentially, then fsynced), safe to cache blocks by (file id, offset) forever, safe to copy for backups or replicas while in use. The price is that an update cannot touch it — updates go to a new file, and compaction reconciles the versions later.

Educational simulation — a 16-key file with 4-entry blocks; real blocks are 4–64 KB and hold hundreds of entries.

When to use — and when not

Use it when

This file design fits any store that writes in sorted batches and reads by key: LSM engines, search-index segments, columnar analytics files share the shape.
It fits when compression and cheap replication matter more than in-place updates.

Avoid it when

This design does not fit data that is updated in place with strict locality requirements — that is what pages are for.
It does not fit tiny, constantly changing datasets where the write-once/compact-later cycle is pure overhead.

Failure modes

Blocks too large for the access pattern: every point read decompresses 64 KB to return 100 bytes.
Index and filters for thousands of open files exceed the memory budget and are evicted, turning every read into three I/Os.
Deleting a file while a reader still holds it — the reference-count bug that immutability was supposed to prevent.