SSTables and Bloom Filters¶

Role in the engine¶

When a memtable is full, it is written out as an SSTable (sorted string table): an immutable file of key-value pairs in internal-key order. Immutability is the key property — a table is written once, sequentially, fsynced, and never modified, so readers need no locks and crash recovery never has to repair a half-updated table. This page builds the file format, the writer, the reader with a block cache, and a bloom filter that lets point lookups skip tables that cannot contain the key.

File layout¶

+------------------+
| data block 0     |  ~4 KB of sorted entries, prefix-compressed
| trailer (5 B)    |  compression type (1 B) + CRC32-C (4 B)
+------------------+
| data block 1     |
| trailer          |
+------------------+
| ...              |
+------------------+
| filter block     |  bloom filter over all user keys in the table
| trailer          |
+------------------+
| index block      |  one entry per data block: last key → (offset, size)
| trailer          |
+------------------+
| footer (48 B)    |  filter handle, index handle, padding, magic number
+------------------+

A block handle is (offset, size) encoded as two uvarints. The footer has a fixed size so a reader can find it at fileSize - 48 without any other information:

const (
    footerSize   = 48
    tableMagic   = 0xdb4775248b80fb57 // detects "this is not an SSTable"
    blockTrailer = 5
)

Data blocks: prefix compression and restart points¶

Sorted keys share long prefixes (user:1042:name, user:1042:email, ...). Each entry stores only the bytes that differ from the previous key:

entry   := uvarint(shared) uvarint(unshared) uvarint(len(value)) key[shared:] value
trailer := restart offsets (uint32 each) | number of restarts (uint32)

Every 16th entry is a restart point: it stores its full key (shared = 0), and its offset is recorded in the trailer. Restart points make binary search possible inside a block — decode the full keys at restart points, binary-search them, then scan at most 15 entries forward.

const restartInterval = 16

func (b *blockBuilder) add(key, val []byte) {
    shared := 0
    if b.counter < restartInterval {
        for shared < min(len(key), len(b.lastKey)) && key[shared] == b.lastKey[shared] {
            shared++
        }
    } else {
        b.counter = 0
    }
    if b.counter == 0 {
        b.restarts = append(b.restarts, uint32(len(b.buf)))
    }
    b.buf = binary.AppendUvarint(b.buf, uint64(shared))
    b.buf = binary.AppendUvarint(b.buf, uint64(len(key)-shared))
    b.buf = binary.AppendUvarint(b.buf, uint64(len(val)))
    b.buf = append(b.buf, key[shared:]...)
    b.buf = append(b.buf, val...)
    b.lastKey = append(b.lastKey[:0], key...)
    b.counter++
}

Seeking inside a block:

func (it *blockIter) Seek(target []byte) {
    // Binary search for the last restart point whose key is <= target...
    i := sort.Search(it.nRestart, func(i int) bool {
        it.key = it.key[:0]
        return it.decodeAt(it.restart(i)) && it.cmp(it.key, target) > 0
    })
    start := max(i-1, 0)
    it.key = it.key[:0]
    if !it.decodeAt(it.restart(start)) {
        return
    }
    // ...then scan forward to the first key >= target.
    for it.Valid() && it.cmp(it.key, target) < 0 {
        it.Next()
    }
}

decodeAt validates every varint, length, and restart offset against the block's bounds and turns any inconsistency into ErrCorrupt — a block that passed its checksum can still be malformed if the writer had a bug, and decoding untrusted lengths without checks is how parsers crash. The length check must compare each length with the remaining bytes separately:

rest := uint64(len(p) - h)
if unshared > rest || vlen > rest-unshared { // NOT: rest < unshared+vlen (can overflow)
    return corrupt
}

The first version of this code wrote rest < unshared+vlen; the fuzzer found an input where unshared + vlen overflowed uint64, wrapped around to a small number, passed the check, and crashed the slice expression — see Testing and Benchmarking.

The interval trades space for speed: a smaller interval means faster seeks and less compression. 16 is LevelDB's default.

