Concurrent Skip List — Professional Level¶

Table of Contents¶

1. Introduction
2. Production Architecture
3. Arena Allocation in Depth
4. Building Pebble's arenaskl from Scratch
5. NUMA-Aware Concurrent Skip Lists
6. Cache-Line Layout, Padding, False Sharing
7. Snapshot Iterators with Epoch-Based Reclamation
8. Comparison with B+tree Memtables
9. Memtable Lifecycle: from Insert to Flush
10. The Role in LSM-Tree Databases
11. skipset Internals Deep Dive
12. Sharded and Hierarchical Designs
13. Persistent Skip Lists for MVCC
14. Operational Concerns: Monitoring, Capacity, Tuning
15. Latency Budget Engineering
16. Memory Reclamation Strategies
17. Concurrency Testing at Scale
18. Cutting Edge: Research Directions
19. Cheat Sheet
20. Self-Assessment
21. Summary

Introduction¶

The junior, middle, and senior files built up the concurrent skip list from sequential to lock-free, in increasing complexity. This file is different. It assumes you have mastered the algorithms and asks: how do you deploy them in production?

Production skip lists live inside larger systems — databases, caches, real-time analytics engines, network proxies. The algorithmic correctness is necessary but not sufficient. You need:

• Memory layouts that minimise GC pressure and cache misses. Arena allocation, embedded fields, padding.
• Scaling to many cores. NUMA awareness, sharding, contention avoidance.
• Snapshot semantics for transactional reads. Epoch-based reclamation, MVCC.
• Operational integration. Metrics, capacity planning, debugging at 3 AM.
• Lifecycle management. Memtable flush, compaction, integration with persistent storage.

This file walks through these concerns, with concrete code where useful and references to production systems (Pebble, RocksDB, skipset) where appropriate. It is the longest file in this folder, and intentionally so: production concerns are by nature numerous and detailed.

After reading this file you will:

• Understand arena allocation and be able to implement a basic arena skip list.
• Know what NUMA does to concurrent data structures and how to mitigate.
• Know how to integrate a skip list memtable into an LSM-tree storage engine.
• Be ready to evaluate production trade-offs (memory vs CPU, latency vs throughput).
• Know how to monitor, debug, and tune a concurrent skip list in production.
• Have read the source of arenaskl and skipset with comprehension.
• Be at the frontier of what is publicly known about concurrent ordered structures in Go.

This is the longest leg of the journey. Settle in.

Production Architecture¶

A typical production skip list sits inside a larger system. Here is the layout for a memtable in an LSM-tree database.

┌─────────────────────────────────────────────────────┐
│ Application (sql query / kv put)                    │
└─────────────────────────────────────────────────────┘
                       │
                       ▼
┌─────────────────────────────────────────────────────┐
│ Storage engine API                                  │
│ - Put(key, val) → writes to WAL, then to memtable   │
│ - Get(key) → reads memtable + cached SSTables       │
│ - Range(lo, hi) → merges memtable + SSTable scans   │
└─────────────────────────────────────────────────────┘
        │                              │
        ▼                              ▼
┌──────────────┐               ┌──────────────────┐
│ WAL (disk)   │               │ Memtable          │
│ append-only  │               │ (skip list)       │
│ for crash    │               │ in-memory         │
│ recovery     │               │ ordered           │
└──────────────┘               └──────────────────┘
                                       │
                                  flush│when full
                                       ▼
                               ┌──────────────────┐
                               │ SSTable (disk)   │
                               │ sorted on-disk   │
                               │ immutable        │
                               └──────────────────┘

In this architecture, the skip list: - Receives every write after WAL. - Serves every read by checking itself first, then layered SSTables. - Flushes its contents to a new SSTable when full. - Is replaced by a fresh empty skip list during flush; the old one is read-only during flush.

This memtable role is the canonical production use. Real systems may stack multiple skip lists (current memtable + immutable flush-pending memtables).

Concurrency demands¶

• Throughput: 100K–1M writes/sec sustained.
• Latency: p99 write < 100 µs (since each write is on the SQL critical path).
• Read latency: p50 < 1 µs (memtable lookup is one component of many).
• Memory: bounded by flush threshold (typically 64-256 MB per memtable).
• Iterators: must produce a consistent snapshot for transactional reads.

These demands are why production memtables are heavily optimised: arena allocation, lock-free, cache-aware, snapshot-capable. A pedagogical skip list does not meet these demands.

Arena Allocation in Depth¶

The single biggest production optimisation is arena allocation: instead of make(...) per node, allocate from a single contiguous buffer.

Why arena¶

• One allocation amortised across all nodes. Avoids per-node GC overhead.
• Cache locality. Sequentially allocated nodes are near each other in memory.
• Bulk deallocation. Drop the arena = drop the whole skip list. No incremental GC.
• Compact representation. 32-bit offsets instead of 64-bit pointers — halves pointer memory.

Basic arena¶

type Arena struct {
    buf []byte
    off atomic.Uint32 // current allocation offset
}

func NewArena(size int) *Arena {
    a := &Arena{buf: make([]byte, size)}
    a.off.Store(1) // skip offset 0 (sentinel = "nil")
    return a
}

func (a *Arena) Alloc(size, align uint32) uint32 {
    for {
        old := a.off.Load()
        aligned := (old + align - 1) &^ (align - 1)
        next := aligned + size
        if next > uint32(len(a.buf)) {
            return 0 // out of space
        }
        if a.off.CompareAndSwap(old, next) {
            return aligned
        }
    }
}

func (a *Arena) GetBytes(off uint32, size uint32) []byte {
    return a.buf[off : off+size]
}

Allocation is one CAS on the offset; ~10 ns uncontended.

Limitations¶

• No free. Once allocated, memory is held for the arena's lifetime. Workable for memtables (whole arena is flushed) but not for long-lived structures.
• Fragmentation. Variable-size keys/values waste alignment padding. Mitigate by sorting allocations by size at insert time.
• Growth. A fixed-size arena fails on overflow. Some implementations grow with a new buffer, but the pointer-to-offset abstraction must then handle multi-buffer indexing.

Production arena in Pebble¶

Pebble's arena: - 64MB default size, configurable. - Two-level structure: many small arenas pooled by size class. - Memory-mapped for crash isolation (in some configurations).

For a Go reimplementation, the basic arena above is sufficient for most cases.

Building Pebble's arenaskl from Scratch¶

Here is a working arena skip list in Go, modelled on Pebble's design. ~500 lines.

package arenaskl

import (
    "sync/atomic"
    "unsafe"
)

const (
    MaxLevel  = 20
    nodeAlign = 4
)

const (
    nodeSize         = uint32(unsafe.Sizeof(node{}))
    levelSize        = uint32(unsafe.Sizeof(uint32(0)))
)

type node struct {
    keyOff uint32
    keyLen uint16
    valOff uint32
    valLen uint16
    height uint16
    // levelOffs[i] = uint32 offset to next node at level i.
    // Stored inline after the struct, of length `height`.
}

func (n *node) nextOffPtr(level uint16) *atomic.Uint32 {
    base := unsafe.Pointer(n)
    addr := uintptr(base) + uintptr(nodeSize) + uintptr(level)*uintptr(levelSize)
    return (*atomic.Uint32)(unsafe.Pointer(addr))
}

type Skiplist struct {
    arena   *Arena
    head    uint32
    height  atomic.Uint32 // current top level
}

func NewSkiplist(arenaSize int) *Skiplist {
    a := NewArena(arenaSize)
    headOff := a.Alloc(nodeSize+uint32(MaxLevel)*levelSize, nodeAlign)
    s := &Skiplist{arena: a, head: headOff}
    s.height.Store(1)
    h := s.nodeAt(headOff)
    h.height = MaxLevel
    return s
}

func (s *Skiplist) nodeAt(off uint32) *node {
    return (*node)(unsafe.Pointer(&s.arena.buf[off]))
}

func (s *Skiplist) keyAt(n *node) []byte {
    return s.arena.GetBytes(n.keyOff, uint32(n.keyLen))
}

func (s *Skiplist) randomHeight() uint16 {
    // Per-goroutine fast PRNG should be plugged in here; using a simple
    // approach for clarity.
    h := uint16(1)
    for h < MaxLevel && fastRandU32()&1 == 0 {
        h++
    }
    return h
}

func (s *Skiplist) findGreaterOrEqual(key []byte, preds *[MaxLevel]uint32) bool {
    var x uint32 = s.head
    for lvl := int(s.height.Load()) - 1; lvl >= 0; lvl-- {
        n := s.nodeAt(x)
        for {
            nextOff := n.nextOffPtr(uint16(lvl)).Load()
            if nextOff == 0 {
                break
            }
            next := s.nodeAt(nextOff)
            nkey := s.keyAt(next)
            cmp := bytes.Compare(nkey, key)
            if cmp >= 0 {
                break
            }
            x = nextOff
            n = next
        }
        preds[lvl] = x
    }
    return false // simplified; real Pebble returns presence/version info
}

