Lab 02 — MemTable + Internal Keys

• Concept: The Skip List
  • Why not an array, hash map, or balanced BST?
  • Why balanced BSTs are hard to make concurrent
    • Red-black tree: what rebalancing actually does
  • Structure: a linked list with express lanes
  • Probabilistic level assignment
  • Search algorithm
  • Insert algorithm
  • Why two pointer writes per level is sufficient: proof by invariant
  • Node layout in memory
  • Memory fragmentation: what 40,000 nodes actually costs
  • Cache behaviour
  • Complexity summary
  • Proving the sorted-array O(n) insert claim
  • Proving O(log n) expected search cost: backwards analysis
  • Making the skip list concurrent-safe
• Concept: Internal Keys and MVCC
  • What is MVCC?
  • Visualising multiple versions
  • MVCC in other database systems
    • PostgreSQL — heap tuple versioning
    • Oracle / MySQL InnoDB — undo log chain
    • LevelDB / RocksDB — inline append-only versions
  • Internal key format: byte layout
  • Why the tag is little-endian
  • CompareInternal: the comparator
  • MemTable.Get: step-by-step
• Iterator design: level-0 traversal
• What the MemTable wraps
• Running the tests
• Running the demo
• FoundationDB parallel

Concept: The Skip List

Why not an array, hash map, or balanced BST?

A storage engine’s in-memory write buffer needs four properties at the same time:

The hash map disqualifies itself immediately: iteration returns keys in arbitrary order. An SSTable flush iterates the MemTable in sorted order to write keys sequentially — an unsorted structure would force a full sort on every flush.

The array can iterate in order, but inserting into a sorted array requires shifting all higher elements right — O(n) per insert on average. For a 4 MiB MemTable holding ~40,000 keys that is 20,000 moves per write — completely unacceptable.

That leaves the balanced BST and the skip list. Both achieve O(log n) for all required operations. Understanding why the skip list wins in practice requires understanding what balanced BSTs actually cost.

Why balanced BSTs are hard to make concurrent

Red-black tree: what rebalancing actually does

A red-black tree is a binary search tree where each node is coloured red or black and the following invariants are maintained after every insert/delete:

1. Every node is red or black.
2. The root is black.
3. Every leaf (nil sentinel) is black.
4. A red node’s children are both black (no two consecutive red nodes).
5. All paths from any node to its descendant nil leaves pass through the same number of black nodes.

Invariant 5 guarantees that the longest path (alternating red/black) is at most twice the shortest path (all black), bounding height at 2 log₂(n+1).

When you insert a new key, it arrives as a red node. If its parent is also red, invariant 4 is violated. The tree repairs itself via two operations:

Colour flip (recolouring): when the new node’s parent and uncle are both red, flip both to black and flip the grandparent to red. This may push the violation up the tree.

Before (violation: P and N are both red):

       G (black)
      / \
    P(r) U(r)
   /
  N(r)

After colour flip:

       G (red)    ← now G may violate with its own parent
      / \
    P(b) U(b)
   /
  N(r)

Rotation (restructuring): when recolouring alone cannot fix the violation, a subtree rotation restructures three nodes. A left rotation on x:

    x                y
   / \              / \
  A   y    →       x   C
     / \          / \
    B   C        A   B

A right rotation is the mirror image. The tree has four cases (left-left, left-right, right-right, right-left) each requiring one or two rotations.

The critical insight for concurrency: a single insert can trigger O(log n) recolouring steps and up to two rotations, modifying nodes at multiple levels of the tree. Making this atomic for concurrent readers is hard:

• Coarse lock (sync.RWMutex on the whole tree): simple but serialises all readers — unacceptable when readers are the majority.
• Lock coupling (hand-over-hand locking): lock parent before releasing child; correct but complex and still serialises the path from root to the insert point.
• RCU (Read-Copy-Update): readers are truly lock-free; writers copy the modified path and atomically swap the root pointer. The Linux kernel uses this for its red-black trees (e.g. the CFS scheduler’s task tree), but the implementation is hundreds of lines of careful pointer manipulation.

In contrast, a skip list writer only touches the O(log n) next[i] pointers along the insertion path — no rebalancing, no rotations, no path-to-root modifications. With careful use of atomic.Pointer, a skip list writer can publish a new node without ever blocking a concurrent reader.

Structure: a linked list with express lanes

Start with a plain sorted singly-linked list. Finding a value takes O(n):

level 0:  head → 10 → 20 → 30 → 40 → 50 → 60 → 70 → 80 → nil

Add an “express lane” at level 1: every other node is also linked at level 1, so you skip two nodes per comparison at that level.

level 1:  head ──────→ 20 ──────→ 40 ──────→ 60 ──────→ 80 → nil
level 0:  head → 10 → 20 → 30 → 40 → 50 → 60 → 70 → 80 → nil

Add level 2 — skips every 4th node at level 0:

level 2:  head ────────────────→ 40 ────────────────→ 80 → nil
level 1:  head ──────→ 20 ──────→ 40 ──────→ 60 ──────→ 80 → nil
level 0:  head → 10 → 20 → 30 → 40 → 50 → 60 → 70 → 80 → nil

With k levels and deterministic promotion (every 2^(k-1)-th node at level k-1), search is O(log n) — exactly like a binary search. But insert now requires updating O(log n) levels of pointers for every node and rebalancing when the structure drifts.