The writer¶

type TableWriter struct {
    w          io.Writer
    off        uint64
    data       blockBuilder
    index      blockBuilder
    lastKey    []byte
    pending    bool        // a finished data block awaits its index entry
    pendingH   blockHandle
    hashes     []uint32    // user-key hashes for the bloom filter
    BlockSize  int         // default 4 KB
    BitsPerKey int         // default 10
}

func (t *TableWriter) Add(ikey, val []byte) {
    if t.pending { // index entry for the previous block: its last key
        t.index.add(t.lastKey, t.pendingH.append(nil))
        t.pending = false
    }
    t.hashes = append(t.hashes, hash32(ukey(ikey)))
    t.data.add(ikey, val)
    t.lastKey = append(t.lastKey[:0], ikey...)
    if t.data.estimatedSize() >= t.BlockSize {
        t.flushData() // write block + trailer, remember its handle in pendingH
    }
}

func (t *TableWriter) Finish() (size uint64, err error) {
    t.flushData()
    if t.pending {
        t.index.add(t.lastKey, t.pendingH.append(nil))
    }
    filterH := t.writeBlock(newBloom(t.hashes, t.BitsPerKey))
    indexH := t.writeBlock(t.index.finish())
    footer := filterH.append(nil)
    footer = indexH.append(footer)
    footer = append(footer, make([]byte, footerSize-8-len(footer))...)
    footer = binary.LittleEndian.AppendUint64(footer, tableMagic)
    // ... write footer; the caller then fsyncs the file
}

The index entry for a block is added lazily, when the next key arrives. LevelDB uses that delay to store a shortened separator instead of the full last key — any key ≥ the block's last key and < the next block's first key works ("the quick" / "the zebra" → "the r") — which makes the index smaller. This implementation stores the full last key for simplicity.

The writer only appends, so the file can be written through any io.Writer — a bufio.Writer over the file in production, a bytes.Buffer in tests.

The reader and the block cache¶

Opening a table reads the footer, then loads the index and filter blocks into memory and keeps them there. Data blocks are read on demand through the block cache:

func (t *Table) readBlock(h blockHandle) ([]byte, error) {
    if b, ok := t.cache.Get(t.id, h.off); ok {
        return b, nil
    }
    // A handle read from disk is untrusted: it must lie inside the file
    // (checked without overflow) before we allocate h.size bytes.
    if h.size > t.size || h.off > t.size-h.size || t.size-h.size-h.off < blockTrailer {
        return nil, ErrCorrupt
    }
    buf := make([]byte, h.size+blockTrailer)
    if _, err := t.r.ReadAt(buf, int64(h.off)); err != nil { // pread: safe for concurrent readers
        return nil, err
    }
    b, tr := buf[:h.size], buf[h.size:]
    want := binary.LittleEndian.Uint32(tr[1:])
    if crc32.Update(crc32.Checksum(b, castagnoli), castagnoli, tr[:1]) != want {
        return nil, ErrCorrupt
    }
    t.cache.Put(t.id, h.off, b)
    return b, nil
}

ReadAt maps to pread(2), which takes an explicit offset and does not move a shared file position, so any number of goroutines can read the same *os.File concurrently. The cache is an LRU keyed by (file id, block offset), protected by one mutex (Cache Replacement Policies). Because blocks are immutable, a reader may keep using a block's slice after it is evicted — the GC keeps it alive until the reader is done, which removes the pin/unpin protocol that a cache without a garbage collector needs (compare the explicit pinning in the Buffer Pool, where frames are reused in place and must not be evicted while in use).

The Profiling with pprof investigation on this engine found the block cache hit rate to be the dominant factor in lookup cost: 8% hits → 2.96 µs per Get; 99.5% hits → 1.09 µs.

A point lookup is a two-level iterator seek: binary-search the index block for the first block whose last key ≥ target, read that block, seek inside it.

Bloom filters: skipping tables¶