func (s *Skiplist) Add(key, val []byte) error {
    var preds [MaxLevel]uint32
    s.findGreaterOrEqual(key, &preds)

    height := s.randomHeight()
    // Bump global height if needed
    for {
        cur := s.height.Load()
        if uint32(height) <= cur {
            break
        }
        if s.height.CompareAndSwap(cur, uint32(height)) {
            break
        }
    }

    // Allocate space for new node
    sz := nodeSize + uint32(height)*levelSize
    off := s.arena.Alloc(sz, nodeAlign)
    if off == 0 {
        return ErrArenaFull
    }
    n := s.nodeAt(off)

    // Allocate key bytes
    keyOff := s.arena.Alloc(uint32(len(key)), 1)
    copy(s.arena.buf[keyOff:], key)
    n.keyOff = keyOff
    n.keyLen = uint16(len(key))

    // Allocate val bytes
    valOff := s.arena.Alloc(uint32(len(val)), 1)
    copy(s.arena.buf[valOff:], val)
    n.valOff = valOff
    n.valLen = uint16(len(val))

    n.height = height

    // Splice in via CAS at each level
    for lvl := uint16(0); lvl < height; lvl++ {
        for {
            predOff := preds[lvl]
            pred := s.nodeAt(predOff)
            nextOff := pred.nextOffPtr(lvl).Load()

            n.nextOffPtr(lvl).Store(nextOff)
            if pred.nextOffPtr(lvl).CompareAndSwap(nextOff, off) {
                break
            }
            // CAS failed; refresh preds[lvl]
            s.findGreaterOrEqual(key, &preds)
        }
    }
    return nil
}

This omits delete (Pebble's memtable rarely deletes; instead, it writes "tombstone" markers that override on read). It also omits proper marker-and-help logic (Pebble uses different mechanisms).

Even simplified, this code shows the structure: arena, offsets, CAS-based splice, fixed maximum height. The full Pebble implementation adds: - Marker pointer logic for true lock-free safety. - Multiple "key kinds" (set, delete, range-delete, merge). - Per-key timestamps for MVCC. - Iterator support with bidirectional traversal.

Reading the full source is genuinely educational. Plan a week.

NUMA-Aware Concurrent Skip Lists¶

On modern multi-socket servers, memory is not uniform. Accessing memory on a different socket than the requesting CPU takes 100-300 ns extra. For lock-free data structures on big iron, NUMA awareness can be a 50%+ win.

The NUMA problem¶

A typical 2-socket server has: - Two NUMA "nodes" (one per socket). - Each node has its own DRAM. - Cross-node access is 1.5-3× slower than local.

A single skip list shared across nodes has nodes scattered across both DRAMs. Every operation touches several cache lines; on average half of them are remote. The structure delivers half its theoretical throughput.

Mitigation 1 — Per-NUMA-node skip lists¶

Run K skip lists, one per NUMA node. Each goroutine pins to a node (via runtime.LockOSThread + pthread_setaffinity_np cgo) and uses the local skip list.

Cross-node queries become expensive or unsupported. Use only when access patterns are naturally node-local.

Mitigation 2 — NUMA-aware allocator¶

Allocate each skip list node on the NUMA node of the inserting goroutine. Go does not expose NUMA-local allocation; use cgo + numa_alloc_local().

The result: a single shared skip list, but each node lives on a specific NUMA node based on who inserted it. Operations still cross nodes, but locality is improved.

Mitigation 3 — Replicate read-only state¶

For very read-heavy workloads, keep a copy of the skip list per NUMA node. Writes go to all (slow); reads use the local copy (fast). The cost: K× memory, K× write cost.

Used by some HPC and analytics systems. Not common in general-purpose databases.

When to care¶

For the vast majority of Go applications, NUMA can be ignored. The Go runtime does some NUMA-aware scheduling but does not expose APIs for memory placement. NUMA awareness becomes worth the effort at: - 32+ core servers - 100M+ ops/sec throughput - Latency-critical workloads where remote memory misses show in p99

If those describe your service, the engineering cost of NUMA-aware skip lists is justified.

Cache-Line Layout, Padding, False Sharing¶

A modern CPU cache line is 64 bytes. Reads and writes happen at line granularity. Concurrent updates to variables in the same line false share: they compete for the line ownership even though they are logically independent.

Identifying false sharing¶

A canonical example:

type Counters struct {
    a atomic.Int64 // 8 bytes
    b atomic.Int64 // 8 bytes
}

a and b likely share a cache line. If goroutine 1 increments a and goroutine 2 increments b, they constantly invalidate each other's cache.

Fix: padding¶

type Counters struct {
    a atomic.Int64
    _ [56]byte // pad to 64
    b atomic.Int64
    _ [56]byte
}

Now each counter has its own cache line. No false sharing.

Skip list specifics¶

Hot fields in a skip list node: - next[0] — written by inserts/deletes that splice next to this node. - next[i] for i > 0 — written less often. - key, val — read-only after construction. - marked (if used) — written exactly once per node.

For the head sentinel, every operation touches next[i]. False sharing among the next[i] slots of head is real:

// Head sentinel layout:
type headNode struct {
    next [MaxLevel]atomic.Pointer[markedRef] // 16 × 8 = 128 bytes, two cache lines
}

Two cache lines, plus or minus alignment. Operations on level 0 vs level 1 share the first line; operations on level 5 vs level 10 share the second.

To eliminate:

type paddedRef struct {
    ref atomic.Pointer[markedRef]
    _   [56]byte
}

type headNode struct {
    next [MaxLevel]paddedRef // 16 × 64 = 1024 bytes
}

Costs 1 KB instead of 128 B. For the head sentinel only, this is fine.

For ordinary nodes, padding is overkill. The contention is on predecessors of currently-modifying threads, which are scattered across the structure.

False sharing between nodes¶

Two adjacent skip list nodes may share a cache line. If two threads update both nodes concurrently, false sharing is possible. Practically rare because allocations are usually aligned and node sizes are 40+ bytes.

In Pebble's arenaskl, the arena allocator aligns each node to 4 bytes. Adjacent nodes can share cache lines. Pebble accepts this trade-off because contention on adjacent nodes is rare in real workloads.

Profiling false sharing¶

Linux: perf stat -e cache-misses,cache-references go test -bench .. A high cache-miss rate compared to a single-threaded baseline suggests false sharing.

go test -benchmem and pprof are less direct; cache effects show as throughput drops at high contention.

Snapshot Iterators with Epoch-Based Reclamation¶

A snapshot iterator gives the appearance that iteration sees the structure exactly as it was at iteration start, even while concurrent updates continue. The standard implementation strategy in lock-free settings is epoch-based reclamation (EBR).

Why EBR¶

Without EBR, two challenges: 1. Visibility. What if a node is inserted after iteration starts? Should the iterator see it? 2. Reclamation. What if a node is deleted during iteration? When can it be freed?

In a GC'd language like Go, reclamation is partly handled by the GC: a node held by the iterator is not freed. But "held by the iterator" via a chain of pointers may keep many nodes alive, even after they are logically deleted.

EBR addresses both: - Each iterator captures an epoch at start. - Each modification is tagged with the current epoch. - Iterators only show modifications with epoch <= startEpoch.

Implementation sketch¶

type SkipList struct {
    // ... usual fields
    epoch atomic.Int64
}

type node struct {
    // ... usual fields
    insertEpoch atomic.Int64
    deleteEpoch atomic.Int64 // 0 if not deleted
}

type SnapshotIterator struct {
    sl         *SkipList
    startEpoch int64
    curr       *node
    lo, hi     int
}

func (s *SkipList) NewSnapshotIterator(lo, hi int) *SnapshotIterator {
    return &SnapshotIterator{
        sl:         s,
        startEpoch: s.epoch.Load(),
        curr:       s.head,
        lo:         lo,
        hi:         hi,
    }
}

func (it *SnapshotIterator) Next() (int, bool) {
    for {
        next := it.advance()
        if next == nil || next.key >= it.hi {
            return 0, false
        }
        // Check visibility based on epochs
        ins := next.insertEpoch.Load()
        del := next.deleteEpoch.Load()
        if ins > it.startEpoch {
            continue // inserted after snapshot
        }
        if del != 0 && del <= it.startEpoch {
            continue // deleted before/at snapshot
        }
        it.curr = next
        return next.key, true
    }
}

func (s *SkipList) Insert(key int) bool {
    // ... existing logic
    newNode.insertEpoch.Store(s.epoch.Add(1))
    return true
}

func (s *SkipList) Delete(key int) bool {
    // ... existing logic; after successful mark:
    victim.deleteEpoch.Store(s.epoch.Add(1))
    return true
}

The iterator sees a consistent snapshot at startEpoch. New inserts and deletes are invisible.

Reclamation¶

Deleted nodes can be physically unlinked but not freed while any active iterator has epoch <= deleteEpoch. In Go, the GC handles this: as long as the iterator holds the node in it.curr, it remains alive. The implicit reference chain keeps reachable nodes alive.

For long-running iterators in a write-heavy workload, this can bloat memory. The mitigation is to bound iterator lifetime — iterators must not "park" indefinitely.

Multi-version concurrency control (MVCC)¶

EBR generalises to MVCC: keep multiple versions of each value, tagged by epoch. Reads at epoch E see the version with the largest epoch ≤ E. Writes create new versions; old versions are reclaimed when no transaction reads them.

A skip list with MVCC values is the foundation of Pebble's transactional layer. The skip list orders by (key, descending epoch). A Get(key, snapshot_epoch) does an ordered scan from (key, snapshot_epoch) and returns the first version with epoch ≤ snapshot_epoch.

Comparison with B+tree Memtables¶

Some databases (WiredTiger, LMDB) use B+tree memtables instead of skip lists. Comparing in detail.

Concurrency¶

B+tree page splits are atomic at the page level but require coordination with parent pointers. Implementations like the Bw-tree (Microsoft Research, 2013) eliminate latches via delta-record encoding but are dramatically more complex than skip lists.

Cache behaviour¶

B+trees win on cache locality. For dense ranges, this is a 2-3× win.

Code complexity¶

Skip list (lock-free): ~400-3000 lines. B+tree (lock-free): ~5000-15000 lines.

The complexity gap is the single biggest reason skip lists dominate in modern in-memory databases. Engineering effort matters more than raw performance.

When B+tree wins¶

• Disk-backed storage (pages map to disk pages).
• Cache-friendly scans (analytical workloads).
• Single-writer regimes (lock-based B+trees are simpler).

When skip list wins¶

• In-memory (cache locality matters less when whole structure fits in cache).
• High concurrent writers (page splits serialise).
• Code simplicity (smaller engineering team).

Real systems often have both. Pebble uses a skip list memtable and B+tree-like SSTables on disk. Each structure plays to its strengths.

Memtable Lifecycle: from Insert to Flush¶

A production memtable goes through phases. Understanding the lifecycle is essential for designing one.

Phase 1 — Active¶

Accepts inserts. Serves reads and range scans. Bounded by size limit (typically 64-256 MB).

Phase 2 — Sealed (read-only)¶

When the active memtable hits its size limit: 1. A new active memtable is created. 2. The old memtable is "sealed": no more writes. 3. The sealed memtable is added to a list of "immutable memtables." 4. Reads check active + immutable + SSTables in order.

This swap must be atomic. Typical implementation: an atomic.Pointer[memtable] for the active, plus a slice (with mutex or RCU) for immutables.

Phase 3 — Flushing¶

A background goroutine reads the immutable memtable in sorted order and writes it as a new SSTable. The SSTable is a sorted file with index and bloom filter.

During flush, reads still use the immutable memtable.

Phase 4 — Discarded¶

After flush completes: 1. The new SSTable is added to the LSM levels. 2. The immutable memtable is removed from the list. 3. The memtable's arena is freed (just GC'd in Go; freed explicitly in C++).

