Iterators, Snapshots, and Transactions¶

Reading a consistent view of many sources¶

At any moment, the data for one key may live in up to seven places: the memtable, the immutable memtable, four L0 tables, and an L1 table — each holding different versions. A range scan must merge all of them into a single sorted stream, show each key once (its newest visible version), hide deleted keys, and present the database as of one instant, even while writes, flushes, and compactions continue. This page builds that from small iterators, then uses the same machinery to add snapshots and optimistic transactions. The concepts are in MVCC in Storage Engines and Isolation Levels and Anomalies.

The iterator interface¶

type Iterator interface {
    First()
    Seek(key []byte) // position at the first entry >= key
    Next()
    Valid() bool
    Key() []byte
    Value() []byte
    Close() error
}

Every source implements it over internal keys: the skip list iterator, the block iterator, and the table iterator (a two-level iterator: index block → data block, from SSTables and Bloom Filters). Iterators compose: the merging iterator is an iterator over iterators, and the DB iterator is an iterator over the merging iterator.

The merging iterator¶

K sorted inputs, one sorted output: a min-heap of the input iterators ordered by their current key (container/heap):

type mergingIter struct {
    its []Iterator // newest source first
    h   iterHeap   // indices of valid iterators, ordered by current key
}

func (h *iterHeap) Less(i, j int) bool {
    a, b := h.its[h.idx[i]], h.its[h.idx[j]]
    if c := h.cmp(a.Key(), b.Key()); c != 0 {
        return c < 0
    }
    return h.idx[i] < h.idx[j] // tie-break by source order (never happens with unique sequences)
}

func (m *mergingIter) Seek(k []byte) {
    for _, it := range m.its {
        it.Seek(k)
    }
    m.rebuild() // heap of all children that are still valid
}

func (m *mergingIter) Next() {
    top := m.its[m.h.idx[0]]
    top.Next()
    if top.Valid() {
        heap.Fix(&m.h, 0) // O(log K)
    } else {
        heap.Pop(&m.h)
    }
}

func (m *mergingIter) Key() []byte { return m.its[m.h.idx[0]].Key() }

Each Next costs O(log K) comparisons. The same iterator drives range scans, flushes, and compaction.

The DB iterator: one version per key, as of a sequence¶

The merging iterator yields every version of every key, newest first per key. DBIter turns that into the user's view at sequence seq:

func (it *DBIter) findNext(skip []byte, skipping bool) {
    skip = append([]byte(nil), skip...)
    for ; it.m.Valid(); it.m.Next() {
        k := it.m.Key()
        uk, tr := ukey(k), trailer(k)
        if tr>>8 > it.seq {
            continue // written after our snapshot: invisible
        }
        if skipping && bytes.Equal(uk, skip) {
            continue // an older version of a key already emitted or deleted
        }
        if ValueType(tr&0xff) == TypeDeletion {
            skip, skipping = append(skip[:0], uk...), true // hide the key and everything older
            continue
        }
        it.key = append(it.key[:0], uk...)
        it.val = append(it.val[:0], it.m.Value()...)
        it.valid = true
        return
    }
    it.valid = false
}

func (it *DBIter) Next() {
    it.m.Next()
    it.findNext(it.key, true) // skip the remaining older versions of the current key
}

Reading findNext against a concrete stream, with seq = 120:

Merged entry	Action
`apple @130 PUT`	Invisible (130 > 120), skip
`apple @110 PUT "red"`	Emit `apple = "red"`
`apple @90 PUT "green"`	Older version of `apple`, skip
`banana @100 DEL`	Tombstone: remember `banana`, skip
`banana @80 PUT "yellow"`	Shadowed by the tombstone, skip
`cherry @50 PUT "dark"`	Emit `cherry = "dark"`

The iterator holds a reference on the version it was created with, so compaction cannot delete the tables under it, and it holds the memtable pointers, so a flush does not affect it. It is a consistent, point-in-time view for as long as it lives — and must be closed, or it pins those files forever (the LSM equivalent of a goroutine leak).

