Snapshots, Sequence Numbers, and GC

We've touched on sequence numbers throughout the course. Here's the full picture: how snapshots, MVCC, and garbage collection compose into a coherent design.

Sequence Numbers Are the Source of Truth

Every write — PUT, DELETE, range delete — gets a unique, monotonically increasing sequence number when it enters the engine. The sequence number is recorded in:

• The WAL record (so recovery can re-order writes)
• The memtable entry (so reads see the latest)
• The SSTable record after flush (so compaction can dedup)

Sequence numbers totalize the write history. Two writes with seqs s1 < s2 happened in that order, even if they're in different SSTables at different levels.

Snapshots Are Just Numbers

Acquiring a snapshot:

Releasing a snapshot:

Both are O(1). Snapshots are stored in a sorted set (or a heap) so compaction can quickly find the smallest active one.

Reading at a Snapshot

For each key visited by a merge iterator at snapshot s:

• Skip versions with seq > s (invisible at this snapshot).
• The first version with seq <= s is the visible answer.

This is essentially the same logic as MVCC in a B-tree database (Postgres, InnoDB), except the version chain is spread across multiple SSTables instead of in a single tuple.

Garbage Collection Rules

Compaction drops a version (PUT or tombstone) when:

1. It's older than the smallest active snapshot's seq.
2. AND a newer version of the same key exists (so this version is shadowed).

If condition 2 fails, the version is still the "latest visible" for some range of seqs and must be preserved. If condition 1 fails, some snapshot still needs it.

For range and point tombstones, the rule extends: keep the tombstone until it's at the bottommost level AND no covered version exists below AND no snapshot needs it.

Pinned Files

A snapshot may pin SSTables: if compaction wants to drop file F but F is the only place a snapshot-visible version of some key lives, compaction must wait or keep F.

In practice engines avoid this by deferring compaction decisions: don't drop versions until they're truly free. RocksDB has knobs for this.

Snapshot Cost

Snapshots are cheap to take and to read but expensive to hold: they pin obsolete versions, blowing space amplification. Long-held snapshots are an operational anti-pattern. Always release them when done.

Repeatable Reads Without ROW LOCKS

This is the killer feature. A reader takes a snapshot, runs a long query without locks, and sees a consistent view of the database at the snapshot moment. Concurrent writers don't block readers; readers don't block writers. MVCC for free.

PostgreSQL has the same model (transaction IDs instead of seqs). LSM engines just have the version chain spread differently.

Practical Notes

• Hold snapshots for the duration of one read, then release.
• For long-running analytics, take a snapshot, dump the data, release.
• For multi-statement transactions, the engine's transaction system uses snapshots internally.
• Backups: take a snapshot, copy the live SSTables, release. The snapshot guarantees the file list is consistent.