Lab 07 — Snapshots and Benchmarks

• What this lab adds
• The MVCC snapshot model
• GetSnapshot() annotated
• Snapshot.Get() execution trace
• Isolation anomaly table
  • Dirty read prevention: proof
• Read-your-writes guarantee
• seqNum lifecycle: end-to-end
• Snapshot.NewIterator() annotated
• Benchmark analysis
  • Why 28 µs per write?
  • Why 6 µs per read?
• Running the tests
  • TestSnapshotIsolation walkthrough
  • TestSnapshotIterator walkthrough
• Running the demo
• FoundationDB parallel

What this lab adds

Lab 06 is a complete compacting key-value store. Lab 07 adds the final user-visible feature: snapshot isolation.

A snapshot captures the database state at a single seqNum and holds it constant regardless of subsequent writes. All reads through the snapshot see exactly the key-value pairs that existed at snapshot creation time. This is the foundation for multi-key transactions, consistent backups, and range scans that cannot be affected by concurrent writers.

The lab also includes benchmarks that demonstrate how the engine performs under sustained write load.

The MVCC snapshot model

Recall from lab02: every Put/Delete writes an internal key:

internal key = userKey || uint64(seqNum<<8 | keyType)

The seqNum is a monotonically increasing counter, incremented for each write. The MemTable and SSTables store all versions of every key. No value is ever overwritten in place.

A snapshot pins a readSeq. Every Get and NewIterator call that goes through the snapshot uses this fixed readSeq instead of the live db.seqNum:

Write sequence:
  seqNum=1: Put("color","red")
  seqNum=2: GetSnapshot() → snap.seqNum = 1
  seqNum=3: Put("color","blue")

snap.Get("color") → searches for versions with seqNum ≤ 1 → "red"
db.Get("color")   → searches for versions with seqNum ≤ 3 → "blue"

Because MVCC stores all versions, both reads are correct simultaneously — the snapshot reader and the live reader see different values of “color” with no locking.

GetSnapshot() annotated

func (db *DB) GetSnapshot() *Snapshot {
    seq := db.inner.SeqNum()   // returns db.seqNum (next-to-assign)
    if seq > 0 {
        seq--                  // convert to last-committed seqNum
    }
    return &Snapshot{db: db, seqNum: seq}
}

Why seq - 1?

db.seqNum is the next seqNum to be assigned — it has not been written yet. The last committed write was db.seqNum - 1. If we used db.seqNum as the snapshot’s readSeq, the snapshot would be trying to see a write that hasn’t happened yet (and may never happen if the write fails).

Timeline:
  seqNum=5: Put("k","v5") written and durable
  db.seqNum is now 6 (next-to-assign)

  GetSnapshot():
    seq = db.SeqNum()  = 6
    seq--              = 5      ← correct: last committed write
    snap.seqNum = 5

  snap.Get("k") → searches for versions with seqNum ≤ 5 → finds "v5" ✓

  If we had used 6: searches for seqNum ≤ 6 → same result.
  But at seqNum=6 the entry does not exist, so the filter would still work.
  The reason for seq-- is conceptual correctness and for the edge case when
  seqNum=0: seq-- would underflow to MaxUint64, returning every possible entry.
  The guard `if seq > 0 { seq-- }` prevents this.

The seqNum=0 edge case: Open starts with seqNum=1 (or higher if MANIFEST has a stored NextSeq). For a fresh empty database: seqNum=1, GetSnapshot() returns snap.seqNum=0. A snap.Get with readSeq=0 finds no records (all stored records have seqNum ≥ 1) — correctly representing an empty snapshot.

Snapshot.Get() execution trace

type Snapshot struct {
    db     *DB
    seqNum uint64
}

func (s *Snapshot) Get(key []byte) ([]byte, bool) {
    return s.db.inner.GetAt(key, s.seqNum)
}

GetAt is the same as Get but uses the provided readSeq instead of db.seqNum:

func (db *DB) GetAt(key []byte, readSeq uint64) ([]byte, bool) {
    // Build the MVCC lookup key:
    ikey := lab02.EncodeInternalKey(key, readSeq, lab02.TypeValue)
    // EncodeInternalKey("color", 1, TypeValue) →
    //   [63 6f 6c 6f 72  01 01 00 00 00 00 00 00]
    //    c  o  l  o  r   ^--keyType=1 (TypeValue), seqNum=1

    // Check mem, imm, L0, L1 — same as Get() but with fixed ikey seqNum:
    if v, ok := db.mem.Get(key, readSeq); ok { return v, true }
    // MemTable.Get calls CompareInternal(ikey_from_mem, ikey) — returns the
    // first version with seqNum ≤ readSeq.

    // ... imm, L0, L1 same pattern ...
}