The whole arena drops at once — no incremental reclamation needed. This is why arena allocation is such a good fit for memtables.

Concurrency in lifecycle¶

• Writers acquire the active memtable via atomic.Pointer.Load(). No locking.
• Readers iterate over (active, immutable[0], immutable[1], ..., sstable[0], ...) in order. No locking on the structure; brief lock on the immutable slice.
• Lifecycle transitions (seal, flush, discard) are coordinated by a single goroutine.

The skip list itself does not know about the lifecycle. It only sees Insert, Get, Range. The orchestration lives one layer up.

Failure handling¶

• WAL failure: refuse the write.
• Memtable full + active not sealed yet: writer waits (this is a key tuning parameter).
• Flush failure: retry indefinitely; the storage engine cannot make progress without flushing.

The Role in LSM-Tree Databases¶

LSM (Log-Structured Merge) trees use skip list memtables. Knowing the broader system clarifies the skip list's role.

LSM basics¶

• Writes append to a WAL + insert into the memtable.
• When memtable fills, flush to SSTable (sorted on disk).
• Periodic compaction merges SSTables into larger ones, eliminating duplicates.
• Reads check memtable, then SSTables newest-to-oldest.

Why LSM¶

• Writes are sequential (WAL + memtable inserts) — fast on spinning disks.
• Reads may need to check many SSTables; bloom filters and tiered storage help.

Where the skip list fits¶

The memtable is the single in-memory tier of the LSM. Its responsibilities: - Accept writes at line speed. - Serve point lookups for keys recently written. - Serve range scans across recently written keys. - Emit sorted output during flush.

The skip list is chosen because all four operations are O(log n) and concurrent-friendly.

Implementations using skip list memtables¶

• LevelDB (Google, 2011): the seminal LSM design. Single-threaded skip list memtable (since LevelDB is single-writer).
• RocksDB (Facebook, 2013): adopted concurrent skip list memtable from LevelDB.
• Pebble (CockroachDB, 2018): Go reimplementation; lock-free arena skip list.
• BadgerDB (Dgraph, 2017): Go LSM with skip list memtable.
• InfluxDB (TSDB, 2016): time-series store with skip list buffer.

The pattern is dominant in this space. If you build a database in Go and need an LSM memtable, you will use a skip list.

skipset Internals Deep Dive¶

Let us walk through github.com/zhangyunhao116/skipset in detail. The file intset.go (~300 lines) is the smallest complete implementation.

Type structure¶

type IntSet struct {
    header       *intNode
    length       int64
    highestLevel int64
}

type intNode struct {
    value       int
    next        []atomicPointer
    mu          sync.Mutex
    flags       uint32 // atomic; bits for marked, fullyLinked
    level       uint32
}

type atomicPointer = atomic.Pointer[intNode]

Note: per-node sync.Mutex (this is lazy lock-based for writes), flags atomic for marked/fullyLinked (this is HLLS).

Add¶

Lazy-style: find, lock predecessors, validate, splice, set fullyLinked.

func (s *IntSet) Add(value int) bool {
    level := s.randomLevel()
    var preds, succs [maxLevel]*intNode
    for {
        lFound := s.findNodeAdd(value, &preds, &succs)
        if lFound != -1 {
            // Key found; check marked and fullyLinked
            nodeFound := succs[lFound]
            if !nodeFound.flags.MGet(marked) {
                for !nodeFound.flags.MGet(fullyLinked) { /* spin */ }
                return false
            }
            continue
        }
        // Try to insert
        var highestLocked = -1
        valid := true
        var prevPred *intNode
        for layer := 0; valid && layer < level; layer++ {
            pred := preds[layer]
            succ := succs[layer]
            if pred != prevPred {
                pred.mu.Lock()
                highestLocked = layer
                prevPred = pred
            }
            valid = !pred.flags.MGet(marked) && pred.loadNext(layer) == succ &&
                (succ == nil || !succ.flags.MGet(marked))
        }
        if !valid {
            unlockInt(preds, highestLocked)
            continue
        }
        nn := newIntNode(value, level)
        for layer := 0; layer < level; layer++ {
            nn.storeNext(layer, succs[layer])
            preds[layer].atomicStoreNext(layer, nn)
        }
        nn.flags.SetTrue(fullyLinked)
        unlockInt(preds, highestLocked)
        atomic.AddInt64(&s.length, 1)
        return true
    }
}

Contains¶

Wait-free.

func (s *IntSet) Contains(value int) bool {
    x := s.header
    nlevel := s.loadHighestLevel()
    for i := nlevel - 1; i >= 0; i-- {
        nex := x.atomicLoadNext(int(i))
        for nex != nil && nex.value < value {
            x = nex
            nex = x.atomicLoadNext(int(i))
        }
        if nex != nil && nex.value == value {
            return nex.flags.MGet(fullyLinked|marked) == fullyLinked
        }
    }
    return false
}

A single bitmask check at the end: flags.MGet(fullyLinked|marked) == fullyLinked is true exactly when fullyLinked is true and marked is false. Elegant.

Remove¶

Two-phase delete, lazy-style.

func (s *IntSet) Remove(value int) bool {
    var (
        nodeToDelete *intNode
        isMarked     bool
        topLayer     int = -1
        preds, succs [maxLevel]*intNode
    )
    for {
        lFound := s.findNodeRemove(value, &preds, &succs)
        if isMarked ||
            (lFound != -1 && (succs[lFound].flags.MGet(fullyLinked|marked) == fullyLinked) &&
                succs[lFound].level-1 == uint32(lFound)) {
            if !isMarked {
                nodeToDelete = succs[lFound]
                topLayer = lFound
                nodeToDelete.mu.Lock()
                if nodeToDelete.flags.MGet(marked) {
                    nodeToDelete.mu.Unlock()
                    return false
                }
                nodeToDelete.flags.SetTrue(marked)
                isMarked = true
            }
            // ... lock predecessors, validate, unlink
            // (omitted; same pattern as Add)
            return true
        }
        return false
    }
}

Random level¶

func (s *IntSet) randomLevel() int {
    rand := fastrand.Uint32()
    bit := bits.TrailingZeros32(rand) + 1
    if bit > maxLevel {
        bit = maxLevel
    }
    return bit
}

fastrand.Uint32() is a per-goroutine PCG, not the mutex-protected math/rand. One PRNG call yields ~32 random bits, one of which is the level.

bits.TrailingZeros32 counts the consecutive 0 bits, equivalent to 1 + log2(rand) with probability 1/2 each. Computes height in O(1) without a coin-flip loop.

Flags¶

const (
    fullyLinked uint32 = 1 << 0
    marked      uint32 = 1 << 1
)

type bitflag uint32

func (b *bitflag) MGet(bits uint32) uint32 {
    return atomic.LoadUint32((*uint32)(b)) & bits
}

func (b *bitflag) SetTrue(bits uint32) {
    for {
        old := atomic.LoadUint32((*uint32)(b))
        if old&bits == bits {
            return
        }
        if atomic.CompareAndSwapUint32((*uint32)(b), old, old|bits) {
            return
        }
    }
}

Packing fullyLinked and marked into a single uint32 saves 4 bytes per node and lets Contains check both in one atomic load.

Optional array for next pointers¶

type optionalArray struct {
    base unsafe.Pointer
    extra [_optionalArraySize]atomicPointer
}

For nodes with small height, the next pointers fit inline (cache-friendly). For tall nodes, base points to a separately-allocated array. Saves an allocation in the common case.

