Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Lab 04 — SSTable (Sorted String Table)

What this lab adds

Labs 01–03 built a durable, crash-safe in-memory engine. The MemTable lives in RAM; when the process exits, all data is gone (only the WAL remains, and the WAL is replayed on reopen). This has a hard limit: the machine’s RAM.

Lab 04 introduces the SSTable: an on-disk file format that stores a sorted, immutable snapshot of a MemTable. Once an SSTable is written:

  • All the data it contains is permanent — no WAL replay needed.
  • The in-memory MemTable can be discarded.
  • Reads can go directly to the SSTable file.

Lab 04 provides two types:

  • Builder — writes an SSTable from a sorted stream of key-value records.
  • Reader — reads an existing SSTable, supporting point lookup (Get) and sequential scan (NewIterator).

Concept: Immutable files and log-structured storage

Traditional storage engines (e.g. B-trees) update data in place: writing a new value for a key overwrites the old value’s disk location. This causes two structural problems:

  1. Random writes — each update seeks to a specific offset in the file. An HDD performs ~100 random writes/s; sequential writes run at GB/s.
  2. Complex crash recovery — a crash during an in-place overwrite leaves the page half-written. B-trees solve this with page-level write-ahead logs or shadow-paging, adding implementation complexity.

A log-structured approach eliminates both:

B-tree (in-place):                  LevelDB (log-structured):
  Page 7:  "apple"→"v1"              MemTable → WAL (append)
  update:  "apple"→"v2"  ← random   MemTable full → SSTable (sequential write)
           seek + overwrite          Old MemTable discarded
           crash risk!               SSTable is immutable: no crash risk

Every write is sequential, and files are never mutated after creation. Immutability also means files can be safely read by multiple goroutines without locking — the OS page cache handles caching automatically.

Concept: Varint encoding

Fixed-width integers waste space when values are small. A 4-byte uint32 uses 4 bytes even for the value 1. SSTable records use varint encoding:

Each byte: 7 bits of data + 1 MSB continuation flag
  MSB = 1: more bytes follow
  MSB = 0: last byte

Encoding examples:
  Value 1:        binary 0000001  → 0x01          (1 byte)
  Value 127:      binary 1111111  → 0x7F          (1 byte)
  Value 128:      binary 10000000 → 0x80 0x01     (2 bytes)
                  ┌────────────────────────────────────────┐
                  │ byte 0: 0x80 = 1_0000000               │
                  │   MSB=1 (more bytes), 7 data bits = 0  │
                  │ byte 1: 0x01 = 0_0000001               │
                  │   MSB=0 (last), 7 data bits = 1        │
                  │ value = (1 << 7) | 0 = 128             │
                  └────────────────────────────────────────┘
  Value 1000:     1000 = 0b1111101000
                  low 7 bits: 1101000 = 104  → 0xE8 (with MSB=1: 0b11101000)
                  high 3 bits: 111     = 7   → 0x07 (with MSB=0: 0b00000111)
                  → 0xE8 0x07          (2 bytes)
  Value 100,000:  → 0xA0 0x8D 0x06    (3 bytes)

For key and value lengths (almost always < 128 bytes in practice), varint saves 3 bytes per record versus a fixed uint32. A 4 MiB MemTable with 40,000 keys averaging 20-byte keys and 80-byte values saves 40,000 × 3 × 2 = 240 KB — about 6% of the file size.

appendVarint / readVarint annotated

// appendVarint appends the varint encoding of v to buf and returns the result.
func appendVarint(buf []byte, v uint64) []byte {
    for v >= 0x80 {                // while more than 7 bits remain
        buf = append(buf, byte(v)|0x80)  // emit low 7 bits with MSB=1
        v >>= 7                    // shift out the 7 bits we just emitted
    }
    return append(buf, byte(v))    // emit final byte with MSB=0
}