A Get for a key that is not in a table would still read one data block from it. With 4 L0 tables and one L1 table, a miss costs up to 5 block reads. A bloom filter answers "is this key definitely not in the table?" from memory:

• An array of m bits and k hash functions. Adding a key sets k bits; checking a key tests them. Any zero bit → definitely absent. All ones → probably present.
• False positive rate ≈ (1 − e^(−kn/m))^k, minimized at k = (m/n)·ln 2. At 10 bits per key the optimum is k ≈ 6.9; the code below rounds down to k = 6, for a rate of about 0.84%.

type bloom []byte // bit array; last byte stores k

func newBloom(hashes []uint32, bitsPerKey int) bloom {
    k := max(1, min(30, int(float64(bitsPerKey)*0.69))) // ln 2 ≈ 0.69
    nBits := max(64, len(hashes)*bitsPerKey)
    nBytes := (nBits + 7) / 8
    nBits = nBytes * 8
    f := make(bloom, nBytes+1)
    f[nBytes] = byte(k)
    for _, h := range hashes {
        delta := h>>17 | h<<15 // double hashing: k probes from one 32-bit hash
        for j := 0; j < k; j++ {
            pos := h % uint32(nBits)
            f[pos/8] |= 1 << (pos % 8)
            h += delta
        }
    }
    return f
}

Double hashing (h, h+δ, h+2δ, ...) derives all k probe positions from one hash computation, with nearly the false-positive rate of k independent hashes (Kirsch and Mitzenmacher). The filter is built over user keys, not internal keys, because lookups ask "does any version of this key exist here?".

Measured: a table of 10,000 keys, probed with 10,000 keys that are not in it, at 10 bits per key: 0.96% false positives — close to the 0.84% theory (FNV-1a is not a perfect hash). The filter costs 1.25 bytes per key and turns ~99% of negative lookups into a few memory probes.

Bits per key	Memory per 1 M keys	Theoretical false positive rate
5	0.6 MB	9.2%
10	1.2 MB	0.84%
16	2.0 MB	0.046%

Bloom filters help point lookups only; a range scan must look at every table whose key range overlaps. RocksDB adds prefix bloom filters for prefix scans and Ribbon filters (same accuracy, ~30% less memory) for large deployments.

Building and verifying a table, end to end¶

The round-trip test writes 10,000 keys into a table in memory, reopens it, looks up keys at the start, middle, and end, iterates over all entries, and measures the filter's false-positive rate:

var buf bytes.Buffer
tw := NewTableWriter(&buf)
for i := 0; i < 10000; i++ {
    tw.Add(makeIKey(nil, fmt.Appendf(nil, "key%06d", i), uint64(i+1), TypeValue),
        fmt.Appendf(nil, "v%d", i))
}
size, _ := tw.Finish()
tab, _ := OpenTable(bytes.NewReader(buf.Bytes()), size, 1, NewBlockCache(1<<20))

Because OpenTable takes an io.ReaderAt and the writer an io.Writer, the same code works on files, in-memory buffers, and fault-injecting wrappers — the payoff of small interfaces.

Common pitfall¶

Building the bloom filter over internal keys. If TableWriter hashed the full internal key (user key + sequence + type), every lookup would need to hash exactly the stored internal key — but a Get only knows the user key and a snapshot sequence, not the sequence the key was written with. Every probe would say "absent", every Get for an existing key would skip the table, and reads would return ErrNotFound for data that is there. The symptom appears only after a flush (the memtable path does not use filters), which makes it look like a flush or compaction bug. The filter key must be exactly what the reader can compute: the user key (or, for prefix filters, its prefix).

Review questions¶

1. Why are SSTables immutable, and what does immutability buy for concurrency and recovery?
2. What are restart points for, and what does the restart interval trade off?
3. Why can this block cache let readers keep using a block after eviction, while the buffer pool must pin its frames?
4. At 10 bits per key, how many probes does this filter use, what false-positive rate does theory predict, and what did the test measure?
5. Why must the bloom filter be built over user keys rather than internal keys?