Full call stack for snap.Get("color") (snap.seqNum=1, color was written at seq=1):

snap.Get("color")
  → db.inner.GetAt("color", 1)
     → ikey = EncodeInternalKey("color", 1, TypeValue)
     → mem.Get("color", 1)
          skip list search for ikey
          finds entry ("color", seq=3) first (if it exists) → seqNum=3 > 1 → skip
          finds entry ("color", seq=1) → seqNum=1 ≤ 1 → return "red" ✓

If “color@seq=1” is not in mem (was flushed to L0/L1), the same ikey is sent to lab04.Reader.Get(ikey) which performs the binary-search + linear scan described in lab04.

Isolation anomaly table

MVCC (snapshot isolation) eliminates read anomalies without locks. It does not protect concurrent writers from each other — that requires either pessimistic locking (lock the key before reading it) or optimistic concurrency control (check at commit time that no conflicting write happened). FDB uses the latter via its conflict-detection layer on top of MVCC.

Dirty read prevention: proof

A write at seqNum=N is added to the MemTable under db.mu, then seqNum is incremented to N+1. GetSnapshot() calls db.SeqNum() which returns the current db.seqNum. At the moment of the snapshot, either:

1. The write at N is complete: db.seqNum = N+1, snapshot sees readSeq=N, which includes the write at N. ✓
2. The write at N is not yet started: db.seqNum = N, snapshot sees readSeq = N-1, which does not include the incomplete write. ✓
3. The write is in progress (between WAL append and seqNum++): the write holds db.mu during seqNum++; GetSnapshot() also calls db.SeqNum() which returns db.seqNum under no lock — but the seqNum is an atomic read in lab08, or reads the committed increment value in labs 05-07. In either case, the snapshot sees either N (before the increment) or N+1 (after), never a partial state.

Read-your-writes guarantee

After Put("k","v") at seqNum=N, db.seqNum is now N+1. A subsequent db.Get("k") uses readSeq = db.seqNum - 1 = N. The MemTable contains the entry ("k", N, TypeValue, "v"). MemTable.Get("k", N) finds this entry (seqNum=N ≤ readSeq=N) and returns "v". ✓

For a snapshot taken after the Put:

• GetSnapshot() sees db.seqNum = N+1, returns snap.seqNum = N.
• snap.Get("k") uses readSeq = N → same result. ✓

For a snapshot taken before the Put:

• GetSnapshot() sees db.seqNum = N, returns snap.seqNum = N-1.
• snap.Get("k") uses readSeq = N-1 → does not see the Put. ✓ This is correct: the write happened after the snapshot was created.

seqNum lifecycle: end-to-end

Open:
  Load MANIFEST → manifest.NextSeq = 100 (last flushed seqNum)
  db.seqNum = 100

WAL replay:
  WAL record: seqNum=100, Put("x","v")
  applyWALRecord: if 100 < manifest.NextSeq=100 → false (not skipped; equal)
  mem.Add(100, TypeValue, "x", "v")
  db.seqNum = 101  (max(current, rec.seqNum+1))

Writes after Open:
  Put("y","w"):
    seq=101; db.seqNum=102
    WAL record written with seq=101
    mem.Add(101, TypeValue, "y", "w")

Flush triggered:
  flushImmutable: builds SSTable from mem (seqNums 100-101)
  manifest.NextSeq = 102  ← persisted
  MANIFEST saved

Crash + reopen:
  manifest.NextSeq = 102
  db.seqNum = 102
  WAL replay: record with seqNum=101 → 101 < 102 → SKIPPED
  (already in SSTable; replaying it again would add duplicate → wrong)

Snapshot.NewIterator() annotated

func (s *Snapshot) NewIterator() *lab06.MergedIterator {
    return s.db.inner.NewIteratorAt(s.seqNum)
}

NewIteratorAt(readSeq) creates a MergedIterator with readSeq=s.seqNum instead of the live db.seqNum. All the dedup and tombstone logic from lab06 applies, but restricted to versions written at or before the snapshot.

This enables consistent range scans:

snap := db.GetSnapshot()
it := snap.NewIterator()
for it.Valid() {
    fmt.Printf("%s = %s\n", it.Key(), it.Value())
    it.Next()
}
// All key-value pairs are from the snapshot instant.
// Concurrent writes during this loop are completely invisible.

Benchmark analysis

The lab07 benchmarks measure raw write throughput:

cd leveldb
go test ./lab07/... -bench=. -benchtime=5s

Expected output (NVMe SSD, macOS):