// readVarint reads one varint from r.
func readVarint(r io.Reader) (uint64, error) {
    var v uint64
    var shift uint
    for {
        var b [1]byte
        if _, err := io.ReadFull(r, b[:]); err != nil {
            return 0, err
        }
        v |= uint64(b[0]&0x7f) << shift   // extract 7 data bits, place at shift
        if b[0]&0x80 == 0 {               // MSB=0: last byte
            return v, nil
        }
        shift += 7
        if shift >= 64 {                   // overflow guard (varint > 9 bytes)
            return 0, errors.New("sstable: varint overflow")
        }
    }
}

Byte-level trace: decode 0xE8 0x07 (= 1000)

byte 0: 0xE8 = 0b11101000
  MSB=1 (more bytes)
  7 data bits: 0b1101000 = 104
  v = 104 << 0 = 104
  shift → 7

byte 1: 0x07 = 0b00000111
  MSB=0 (last byte)
  7 data bits: 0b0000111 = 7
  v |= 7 << 7 = 7 × 128 = 896
  v = 104 + 896 = 1000 ✓

SSTable file layout

┌──────────────────────────────────────────────────────────────────┐
│  DATA SECTION                                                     │
│  ┌────────────────────────────────────────────────────────────┐  │
│  │ record 0: varint(kLen) │ ikey │ varint(vLen) │ value       │  │
│  │ record 1: varint(kLen) │ ikey │ varint(vLen) │ value       │  │
│  │ …                                                           │  │
│  └────────────────────────────────────────────────────────────┘  │
├──────────────────────────────────────────────────────────────────┤
│  INDEX SECTION  (one entry per data record)                       │
│  ┌────────────────────────────────────────────────────────────┐  │
│  │ entry 0: varint(kLen) │ ikey │ 8B LE file-offset-of-rec0  │  │
│  │ entry 1: varint(kLen) │ ikey │ 8B LE file-offset-of-rec1  │  │
│  │ …                                                           │  │
│  └────────────────────────────────────────────────────────────┘  │
├──────────────────────────────────────────────────────────────────┤
│  FOOTER  (exactly 16 bytes)                                       │
│  ┌────────────────────────┬──────────────────────────────────┐   │
│  │ indexOffset  (8B LE)   │  magic = 0x000000001edb4b4f (8B) │   │
│  └────────────────────────┴──────────────────────────────────┘   │
└──────────────────────────────────────────────────────────────────┘

Keys are internal keys from lab02: userKey || uint64(seqNum<<8 | keyType).

Why store an index at all? Without an index, finding a key requires scanning every record from offset 0. For a 2 MiB SSTable with 100-byte average record size, that is up to 20,000 reads. The in-memory index (one entry per record, ~24 bytes each for a 20-byte key) costs ~480 KB of RAM but reduces Get to a binary search O(log N) + short linear scan.

Why is the index at the end, not the beginning? The Builder writes records in one sequential pass. If the index were first, the builder would need to either pre-allocate space for it (unknown size before writing) or do two passes. Appending the index after all data records allows a single forward pass. The 16-byte footer at the very end tells the reader where the index starts.

The magic number 0x1edb4b4f is checked before parsing. A truncated or corrupt file returns a descriptive error rather than silently returning wrong data.

Builder: writing an SSTable

type indexEntry struct {
    lastKey []byte
    offset  uint64   // byte offset of this record in the data section
}

type Builder struct {
    f          *os.File
    index      []indexEntry
    dataOffset int64    // current write position in the file
}

Add(ikey, value []byte) annotated

func (b *Builder) Add(ikey, value []byte) error {
    offset := b.dataOffset      // save current position = offset of this record

    var rec []byte
    rec = appendVarint(rec, uint64(len(ikey)))   // 1-3 bytes for key length
    rec = append(rec, ikey...)                   // key bytes
    rec = appendVarint(rec, uint64(len(value)))  // 1-3 bytes for value length
    rec = append(rec, value...)                  // value bytes

    n, err := b.f.Write(rec)   // single write syscall per record
    if err != nil {
        return err
    }
    b.dataOffset += int64(n)

    // Register this record in the index:
    keyCopy := make([]byte, len(ikey))
    copy(keyCopy, ikey)        // own the key bytes — ikey may be reused by caller
    b.index = append(b.index, indexEntry{lastKey: keyCopy, offset: uint64(offset)})
    return nil
}