The skip list insight (Pugh, 1990): choose the number of levels for a new node randomly, with probability p of gaining each additional level. This collapses all deterministic restructuring into a single coin flip per insert.

Probabilistic level assignment

Each new node is assigned a level h drawn from a geometric distribution:

P(h = 1) = 1 - p               ≈ 75%  (stays at level 1 only)
P(h = 2) = p(1-p)              ≈ 19%  (reaches level 2)
P(h = 3) = p²(1-p)             ≈  5%  (reaches level 3)
P(h = k) = p^(k-1) * (1-p)

With p = 0.25 (as in our implementation), a node needs 3 coin flips to reach level 3. The expected number of nodes at level k is:

E[nodes at level k] = n · p^(k-1)

n=1000, p=0.25:
  level 1: 1000  nodes  (all of them)
  level 2:  250  nodes  (every ~4th)
  level 3:   63  nodes  (every ~16th)
  level 4:   16  nodes  (every ~64th)
  level 5:    4  nodes

This mimics the deterministic structure but with random spacing — the expected search time is O(log n) because the structure tracks a random approximation of the perfectly-balanced case.

Our randomLevel() generates this distribution directly:

// randomLevel returns a random level in [1, maxLevel] with geometric
// distribution at probability prob (0.25).  Never returns 0.
func randomLevel() int {
    lvl := 1
    for lvl < maxLevel && rand.Float64() < prob {
        lvl++
    }
    return lvl
}

Each iteration of the loop is one coin flip: continue to the next level with probability 0.25, stop with probability 0.75. Because the loop exits at maxLevel = 12, the maximum storable key count before height becomes a bottleneck is roughly (1/p)^maxLevel = 4^12 ≈ 16 million — far beyond our 4 MiB flush threshold.

Search algorithm

To find value x, start at the top-left (highest active level of the head node). At each position:

• If next.key < x: advance right (move to next node at this level).
• If next.key ≥ x or next == nil: drop down one level.
• At level 0, if next.key == x: found.
• At level 0, if next.key > x or next == nil: not present.

Traced example — search for 60 in a skip list with max 4 active levels:

level 3:  head ─────────────────────────────→ 50 ──────────────→ nil
level 2:  head ─────→ 10 ──────────────────→ 50 ──→ 80 ─────→ nil
level 1:  head ─────→ 10 ──────→ 30 ────────→ 50 ──→ 80 ─────→ nil
level 0:  head → 10 → 20 → 30 → 40 → 50 → 60 → 70 → 80 → 90 → nil

Start at head, level 3
  L3: next=50, 50 < 60 → advance. Now at 50, L3.
  L3: next=nil → drop to L2. Now at 50, L2.
  L2: next=80, 80 > 60 → drop to L1. Now at 50, L1.
  L1: next=80, 80 > 60 → drop to L0. Now at 50, L0.
  L0: next=60, 60 == 60 → found.

5 comparisons. A plain list scan would take 6. With n=10,000 and 6 active levels, the expected comparisons drop from 10,000 to roughly 30.

Insert algorithm

Insert is a search that records its path, then splices the new node in:

// Put inserts or replaces the entry for key.
func (sl *SkipList) Put(key, value []byte) {
    var update [maxLevel]*node   // update[i] = rightmost node at level i with key < new key
    cur := sl.head
    for i := sl.level - 1; i >= 0; i-- {
        for cur.next[i] != nil && CompareInternal(cur.next[i].key, key) < 0 {
            cur = cur.next[i]
        }
        update[i] = cur          // last node at level i that is still < key
    }

    // Exact duplicate: same internal key (same userKey + seqNum + type).
    if n := update[0].next[0]; n != nil && CompareInternal(n.key, key) == 0 {
        n.value = value
        return
    }

    lvl := randomLevel()
    if lvl > sl.level {
        for i := sl.level; i < lvl; i++ {
            update[i] = sl.head  // new levels start from the head
        }
        sl.level = lvl
    }

    n := &node{key: key, value: value}
    for i := 0; i < lvl; i++ {
        n.next[i] = update[i].next[i]   // point new node forward
        update[i].next[i] = n           // point predecessor to new node
    }
    sl.length++
}

Traced example — insert 35 (coin flips yield level h=2):

Level 1 search pass: last node with key < 35 → node(30) → update[0] = node(30)
Level 0 search pass: same result            → update[1] = node(30)

Create node(35) with 2 levels.

Splice at level 1: 35.next[1] = 30.next[1] = 50;  30.next[1] = 35
Splice at level 0: 35.next[0] = 30.next[0] = 40;  30.next[0] = 35

Result:
  L1: head → 10 → 30 → 35 → 50 → 80 → nil   ← 35 inserted
  L0: head → 10 → 20 → 30 → 35 → 40 → 50 → 60 → 70 → 80 → 90 → nil

Only two pointer writes per level. No rotations. No path-to-root updates.

Why two pointer writes per level is sufficient: proof by invariant

The update array is provably correct because the search phase establishes a strict invariant at every level i:

INVARIANT: after the search loop at level i,
  update[i].key  <  newKey  ≤  update[i].next[i].key
  (or update[i].next[i] == nil)

Proof: the inner loop for cur.next[i] != nil && Compare(cur.next[i].key, key) < 0 advances cur as long as the next node’s key is strictly less than newKey. It stops precisely when cur.next[i].key ≥ newKey or cur.next[i] == nil. At that moment, update[i] = cur — recording the last node that is strictly less than newKey at this level.