These tricks together make skipset ~30% faster than a pure pedagogical lock-based implementation, while remaining ~600 readable lines.

Studying skipset after the senior file is a satisfying experience: you see every concept applied in production code.

Sharded and Hierarchical Designs¶

For workloads exceeding single-structure capacity, sharding is the standard answer.

Hash-based sharding¶

type Sharded[K cmp.Ordered, V any] struct {
    shards    [N]*SkipMap[K, V]
    hashFunc  func(K) uint64
}

func (s *Sharded[K, V]) Get(k K) (V, bool) {
    return s.shards[s.hashFunc(k)%N].Get(k)
}

Throughput scales near-linearly with N because shards do not contend.

Lost: cross-shard range queries. Range(lo, hi) would require merging N shards, with no efficient way to advance globally.

Use cases: per-user caches, per-source logging buffers, hash-partitioned key-value stores.

Range-based sharding¶

Partition keyspace into ranges: [a, m) -> shard 0, [m, z) -> shard 1, etc.

type RangeSharded struct {
    shards     []*SkipList
    boundaries []int // sorted
}

func (s *RangeSharded) shardFor(k int) int {
    return sort.SearchInts(s.boundaries, k)
}

Cross-shard range queries are tractable: iterate over relevant shards in order.

The trade-off: boundary placement. Uneven keys lead to hotspots. Periodic rebalancing helps.

Used by distributed databases for replica placement (each shard is a range owned by a set of nodes).

Hierarchical (skip list of skip lists)¶

A coarse skip list of "buckets," where each bucket is itself a skip list. The top level handles range navigation; the bottom level handles fine-grained inserts.

type Hierarchical struct {
    top *SkipList // keys are bucket boundaries
    // each bucket lookup yields a sub-skip-list
}

Used in very-large-scale systems (Cassandra-like clustering). Rare in single-process Go.

Trade-offs¶

Default to a single skip list. Shard only when measured contention demands it.

Persistent Skip Lists for MVCC¶

A persistent (functional) skip list keeps all old versions. Writes produce new versions; old ones remain readable.

Why persistent¶

• MVCC: each transaction reads its consistent snapshot.
• Time-travel queries: read the database as it was at a past timestamp.
• Snapshot isolation: cheap snapshot creation.

Implementation strategies¶

Strategy 1 — Path copying¶

Each insert copies the path from root (head) to the inserted node, sharing the rest of the structure. Old versions retain their own paths.

Costs O(log n) memory per insert. Tractable for moderate write rates.

Strategy 2 — Versioned nodes¶

Each node carries a version. Reads use the version <= snapshot epoch. Writes create new versions of changed nodes; old versions remain.

type vnode struct {
    key       int
    versions  []version // sorted by epoch
}

type version struct {
    epoch int64
    val   any
    next  []*vnode // version-specific next pointers
}

Memory grows over time; reclamation requires tracking which epochs are still "active."

Strategy 3 — Append-only log¶

Treat the skip list as a persistent log; each operation is an entry. Reads at epoch E replay entries up to E.

Slow but simple. Useful for audit logs, not main data path.

In Pebble¶

Pebble uses MVCC at the key level, not at the structure level. Keys are stored as (user_key, sequence_number). The skip list itself is not persistent; old versions are stored as separate entries in the skip list.

This avoids the complexity of persistent skip lists at the cost of more keys (and thus more memory).

Operational Concerns: Monitoring, Capacity, Tuning¶

Production skip lists need operational support. The minimum:

Metrics¶

• Size. Len() exposed as a gauge.
• Memory. Arena usage (current bytes / max bytes).
• Throughput. Inserts/sec, deletes/sec, gets/sec.
• Latency. Histogram of operation latency.
• CAS failures. Counter, normalised by total operations.
• Flush rate (for memtables). How often the memtable fills and rolls over.
• Memtable count. Active + immutable.

Each metric guides a decision: - Size + memory → capacity planning. - Throughput → scaling decisions. - Latency → SLO compliance. - CAS failures → contention diagnostics. - Flush rate → memtable size tuning.

Capacity planning¶

For an LSM-tree memtable: - Throughput: P writes/sec, each with average size B bytes. - Memtable size: S MB. - Flush time: T seconds. - Sustained write capacity: S / (P × B) seconds before flush; must be >> T.

Tune S to balance memory and flush frequency. Higher S = less frequent flush = more memory; lower S = more frequent flush = more I/O.

Tuning checklist¶

• MaxLevel = ceil(log2(expected_max_size)). Default 16 covers up to 64K keys; 32 covers 4B.
• p = 1/2 (default). Tune to 1/4 only with measurement.
• Per-goroutine PRNG. Avoid global RNG mutex.
• Arena size: balance allocation overhead vs flush frequency.
• Padding head sentinel: only if benchmarks show false sharing.

Debugging¶

A production skip list misbehaves. The diagnostic order:

1. Check metrics: any anomaly in size, latency, CAS failures?
2. Check logs: any errors? (rare for skip list itself)
3. Run profile: CPU + memory + block. Look for unexpected hot paths.
4. Reproduce in test: synthetic workload matching production access pattern.
5. Step through with delve if a hypothesis emerges.

90% of issues are mismatches between expected and actual workload, not algorithmic bugs. Tuning fixes most; rewriting is rarely needed.

Latency Budget Engineering¶

A senior engineer thinks in terms of latency budgets. For a SQL query that takes 1 ms p99: - Network: 200 µs - Parsing: 50 µs - Planning: 100 µs - Execution: 600 µs - Result serialisation: 50 µs

If execution includes 10 memtable lookups at 1 µs each, that is 10 µs — 1.7% of the execution budget. Plenty of headroom.

If execution includes 1000 memtable lookups (full-table scan), that is 1 ms — the entire query budget. The skip list is no longer "fast enough"; either reduce scan count, paginate, or cache.

Budgeting for skip list operations¶

Typical Go numbers (8-core M3, 1M-key skip list):

For applications: - API serving 10 requests/sec: skip list cost is negligible. - API serving 10K requests/sec, each with 5 lookups: 50K ops/sec on the skip list, ~50 ms of CPU per second. Workable. - API serving 100K requests/sec: half a million ops/sec on the skip list, 500 ms of CPU per second. Profile.

Bottom line: at low scale, ignore the skip list cost. At high scale, profile and optimise the hot path. At extreme scale, consider sharding.

Memory Reclamation Strategies¶

Beyond Go's GC, there are advanced reclamation strategies worth knowing.

GC¶

Default in Go. Reclaims any unreachable memory. Cost: GC pauses (typically 1-5 ms on modern hardware), CPU overhead during marking (~5% of CPU under typical load).

Adequate for most use cases. Pebble's arenaskl adds the arena specifically to reduce GC pressure on the skip list's allocations.

Manual arena¶

Allocate from a pre-sized buffer. No per-node free. Whole buffer is dropped at lifecycle end.

Used in memtables. Trades flexibility for performance.

Hazard pointers¶

Each thread publishes the pointers it currently reads. Deleters scan all hazard pointers before freeing.

Required in C++. Not used in Go (GC handles it).

Epoch-based reclamation (EBR)¶

Threads enter epochs. Deletes are deferred until all threads have left the deletion epoch.

Used in Rust (crossbeam-epoch). In Go, the GC achieves the same effect with no library code.

Quiescent-state-based reclamation (QSBR)¶

Variant of EBR; threads explicitly declare "quiescent" points where they hold no shared references. Lower overhead than full EBR.

Used in the Linux kernel (RCU). Inapplicable to Go.

Reference counting¶

Per-node atomic counter; free at zero. Cost: one CAS per pointer hop.

Used in some C++ libraries (folly). Heavy compared to GC.

For Go applications, the choice is usually between "GC" and "arena." Hazard pointers and EBR are unnecessary; the GC handles their concerns.

Concurrency Testing at Scale¶

Production skip lists need testing beyond what was covered in senior.md.

Continuous fuzzing¶

Run go test -fuzz on a CI server for hours per day. Catches edge cases that static tests miss.

Adversarial workloads¶

Specifically test: - All-same-key workload (every op targets the same key). - Hot-spot workload (90% of ops target 1% of keys). - Burst workload (sudden 100× spike in throughput). - Long-tail workload (occasional very-slow operations).

These break naive implementations. Production code must survive.

Replay-based testing¶

Capture a production trace (anonymised). Replay against the skip list. Compare metrics. Useful for regression testing.

Chaos testing¶

Randomly inject: - Goroutine pauses (simulate preemption). - Slow consumers (simulate slow downstream). - GC pauses (force a runtime.GC()).

Confirm the skip list remains correct and bounded.

Performance regression CI¶

Automated benchmarks on every PR. Block merges that regress p99 by >10%.

This requires a stable benchmark environment (consistent hardware, no other processes). Some teams use dedicated benchmark servers; others use cloud instances with reproducible configurations.

Cutting Edge: Research Directions¶

Active areas of research in concurrent ordered structures:

Persistent-memory-aware structures¶

Intel Optane and similar persistent memory technologies need rebuilt data structures that survive crashes. The Pinit skip list (Lersch et al., 2019) is one design. Implementations are in C++; Go versions are nascent.

Hardware-transactional-memory variants¶

Modern CPUs (Intel TSX, IBM POWER) support hardware transactions. Skip lists can be built with HTM: read multiple memory locations atomically. Faster than CAS for short transactions but limited transaction size.