Keys must be added in CompareInternal ascending order — the caller (MemTable flush) iterates the skip list which already yields keys in that order.

Finish() annotated

func (b *Builder) Finish() error {
    indexOffset := b.dataOffset    // index section begins immediately after data

    // Write each index entry:
    for _, e := range b.index {
        var rec []byte
        rec = appendVarint(rec, uint64(len(e.lastKey)))
        rec = append(rec, e.lastKey...)
        var offBuf [8]byte
        binary.LittleEndian.PutUint64(offBuf[:], e.offset)
        rec = append(rec, offBuf[:]...)    // 8-byte LE file offset
        if _, err := b.f.Write(rec); err != nil {
            return err
        }
    }

    // Write 16-byte footer:
    var footer [16]byte
    binary.LittleEndian.PutUint64(footer[0:8], uint64(indexOffset))  // index start
    binary.LittleEndian.PutUint64(footer[8:16], magic)               // 0x1edb4b4f
    if _, err := b.f.Write(footer[:]); err != nil {
        return err
    }
    return b.f.Sync()   // fdatasync: ensure file is durable before returning
}

b.f.Sync() calls fdatasync — the same guarantee as the WAL. A crash after Finish returns leaves a fully intact SSTable.

Byte-level example: building a 2-record SSTable

Records (in CompareInternal order):
  ikey0 = EncodeInternalKey("apple", 3, TypeValue) = [61 70 70 6c 65  01 03 00 00 00 00 00 00]  (13 bytes)
  val0  = "green"   = [67 72 65 65 6e]  (5 bytes)

  ikey1 = EncodeInternalKey("name", 1, TypeValue)  = [6e 61 6d 65  01 01 00 00 00 00 00 00]  (12 bytes)
  val1  = "Alice"  = [41 6c 69 63 65]  (5 bytes)

Data section (after Builder.Add × 2):
  offset  0:  0d                       ← varint(13): kLen=13
  offset  1:  61 70 70 6c 65  01 03 00 00 00 00 00 00  ← ikey0 "apple" seq=3
  offset 14:  05                       ← varint(5): vLen=5
  offset 15:  67 72 65 65 6e           ← val0 "green"
  offset 20:  0c                       ← varint(12): kLen=12
  offset 21:  6e 61 6d 65  01 01 00 00 00 00 00 00  ← ikey1 "name" seq=1
  offset 33:  05                       ← varint(5): vLen=5
  offset 34:  41 6c 69 63 65           ← val1 "Alice"
  dataOffset = 39

Index section (starting at offset 39):
  entry 0 (points to data offset 0):
    0d                                 ← varint(13)
    61 70 70 6c 65  01 03 00 00 00 00 00 00  ← key copy
    00 00 00 00 00 00 00 00            ← offset=0 (LE uint64)

  entry 1 (points to data offset 20):
    0c                                 ← varint(12)
    6e 61 6d 65  01 01 00 00 00 00 00 00  ← key copy
    14 00 00 00 00 00 00 00            ← offset=20 (0x14)

Footer (last 16 bytes):
  27 00 00 00 00 00 00 00  ← indexOffset = 39 (0x27)
  4f 4b db 1e 00 00 00 00  ← magic = 0x1edb4b4f

Reader: opening and searching an SSTable

Open(path) annotated