Given that invariant, two pointer writes are exactly sufficient to splice n in:

Before:  update[i]  ──[i]──→  successor
After:   update[i]  ──[i]──→  n  ──[i]──→  successor

Write 1: n.next[i]         = update[i].next[i]   (= successor)
Write 2: update[i].next[i] = n

No other node at level i needs its pointers changed — n is correctly positioned between its predecessor (already found) and successor (already known) at every level. This is why skip list insert requires no global restructuring whereas a red-black tree insert may modify any ancestor up to the root.

Node layout in memory

Our node struct:

type node struct {
    key   []byte        // internal key (userKey + 8-byte tag)
    value []byte
    next  [maxLevel]*node  // array of 12 pointers, each 8 bytes on 64-bit
}

Memory cost per node on a 64-bit system:

key header:   16 bytes  (slice: data pointer + length)
value header: 16 bytes  (slice: data pointer + length)
next array:   96 bytes  (12 × 8-byte pointer)
─────────────────────────────────────────────────────
struct total: 128 bytes + heap for key/value bytes

Only the levels actually used are populated; unused pointers are nil. A level-1 node uses 96 bytes for the array but only the first 8 bytes are non-nil — a small waste. Real LevelDB uses a variable-length node that allocates only as many pointer slots as the node’s level, saving 84 bytes for the common case.

Memory fragmentation: what 40,000 nodes actually costs

A full 4 MiB MemTable (FlushThreshold = 4 × 1024 × 1024 bytes) holds roughly:

FlushThreshold / (avg_internal_key_size + avg_value_size)
= 4,194,304 / (24 + 80) = ~40,000 nodes  (assuming 16-byte user keys, 80-byte values)

Per-node heap cost breakdown (our fixed-array implementation):

  node struct header:       128 bytes  (2 slice headers × 16 B + 12 pointers × 8 B)
  internal key bytes:        24 bytes  (16 B user key + 8 B tag, avg)
  value bytes:               80 bytes  (avg)
  Go allocator metadata:    ~16 bytes  (runtime size class header per heap object)
  ────────────────────────────────────────────────────────────────────────────────
  Total per node:           ~248 bytes

For 40,000 nodes:
  Total heap:  40,000 × 248 ≈ 9.7 MiB

Notice: the MemTable’s size counter tracks only len(ikey) + len(value) per call to Add — it does not account for the 128-byte struct overhead or the 16-byte Go runtime metadata. ApproximateSize() therefore under-reports by roughly:

40,000 × (128 + 16) / (40,000 × (24 + 80)) = 144 / 104 ≈ 1.38×

The actual heap usage is about 38% higher than ApproximateSize() reports. This is acceptable — the flush threshold is a soft limit; briefly exceeding FlushThreshold by 38% before a flush is triggered does not cause correctness problems.

Pointer overhead breakdown:

Fixed-array waste per node:
  Expected node level: E[h] = 1/(1-p) = 1/0.75 ≈ 1.33 levels
  Average occupied pointer slots: 1.33
  Average wasted pointer slots:   12 - 1.33 = 10.67 wasted
  Waste per node:                 10.67 × 8 bytes = 85 bytes
  Total wasted for 40,000 nodes:  40,000 × 85 ≈ 3.3 MiB

Variable-length node (real LevelDB arena style):
  Allocates exactly h pointer slots per node
  Expected waste: 0
  Total pointer memory: 40,000 × 1.33 × 8 ≈ 426 KB

Our choice of [maxLevel]*node wastes ~3.3 MiB of zeroed pointer slots. The trade-off is zero dynamic allocation of the next array — the struct size is known at compile time, GC can trace it statically, and no arena allocator is needed.

Cache behaviour

The skip list has worse cache locality than a sorted array:

• Sorted array binary search: accesses cache-line-aligned contiguous memory; hardware prefetcher easily predicts the access pattern.
• Skip list search: pointer-chasing; each cur.next[i] dereference may cause a cache miss (~4 ns L1, ~12 ns L2, ~50 ns L3, ~100 ns main memory on modern hardware).

At n=40,000 nodes (a full 4 MiB MemTable), the skip list makes ~8–15 pointer dereferences per lookup. At 50 ns each, that is ~400–750 ns — still much faster than any disk I/O (NVMe: ~100 µs; HDD: ~10 ms). The cache miss cost is irrelevant compared to what follows (a WAL fdatasync), so the skip list’s simplicity wins over the sorted array’s cache friendliness.

Proving the cache miss cost claim with concrete numbers:

Typical cache miss latencies on a modern x86-64 system (Zen 4 / Ice Lake):

L1 hit:         ~4 ns   (4 KB per core)
L2 hit:         ~12 ns  (512 KB per core)
L3 hit:         ~30 ns  (shared, 8–32 MB)
DRAM:           ~80 ns  (64 ns CAS + controller latency)
NVMe SSD:       ~100 µs (PCIe 4.0 drive, queue depth 1)
HDD:            ~8 ms   (7200 RPM, average seek + rotation)

With 40,000 nodes spanning ~9.7 MiB of heap — exceeding most L3 caches — the working set of an active MemTable lives mostly in DRAM. Each pointer chase:

skip list node struct (128 B) = 2 cache lines (64 B each)
P(node in L3) for random access into 9.7 MiB ≈ 0%  (if L3 < 9.7 MiB)
→ each right-move hop costs ~80 ns (DRAM)
~8 right-move hops × 80 ns = 640 ns per lookup

But the WAL fdatasync following every write costs 100 µs (NVMe) or 5 ms (HDD). The 640 ns lookup cost is 0.6% of the NVMe fsync cost — statistical noise. This is the core argument for choosing the skip list over the sorted array despite worse cache behaviour.

Complexity summary

Proving the sorted-array O(n) insert claim

A sorted array stores keys contiguously. Inserting a new key at position k requires shifting every element from k onward by one slot:

// Conceptual sorted-array insert — Go pseudocode:
func insertSorted(arr [][]byte, newKey []byte) [][]byte {
    pos := sort.Search(len(arr), func(i int) bool {
        return bytes.Compare(arr[i], newKey) >= 0
    })                              // O(log n) comparisons — fast
    arr = append(arr, nil)          // grow slice by one
    copy(arr[pos+1:], arr[pos:])    // O(n-pos) pointer moves — slow
    arr[pos] = newKey
    return arr
}

The copy call is the problem. Consider a 4 MiB MemTable with 40,000 internal keys. Each key is a []byte header (16 bytes on 64-bit). The slice of headers occupies 40,000 × 16 = 640 KB.

Insertion position statistics for 40,000 random inserts:
  pos=0         (prepend):   40,000 moves = 640 KB moved
  pos=20,000    (middle):    20,000 moves = 320 KB moved
  pos=39,999    (append):         1 move  =  16 B  moved
  average:                   20,000 moves = 320 KB per insert

At memory bandwidth of ~50 GB/s (DDR5 single-channel read+write):

320 KB per insert / 50,000,000 KB/s ≈ 6.4 µs per insert
40,000 inserts × 6.4 µs / 2 (average fraction) ≈ 128 ms total

That is 128 ms just for pointer moves before a single fdatasync. The skip list does 2 pointer writes per level × ~1.33 average levels = ~3 writes total per insert, taking under 10 ns — zero bulk memory movement.

Proving O(log n) expected search cost: backwards analysis

Pugh’s original paper (1990) derives the expected search cost using backwards analysis: instead of asking “how many nodes does the search visit?”, ask “if I were walking backwards from the found node to the head, which nodes would I have visited?”

Define C(k, n) = expected number of comparisons to climb k levels in a skip list of n nodes. The recurrence is:

At any node at level i:
  - With probability p: this node also exists at level i+1 (it was promoted).
    → the backwards path goes up one level.  Cost: 1 + C(k-1, ???)
  - With probability (1-p): this node is only at level i.
    → the backwards path goes left one step.  Cost: 1 + C(k, n-1)

Recurrence:
  C(k, n) = (1-p) × (1 + C(k, n-1)) + p × (1 + C(k-1, ???))
           = 1 + (1-p)×C(k, n-1) + p×C(k-1, ???)

Solving this recurrence (see Pugh 1990, Theorem 4) yields:

Expected comparisons ≤ (log_{1/p}(n)) / p + 1/(1-p)

With p=0.25, n=40,000:
  log_4(40,000) ≈ 7.8
  bound ≤ 7.8 / 0.25 + 1/0.75
        ≤ 31.2 + 1.33
        ≈ 32.5 comparisons

This is an upper bound; the actual expected value is closer to log_{1/p}(n) ≈ 8 comparisons because many of those 32 “comparisons” are level-drops that reuse an already-loaded pointer without a new cache miss. In practice, only forward advances (right moves) cause pointer chasing — and the expected number of right moves is bounded by log_{1/p}(n) ≈ 8.

Making the skip list concurrent-safe

Our skip list is not safe for concurrent use — the comment in skiplist.go makes this explicit. The DB struct (lab 03) holds a sync.Mutex that serialises all access. Real engines allow concurrent lock-free reads.

The race condition is between a writer executing:

// Writer splice at level i:
n.next[i] = update[i].next[i]      // Step A: set n's forward pointer
update[i].next[i] = n              // Step B: publish n to readers

and a concurrent reader executing:

// Reader advance at level i:
if cur.next[i] != nil && Compare(cur.next[i].key, key) < 0 {
    cur = cur.next[i]              // loads update[i].next[i]
}

If the reader loads update[i].next[i] between Steps A and B, it sees the old successor (before n was inserted) — which is correct. If it loads after Step B, it sees n — also correct. The only unsafe scenario is if the CPU or compiler reorders Steps A and B so that Step B becomes visible to a reader before Step A completes.

Go’s memory model guarantees that a plain assignment is not an atomic store. A reader on another goroutine can observe a partial state where update[i].next[i] points to n but n.next[i] is still zero (nil).

The fix — what RocksDB’s InlineSkipList does — is to use atomic operations:

// Lock-free node struct (Go 1.19+):
type node struct {
    key   []byte
    value []byte
    next  [maxLevel]atomic.Pointer[node]
}

// Writer splice — sequential store order matters:
for i := 0; i < lvl; i++ {
    // Set n's forward pointer BEFORE publishing n as reachable:
    n.next[i].Store(update[i].next[i].Load())
    // Now publish atomically — any reader that sees n also sees n.next[i]:
    update[i].next[i].Store(n)
}