Go does not expose HTM. Likely never will. Research curiosity for Go developers.

Wait-free variants¶

Wait-free skip lists exist (Fomitchev-Ruppert 2004 variant). Slower than lock-free in average case, faster in worst case. Used in safety-critical systems.

Cache-conscious layouts¶

Beyond arenaskl, research explores even more cache-friendly layouts: nodes packed into 16-byte cache-line chunks, prefetch-aware traversals. Diminishing returns; most workloads are not cache-bound.

Concurrent ordered tries¶

For string keys, concurrent radix tries (ROART, ConcurrentART) can outperform skip lists. Active research.

GPU skip lists¶

Specialised for massively-parallel workloads. CUDA / OpenCL implementations exist; performance is workload-dependent.

For Go specifically, the cutting edge is more about integration (with WAL, with replication, with cloud storage) than about new algorithms.

Cheat Sheet¶

Production-grade skip list checklist:

  [ ] Arena allocation (or pooled allocator)
  [ ] Lock-free or lazy lock-based (NOT coarse-locked)
  [ ] Per-goroutine fast PRNG (NOT math/rand global)
  [ ] Embedded next array (NOT slice)
  [ ] Head-sentinel cache-line padding
  [ ] Type-specialised or generic with proper bounds
  [ ] Snapshot iterator with epoch reclamation (if MVCC)
  [ ] Linearisability-verified (property tests + porcupine)
  [ ] Race-detector clean (test -race -count=100)
  [ ] Long-soak tested (24+ hours)
  [ ] Metrics exposed (size, latency, CAS rate)
  [ ] Capacity planned (memory bounds documented)

When to roll your own:                  Almost never.
When to use skipset:                    95% of cases.
When to use arenaskl:                   Building an LSM-tree database.
When to use a sorted slice + RWMutex:   Tiny data, infrequent writes.

Production reference implementations:
  github.com/zhangyunhao116/skipset       — general-purpose
  github.com/cockroachdb/pebble/internal/arenaskl  — memtable

Bottleneck order under high load:
  1. GC pressure       → fix with arena
  2. Lock contention   → fix with lock-free
  3. False sharing     → fix with padding
  4. Cache misses      → fix with layout
  5. NUMA              → fix with per-node sharding

Self-Assessment¶

• I can implement an arena-allocated skip list in Go.
• I understand the difference between GC-based, hazard-pointer-based, and epoch-based reclamation.
• I can describe how a skip list integrates into an LSM-tree memtable.
• I have read Pebble's arenaskl source and understand each component.
• I have read skipset's source and recognise lazy lock-based + atomic publication.
• I can design a sharded skip list and explain the trade-offs.
• I can implement a snapshot iterator with epoch-based reclamation.
• I can explain NUMA effects and propose mitigations.
• I understand cache-line padding and false sharing in the context of skip lists.
• I have a metrics and capacity plan for a production deployment.
• I can debug a misbehaving skip list in production using profiles and metrics.

If most of these are checked, you have reached the top of this folder.

Summary¶

Production skip lists are a sophisticated topic. The algorithms are only a fraction of the work; the rest is allocator design, NUMA awareness, lifecycle management, monitoring, and integration with surrounding systems.

The takeaways:

1. Use skipset for general purposes. It is the right answer for 95% of Go applications that need a concurrent ordered set/map.

2. Use arenaskl (or build similar) for database memtables. Arena allocation is the single biggest production optimisation.

3. Lock-free is not always better. skipset chose lazy lock-based with atomic publication for simplicity. Match the design to the workload.

4. Cache and NUMA matter at high scale. Below 32 cores and 10 M ops/sec, ignore them. Above, profile and optimise.

5. Snapshot iterators and MVCC are advanced topics. For most applications, weakly-consistent iteration is fine.

6. Operational integration matters more than algorithmic perfection. Metrics, capacity, debugging access are essential.

You have completed the longest chapter in this folder. Beyond this is research, not engineering practice. If you want to push further:

• Read the recent literature on persistent-memory data structures.
• Contribute to skipset or arenaskl.
• Build a domain-specific skip list variant for a real production system.

The concurrent skip list is, after 35 years of research, a mature topic. The journey from "what is a skip list" to "ship a NUMA-aware, snapshot-capable, arena-allocated, lock-free implementation in production" is one of the longest in computer science applied to a single data structure.

You have made the journey. Welcome to the top.

Appendix — Final Engineering Wisdom¶

After thousands of words and code samples, what remains? A few wisdoms:

Wisdom 1. The simplest concurrent data structure that meets your performance budget is the right one. Lock-free is a tool, not a goal.

Wisdom 2. Use the best library available (skipset, arenaskl). Hand-rolling concurrent data structures is among the most error-prone activities in software engineering.

Wisdom 3. Measure before optimising. Always. The hot path is rarely where you think.

Wisdom 4. Test extensively. Concurrent bugs hide for months and surface at 3 AM during a outage. Property tests, race detector, porcupine, long soaks — all of them, every time.

Wisdom 5. Document the concurrency contract. Future you (and your colleagues) will thank you. "Linearisable for Insert/Delete/Contains; weakly-consistent for Range" is a sentence worth writing.

Wisdom 6. Build with operational concerns in mind from day one. Metrics, capacity, debugging — these are not afterthoughts.

Wisdom 7. Production code is 90% boring. The interesting algorithms are 10%. Spend your effort proportionally.

Wisdom 8. Keep learning. The concurrent data structures field continues to evolve; new tricks emerge every few years.

That is the end of the formal material. Beyond this is your own practice and your own production experience. Good luck building.

— end of professional level —

Appendix — A Complete Production Memtable Design¶

To pull together everything, let us walk through a complete design for a production-grade memtable in Go. This is the kind of system you might see in an embedded database.

Goals¶

• Throughput: 1M writes/sec sustained on 8-core hardware.
• Latency: p99 insert < 50 µs.
• Memory: bounded by configurable size (64MB-256MB).
• Crash safety: paired with WAL.
• Iterators: snapshot-consistent for transactional reads.
• Operational: metrics, debuggable, capacity-planning friendly.

Component breakdown¶

┌───────────────────────────────────────┐
│ MemtableManager                       │
│ - manages active + immutable          │
│ - coordinates flush                   │
│ - exposes Get/Range across all        │
└───────────────────────────────────────┘
        ↓                ↓
┌─────────────────┐   ┌──────────────────┐
│ Active Memtable  │  │ Immutable List    │
│ - skip list      │  │ - frozen memtables│
│ - arena          │  │ - awaiting flush  │
└─────────────────┘   └──────────────────┘
        ↑                       ↓
        │ writes               │ flush goroutine
        │                       │
┌─────────────────────────────────────┐
│ WAL (append-only file)               │
│ - synced before memtable write       │
└─────────────────────────────────────┘

Code skeleton¶

package memtable

import (
    "sync"
    "sync/atomic"
)

type Manager struct {
    active     atomic.Pointer[Memtable]
    immutable  []*Memtable
    immutableMu sync.RWMutex

    maxSize   int
    flushChan chan *Memtable
    wal       *WAL
}

type Memtable struct {
    sl       *Skiplist
    arena    *Arena
    sequence atomic.Uint64
    size     atomic.Int64
}

func (m *Manager) Put(key, val []byte) error {
    seq := m.active.Load().sequence.Add(1)
    if err := m.wal.Write(key, val, seq); err != nil {
        return err
    }
    active := m.active.Load()
    if active.size.Load() > int64(m.maxSize) {
        m.rotate()
        active = m.active.Load()
    }
    return active.sl.Add(key, val, seq)
}

func (m *Manager) Get(key []byte) ([]byte, bool) {
    if val, ok := m.active.Load().sl.Get(key); ok {
        return val, true
    }
    m.immutableMu.RLock()
    defer m.immutableMu.RUnlock()
    for i := len(m.immutable) - 1; i >= 0; i-- {
        if val, ok := m.immutable[i].sl.Get(key); ok {
            return val, true
        }
    }
    return nil, false
}

func (m *Manager) Range(lo, hi []byte, f func([]byte, []byte) bool) {
    // Build iterator chain: active + immutables, merged in order.
    // Each iterator is a snapshot at its memtable's current sequence.
    iters := []Iterator{m.active.Load().sl.NewIterator(lo, hi)}
    m.immutableMu.RLock()
    for _, imm := range m.immutable {
        iters = append(iters, imm.sl.NewIterator(lo, hi))
    }
    m.immutableMu.RUnlock()
    // Merge-sort across iterators
    merged := NewMergeIterator(iters)
    for merged.Valid() {
        if !f(merged.Key(), merged.Value()) {
            return
        }
        merged.Next()
    }
}

func (m *Manager) rotate() {
    m.immutableMu.Lock()
    defer m.immutableMu.Unlock()
    old := m.active.Load()
    m.immutable = append(m.immutable, old)
    m.active.Store(newMemtable(m.maxSize))
    select {
    case m.flushChan <- old:
    default:
        // flush is busy; ok, will catch up
    }
}

func (m *Manager) FlushLoop() {
    for mt := range m.flushChan {
        if err := m.flushToSSTable(mt); err != nil {
            // log and retry
            continue
        }
        m.immutableMu.Lock()
        // Remove mt from immutable list
        for i, im := range m.immutable {
            if im == mt {
                m.immutable = append(m.immutable[:i], m.immutable[i+1:]...)
                break
            }
        }
        m.immutableMu.Unlock()
        // GC will reclaim mt + arena
    }
}