func Open(path string) (*Reader, error) {
    f, err := os.Open(path)
    // ...

    // 1. Read 16-byte footer from the end of the file:
    var footer [16]byte
    f.ReadAt(footer[:], info.Size()-16)
    idxOffset := int64(binary.LittleEndian.Uint64(footer[0:8]))
    if binary.LittleEndian.Uint64(footer[8:16]) != magic {
        return nil, fmt.Errorf("sstable %s: bad magic", path)  // corrupt file
    }

    // 2. Seek to index section and read all entries into memory:
    f.Seek(idxOffset, io.SeekStart)
    r := &Reader{f: f, indexOffset: idxOffset}
    for pos < info.Size()-16 {     // stop at footer
        klen, _ := readVarint(f)
        key := make([]byte, klen)
        io.ReadFull(f, key)
        var offBuf [8]byte
        io.ReadFull(f, offBuf[:])
        offset := binary.LittleEndian.Uint64(offBuf[:])
        r.index = append(r.index, indexEntry{lastKey: key, offset: offset})
    }
    return r, nil
}

Why load the entire index into memory? The index is small relative to the data section. For a 2 MiB SSTable with 100-byte average records, there are ~20,000 records. Each index entry is varint(kLen) + key + 8B ≈ 30 bytes for a 20-byte key. Total index size: 20,000 × 30 = 600 KB. At most a few percent of RAM even with many SSTables open simultaneously. The payoff: all subsequent Get calls are binary searches in RAM with no index-section I/O.

Get(ikey) annotated

func (r *Reader) Get(ikey []byte) ([]byte, bool) {
    // Phase 1: binary search the in-memory index.
    // Goal: find the first index entry whose key >= ikey.
    lo, hi := 0, len(r.index)-1
    for lo < hi {
        mid := (lo + hi) / 2
        if lab02.CompareInternal(r.index[mid].lastKey, ikey) < 0 {
            lo = mid + 1    // index[mid] < ikey: answer must be to the right
        } else {
            hi = mid        // index[mid] >= ikey: answer is here or to the left
        }
    }

    // Phase 2: seek to data[lo].offset and linear-scan forward.
    r.f.Seek(int64(r.index[lo].offset), io.SeekStart)
    for pos < r.indexOffset {       // don't read past data section
        klen, _ := readVarint(r.f)
        k := make([]byte, klen)
        io.ReadFull(r.f, k)
        vlen, _ := readVarint(r.f)
        v := make([]byte, vlen)
        io.ReadFull(r.f, v)

        cmp := lab02.CompareInternal(k, ikey)
        if cmp == 0 {
            return v, true   // exact hit
        }
        if cmp > 0 {
            // k > ikey: check if same userKey (MVCC case — see below)
            uk, _, _  := lab02.DecodeInternalKey(k)
            searchUK, _, _ := lab02.DecodeInternalKey(ikey)
            if bytes.Equal(uk, searchUK) {
                return v, true   // same userKey, lower seqNum → valid MVCC match
            }
            break   // past the target userKey
        }
    }
    return nil, false
}

Why the binary search works here

CompareInternal sorts by (userKey ASC, seqNum DESC). All versions of a user key are contiguous in the data section and come before all versions of the next user key. The binary search finds the first index entry whose key ≥ the lookup key, which is the entry closest to — but not past — the target. The linear scan from there reaches the target within a few records.

MVCC-aware lookup

A lookup at readSeq=R builds the lookup key as EncodeInternalKey(uk, R, TypeValue). The file contains entries at various seqNums. Due to the descending seqNum sort, the first matching user key entry in the file is the most recent version ≤ R — exactly the MVCC-correct answer.

File contents for key "apple" (seqNum descending):
  ("apple", seq=10, TypeValue, "green")
  ("apple", seq=5,  TypeValue, "red")
  ("apple", seq=2,  TypeValue, "blue")

Lookup ikey = EncodeInternalKey("apple", 7, TypeValue):
  Binary search → points to entry for seq=10 (first "apple" entry ≥ our key)
  Linear scan:
    rec: ("apple", seq=10) → CompareInternal returns < 0 (10 > 7 in the tag)
         Wait: seqNum DESC means lower tag = higher seqNum.
         Actually CompareInternal(stored, ikey) > 0 means stored seqNum < ikey seqNum.
         The first stored entry with seqNum ≤ 7 is seq=5.
    rec: ("apple", seq=5) → userKeys match, seqNum 5 ≤ 7 → return "red" ✓