// Reader advance — load atomically:
cur = cur.next[i].Load()

The atomic.Pointer.Store issues a release fence; Load issues an acquire fence. This means any reader that loads n from update[i].next[i] is guaranteed to observe n.next[i] as set by Step A — the happens-before relationship is established.

This works for single-writer / many-readers (our MemTable pattern). For multiple concurrent writers, each writer’s splice would need a CAS loop:

// CAS splice — retry if another writer raced:
for {
    old := update[i].next[i].Load()
    n.next[i].Store(old)  // set n's forward pointer to current successor
    if update[i].next[i].CompareAndSwap(old, n) {
        break             // success: we atomically claimed the slot
    }
    // Another writer beat us — reload and retry
}

Our implementation skips all of this. The cost is a mutex acquisition on every read and write — but for a single-threaded write path (WAL serialises writes), the mutex overhead (~20 ns uncontended) is acceptable.

Concept: Internal Keys and MVCC

What is MVCC?

Multi-Version Concurrency Control is a concurrency strategy where the database never overwrites a value in place. Every write creates a new version of the key tagged with a monotonically increasing sequence number. Old versions coexist with new ones until a background process (compaction) removes them.

This solves two problems that plague simple key-value stores:

Problem 1 — Snapshot isolation: a long-running scan started at time T should see the data as it existed at T, not as modified by concurrent writers. With a single-version store, a writer can change a key between two reads in the same scan — breaking consistency.

Problem 2 — Delete vs. read race: if Delete("k") immediately removes the entry, a concurrent Get("k") that already passed the “key exists” check may find nothing. With MVCC, Delete inserts a tombstone — a special version that says “key k was deleted at seqNum N” — rather than removing any data.

Both problems disappear when a reader is assigned a fixed readSeq and ignores all versions with seqNum > readSeq.

Visualising multiple versions

Timeline of writes:
  seqNum=1:  Put("name", "Alice")
  seqNum=2:  Put("city", "London")
  seqNum=3:  Put("name", "Bob")     ← Alice still in MemTable
  seqNum=4:  Delete("city")         ← London still in MemTable

What lives in the MemTable (sorted by internal key):
  ┌────────────────────────────────────────────────────────────┐
  │ internal key                   │ value  │ visible at       │
  ├────────────────────────────────┼────────┼──────────────────┤
  │ ("city",  seq=4, typeDelete)   │ nil    │ readSeq ≥ 4      │
  │ ("city",  seq=2, typeValue)    │"London"│ readSeq 2..3     │
  │ ("name",  seq=3, typeValue)    │ "Bob"  │ readSeq ≥ 3      │
  │ ("name",  seq=1, typeValue)    │"Alice" │ readSeq 1..2     │
  └────────────────────────────────┴────────┴──────────────────┘

A reader at readSeq=2 calls Get("name", 2):

1. Builds lookup key ("name", seq=2, typeValue).
2. Skip list positions on the first internal key ≥ that lookup.
3. Due to descending seqNum sort: ("name", seq=3) sorts before ("name", seq=2). The first key ≥ lookup is ("name", seq=2) itself.
4. seq=2 ≤ readSeq=2 and type=typeValue → return “Alice”. ✓

The same reader calling Get("city", 2):

1. Lookup key: ("city", seq=2, typeValue).
2. First key ≥ lookup: ("city", seq=2) → seq=2 ≤ readSeq=2, typeValue → “London”. ✓

A reader at readSeq=4 calling Get("city", 4):

1. Lookup key: ("city", seq=4, typeValue).
2. First key ≥ lookup: ("city", seq=4, typeDelete) → type=typeDelete → return not found. ✓

No lock was held. No reader was blocked by a writer.

MVCC in other database systems

MVCC is not unique to LevelDB. Comparing implementations reveals what each design trades off.

PostgreSQL — heap tuple versioning

PostgreSQL stores every version of a row directly in the heap file (the table’s data file). Each tuple (row version) carries a 23-byte system header:

/* From PostgreSQL src/include/access/htup_details.h (simplified) */
typedef struct HeapTupleHeaderData {
    TransactionId t_xmin;  /* 4 B — txn ID that inserted this tuple */
    TransactionId t_xmax;  /* 4 B — txn ID that deleted/updated it (0=live) */
    CommandId     t_cid;   /* 4 B — command within the transaction */
    ItemPointerData t_ctid;/* 6 B — pointer to newer version (chain) */
    /* ... 5 more bytes of flags ... */
} HeapTupleHeaderData;   /* total: 23 bytes before the actual row data */

A reader with transaction ID T sees a tuple when:

• t_xmin committed AND t_xmin ≤ T (the insert is visible)
• t_xmax == 0 OR t_xmax > T OR t_xmax aborted (not yet deleted)

This is exactly our model with different names:

Key difference: PostgreSQL stores versions in an unsorted heap (rows are appended in transaction order, not key order). A B-tree index maps user keys to heap positions. Our skip list is both the storage and the index — no separate index structure needed. The cost: skip list scans must visit every version of a key; the PostgreSQL heap only stores one version per page slot and chains to older versions via t_ctid.

Oracle / MySQL InnoDB — undo log chain

Oracle and InnoDB take the opposite approach: the primary table stores only the latest version. Older versions live in a separate undo log:

Primary row:   key → current_value  (always the newest)
Undo log:      [txn_id, before_image, pointer_to_older_undo_entry]
               [txn_id, before_image, pointer_to_older_undo_entry]
               ...

A reader that needs an older version reconstructs it by reading the current row and applying undo entries in reverse until reaching its snapshot point.

Pros: the primary table never grows with old versions; reads that need only the latest version are maximally fast; the table file stays compact.

Cons: a reader with an old snapshot that needs a heavily-updated row may need to chase many undo log entries (“long undo chain”) — O(versions_since_snapshot) per row. This is why SELECT * on a hot table during a long-running OLAP query can be slow: every row’s history must be reconstructed.

LevelDB / RocksDB — inline append-only versions

Our design (and RocksDB’s): all versions coexist inline in the skip list and SSTables. No undo log. No separate version chain to follow.

Pros: lookup cost is O(log n) regardless of how many versions exist — the seek lands directly on the right version without chasing any pointers.

Cons: space grows with write traffic until compaction runs. A key updated 1000 times occupies 1000 entries in the skip list; in InnoDB it occupies 1 row

• 1000 undo log entries (same space, but the undo log is compressible and separate).

Internal key format: byte layout

User keys are never stored raw in the skip list or on disk. Every entry is stored under a composite internal key:

┌──────────────────────────────────┬─────────────────────────────────────────┐
│  userKey  (N bytes, arbitrary)   │  tag  (8 bytes, little-endian uint64)   │
│                                  │  = (seqNum << 8) | uint64(keyType)      │
└──────────────────────────────────┴─────────────────────────────────────────┘

The 8-byte tag encodes both the sequence number and the key type:

 bit 63                bit 8   bit 7         bit 0
 ┌──────────────────────────┬──────────────────┐
 │   seqNum  (56 bits)      │  keyType (8 bits) │
 └──────────────────────────┴──────────────────┘

keyType: 0 = TypeDelete (deletion tombstone)
         1 = TypeValue  (live value)

seqNum range: 0 .. 2^56-1 = 72,057,594,037,927,935

EncodeInternalKey from our key.go:

// EncodeInternalKey encodes userKey + seqNum + kt into a single byte slice.
func EncodeInternalKey(userKey []byte, seqNum uint64, kt KeyType) []byte {
    buf := make([]byte, len(userKey)+8)
    copy(buf, userKey)
    tag := (seqNum << 8) | uint64(kt)
    binary.LittleEndian.PutUint64(buf[len(userKey):], tag)
    return buf
}

Concrete example — EncodeInternalKey([]byte("name"), 3, TypeValue):

userKey = "name" = [0x6e 0x61 0x6d 0x65]

seqNum = 3, kt = TypeValue = 1
tag = (3 << 8) | 1 = 0x0000000000000301

Little-endian 8 bytes of 0x0000000000000301:
  byte 0: 0x01   (least significant)
  byte 1: 0x03
  byte 2: 0x00
  byte 3: 0x00
  byte 4: 0x00
  byte 5: 0x00
  byte 6: 0x00
  byte 7: 0x00   (most significant)

Internal key bytes:
  [0x6e, 0x61, 0x6d, 0x65,  0x01, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]
   n     a     m     e      ─────────── tag LE ──────────────────────────────

DecodeInternalKey reverses this:

// DecodeInternalKey splits an internal key back into its components.
func DecodeInternalKey(b []byte) (userKey []byte, seqNum uint64, kt KeyType) {
    tag := binary.LittleEndian.Uint64(b[len(b)-8:])
    return b[:len(b)-8], tag >> 8, KeyType(tag & 0xff)
}

tag >> 8 shifts out the keyType byte and recovers the seqNum. tag & 0xff masks the lower 8 bits and recovers the keyType.

Why the tag is little-endian

The tag is stored with binary.LittleEndian — the least significant byte first. This means the keyType byte (& 0xff) is at offset 0 of the tag field (the byte immediately after the user key).

Compare two internal keys for the same userKey at different seqNums:

("name", seq=1, TypeValue):
  bytes: ... 0x01 0x00 0x00 0x00 0x00 0x00 0x00 0x00
                                 ↑ seq=1 in bits 63..8

("name", seq=3, TypeValue):
  bytes: ... 0x01 0x03 0x00 0x00 0x00 0x00 0x00 0x00
                                 ↑ seq=3 in bits 63..8

A plain bytes.Compare on these two byte slices would sort seq=1 before seq=3 — wrong for MVCC (we want highest seqNum first). This is why we do not use bytes.Compare on internal keys directly.

CompareInternal: the comparator

// CompareInternal compares two internal keys.
// Primary sort: userKey ascending.
// Secondary sort: seqNum descending (higher seqNum sorts first).
func CompareInternal(a, b []byte) int {
    ukA, seqA, _ := DecodeInternalKey(a)
    ukB, seqB, _ := DecodeInternalKey(b)

    if c := bytes.Compare(ukA, ukB); c != 0 {
        return c          // different user keys: lexicographic order
    }
    // Same user key: invert seqNum so higher comes first.
    if seqA > seqB {
        return -1         // a has higher seqNum → a sorts before b
    }
    if seqA < seqB {
        return 1
    }
    return 0
}

The inversion (seqA > seqB → return -1) is the critical line. It makes the skip list treat a key with seqNum=10 as “smaller” (earlier in sorted order) than the same key with seqNum=5 — the opposite of the natural number ordering.