Two simplifications compared with LevelDB: no reverse iteration (Prev requires every child iterator to support it and is the most intricate code in LevelDB's DBIter), and keys and values are copied into the iterator on each step (zero-copy iterators return slices into blocks that are only valid until the next Next).

Snapshots¶

A snapshot is just a sequence number that the engine promises to keep readable:

func (db *DB) GetSnapshot() *Snapshot {
    db.mu.Lock()
    defer db.mu.Unlock()
    s := db.lastSeq.Load()
    db.snapshots[s]++ // registered: compaction must not drop versions it can see
    return &Snapshot{seq: s}
}

Reads and iterators take a snapshot's sequence instead of the latest. Compaction computes the oldest live snapshot and keeps any version that some snapshot can still see. The test writes a=1, takes a snapshot, overwrites and then deletes a, writes 50,000 more keys to force several flushes and compactions, and checks that the snapshot still reads a=1 while the latest view reports not found.

Like iterators, long-lived snapshots have a cost: every version newer than the snapshot that is overwritten afterwards must be kept, so space amplification grows for as long as the snapshot lives. The same is true of long-running transactions in PostgreSQL (dead tuples that vacuum cannot remove — MVCC in PostgreSQL).

Transactions on top of the engine¶

Snapshots give consistent reads; batches give atomic writes. A transaction needs one more thing: isolation between concurrent read-modify-write cycles. The classic failure without it is the lost update: two clients read counter = 5, both write 6.

Optimistic concurrency control¶

Read from a snapshot, buffer writes, and at commit validate that nothing the transaction read has been changed by someone else since:

type Txn struct {
    db     *DB
    snap   *Snapshot
    reads  map[string]uint64 // key → sequence of the version we read (0 = absent)
    writes map[string][]byte // buffered; nil = delete
    order  []string
}

func (t *Txn) Get(key []byte) ([]byte, error) {
    if v, ok := t.writes[string(key)]; ok { // read your own writes
        if v == nil {
            return nil, ErrNotFound
        }
        return v, nil
    }
    v, seq, err := t.db.get(key, t.snap) // value + sequence of the entry that answered
    if err != nil && !errors.Is(err, ErrNotFound) {
        return nil, err
    }
    t.reads[string(key)] = seq
    return v, err
}

func (t *Txn) Commit(o WriteOptions) error {
    defer t.Rollback() // releases the snapshot
    commitMu.Lock()    // validation and write must be one atomic step
    defer commitMu.Unlock()
    for k, seenSeq := range t.reads {
        _, cur, err := t.db.get([]byte(k), nil) // latest committed version
        if err != nil && !errors.Is(err, ErrNotFound) {
            return err
        }
        if cur != seenSeq {
            return ErrConflict // someone changed what we read: caller retries
        }
    }
    var b Batch
    for _, k := range t.order {
        if v := t.writes[k]; v == nil {
            b.Delete([]byte(k))
        } else {
            b.Put([]byte(k), v)
        }
    }
    return t.db.Write(&b, o) // atomic: one batch, one WAL record
}

The sequence number of the version a transaction read is its version stamp: if the latest version of the key has a different sequence at commit time, another transaction committed a write in between. Tests:

Lost updates: 8 goroutines each increment a counter 200 times with retry on conflict. Final value: exactly 1,600; along the way, 692 commits were rejected and retried.
Write skew: Alice and Bob are both on call. T1 checks Bob is on call and takes Alice off; T2 checks Alice is on call and takes Bob off. Each writes a key the other only read. Under snapshot isolation alone both would commit and nobody would be on call. Here T2's read of alice_on_call fails validation after T1 commits, and T2 gets ErrConflict.

Because every read is validated and validation plus write happen in one critical section, committed transactions are serializable for point reads. Its limits:

Limitation	Consequence	Real-world fix
Range reads are not validated	Phantoms: a scan for "all orders of user 7" misses a concurrently inserted order	Validate ranges (predicate locks / range read sets), as CockroachDB does
`commitMu` is global	Commits are serialized; validation does a `get` per read key	Validate inside the commit goroutine; validate against a recent-writes index instead of full lookups
Non-transactional `db.Put` bypasses validation	A plain write between validation and commit could be missed	All writers to transactional keys go through transactions
High contention	Many retries (692 for 1,600 commits here)	Pessimistic locking for hot keys
Compaction may drop a tombstone a transaction read	Validation sees `0` instead of the tombstone's sequence → a spurious conflict	Safe direction (abort, retry); acceptable

Pessimistic locking¶

The alternative takes a lock on each key before reading it for update and holds it until commit (two-phase locking): no wasted work on conflict, but transactions wait for each other, deadlocks must be detected or prevented (lock ordering, timeouts), and a slow client holding locks blocks everyone. RocksDB offers both (OptimisticTransactionDB and TransactionDB); the trade-off is the same as in Locking and Concurrency: optimistic wins at low contention, pessimistic at high contention.

Common pitfall¶

Forgetting to close iterators. A Go service built on an LSM engine (Pebble, Badger) runs range scans in request handlers and returns early on errors without defer it.Close(). Each leaked iterator pins its memtables and its version — so every SSTable that existed when it was opened. Compactions keep producing new tables, but the inputs they replaced can never be deleted. Disk usage climbs for days while the "live" data size stays flat, and memory grows with the pinned memtables. Pebble reports open iterators and pinned resources in its metrics; the code-level fix is the same rule as for files and response bodies: defer it.Close() on the line after creating the iterator.

Review questions¶

Why does the merging iterator need a heap, and what does each Next cost?
Walk through findNext for a key with a tombstone at sequence 100 and a value at sequence 80, read at sequence 120 and at sequence 90.
Why does a long-lived snapshot increase disk usage?
How does the transaction detect that another transaction changed a key it read? Why does that also prevent write skew?
Which anomaly can this transaction implementation still allow, and what would fix it?