This skeleton compiles (with appropriate helper functions). It captures the essentials of a production memtable: atomic active pointer, immutable list, flush goroutine, iterator chain.

Where the skip list fits¶

The Skiplist inside each Memtable is the lock-free concurrent skip list we have studied. The rest is orchestration.

The skip list is responsible for ~80% of the CPU time in this design. The other 20% is WAL writes, iterator merging, flush, etc.

Engineering judgment¶

• Why per-memtable arena: enables bulk free on flush.
• Why immutable list (not just active + flushing): allows flush to keep up with high write rate; no back-pressure unless list grows unbounded.
• Why merge iterators: simpler than maintaining a single global structure.
• Why RWMutex on immutableMu: rotation is rare; reads are frequent.

These are not "the right answer" — they are reasonable engineering trade-offs. Other designs are equally valid. The Pebble memtable design has slightly different choices, optimised for their specific workload.

Appendix — A Deep Look at Memtable Flush¶

Flush is the most operationally complex part of a memtable. The skip list is sorted, but turning it into an SSTable involves:

1. Iterate the skip list in sorted order.
2. Encode each entry to the SSTable format (key + value + metadata + bloom filter bits).
3. Write blocks of encoded entries to disk.
4. Build an index of block boundaries.
5. Append the index, footer, and bloom filter to the file.
6. Atomically rename or commit the file.
7. Notify the LSM manager.

Iteration during flush¶

The flushing goroutine iterates the immutable skip list. Concurrent reads also iterate it (the immutable is still in the read path). Concurrent inserts go to the active memtable, not the immutable.

Since the immutable does not accept writes, lock-free reads are entirely safe. Iteration is just a level-0 walk.

Memory pressure during flush¶

If flush is slow and writes are fast, the immutable list grows. Memory grows. At some point either:

• Block writes (back-pressure).
• Spill to a tier-1 cache.
• Allow OOM (almost never the right answer).

Most systems block writes when the immutable list exceeds a threshold (e.g., 8 immutables). This is the write stall visible in operational dashboards.

Crash safety during flush¶

If the process crashes during flush: - WAL still contains the writes. - On restart, the WAL is replayed into a fresh memtable. - The partially-written SSTable is discarded.

This is why crash safety lives in the WAL, not the memtable.

Flush throughput¶

A 64MB memtable with 1M keys takes ~500 ms to flush on a modern SSD. At 1M writes/sec, a 64MB memtable fills in ~5 seconds. Flush keeps up easily.

At 10M writes/sec, the memtable fills in 0.5 seconds, faster than flush. The system must either: increase memtable size, parallelise flush, or shed load.

Compaction interactions¶

After flush, the new SSTable lives at "level 0" of the LSM. Over time, level-0 SSTables are compacted into level-1, then level-2, etc. Each compaction merges multiple SSTables (sorted) into a single new SSTable.

Compaction is not the memtable's concern — it operates on disk SSTables. But the rate of compaction is driven by the rate of flush, which is driven by the rate of writes.

Appendix — The Operations Side of a Production Memtable¶

Operational concerns are often discussed in isolation; here they are tied to specific failure modes.

Failure mode 1 — Write stall¶

Symptom: latency spikes, throughput drops. Cause: too many immutable memtables backing up. Root cause: flush is slow (slow disk, contended SST writes, large memtables). Diagnosis: monitor immutable count and flush latency. Fix: faster disk, smaller memtables, increased parallelism for flush, or rate-limit writes.

Failure mode 2 — OOM¶

Symptom: process crashes with "out of memory." Cause: memtable grew beyond expected size, or immutable list grew unbounded. Root cause: usually a tuning bug (memtable size too large for available memory). Diagnosis: heap profile; look for large arena allocations. Fix: reduce memtable size; cap immutable list with hard back-pressure.

Failure mode 3 — Read amplification¶

Symptom: reads slow as data grows. Cause: many SSTables to check on each read. Root cause: compaction not keeping up; LSM level fanout too high. Diagnosis: read profile; count SSTables checked per read. Fix: more aggressive compaction; tune LSM levels; add bloom filters.

The skip list itself is rarely the cause of any of these. Its operations are typically <1% of read/write latency. Operational issues live in WAL, flush, compaction, and disk.

Failure mode 4 — Latency tail¶

Symptom: p50 fine; p99 terrible. Cause: contention spikes, GC pauses, write stalls. Root cause: usually a load spike or workload shift. Diagnosis: latency histogram; correlate with system metrics. Fix: load shedding; capacity planning; tune GC.

The skip list's own latency tail (from CAS retries) is small compared to GC and disk effects. Focus tuning where the budget hurts most.

Appendix — A Realistic Story: Memtable in a Time-Series Database¶

Setting: building a time-series database (TSDB) in Go. Writes are append-mostly: (timestamp, metric, value).

Design choices¶

• Memtable: skip list keyed by (timestamp_minute, metric_id).
• Memtable size: 128 MB.
• Flush to SSTable when memtable full or every 60 seconds (whichever first).
• SSTable: sorted run, compressed.
• Compaction: tiered, with level-0 → level-1 → level-2.

Throughput plan¶

• Target: 500K writes/sec from 100 application servers.
• Each write: ~50 bytes.
• Memory growth: 500K × 50B × 60s = 1.5 GB per minute → flush every ~5 seconds.
• Time per flush: ~1 second.
• Concurrent immutables at peak: ~1.

This plan is tight on memory. A 10× spike would queue up 10 immutables = 1.5 GB. Doable but worth monitoring.

Implementation choices¶

• Lock-free skip list with arena allocation (chosen for low GC pressure at 500K writes/sec).
• Single arena per memtable, 128 MB.
• Snapshot iterators not needed (TSDB is mostly append; no transactional reads).
• Bloom filter on each SSTable for point lookups by metric_id.

Operational metrics¶

• Writes per second
• Read latency p50/p99
• Memtable size
• Immutable count
• Flush duration
• SSTable count per level
• Compaction queue depth

A team that ships this would spend ~3 months on the initial implementation, ~1 month on operationalisation, and ~6 months on tuning under real load. The concurrent skip list is ~10% of the total engineering time; the other 90% is the LSM, the WAL, the operational integration.

What "the right tool" looks like¶

Could you have built this with sync.Map plus a sorted index? Probably not — sync.Map does not support range queries efficiently.

Could you have built it with a B+tree memtable? Yes, but the implementation is 3× more complex.

Could you have built it with skipset (general-purpose)? Yes for moderate scale (~100K writes/sec). Above that, the per-node mutex contention in skipset becomes a bottleneck and you need arenaskl or a custom variant.

This is the kind of decision tree you walk through in a real architecture review.

Appendix — Production Story: The Day the Skip List Broke¶

A real (anonymised) story. A SaaS company ran a Go service using a hand-rolled concurrent skip list for an in-memory index. The service had been in production for 18 months without incident.

One Tuesday at 14:30 PT, alerts fired: p99 latency had jumped from 5 ms to 800 ms. Active alerts: high CPU, growing memory, growing goroutine count.

The investigation, in order:

14:35. On-call engineer pages a colleague familiar with the service. They confirm the issue and check recent deploys. No deploys in 6 hours.

14:40. Profile shows 60% of CPU in runtime.mallocgc. Heap profile shows huge growth in *node allocations from the skip list. The skip list size has grown 10×.

14:45. Check upstream services. A bug in a partner service was sending 100× the normal request rate to one specific endpoint. The endpoint inserts into the skip list.

14:50. Hypothesis: the skip list is correctly accepting all writes, but at 100× normal rate. Memory is growing because writes are never being garbage collected. The "size growth" is real, not a bug.

14:55. Immediate mitigation: enable rate limiting at the API gateway for the affected endpoint. Drop excess traffic.

15:00. Latency recovers within 2 minutes. Memory begins to shrink as GC cycles reclaim now-unreferenced data.

15:15. Confirm root cause with partner service team. They had pushed a buggy change that retried failed requests in a tight loop.

Post-mortem actions: 1. Add a hard cap to the skip list size. Reject inserts beyond the cap. 2. Add an alert on skip list size growing >2× the baseline. 3. Negotiate with partner team to add their own rate limiting. 4. Document the new cap behaviour.

The skip list was not buggy. The system using it was missing safety limits. This is a typical production failure: not algorithmic, but operational.

The lesson: every shared data structure needs size limits and rate controls at the entry point. The skip list is not responsible for refusing inserts; the caller is.

Appendix — Architecture Patterns Around Skip Lists¶

Several architectural patterns use skip lists, beyond just "in-memory ordered set."

Pattern 1 — Bounded write buffer¶

A skip list bounded to a max size, acting as a write buffer that is periodically drained.

type Buffer struct {
    sl     *SkipList
    cap    int
    drainC chan []Entry
}

func (b *Buffer) Add(e Entry) error {
    if b.sl.Len() >= b.cap {
        if !b.drain() {
            return ErrBufferFull
        }
    }
    b.sl.Insert(e.Key)
    return nil
}

Used for: log buffering, metrics aggregation, batched writes.

Pattern 2 — Sliding window with TTL¶

A skip list keyed by timestamp, with periodic cleanup of old entries.

type Window struct {
    sl       *SkipList
    duration time.Duration
}

func (w *Window) GC() {
    cutoff := time.Now().Add(-w.duration).UnixNano()
    // Delete all keys < cutoff
    ...
}

