Memtable and Skip List¶

Requirements¶

The memtable holds recent writes in sorted order until they are flushed to an SSTable. It must support:

• insert of internal keys, from one writer at a time (the commit goroutine — see Architecture Overview);
• seek to the first key ≥ a target, from many concurrent readers, without locks, while the writer keeps inserting;
• in-order iteration, for flushes and range scans;
• a cheap size estimate, to decide when to flush.

A balanced tree needs rebalancing, which moves nodes under concurrent readers. A skip list never moves a node once inserted: an insert only links a new node in, which can be made atomic per level. That is why LevelDB, RocksDB, Pebble, and Badger all use one. The data structure background is in Redis ZSET and Skip Lists.

Structure¶

Each node has a random height; level 0 links all nodes in order, and each higher level skips roughly 3 of every 4 nodes below it (probability 1/4 per extra level). A search starts at the top level of the head, moves right while the next key is smaller than the target, and drops down a level when it would overshoot: O(log n) expected steps.

const maxHeight = 12 // 4^12 ≈ 16 M: plenty for a memtable

type slNode struct {
    key  []byte
    val  []byte
    next [maxHeight]atomic.Pointer[slNode] // only the first `height` are used
}

type SkipList struct {
    head   slNode
    height atomic.Int32
    cmp    func(a, b []byte) int
    size   atomic.Int64 // approximate bytes, for the flush decision
}

func randomHeight() int {
    h := 1
    for h < maxHeight && rand.Uint32()%4 == 0 {
        h++
    }
    return h
}

Search¶

// findGE returns the first node with key >= k. If prev is non-nil,
// prev[i] receives the last node at level i whose key is < k.
func (s *SkipList) findGE(k []byte, prev *[maxHeight]*slNode) *slNode {
    x := &s.head
    level := int(s.height.Load()) - 1
    for {
        next := x.next[level].Load()
        if next != nil && s.cmp(next.key, k) < 0 {
            x = next // move right
            continue
        }
        if prev != nil {
            prev[level] = x
        }
        if level == 0 {
            return next
        }
        level-- // drop down
    }
}

Insert: publishing a node safely¶

// Insert requires that callers serialize writers. Keys are unique
// (internal keys always are, because every write has its own sequence).
func (s *SkipList) Insert(key, val []byte) {
    var prev [maxHeight]*slNode
    s.findGE(key, &prev)
    h := randomHeight()
    if cur := int(s.height.Load()); h > cur {
        for i := cur; i < h; i++ {
            prev[i] = &s.head
        }
        // A reader that sees the new height before the new links simply
        // finds nil at those levels of the head and drops down: harmless.
        s.height.Store(int32(h))
    }
    n := &slNode{key: key, val: val}
    for i := 0; i < h; i++ {
        n.next[i].Store(prev[i].next[i].Load()) // 1. link the node to its successor (not yet visible)
        prev[i].next[i].Store(n)                // 2. publish: make the predecessor point at it
    }
    s.size.Add(int64(len(key) + len(val) + 16*h + 32))
}

Why this is safe for readers running concurrently, in terms of the Go memory model:

1. The node's key, val, and its own next[i] are written before the atomic Store that makes prev[i] point at it.
2. A reader reaches the node only through an atomic Load of some next pointer. An atomic load that observes an atomic store creates a happens-before edge, so the reader is guaranteed to see the fully initialized key, value, and successor link.
3. Levels are published bottom-up. A reader may see the node at level 0 but not yet at level 2 — it is then just a node with a shorter tower for a moment, and searches remain correct because every level is a valid sorted sub-list at every instant.
4. Nodes are never removed or modified after publication, so a reader holding a pointer can never see it change. (Deletion is a tombstone entry, not an unlink.)

The writer itself needs no lock against readers. Writers must be serialized against each other — two concurrent inserts at the same position could both read the same prev[i].next[i] and one link would be lost. The engine guarantees that by having exactly one commit goroutine.