Why? Because all algorithms (skip list search, SSTable binary search, iterator) find the first element ≥ the lookup key. If higher seqNums sort first, a lookup key of (userKey, readSeq) lands directly on the most recent version ≤ readSeq. With ascending seqNum order, you would have to scan backward from the oldest version — which the forward-only skip list cannot do efficiently.

MemTable.Get: step-by-step

func (m *MemTable) Get(userKey []byte, readSeq uint64) ([]byte, bool) {
    // Step 1: build a lookup key with the caller's readSeq.
    // TypeValue is used here because TypeValue = 1 > TypeDelete = 0,
    // making the lookup key sort *before* a TypeDelete entry at the same
    // seqNum — ensuring the TypeDelete is found if it exists.
    lookupKey := EncodeInternalKey(userKey, readSeq, TypeValue)

    // Step 2: skip-list seek — find the rightmost node < lookupKey.
    cur := m.sl.head
    for i := m.sl.level - 1; i >= 0; i-- {
        for cur.next[i] != nil && CompareInternal(cur.next[i].key, lookupKey) < 0 {
            cur = cur.next[i]
        }
    }
    n := cur.next[0]    // first node >= lookupKey

    // Step 3: validate the result.
    if n == nil {
        return nil, false   // past the end of the skip list
    }
    uk, seq, kt := DecodeInternalKey(n.key)
    if string(uk) != string(userKey) || seq > readSeq {
        return nil, false   // moved to a different user key, or version too new
    }

    // Step 4: interpret keyType.
    if kt == TypeDelete {
        return nil, false   // tombstone: key was deleted at seq ≤ readSeq
    }
    return n.value, true
}

Worked example — Get("name", readSeq=2) against the MemTable containing:

Skip list order (internal keys):
  [0] ("city",  seq=4, TypeDelete)
  [1] ("city",  seq=2, TypeValue)   = "London"
  [2] ("name",  seq=3, TypeValue)   = "Bob"
  [3] ("name",  seq=1, TypeValue)   = "Alice"

1. Build lookupKey = ("name", seq=2, TypeValue).
2. CompareInternal sorts it between [1] and [2]:
   • ("city", seq=2) < ("name", seq=2) because “city” < “name”.
   • ("name", seq=3) < ("name", seq=2) because seq=3 > seq=2 (inverted).
   • ("name", seq=1) > ("name", seq=2) because seq=1 < seq=2 (inverted).
3. Skip list seek stops at [1] (last node < lookupKey), so n = [2] which is ("name", seq=3).
4. uk="name" == userKey, but seq=3 > readSeq=2 → skip; step 3 returns false.

Wait — this returns not found, but “Alice” exists at seq=1 ≤ readSeq=2. Is the implementation wrong?

No. The Get implementation finds the most recent version ≤ readSeq. There is no version at exactly seq=2, and the only candidate is seq=3 which is newer than readSeq=2. The implementation correctly skips it.

But then seq=1 is never reached — is Alice lost?

Let us re-examine. The skip list seek finds n = first node ≥ lookupKey. lookupKey is ("name", seq=2, TypeValue).

With the descending seqNum sort:

• ("name", seq=3) has internal comparison value “less than” ("name", seq=2) — because higher seqNum sorts first, seq=3 comes before seq=2 in the skip list.
• ("name", seq=1) has internal comparison value “greater than” ("name", seq=2).

So the sorted order in the skip list is:

... ("name", seq=3) → ("name", seq=2 would go here) → ("name", seq=1) ...

The seek returns n = first node ≥ ("name", seq=2) = ("name", seq=1).

Now step 3: seq=1 ≤ readSeq=2 and kt=TypeValue → return n.value = "Alice". ✓

The key insight: the lookup key itself does not exist in the list. The first node ≥ the lookup key is the closest version not newer than readSeq — exactly the MVCC semantics we need.

Iterator design: level-0 traversal

All compaction-path access (lab 06) and WAL-replay verification goes through the iterator. The full iterator API from skiplist.go:

// SlIter is a forward-only iterator over a SkipList.
type SlIter struct {
    cur *node  // currently pointed-at node; nil when exhausted
}

// SeekToFirst positions the iterator at the first real element.
// head.next[0] is the first node that carries an actual key.
func (it *SlIter) SeekToFirst(sl *SkipList) {
    it.cur = sl.head.next[0]  // skip the sentinel head (key == nil)
}

// Next advances one step along the level-0 linked list.
// Time: O(1) — just follow one pointer.
func (it *SlIter) Next() { it.cur = it.cur.next[0] }

// Valid reports whether the iterator is on a real node.
func (it *SlIter) Valid() bool { return it.cur != nil && it.cur.key != nil }

// Key and Value return the current internal key and value.
func (it *SlIter) Key() []byte   { return it.cur.key }
func (it *SlIter) Value() []byte { return it.cur.value }

The iterator only uses level 0. The higher levels exist solely for O(log n) point lookups. Level 0 is a complete linked list of every node in sorted order — the iterator simply walks it left to right.

Why the iterator sees MVCC versions in the right order for compaction:

Compaction needs to merge multiple MemTable/SSTable iterators and keep only the most recent version of each user key below the GC watermark. Because internal keys sort with seqNum descending, the iterator produces versions from newest to oldest for each user key:

Iterator output for MemTable containing:
  Put("apple", "green",  seq=2)
  Put("apple", "red",    seq=4)
  Put("cherry", "red",   seq=1)

Iteration sequence (level-0 order):
  Step 1: ("apple",  seq=4, TypeValue) → "red"      ← newest apple first
  Step 2: ("apple",  seq=2, TypeValue) → "green"
  Step 3: ("cherry", seq=1, TypeValue) → "red"

The compaction algorithm (lab 06) exploits this property:

PSEUDO-CODE — compaction iterator logic:
  prevUserKey = ""
  for each entry in merged iterator:
    uk, seq, kt = DecodeInternalKey(entry.Key)
    if uk == prevUserKey:
      // A newer version already emitted — drop this older version
      continue
    if kt == TypeDelete && seq < gcWatermark:
      // Tombstone below watermark — drop it (no reader can see the old value)
      prevUserKey = uk
      continue
    emit(entry)     // keep this entry in the new SSTable
    prevUserKey = uk

The descending seqNum sort guarantees that uk == prevUserKey on the second and subsequent versions — making “drop older versions” a trivial string comparison rather than a sorted set lookup.

Iterator and MemTable.NewIterator:

// NewIterator returns a forward iterator positioned at the first element.
func (m *MemTable) NewIterator() *SlIter {
    it := &SlIter{}
    it.SeekToFirst(m.sl)  // position at head.next[0]
    return it
}

The caller uses it as:

it := mem.NewIterator()
for ; it.Valid(); it.Next() {
    uk, seq, kt := DecodeInternalKey(it.Key())
    // process entry...
}

What the MemTable wraps

MemTable is a thin wrapper that translates between the public API (userKey []byte, seqNum, keyType) and the raw skip list’s internal key format:

// Add inserts a record into the MemTable.
func (m *MemTable) Add(seqNum uint64, kt KeyType, userKey, value []byte) {
    ikey := EncodeInternalKey(userKey, seqNum, kt)
    m.sl.Put(ikey, value)
    m.size += int64(len(ikey) + len(value))
}

The size field tracks approximate memory usage. When it exceeds FlushThreshold (4 MiB, added in lab 05), the MemTable is frozen and a fresh one takes its place.

Running the tests

The test file exercises four distinct behaviours:

// TestSeqNumMVCC confirms that two writes to the same key at different
// sequence numbers are independently readable.
func TestSeqNumMVCC(t *testing.T) {
    m := NewMemTable()
    m.Add(1, TypeValue, []byte("k"), []byte("v1"))
    m.Add(2, TypeValue, []byte("k"), []byte("v2"))

    v, ok := m.Get([]byte("k"), 1)  // readSeq=1 → v1
    if !ok || string(v) != "v1" {
        t.Errorf("readSeq=1: want v1 got %q ok=%v", v, ok)
    }
    v, ok = m.Get([]byte("k"), 2)   // readSeq=2 → v2
    if !ok || string(v) != "v2" {
        t.Errorf("readSeq=2: want v2 got %q ok=%v", v, ok)
    }
}

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

Expected:

=== RUN   TestBasicPutGet
--- PASS: TestBasicPutGet (0.00s)
=== RUN   TestDeleteReturnsNotFound
--- PASS: TestDeleteReturnsNotFound (0.00s)
=== RUN   TestSeqNumMVCC
--- PASS: TestSeqNumMVCC (0.00s)
=== RUN   TestIteratorSortedOrder
--- PASS: TestIteratorSortedOrder (0.00s)
PASS
ok      github.com/10xdev/leveldb/lab02

Running the demo

go run ./lab02/demo

The demo writes five entries and then:

1. Iterates the full MemTable — showing internal-key sorted order (userKey ASC, seqNum DESC within each user key).
2. Reads “apple” at three different readSeq values — demonstrating point-in-time snapshot reads without any locking.

Expected output:

add seq=1  banana     = yellow
add seq=2  apple      = green
add seq=3  cherry     = red
add seq=4  apple      = red
add seq=5  date       = brown

--- sorted iteration ---
  apple      seq=4    val=red
  apple      seq=2    val=green
  banana     seq=1    val=yellow
  cherry     seq=3    val=red
  date       seq=5    val=brown

--- MVCC get for 'apple' ---
  readSeq=2    apple = green
  readSeq=4    apple = red
  readSeq=10   apple = red

Notice:

• “apple” appears twice in the iteration — both versions are retained.
• seq=4 comes before seq=2 in the output — descending seqNum sort.
• readSeq=10 returns the latest value (“red”) because no version has seqNum > 4.

FoundationDB parallel

In FoundationDB, every committed transaction receives a globally ordered read version (a 64-bit integer). tr.SetReadVersion(v) is the exact equivalent of our readSeq parameter — it pins the snapshot to a specific point in history. tr.GetReadVersion() returns the current cluster version, equivalent to db.seqNum in our engine.

FDB’s storage servers maintain multiple committed versions of each key in their B-tree, cleaned up by a background GC process once the GC watermark (the oldest active read version across all clients) advances — directly equivalent to compaction dropping old MVCC versions in lab 06.

The key architectural difference: FDB’s version counter is maintained by the sequencer (a single process elected by Paxos that assigns versions to transactions across the entire cluster), ensuring total order across many concurrent clients. Our db.seqNum is a per-process counter with no network coordination — sufficient for a single-node engine.