Used for: rate limiting (last N seconds), online analytics, session tracking.

Pattern 3 — Sparse index for large data¶

A skip list of "sparse" pointers into a larger structure (e.g., every 1000th element of a sorted dataset). Skip list serves coarse navigation; finer search happens within the sparse range.

Used for: in-memory indexes of larger on-disk structures, hybrid memory-disk systems.

Pattern 4 — Multi-version log¶

A skip list keyed by (timestamp, key), storing every version. Reads at a specific timestamp see the latest version <= that timestamp.

Used for: MVCC databases, audit logs, change data capture.

Pattern 5 — Time-bucketed materialised view¶

A skip list of time-bucket aggregates. Each bucket is a small structure (sum, count, max) covering, say, a 1-minute window.

type Bucket struct {
    timestamp int64
    sum       atomic.Int64
    count     atomic.Int64
}

type View struct {
    sl *SkipList // keyed by timestamp
}

Used for: real-time dashboards, OLAP-on-OLTP.

These patterns share the property that they layer business logic on top of the skip list's ordered concurrent guarantees. The skip list is a building block, not a finished system.

Appendix — A Detailed Look at arenaskl Internals¶

Beyond the brief sketch earlier, here are deeper notes on Pebble's arenaskl.

Memory layout¶

[Arena]
 ┌──────────────────────────────────────────┐
 │ Header (32 bytes)                         │
 ├──────────────────────────────────────────┤
 │ Node 1 (variable size, padded to 4)      │
 ├──────────────────────────────────────────┤
 │ Key bytes for node 1                      │
 ├──────────────────────────────────────────┤
 │ Value bytes for node 1                    │
 ├──────────────────────────────────────────┤
 │ Node 2 ...                                │
 │ ...                                       │
 │                                           │
 └──────────────────────────────────────────┘

Sequential allocation. No "free." Whole arena dies at memtable flush.

Node layout¶

// Conceptual (Pebble uses unsafe.Pointer + offsets)
type node struct {
    keyOffset    uint32
    keySize      uint32
    keyTrailerSize uint16
    height       uint16
    valueOffset  uint32
    valueSize    uint32
    // Tail: heights × uint32 (atomic next offsets)
}

Note keyTrailerSize: Pebble's keys carry trailers (sequence number + kind) for MVCC. The actual user key is a prefix; the trailer is everything else.

Sequence numbers¶

Each insert gets a monotonic sequence number. Multiple versions of the same user key are distinguished by sequence. Reads use a snapshot sequence.

This is MVCC at the key level: instead of versioning the data structure, version the keys. The skip list is conventionally ordered by (user_key, descending_sequence).

Iteration¶

Pebble's iterator supports SeekGE(key), Next(), Prev(), SeekPrefix(prefix), First(), Last(). Implementation uses cached "current" position + arena offset arithmetic.

Backward iteration (Prev) is expensive in a forward-only skip list. Pebble does a forward search from a recent endpoint, which is O(log n) per Prev call.

Concurrency model¶