Callers must also handle TypeDelete results: if the returned record is a tombstone, the key does not exist at readSeq and the caller must not fall through to older SSTable levels.

SSTIter: sequential scan

func (r *Reader) NewIterator() *SSTIter {
    it := &SSTIter{r: r}
    r.f.Seek(0, io.SeekStart)   // start at beginning of data section
    it.advance()                // prime the first record
    return it
}

func (it *SSTIter) advance() {
    pos, _ := it.r.f.Seek(0, io.SeekCurrent)
    if pos >= it.r.indexOffset {    // past data section → done
        it.done = true
        return
    }
    klen, _ := readVarint(it.r.f)
    k := make([]byte, klen); io.ReadFull(it.r.f, k)
    vlen, _ := readVarint(it.r.f)
    v := make([]byte, vlen); io.ReadFull(it.r.f, v)
    it.key = k; it.val = v
}

func (it *SSTIter) Valid() bool   { return !it.done }
func (it *SSTIter) Key()   []byte { return it.key }
func (it *SSTIter) Value() []byte { return it.val }
func (it *SSTIter) Next()         { it.advance() }

The iterator maintains a file cursor — each call to Next() advances one record. This is the interface used by:

  • Lab 06 compaction (MergedIterator merges multiple SSTIters).
  • Lab 08 full-database scan (NewIterator).

Read amplification: why a single SSTable isn’t enough

After a MemTable flush, Get("k") checks:

  1. Active MemTable (RAM)
  2. Immutable MemTable, if flushing (RAM)
  3. L0 SSTable (disk)

But after 4 flushes, there are 4 L0 files, each potentially containing the key. The read path must check all of them (newest first) — this is read amplification: one logical Get becomes up to K file reads.

Lab 06 compaction solves this by merging L0 files into L1 with non-overlapping key ranges, bounding L1 reads to exactly 1 file per key lookup.

Running the tests

cd leveldb
go test ./lab04/... -v -count=1

Expected output:

=== RUN   TestBuildAndRead
--- PASS: TestBuildAndRead (0.00s)
=== RUN   TestGetMissing
--- PASS: TestGetMissing (0.00s)
=== RUN   TestIteratorOrder
--- PASS: TestIteratorOrder (0.00s)
=== RUN   TestCorruptFooter
--- PASS: TestCorruptFooter (0.00s)
PASS
ok      github.com/10xdev/leveldb/lab04

TestBuildAndRead walkthrough

Writes N records with Builder.Add, calls Finish, then opens a Reader and calls Get for each key. Also calls NewIterator and verifies keys come back in ascending order. This exercises both the binary-search path and the sequential scan.

TestCorruptFooter

Writes a valid SSTable, then overwrites the last 16 bytes with garbage. Asserts that Open returns a "bad magic" error. This verifies the corruption detection before any data is parsed.

Running the demo

go run ./lab04/demo

Expected output:

built  SSTable: 3 records, size=NNN bytes
get    apple  → green
get    name   → Alice
get    lang   → Go
iterate (sorted order):
  apple  = green
  lang   = Go
  name   = Alice

FoundationDB parallel

In FDB, the equivalent persistent unit is a B-tree page inside the storage server. Pages are copy-on-write (immutable once written), and the storage server keeps an in-memory page cache indexing page IDs to disk offsets — exactly our []indexEntry. Our SSTable is a radically simplified single-level B-tree where the entire file is one “page” and the index covers every record.

Real LevelDB and RocksDB split SSTables into 4 KiB data blocks with one index entry per block — rather than one per record. This reduces index RAM usage by ~100× for large files while only increasing the scan length from 1 record to at most one block (40–80 records). They also add a Bloom filter per SSTable: a 10-bit/key probabilistic bit-array answering “is key X definitely NOT in this file?” in O(1) without any disk I/O. With a 1% false-positive rate this eliminates ~99% of unnecessary file reads for missing keys.