Sequence Numbers & MVCC Versions

When the memtable supports snapshots (consistent reads at a point in time), it needs to remember more than just the latest value for each key. It needs to track every write and tag each one with a monotonically increasing sequence number (also called LSN — Log Sequence Number).

The Idea

Instead of key -> value, the memtable stores (key, seq) -> value pairs, sorted by (key ASC, seq DESC):

("user:1", 105) -> "alice@v3"
("user:1", 87)  -> "alice@v2"
("user:1", 12)  -> "alice@v1"
("user:2", 99)  -> "bob"
("user:3", 110) -> "carol"

A read at sequence number snap looks up the smallest (key, seq') where seq' <= snap. In the example above, read('user:1', snap=90) returns alice@v2 (seq 87).

Why "seq DESC" Inside a Key?

Sorting versions newest-first inside a key means the iterator naturally walks from the most recent to the oldest version. To find the visible version at snapshot snap, scan forward and pick the first entry with seq <= snap. Done.

Where the Sequence Number Comes From

A single global counter advances on every write — usually one number per WAL append. The memtable, the WAL, and the SSTable footer all record the same sequence number for the same write. That global ordering is what gives the LSM tree a consistent total order across all storage levels.

Snapshot Reads

Acquiring a snapshot is essentially free: just record the current sequence number. Future reads use that number as their upper bound. As long as compaction preserves at least the latest version per key for every live snapshot, the snapshot stays consistent.

When Can Versions Be Dropped?

During compaction, if a key has multiple versions and the second-newest version has seq < min(active snapshots), every older version can be discarded. That's the standard MVCC garbage-collection rule.

Implementation Note

SortedDict[(key, -seq)] = value works fine in Python. Negating seq makes the natural sort order put higher seqs first per key, so bisect_left((key, -snap)) jumps to the first visible version.