• Add: lock-free, CAS-based splice.
• Get: lock-free walk (no need to handle marked nodes because Pebble's memtable does not delete; tombstones are written as keys).
• Iterator: holds offsets, advances via atomic reads.

Pebble simplifies by not supporting delete; instead, deletes are written as "tombstone" keys that override regular keys on read. This eliminates the marker-and-help complexity.

Trade-offs¶

Pebble's design is opinionated: - Optimised for memtable workloads (write-heavy, no in-place delete). - Not a general-purpose concurrent skip list. - Tightly coupled to Pebble's LSM and MVCC.

Studying it teaches a lot about production engineering even if you do not directly use it.

Appendix — Capacity Planning Worksheet¶

For deploying a skip list-based system to production, work through this:

Step 1 — Throughput estimation¶

• Peak QPS: ____ (e.g., 100K)
• Peak ops/sec on the skip list: _ × _ (operations per QPS, e.g., 5 lookups + 1 insert = 6)
• Total skip list ops/sec: _ × _ = ____

Step 2 — Latency budget¶

• Total request budget (e.g., 10 ms p99): ____
• Skip list portion (e.g., 5%): ____
• Skip list latency budget: _ × _ = ____ µs

Step 3 — Memory¶

• Estimated keys at steady state: ____
• Bytes per key (key + value + ~40 bytes overhead): ____
• Total memory: _ × _ = ____ MB

Step 4 — Hardware¶

• Cores needed for skip list CPU: (ops/sec × ns/op) / 10^9 = ____ cores
• Total cores including non-skip-list work: ____
• Memory headroom for GC, OS, other services: ____

Step 5 — Reserve¶

• Add 50% capacity for spikes.
• Add 20% memory for fragmentation, GC overhead.

This worksheet sizes the hardware. Validate with a load test before going to production.

Appendix — Failure Recovery¶

When a system using a skip list memtable crashes, recovery involves:

1. Detect crash. OS or container orchestrator restarts the process.
2. Read WAL. Open the WAL file, identify the last fully-written record (truncate any partial record at the tail).
3. Replay into memtable. For each WAL record, insert into a fresh memtable.
4. Catch up. Recover any SSTables not yet flushed. Verify checksums.
5. Resume. Accept new writes once memtable is rebuilt.

Recovery time is bounded by WAL size. A 1 GB WAL with 1 million records takes ~1 second to replay (at ~1 µs per insert). Tune memtable size to balance WAL replay time against memtable flush time.

Concurrent recovery¶

If multiple WAL files exist (one per writer thread), they can be replayed in parallel — but the resulting memtable must still be consistent. The simplest approach: serialise replay. The advanced approach: replay in parallel into multiple "shadow" memtables and merge at the end.

Idempotent recovery¶

WAL writes must be idempotent: replaying a record twice produces the same state as replaying once. For an insert (set semantics), this is automatic. For delete or increment operations, encode the operation type and the desired final state.

Appendix — Cross-Cutting Concerns¶

A few topics that apply across all production skip lists.

Observability¶

Expose internal state via expvar, Prometheus, or your preferred metrics library:

var (
    sklSize      = expvar.NewInt("skiplist.size")
    sklOpCount   = expvar.NewInt("skiplist.ops")
    sklCASFails  = expvar.NewInt("skiplist.cas_fails")
    sklLatencyP99 = expvar.NewFloat("skiplist.latency_p99_ns")
)

func (s *SkipList) Insert(key int) bool {
    sklOpCount.Add(1)
    start := time.Now()
    defer func() {
        latency := time.Since(start).Nanoseconds()
        // ... update histogram, etc.
    }()
    // ... insert logic
}

Metrics let you see what is happening without attaching a debugger.

Tracing¶

Distributed tracing (OpenTelemetry) lets you correlate skip list operations with surrounding requests. For latency investigations, the trace shows which sub-operation is slow.

ctx, span := tracer.Start(ctx, "skiplist.Insert")
defer span.End()
// ... insert

Overhead: ~100 ns per span. Negligible.

Health checks¶

A /healthz endpoint should verify the skip list is responsive:

func (s *Service) Healthz(w http.ResponseWriter, r *http.Request) {
    if !s.sl.Contains(canaryKey) {
        http.Error(w, "skip list missing canary", 500)
        return
    }
    w.Write([]byte("ok"))
}

A real liveness check has to do something with the skip list. A "ping" endpoint that does not touch the skip list does not catch skip list corruption.

Profiling¶

pprof endpoints exposed at /debug/pprof/ (Go's built-in) let you take CPU and memory profiles in production. For ongoing systems, this is non-negotiable.

Logging¶

Log significant events: flushes, large allocations, capacity events. Avoid logging every operation; log volume kills disks and storage costs money.

Appendix — A Story About arenaskl's Bug Fix¶

In 2019, the Pebble team discovered a subtle bug in arenaskl (CockroachDB's memtable skip list). Under very specific conditions, a CAS retry could splice a new node ahead of a node still being inserted by another thread.

The investigation took 2 weeks. The fix was 3 lines. The post-mortem was 30 pages.

Key insights from the post-mortem: 1. Lock-free correctness is incredibly subtle. 2. Original implementation had passed extensive testing. 3. The bug was found by a synthetic stress test, not in production (Pebble was lucky). 4. The fix involved tightening the precondition on a specific CAS.

The takeaway: even highly experienced teams ship subtle bugs in lock-free code. Testing must be aggressive and continuous.

Source: CockroachDB engineering blog, "A Tale of Two Skiplists" (or similar; specifics vary).

Appendix — Skip Lists in Distributed Systems¶

Skip lists also appear in distributed systems, in two ways:

Distributed skip list as routing structure¶

Chord (Stoica et al., 2001) and similar peer-to-peer DHTs use a skip list-like overlay for routing. Each node knows its finger table — pointers to nodes at exponentially-increasing distances. Lookup is O(log n) hops, just like a skip list.

This is conceptually a skip list at the node level, not at the data level.

Skip list memtable in distributed databases¶

CockroachDB, TiDB, Yugabyte, and similar distributed SQL databases use Pebble (or similar) for storage on each node. The skip list memtable lives on each node.

The distribution layer (replication, sharding, consensus) sits above the storage engine. The skip list is a local implementation detail.

When you scale a distributed database to 1000 nodes, you have 1000 skip list memtables, each operating independently. The skip list itself does not need to know about distribution.

Appendix — Comparison With Specialised Concurrent Structures¶

For specific workloads, specialised structures may beat a generic concurrent skip list.

Lock-free queue¶

For producer-consumer workloads with no ordering requirement beyond FIFO: - Michael-Scott queue: lock-free, ~50 lines. - Faster than a skip list for pure FIFO.

Lock-free hash table¶

For point lookups without ordering: - xsync.Map or concurrent-map: faster than sync.Map for high-churn workloads. - Faster than a skip list for point operations.

Lock-free priority queue¶

For workloads where you only ever remove the minimum: - Concurrent heap (e.g., Hunt, Michael, Parthasarathy, Scott 1996). - Faster than a skip list-based priority queue for Min+Pop only.

Lock-free B+tree¶

For very large ordered indexes: - Bw-tree (Microsoft, 2013): lock-free B+tree. ~10000 lines. Higher per-op latency than a skip list, much better cache behaviour. - Used in SQL Server, Azure CosmosDB.

Lock-free trie¶

For string keys with prefix queries: - ROART (Wang et al., 2018): concurrent adaptive radix tree. - Faster than a skip list for string keys.

The skip list is a generalist. For your specific workload, a specialist may be faster. The decision tree:

• Ordered + many concurrent writers + range queries → skip list (your default).
• Ordered + few writers + range queries → sorted slice + RWMutex.
• Ordered + many writers + no range queries → consider a concurrent heap.
• Unordered + many writers → sync.Map or xsync.Map.
• String keys + prefix queries → ROART.
• Very large + memory-mapped → B+tree.

Appendix — End-of-Field Knowledge Check¶

After everything in this folder, can you:

• Implement a single-threaded skip list from memory? (Junior)
• Implement a coarse-locked concurrent skip list? (Junior)
• Implement the Herlihy/Lev/Luchangco/Shavit lazy skip list? (Middle)
• Implement a Fraser-style lock-free skip list? (Senior)
• Implement an arena-allocated skip list with snapshot iterators? (Professional)
• Compare and choose between these designs based on a workload? (Professional)
• Deploy and operate a skip list memtable in production? (Professional)
• Read skipset and arenaskl source with full comprehension? (Professional)
• Diagnose and fix a production skip list issue at 3 AM? (Professional)
• Contribute to the published literature on concurrent skip lists? (Beyond)

The first six are tractable in a month of focused effort. The seventh and eighth take a year of production experience. The ninth comes from at least one outage. The tenth is research.

If you have all ten, you are in the top 1% of working engineers who understand this material. Congratulations.

If you have eight, you are an excellent senior engineer.

If you have six, you have completed the curriculum.

If you have four, keep practising. The material rewards repetition.

Appendix — Where Skip Lists Are Going¶

Predictions for the next decade of concurrent skip list research and engineering.

Persistent memory support¶

Intel Optane and similar NVRAM technologies are slowly entering production. Skip lists that survive crashes (without a separate WAL) are an active research area. The Pinit skip list (Lersch et al., 2019) is a notable design.

In Go, persistent-memory support is nascent. Library work is likely in the next 3-5 years.

Hardware transactional memory¶

Intel TSX and IBM POWER offer HTM. A skip list using HTM for the insert critical section can be faster than CAS-based lock-free for short transactions. Go does not expose HTM directly; future Go versions might.

GPU-resident structures¶

For massively-parallel analytic workloads, GPU-resident skip lists are an active topic. Performance is workload-specific; the field is young.

Not applicable to standard Go.

Cache-conscious refinements¶

Continued research into layouts that minimise cache misses. Embedded arrays, packed encodings, learned indexes (using ML to predict positions). Diminishing returns; most workloads are not cache-bound.

Integration with new persistence tiers¶

As storage hierarchies grow (RAM → NVRAM → SSD → HDD → tape), skip lists may serve as in-memory tiers in deeper LSMs. The patterns scale; the implementation details vary.

Formal verification¶

Tools like TLA+ and Iris are being applied to verify lock-free algorithms. Expect more lock-free skip list designs to come with mechanised proofs in the next decade.

Appendix — Truly Final Words¶

Five files. Thousands of lines. Hundreds of code samples. Dozens of diagrams. From "what is a skip list" to "ship a production lock-free skip list memtable in a distributed database."

This is one of the most thoroughly-explored data structures in computer science. After this folder, you have seen most of what is publicly known about them.

The most important thing you can do now is use the knowledge. Find a real problem in your work where a concurrent ordered structure helps. Build it. Test it. Ship it. Profile it. Tune it. Operate it. The compounding value of doing far exceeds reading.

Good luck. Build well.

— end of folder —

Appendix — Detailed Engineering Case Studies¶

Case 1 — Building a Concurrent Cache with TTL¶

A team needs an LRU-with-TTL cache for HTTP responses. Up to 10M entries, ~1 KB each. Reads: 100K/sec. Writes: 10K/sec. Each entry has a TTL (1-3600 seconds).

Design.

Two structures: 1. A sync.Map[key]entry for O(1) point lookups. 2. A concurrent skip list keyed by (expiry_time, key) for ordered cleanup.

type Cache struct {
    data     sync.Map           // key -> *entry
    expiries *SkipList          // (expiry_nanos, key) -> *entry
    janitor  *time.Ticker
}

type entry struct {
    val    []byte
    expiry int64
}

func (c *Cache) Get(key string) ([]byte, bool) {
    v, ok := c.data.Load(key)
    if !ok {
        return nil, false
    }
    e := v.(*entry)
    if time.Now().UnixNano() > e.expiry {
        return nil, false // expired
    }
    return e.val, true
}

func (c *Cache) Set(key string, val []byte, ttl time.Duration) {
    expiry := time.Now().Add(ttl).UnixNano()
    e := &entry{val: val, expiry: expiry}
    c.data.Store(key, e)
    c.expiries.Insert(encodeKey(expiry, key))
}

func (c *Cache) runJanitor() {
    for now := range c.janitor.C {
        cutoff := now.UnixNano()
        c.expiries.Range(0, cutoff, func(k int) bool {
            _, key := decodeKey(k)
            c.data.Delete(key)
            c.expiries.Delete(k)
            return true
        })
    }
}

Trade-offs.

• The skip list is used for ordered cleanup. Without it, the janitor would have to scan the entire data map every interval — O(N) work each time.
• The data map is sync.Map, optimised for read-mostly. Reads benefit; writes are slightly slower but acceptable at 10K/sec.
• The janitor runs every second. Cleanup is amortised; latency tail of Set is unaffected.

Performance estimate.

• Reads: 100K/sec on sync.Map — well within capacity.
• Writes: 10K/sec on both sync.Map and skip list — easy.
• Janitor: cleans 1-100K expired entries per second; bounded by skip list range scan + map deletes.
• Memory: 10M × ~1100 bytes (val + headers) = 11 GB.

Operational notes.

• Monitor: cache size, hit rate, janitor latency.
• Alert: cache size > 12 GB (memory pressure).
• Capacity: 11 GB is OK for a 16 GB machine; consider sharding above that.

This is a real, production-grade design. The skip list does one specific job (ordered cleanup), and does it well.

Case 2 — Real-Time Leaderboard¶

A multiplayer game needs a per-region leaderboard. ~1M players per region, updated continuously. Top-100 fetched ~10/sec by the lobby UI.

Design.

type Leaderboard struct {
    players sync.Map           // playerID -> *playerScore
    rank    *SkipList          // (score_descending, playerID) -> *playerScore
}

type playerScore struct {
    playerID string
    score    int64
}

func (l *Leaderboard) UpdateScore(playerID string, newScore int64) {
    v, _ := l.players.LoadOrStore(playerID, &playerScore{playerID: playerID})
    p := v.(*playerScore)
    oldScore := atomic.SwapInt64(&p.score, newScore)
    if oldScore != 0 {
        l.rank.Delete(encodeRank(oldScore, playerID))
    }
    l.rank.Insert(encodeRank(newScore, playerID))
}

func (l *Leaderboard) Top100() []*playerScore {
    var top []*playerScore
    l.rank.Range(0, math.MaxInt, func(k int) bool {
        _, pid := decodeRank(k)
        v, _ := l.players.Load(pid)
        if v != nil {
            top = append(top, v.(*playerScore))
        }
        return len(top) < 100
    })
    return top
}

Trade-offs.

• Single concurrent skip list for ranking. Lock-free; scales to millions of updates per second.
• encodeRank(score, pid) packs both into a single int by reversing score bits (so higher scores come first in ascending order).
• Race window: between Delete and Insert, a player is temporarily not in the rank. Top100 may briefly see a player with the wrong score. Acceptable.

Stricter consistency option.

If briefly-wrong-scores are unacceptable, use a per-player mutex during update:

type playerScore struct {
    mu    sync.Mutex
    score int64
}

func (l *Leaderboard) UpdateScore(playerID string, newScore int64) {
    v, _ := l.players.LoadOrStore(playerID, &playerScore{})
    p := v.(*playerScore)
    p.mu.Lock()
    defer p.mu.Unlock()
    if p.score != 0 {
        l.rank.Delete(encodeRank(p.score, playerID))
    }
    p.score = newScore
    l.rank.Insert(encodeRank(newScore, playerID))
}

Per-player lock + skip list operations. Slightly higher latency, no atomicity gap. Most games choose the eventually-consistent design because the briefly-wrong-window is invisible to humans.

Case 3 — Order Book in a Trading System¶

A financial exchange maintains an order book per security: buy orders sorted descending by price, sell orders sorted ascending. Updates: ~1M/sec at peak.

Design.