Go's sync/atomic operations are sequentially consistent: every atomic store is a release and every atomic load an acquire, and all of them appear in one global order. That is stronger than this algorithm strictly needs (release/acquire would do, and is slightly cheaper on ARM), but it means there are no orderings to choose and get wrong (Memory Model and Atomics).

Measured¶

1 M random 19-byte keys, Apple M1 Pro:

Readers scale almost linearly because they share nothing writable: no lock, no reference count, no cache line written by readers. A seek is ~20 dependent pointer loads (log₄ of 1 M ≈ 10 levels × ~2 steps), most of them cache misses into a 150 MB structure — which is why a single seek takes 2 µs: it is memory latency, exactly the shuffled linked list of CPU and Cache Efficiency.

The memtable on top¶

The memtable stores internal keys (user key + sequence + type) in the skip list and implements "newest visible version" lookups:

func (m *MemTable) Add(seq uint64, t ValueType, key, val []byte) {
    ik := makeIKey(make([]byte, 0, len(key)+8), key, seq, t)
    m.sl.Insert(ik, append([]byte(nil), val...)) // copy: the caller's batch buffer is reused
}

// Get returns the newest version of key visible at snapshot seq.
func (m *MemTable) Get(key []byte, seq uint64) (val []byte, deleted, found bool) {
    it := m.sl.Iter()
    it.Seek(makeIKey(nil, key, seq, TypeValue)) // TypeValue (1) sorts before TypeDeletion (0) at equal seq
    if !it.Valid() || !bytes.Equal(ukey(it.Key()), key) {
        return nil, false, false
    }
    if ValueType(trailer(it.Key())&0xff) == TypeDeletion {
        return nil, true, true // a tombstone shadows anything older
    }
    return it.Value(), false, true
}

The seek target (key, seq, TypeValue) is the largest trailer a visible entry can have; because trailers sort descending, the first entry at or after it is the newest version with sequence ≤ seq. Entries written after the snapshot (larger sequence) sort before the target and are skipped automatically.

What the real engines do differently¶

• Arena allocation. Every node here is a separate Go allocation (144 B, mostly the fixed 12-pointer tower). LevelDB and Pebble allocate nodes from a large arena with towers of exactly height pointers, using offsets instead of pointers. In Go this has a second benefit: a memtable that is one big []byte contains no pointers, so the GC never scans it — with 64 MB memtables, that is a lot of marking avoided (Garbage Collector). Pebble's arenaskl does exactly this.
• Wasted tower space. With p = 1/4, the average height is 1.33, but this node always reserves 12 pointer slots (96 bytes). Allocating towers of the actual height (a slice, or an arena) cuts node size by more than half.
• Concurrent inserts. RocksDB's InlineSkipList allows several concurrent writers using CAS on each level; most engines stay with one writer plus group commit.
• Size accounting in arena engines is exact (bytes used in the arena); here it is an estimate.

Common pitfall¶

Storing the caller's slices without copying. Batch.Iterate hands Add slices that point into the batch's buffer, and the commit goroutine reuses one merged batch buffer for every group. If Add inserted those slices directly — an easy "optimization" to make — the next group's bytes would overwrite the previous group's keys inside the skip list: keys would change after insertion, breaking the sort order, and lookups would fail intermittently, depending on timing and buffer capacity. Any structure that outlives a call must own its bytes: copy on insert (as Add does with makeIKey into a fresh slice and append([]byte(nil), val...)), or document precisely that the caller transfers ownership.

Review questions¶

1. Why can a skip list support lock-free readers during inserts while a balanced tree cannot easily do so?
2. Which happens-before edge guarantees that a reader sees a node's key after finding the node?
3. What can a reader observe while a node is linked at level 0 but not yet at level 2, and why is it harmless?
4. Why does Get seek to (key, seq, TypeValue), and how does that skip entries newer than the snapshot?
5. What would an arena-based memtable save in a Go engine besides allocation time?