BenchmarkPut-8         50000    28000 ns/op    35714 ops/s
BenchmarkGet-8        200000     6200 ns/op   161290 ops/s

Why 28 µs per write?

Each Put involves:

1. db.mu.Lock()                            ~100 ns (uncontended mutex)
2. WAL encode (in-memory)                  ~200 ns
3. wal.Write(record)                       ~100 ns (buffered write)
4. wal.fdatasync()                         ~20 µs  ← dominant cost on NVMe
5. mem.Add(key, value)                     ~500 ns (skip list insert)
6. db.mu.Unlock()                          ~100 ns
Total: ~21-25 µs, matching the ~28 µs observed

The fdatasync call is the bottleneck. On a macOS APFS SSD, fdatasync (actually fcntl(F_FULLFSYNC) on macOS for true durability) takes 5–30 µs. On a mechanical HDD it would be 2–10 ms.

To increase write throughput, real engines use group commit: one goroutine collects N concurrent writes into a single WAL buffer and issues a single fdatasync for all of them. This amortizes the sync cost:

Without group commit: 10 writers × 20 µs/sync = 200 µs elapsed for 10 writes
With group commit:    10 writers batched → 1 × 20 µs/sync = 2 µs per write

RocksDB’s WriteBatch implements group commit. Lab 03’s WriteBatch is the precursor; lab 08 adds the plumbing to amortize the sync cost.

Why 6 µs per read?

Get acquires db.mu for a microsecond to snapshot the pointers, then reads from the MemTable (O(log N) skip list search, all in L1 cache after warm-up) or the OS page cache (L0/L1 SSTables). For a hot working set entirely in the MemTable, the 6 µs is dominated by the mutex and skip list traversal.

Running the tests

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

Expected output:

=== RUN   TestSnapshotIsolation
--- PASS: TestSnapshotIsolation (0.00s)
=== RUN   TestSnapshotDoesNotSeeNewWrites
--- PASS: TestSnapshotDoesNotSeeNewWrites (0.00s)
=== RUN   TestSnapshotIterator
--- PASS: TestSnapshotIterator (0.00s)
=== RUN   TestReadYourWrites
--- PASS: TestReadYourWrites (0.00s)
PASS
ok      github.com/10xdev/leveldb/lab07

TestSnapshotIsolation walkthrough

db.Put("k", "v1")          // seqNum=1
snap := db.GetSnapshot()   // snap.seqNum=1
db.Put("k", "v2")          // seqNum=2

v, _ := snap.Get("k")      // should return "v1"
assert(v == "v1")          // ✓ snapshot sees seqNum ≤ 1

v, _ = db.Get("k")         // should return "v2"
assert(v == "v2")          // ✓ live read sees seqNum ≤ 2

TestSnapshotIterator walkthrough

1. Write keys “a”, “b”, “c”.
2. Take snapshot S1.
3. Write keys “d”, “e” and delete “b”.
4. Iterate S1 → sees “a”, “b”, “c” (no “d”, “e”; “b” not deleted).
5. Iterate live DB → sees “a”, “c”, “d”, “e” (“b” deleted).

Running the demo

go run ./lab07/demo

Expected output:

=== Scenario: snapshot isolation ===
  before snapshot: color=red
  snap.Get(color)=red     ← snapshot at seqNum=1
  after db.Put(color,blue) at seqNum=2:
  snap.Get(color)=red     ← unchanged ✓
  db.Get(color)=blue      ← live read ✓

=== Benchmark: 5000 sequential writes ===
  5000 writes in NNNms → NNN writes/s

=== Scenario: snapshot range scan ===
  scan at snapshot sees N keys
  scan at live DB sees N+K keys (K added after snapshot)

FoundationDB parallel

FDB’s snapshot isolation is built directly on the same MVCC model. Every FDB transaction reads at a readVersion (FDB’s equivalent of our seqNum). GetSnapshot() calls db->getReadVersion() which returns the current committed version — exactly db.seqNum - 1 in our engine.

FDB extends the model further with strict serializability (snapshot isolation

• conflict detection): two transactions conflict if they read and write the same key. The conflict resolver at the proxy checks read-write conflicts at commit time, rejecting the transaction with a retryable error (transaction_too_old) if the readVersion is stale. This gives users the ability to write read-modify-write transactions without programmer-visible locking.

Snapshot.Release() is a no-op in our implementation. In production engines (RocksDB, FDB), Release() unregisters the snapshot from a global snapshot list. The compaction process maintains minSnap = min(snap.seqNum across all live snapshots). MVCC versions older than minSnap that have been superseded by newer versions can be safely garbage-collected during compaction — reducing SSTable bloat from long-lived snapshots.