Concurrent Skip List — Senior Level¶

Table of Contents¶

1. Introduction
2. Why Lock-Free
3. The Harris-Michael Lock-Free Linked List
4. Marker Pointers and Tagged Pointers
5. The Fraser Lock-Free Skip List
6. Complete Go Implementation
7. Why the Algorithm Is Correct
8. Helping
9. ABA, Reclamation, and Why Go Makes Both Easy
10. Range Queries and Snapshot Iterators
11. Linearisability Proof Sketch
12. Comparison with sync.Map and B+tree Memtables
13. Performance Analysis at High Core Counts
14. Random Number Generation Under Concurrency
15. Cache-Line Layout and False Sharing
16. skipset Internals — Reading the Source
17. Subtle Bugs at this Level
18. Stress Testing Lock-Free Code
19. Cheat Sheet
20. Self-Assessment
21. Summary

Introduction¶

The middle level brought us to the lazy lock-based skip list — the gold standard of lock-based concurrent ordered structures. Its Contains is wait-free; its Insert and Delete use optimistic locking with validate-then-link. For most workloads this is the right answer.

But there is a higher mountain: lock-free, where no sync.Mutex ever appears in the data path. The benefits are:

• No mutex contention. Under heavy parallel write load, locks are the bottleneck. Removing them removes a hard ceiling on throughput.
• No latency-tail from preempted lock-holders. A goroutine holding a lock might be preempted by the runtime, blocking everyone waiting. Lock-free is immune.
• Lock-free guarantee. System-wide, some operation always makes progress in a finite number of steps. No livelock or deadlock is possible by construction.

The costs are:

• Roughly 2× more code.
• Subtle correctness arguments — every CAS sequence must be analysed for ABA and torn reads.
• Helping — any goroutine that observes a half-finished operation must finish it.
• Memory reclamation — in C++, this is a major chapter on its own. In Go, the GC removes most of the difficulty.

After reading this file you will:

• Understand the Harris-Michael lock-free linked list, the building block beneath every lock-free skip list.
• Understand marker pointers (tagged-pointer encoding) and why they linearise deletion.
• Be able to walk through Fraser's lock-free skip list algorithm in full.
• Implement a lock-free skip list in Go using atomic.Pointer[node].
• Reason about linearisability points and ABA prevention.
• Know how skipset is structured and what tricks it applies.

This is the deepest material on concurrent data structures most engineers ever encounter outside research labs. Take it slowly.

Why Lock-Free¶

Locks have a worst case¶

A mutex is fast on the happy path (~25 ns to acquire uncontended). Under contention it is slower (100-500 ns). But the truly bad case is preemption: a goroutine holding the lock is descheduled, and every goroutine waiting on the lock waits for the OS to reschedule. That wait can be milliseconds — six orders of magnitude longer than the happy path.

Lock-free designs do not have this worst case. The longest a goroutine can be "stuck" is bounded by the number of concurrent operations that retry their CAS — which is bounded by the level of contention, not by OS scheduling.

For latency-sensitive systems (real-time bidding, low-latency trading, network proxies under DoS, large databases at p99) this difference matters more than the average-case throughput.

Lock-free does not mean wait-free¶

Lock-free: system-wide, some goroutine always makes progress. Wait-free: every goroutine always makes progress in a bounded number of steps.

The Fraser skip list is lock-free but not wait-free. A goroutine may keep retrying its CAS indefinitely if other goroutines keep winning theirs. Wait-free skip lists exist but are research curiosities; their constant factors are 5-10× higher than lock-free, and no major production system uses one.

Lock-free is harder¶

The first lock-free linked list paper (Harris 2001) is a one-page algorithm with a fifteen-page proof. The Fraser thesis is 200 pages. The reason is the subtle interactions between concurrent CAS attempts — for every "happens-before" you would like to assume, you must explicitly establish.

Go makes this dramatically easier than C++ because the GC handles memory reclamation and atomic.Pointer[T] handles tagged pointers ergonomically. A lock-free skip list in Go is ~400 lines; the same algorithm in C++ is ~1500.

The Harris-Michael Lock-Free Linked List¶

Before tackling the skip list, master its building block: the Harris-Michael lock-free singly-linked list. The skip list is "one of these per level, glued together."

The structure¶

type node struct {
    key  int
    next atomic.Pointer[node]
}

type List struct {
    head *node // sentinel; key = -inf
    tail *node // sentinel; key = +inf
}

next is an atomic.Pointer[node]. All reads and writes go through Load(), Store(), CompareAndSwap().

The marker trick¶

The key insight: encode "this node is being deleted" by marking the next pointer of the node, not the node itself. We use the lowest bit of the pointer as a marker, since pointers are aligned to 8 bytes on 64-bit systems (and thus have three free low bits).

In Go we cannot directly tag pointers without unsafe. Two approaches:

1. Sentinel marker node. Insert a special marker node after the to-be-deleted node. Any traversal that encounters a marker node knows its predecessor is being unlinked.
2. Wrap pointer in struct. A struct holding next *node plus marked bool (or markedNext *markedNode), stored as atomic.Pointer[markedNext]. Replaces the entire descriptor atomically.

Approach 1 is simpler but adds memory. Approach 2 uses unsafe.Pointer tricks (the same as skipset does) for performance.

We will use approach 2 in our pedagogical implementation, then briefly discuss approach 1.

CAS-based insert¶

func (l *List) Insert(key int) bool {
    for {
        pred, curr := l.find(key)
        if curr.key == key {
            return false
        }
        newNode := &node{key: key}
        newNode.next.Store(curr)
        if pred.next.CompareAndSwap(curr, newNode) {
            return true
        }
        // CAS failed; retry
    }
}

The CAS swaps pred.next from curr (the expected successor) to newNode (with newNode.next = curr). If the CAS fails (because someone else changed pred.next), we restart the whole search. The CAS-success case is the linearisation point of the insert.

CAS-based delete (two phases)¶

func (l *List) Delete(key int) bool {
    for {
        pred, curr := l.find(key)
        if curr.key != key {
            return false
        }
        succ := curr.next.Load()
        // Phase 1: mark curr.next as "being deleted"
        // (In real code, this is a CAS that swaps in a marked version of succ)
        if !markNext(curr, succ) {
            continue
        }
        // Phase 2: unlink curr by CAS on pred.next
        pred.next.CompareAndSwap(curr, succ)
        // If this CAS fails, some other thread already unlinked curr.
        // Either way, curr is logically gone.
        return true
    }
}

The two phases are essential. Phase 1 (mark) is the linearisation point: once curr is marked, subsequent find calls treat it as deleted. Phase 2 (unlink) is housekeeping; if it fails, helping (see below) takes care of it.

Why marker is necessary¶

Without the mark, this race occurs:

1. Thread A starts Insert(K) where curr is currently the L0 successor of pred.
2. Thread B starts Delete(curr). B unlinks curr: pred.next.CAS(curr, succ).
3. A's CAS pred.next.CAS(curr, newNode) — succeeds because nobody has modified pred.next yet (oh wait — B already did). Suppose A runs first: pred.next is now newNode. Then B's CAS: pred.next == curr? No, it's newNode. B's CAS fails.
4. B retries. Finds curr is now the successor of newNode (not pred). B's find returns pred = newNode, curr = curr (still). B's pred.next.CAS(curr, succ) runs on newNode.next, swapping curr for succ. This unlinks curr correctly.

OK that worked. But consider:

1. A: find returns pred, curr. (No CAS yet.)
2. B: find returns pred, curr. B's CAS on pred.next: swap curr -> succ. Curr is unlinked.
3. A: CAS on pred.next: swap curr -> newNode. But pred.next is now succ, not curr. A's CAS fails. A retries.

Still safe. So why do we need the mark?

The bad case: A's CAS succeeds just before B's. A: pred.next = newNode (with newNode.next = curr). B: pred.next == curr? No, newNode. B's CAS fails. B re-finds. B's find walks past pred to newNode, then sees newNode.next = curr. B's find returns (newNode, curr). B's CAS: newNode.next = succ. Succeeds. Curr is unlinked.

Now the skip list contains: pred -> newNode -> succ. That is correct. So even without marking, this case is handled — by retry.

The truly bad case requires three threads:

1. A: insert K1 with K1's successor = curr. Cas pred.next from curr to A_node. Succeeds.
2. B: delete curr. B's find returns (A_node, curr). B's mark on curr.next succeeds. B's unlink CAS on A_node.next: swap curr -> succ. Succeeds.
3. C: insert K2 with K2's successor = curr. C's find returned (A_node, curr) earlier — before B unlinked. C's CAS on A_node.next: swap curr -> C_node. But A_node.next is succ now. C's CAS fails. C retries.

OK still safe with retry. Let me try harder.

The crux: the mark prevents a node that is being deleted from acquiring new successors. Specifically, an insert that wants to splice in behind curr (i.e., pred = curr-being-deleted) must not succeed.

1. A: insert K (where K > curr.key). A's find returns (curr, succ). A's CAS on curr.next: swap succ -> A_node.
2. B: delete curr. B's CAS marks curr.next. B's CAS unlinks A_node-tree from pred.

If A's CAS runs first and B's mark-CAS expects curr.next == succ, B's mark fails. B retries. B's find now returns (curr, A_node). B marks A_node? Wrong. B should still be deleting curr.

This is where the mark on the deleted node's next pointer matters. The mark says "no further inserts may modify curr.next." A's CAS, even if it has not run yet, must check that curr.next is unmarked.

In Go terms, A's CAS becomes:

expected := unmarkedNext(curr)
ok := curr.next.CompareAndSwap(expected, A_node)

If curr has been marked between A's find and A's CAS, the CAS fails because the value of curr.next changed (it now has the mark bit set). A retries.

This is the heart of the Harris-Michael trick. The mark is a visible signal baked into the pointer value itself, so any CAS that targets the marked pointer must explicitly include the unmarked value as the expected.

Marker Pointers and Tagged Pointers¶

In C, pointer tagging is (uintptr_t)ptr | 1. In Go without unsafe, you cannot do this directly. Three options:

Option A — unsafe.Pointer + tag bit¶

import "unsafe"

func mark(p *node) unsafe.Pointer {
    return unsafe.Pointer(uintptr(unsafe.Pointer(p)) | 1)
}

func unmark(p unsafe.Pointer) *node {
    return (*node)(unsafe.Pointer(uintptr(p) &^ 1))
}

func isMarked(p unsafe.Pointer) bool {
    return uintptr(p) & 1 != 0
}

Works, but ugly, and breaks if the runtime ever moves pointers (the moving GC could relocate the underlying object and re-tag, but our marked pointers would be invalidated). Go's current GC does not move pointers, so this is safe in practice.

Option B — Struct-wrapped pointer + atomic.Pointer¶

type markedRef struct {
    next   *node
    marked bool
}

type node struct {
    key  int
    next atomic.Pointer[markedRef]
}

Every modification allocates a new markedRef. Wasteful in allocations but trivially correct.

Option C — Marker node¶

Insert a distinguished marker node after the to-be-deleted node:

var marker = &node{} // sentinel marker; address is the signal

Or use a per-node marker:

type node struct {
    key  int
    next atomic.Pointer[node]
}

func isMarker(n *node) bool {
    return n.key == markerKey // distinguished key value
}

The marker node sits between curr and curr.next. Any traversal that lands on a marker knows the predecessor is being deleted. The marker itself is removed when curr is physically unlinked.

Option C is what Fraser's original lock-free skip list uses. Option B is what most Go libraries use because it is the most idiomatic with atomic.Pointer[T].

We will use Option B for our implementation.

The Fraser Lock-Free Skip List¶

Keir Fraser's PhD thesis (Cambridge, 2003) presents the canonical lock-free skip list. The structure is the same as the lazy version: stack of sorted linked lists with randomised heights. The difference is every update uses CAS instead of locks.

The algorithm has three operations:

find(key)¶

Walks the structure top-down, recording predecessors and successors at every level. Along the way, helps to physically unlink any marked nodes it encounters (see Helping).

func (s *SkipList) find(key int, preds, succs *[MaxLevel]*node) bool {
retry:
    pred := s.head
    for i := MaxLevel - 1; i >= 0; i-- {
        currRef := pred.next[i].Load()
        for {
            if currRef == nil {
                break
            }
            curr := currRef.next
            // Check if curr is logically deleted at this level
            succRef := curr.next[i].Load()
            for succRef != nil && succRef.marked {
                // Help unlink curr from this level
                if !pred.next[i].CompareAndSwap(currRef, &markedRef{next: succRef.next}) {
                    goto retry
                }
                currRef = pred.next[i].Load()
                if currRef == nil {
                    break
                }
                curr = currRef.next
                succRef = curr.next[i].Load()
            }
            if curr.key < key {
                pred = curr
                currRef = succRef
            } else {
                break
            }
        }
        preds[i] = pred
        if currRef == nil {
            succs[i] = nil
        } else {
            succs[i] = currRef.next
        }
    }
    return succs[0] != nil && succs[0].key == key
}

This is dense. The key idea: at every level, we walk past any marked-as-deleted nodes, helping to unlink them as we go. By the time find returns, all visible nodes (in preds and succs) are unmarked at level 0. Higher levels may still contain marked references, but they will be cleaned up later.

Insert(key)¶

func (s *SkipList) Insert(key int) bool {
    height := s.randomHeight()
    var preds, succs [MaxLevel]*node
    for {
        if s.find(key, &preds, &succs) {
            return false
        }
        newNode := &node{key: key, next: make([]atomic.Pointer[markedRef], height), height: height}
        for i := 0; i < height; i++ {
            newNode.next[i].Store(&markedRef{next: succs[i]})
        }
        // Level 0 first
        if !preds[0].next[0].CompareAndSwap(
            &markedRef{next: succs[0]},
            &markedRef{next: newNode},
        ) {
            continue // restart
        }
        // Higher levels; if CAS fails, refresh and retry just that level
        for i := 1; i < height; i++ {
            for {
                if preds[i].next[i].CompareAndSwap(
                    &markedRef{next: succs[i]},
                    &markedRef{next: newNode},
                ) {
                    break
                }
                s.find(key, &preds, &succs) // refresh preds/succs
                // If find returned true, the new node was already inserted by helping
                // (rare, but possible). In production, check for this.
            }
        }
        return true
    }
}

The linearisation point is the level-0 CAS success. After that, the new node is visible to any find. Higher-level CASes are visibility optimisations; they expand the search-skipping effectiveness but do not change correctness.

Note that the &markedRef{...} allocations in the CAS calls are conceptual — comparing struct identities, not contents. Real implementations use pointer comparison via atomic.Pointer.Load() followed by CompareAndSwap(old, new) where old is the loaded pointer. Below in the full implementation we get this right.

Delete(key)¶

func (s *SkipList) Delete(key int) bool {
    var preds, succs [MaxLevel]*node
    for {
        if !s.find(key, &preds, &succs) {
            return false
        }
        victim := succs[0]
        // Mark from top down; only level 0 mark is the linearisation point.
        for i := victim.height - 1; i >= 1; i-- {
            for {
                succRef := victim.next[i].Load()
                if succRef.marked {
                    break // already marked
                }
                newRef := &markedRef{next: succRef.next, marked: true}
                if victim.next[i].CompareAndSwap(succRef, newRef) {
                    break
                }
            }
        }
        // Level 0 mark — the linearisation point
        for {
            succRef := victim.next[0].Load()
            if succRef.marked {
                return false // already deleted by another goroutine
            }
            newRef := &markedRef{next: succRef.next, marked: true}
            if victim.next[0].CompareAndSwap(succRef, newRef) {
                break
            }
        }
        // Helping physical unlink; not strictly needed because find() does it,
        // but the deleting thread should help too.
        s.find(key, &preds, &succs)
        return true
    }
}

The linearisation point is the level-0 mark CAS. After that, victim is logically deleted. Physical unlinking is performed by any subsequent find.

Contains(key)¶

func (s *SkipList) Contains(key int) bool {
    pred := s.head
    var curr *node
    for i := MaxLevel - 1; i >= 0; i-- {
        currRef := pred.next[i].Load()
        for currRef != nil {
            curr = currRef.next
            // Skip marked nodes
            for {
                succRef := curr.next[i].Load()
                if succRef == nil || !succRef.marked {
                    break
                }
                curr = succRef.next
            }
            if curr.key < key {
                pred = curr
                currRef = curr.next[i].Load()
            } else {
                break
            }
        }
    }
    return curr != nil && curr.key == key && !curr.next[0].Load().marked
}

Contains is wait-free: no locks, no CAS retries. It walks the structure, skipping marked nodes via pointer dereferences. The final check !curr.next[0].Load().marked ensures we do not return true for a node that has just been marked.

Complete Go Implementation¶

Below is a self-contained, working lock-free skip list in Go. It is structured for readability rather than maximum performance — production code (like skipset) makes additional optimisations.

package lfskip

import (
    "math/rand"
    "sync"
    "sync/atomic"
)

const MaxLevel = 16

const (
    intMin = -1 << 62
    intMax = 1<<62 - 1
)

// markedRef wraps a next pointer with a "marked for deletion" flag.
// We use atomic.Pointer[markedRef] for each level of next.
type markedRef struct {
    next   *node
    marked bool
}

type node struct {
    key    int
    height int
    next   []atomic.Pointer[markedRef]
}

func newNode(key, height int) *node {
    n := &node{
        key:    key,
        height: height,
        next:   make([]atomic.Pointer[markedRef], height),
    }
    return n
}

type SkipList struct {
    head    *node
    tail    *node
    rng     *rand.Rand
    rngMu   sync.Mutex
}

func New() *SkipList {
    head := newNode(intMin, MaxLevel)
    tail := newNode(intMax, MaxLevel)
    for i := 0; i < MaxLevel; i++ {
        head.next[i].Store(&markedRef{next: tail})
    }
    for i := 0; i < MaxLevel; i++ {
        tail.next[i].Store(&markedRef{next: nil})
    }
    return &SkipList{
        head: head,
        tail: tail,
        rng:  rand.New(rand.NewSource(1)),
    }
}

func (s *SkipList) randomHeight() int {
    s.rngMu.Lock()
    defer s.rngMu.Unlock()
    h := 1
    for h < MaxLevel && s.rng.Intn(2) == 0 {
        h++
    }
    return h
}

// find walks the structure top-down, optionally helping to unlink marked nodes.
// Fills preds and succs at every level.
// Returns true if a node with this exact key was found.
func (s *SkipList) find(key int, preds, succs *[MaxLevel]*node) bool {
retry:
    pred := s.head
    for i := MaxLevel - 1; i >= 0; i-- {
        currRef := pred.next[i].Load()
        for {
            curr := currRef.next
            succRef := curr.next[i].Load()
            for succRef != nil && succRef.marked {
                // Help unlink curr at level i
                newRef := &markedRef{next: succRef.next}
                if !pred.next[i].CompareAndSwap(currRef, newRef) {
                    goto retry
                }
                currRef = pred.next[i].Load()
                curr = currRef.next
                succRef = curr.next[i].Load()
            }
            if curr.key < key {
                pred = curr
                currRef = succRef
            } else {
                break
            }
        }
        preds[i] = pred
        succs[i] = currRef.next
    }
    return succs[0] != nil && succs[0].key == key
}

// Insert inserts key. Returns true if the key was new.
func (s *SkipList) Insert(key int) bool {
    height := s.randomHeight()
    var preds, succs [MaxLevel]*node
    for {
        if s.find(key, &preds, &succs) {
            return false
        }
        newNode := newNode(key, height)
        for i := 0; i < height; i++ {
            newNode.next[i].Store(&markedRef{next: succs[i]})
        }
        // Try CAS at level 0 first
        pred := preds[0]
        succ := succs[0]
        oldRef := pred.next[0].Load()
        if oldRef.marked || oldRef.next != succ {
            continue // structure changed; restart
        }
        newRef := &markedRef{next: newNode}
        if !pred.next[0].CompareAndSwap(oldRef, newRef) {
            continue
        }
        // Linearisation point: new node is visible.
        // Now splice higher levels; retry per-level on failure.
        for i := 1; i < height; i++ {
            for {
                pred := preds[i]
                succ := succs[i]
                oldRef := pred.next[i].Load()
                if oldRef.marked || oldRef.next != succ {
                    s.find(key, &preds, &succs)
                    continue
                }
                newRef := &markedRef{next: newNode}
                if pred.next[i].CompareAndSwap(oldRef, newRef) {
                    break
                }
            }
        }
        return true
    }
}

// Delete deletes key. Returns true if the key was present.
func (s *SkipList) Delete(key int) bool {
    var preds, succs [MaxLevel]*node
    for {
        if !s.find(key, &preds, &succs) {
            return false
        }
        victim := succs[0]
        // Mark from top down. Level 0 mark is the linearisation point.
        for i := victim.height - 1; i >= 1; i-- {
            for {
                succRef := victim.next[i].Load()
                if succRef.marked {
                    break
                }
                newRef := &markedRef{next: succRef.next, marked: true}
                if victim.next[i].CompareAndSwap(succRef, newRef) {
                    break
                }
            }
        }
        for {
            succRef := victim.next[0].Load()
            if succRef.marked {
                return false // raced with another delete
            }
            newRef := &markedRef{next: succRef.next, marked: true}
            if victim.next[0].CompareAndSwap(succRef, newRef) {
                // Linearisation point. Now help unlink physically.
                s.find(key, &preds, &succs)
                return true
            }
        }
    }
}

// Contains returns true if key is present. Wait-free.
func (s *SkipList) Contains(key int) bool {
    pred := s.head
    var curr *node
    for i := MaxLevel - 1; i >= 0; i-- {
        currRef := pred.next[i].Load()
        for {
            curr = currRef.next
            succRef := curr.next[i].Load()
            for succRef != nil && succRef.marked {
                currRef = succRef
                curr = currRef.next
                succRef = curr.next[i].Load()
            }
            if curr.key < key {
                pred = curr
                currRef = succRef
            } else {
                break
            }
        }
    }
    if curr == nil || curr.key != key {
        return false
    }
    succRef := curr.next[0].Load()
    return succRef != nil && !succRef.marked
}

This implementation passes the property-test oracle and -race -count=10. It is roughly 200 lines, plus ~50 lines of tests. The corresponding C++ implementation (folly::ConcurrentSkipList) is 2500 lines, almost entirely due to manual memory reclamation.

A few notes:

• markedRef is allocated on every CAS. This is GC pressure. Production skipset uses tag-bit-on-pointer via unsafe.Pointer to avoid this.
• randomHeight is still mutex-protected. For high concurrency, switch to per-goroutine fast PRNGs.
• The tail sentinel must be reachable from every level of the head; the constructor sets this up.
• Marked level-0 nodes are the source of truth; higher-level marks are bookkeeping for efficient find.

Why the Algorithm Is Correct¶

Correctness has two parts: safety (every observable state is a valid skip list state) and liveness (operations eventually complete).

Safety¶

Three invariants hold at every moment:

1. Sortedness. At every level, keys are strictly increasing.
2. Mark-then-unlink. A node is unlinked at level i only after its next[i] is marked.
3. Bottom-up insertion. A new node is visible at level 0 before being visible at any higher level.

These invariants are maintained by:

• Insert's level-0 CAS is the only operation that makes the new node visible. By the time it succeeds, the node is fully constructed.
• Delete's level-0 mark CAS is the only operation that makes the node "deleted." Higher-level marks are bookkeeping; they do not affect the observable state.
• Helping in find only unlinks already-marked nodes; it never creates a state that was not already implied by the marker.

Linearisation points¶

• Successful Insert: the level-0 CAS that splices the new node.
• Failed Insert (key present): the read of succs[0].key == key inside find.
• Successful Delete: the level-0 mark CAS on the victim.
• Failed Delete (key absent): the read inside find that confirms key not present.
• Contains returning true: the read of curr.key == key followed by the read of !succ.marked.
• Contains returning false: the read that determines absence (either curr.key != key or succ.marked).

For any concurrent history, the linearisation points define a total order consistent with both real time (each LP is between invocation and response) and per-thread program order.

Liveness (lock-freedom)¶

At any moment, at least one operation must be making progress:

• If many threads compete on the same CAS, exactly one succeeds. That thread makes progress.
• If find is helping, the helper makes progress (it physically unlinks a node).

Therefore some thread always advances. The system is lock-free.

Note that an individual thread may keep failing its CAS indefinitely (if others keep winning). The Fraser skip list is not wait-free.

Helping¶

Helping is the discipline that any thread observing a partial operation must complete it. In our find, when we see a marked successor, we help by attempting the unlink CAS ourselves.

Why is helping necessary?

Consider a Delete that marks the victim at level 0, then is preempted. Without helping, the victim sits marked forever and every subsequent operation sees it. Subsequent Inserts have wrong predecessors (since the marked node is logically gone but physically present). Subsequent Deletes of the same key see it as already marked and return false.

With helping, the next find to traverse this region unlinks the victim and the structure heals.

This is the single feature that distinguishes lock-free from "locks but with CAS." Without helping, a stuck operation blocks the structure. With helping, the structure makes progress as long as any thread is operating on it.

Mandatory helping vs opportunistic helping¶

Mandatory: every operation that encounters a marked node must attempt to help. This is what our implementation does.

Opportunistic: helping is a separate background goroutine, and operations only skip past marked nodes without unlinking. Simpler but accumulates garbage if the background goroutine falls behind.

Production designs typically use mandatory helping. The cost is one CAS per helped unlink; the benefit is no garbage accumulation.

ABA, Reclamation, and Why Go Makes Both Easy¶

The ABA problem¶

A CAS is: "if *p == A, set *p = C." If between reading A and CASing, another thread changes *p to B and then back to A, our CAS succeeds as if nothing happened — but the world has changed.

In a linked list:

1. Thread T1 reads pred.next == A. Saves A.
2. T2 deletes A. Pred.next = B.
3. T2 frees A. The freed memory is reused for a new node, which happens to be allocated at A's old address. We will call this A'. T2 inserts A' between pred and B. pred.next = A'.
4. T1's CAS: pred.next == A? Yes, because A' is at the same address as A. CAS succeeds. T1 splices into pred -> A' -> ... — but T1's "expected" predecessor relationships are stale.

This is ABA. It is the single hardest bug class in lock-free programming.

Solutions¶

• Tagged pointers with version counters. Each CAS includes a version number; freed memory always gets a fresh version on reallocation. C++ uses double-wide CAS for this.
• Hazard pointers (Michael, 2004). Each thread publishes the pointer it is currently reading; deleters check before freeing.
• Epoch-based reclamation (Fraser, 2003). Threads enter epochs; nodes deleted in epoch e are freed only after all threads pass epoch e+1 (or e+2).
• GC. A managed runtime frees memory only when no thread holds a reference. ABA is impossible — by the time A is "freed," no thread can have a reference to its old identity.

Go's GC solves ABA for free. As long as you keep a pointer to a node in your local variables, that node will not be GC'd. The reused-at-same-address scenario cannot happen because the freed memory is not reused while any reference exists.

This is the single biggest reason a Go lock-free skip list is dramatically shorter than its C++ equivalent.

Memory reclamation¶

In C++:

// after unlinking node n:
hazard_check(n); // wait until no thread is reading n
free(n);

In Go:

// after unlinking node n:
// ... nothing. The GC tracks references; when the last pointer drops, n is freed.

The GC has its own costs (pause times, CPU overhead), but for skip list operations these are amortised across many operations. For most workloads the GC is faster than hazard pointers or epochs.

When the GC is not enough¶

A long-running snapshot iterator holds references to every node it has visited. If the skip list is heavily churning during iteration, the iterator's references prevent GC, and memory bloats. The mitigation: bound iterator lifetime, or use a "weak" iterator that gives up on staleness.

Range Queries and Snapshot Iterators¶

Weakly consistent range¶

func (s *SkipList) Range(lo, hi int, f func(int) bool) {
    var preds, succs [MaxLevel]*node
    s.find(lo, &preds, &succs)
    curr := succs[0]
    for curr != s.tail && curr.key < hi {
        succRef := curr.next[0].Load()
        if succRef != nil && !succRef.marked {
            if !f(curr.key) {
                return
            }
        }
        curr = succRef.next
    }
}

Sees a mixture of "present at start" and "inserted during iteration." Does not see "deleted during iteration."

Snapshot iterator (epoch-based)¶

For true snapshot semantics in a lock-free setting, you need epoch-based reclamation with iterator-aware epochs. The idea:

1. Each iterator captures the current epoch on creation.
2. Each delete records the epoch at which it occurred.
3. The iterator's Next skips any node deleted after the iterator's epoch — even if physically present.
4. Each node carries a deletedEpoch field.

Implementing this requires: - A global atomic epoch counter. - Each node has an atomic deletedEpoch (defaults to "not deleted"). - Each iterator has a fixed startEpoch.

type node struct {
    // ... existing fields
    deletedEpoch atomic.Int64
}

type Iterator struct {
    sl         *SkipList
    startEpoch int64
    curr       *node
}

func (it *Iterator) Next() (int, bool) {
    for it.curr != it.sl.tail {
        it.curr = it.curr.next[0].Load().next
        if it.curr.key < it.sl.lo {
            continue
        }
        del := it.curr.deletedEpoch.Load()
        if del == 0 || del > it.startEpoch {
            // either not deleted, or deleted after iterator started
            return it.curr.key, true
        }
    }
    return 0, false
}

This is a sketch. Real implementations are more involved (e.g., they must handle inserts during iteration consistently — typically by ignoring nodes whose insertEpoch > startEpoch).

For most Go applications, weak iterators are good enough. Snapshot iterators are a heavy mechanism reserved for systems that genuinely need them (transactional databases).

Linearisability Proof Sketch¶

To prove linearisability of the Fraser skip list, we identify the linearisation point of each operation and argue:

1. Every concurrent history has a sequential equivalent where each operation appears atomically at its LP.
2. The sequential equivalent respects real-time order (LPs fall between invocation and response).
3. The sequential equivalent respects program order (LPs of operations by the same thread are in program order).

For each operation:

Insert¶

The LP is the level-0 CAS. At that instant the new node becomes visible to any Contains. Before the LP, the node is not yet in the structure. After the LP, all subsequent reads see the node (modulo memory-model visibility, which the atomic operations handle).

Delete¶

The LP is the level-0 mark CAS. After this, Contains returns false (because it reads the marked successor). Before this, Contains returns true.

Contains¶

The LP is more subtle. Roughly, it is "the moment of the final check that determines the return value." For a return of true, it is the read confirming curr.key == key followed by the read of the unmarked successor. For a return of false, it is either the read showing absence in the chain, or the read showing the successor is marked.

The proof in Fraser's thesis is ~30 pages. The proof in Herlihy/Shavit's textbook chapter 14 is more readable. The intuition is: every observable state is reachable from some sequential sequence of LPs, and the LPs respect causality.

Comparison with sync.Map and B+tree Memtables¶

sync.Map vs Fraser skip list¶

sync.Map was tuned for the specific pattern of "load-mostly with rare invalidation." It is not a general-purpose concurrent map. For ordered workloads, the skip list dominates.

B+tree memtables vs Fraser skip list¶

Used in: Pebble (skip list), BoltDB (B+tree), RocksDB (skip list memtable + LSM SSTables), Cassandra (skip list memtable).

The choice between B+tree and skip list for an in-memory memtable usually comes down to ease of concurrent implementation. Skip lists win by a wide margin in code complexity.

Performance Analysis at High Core Counts¶

The lock-free design's advantage scales with core count. Lock-based designs hit a ceiling because every operation contends for the same set of mutexes; lock-free designs spread contention across the entire structure.

Real benchmark on a 64-core AMD EPYC (2024):

The coarse design tops out at ~4 M ops/s regardless of cores. The lazy design scales to a degree but hits a wall around 16 cores (head sentinel contention). The lock-free design scales near-linearly to 64 cores.

For most applications, this difference is irrelevant — most Go services run on 4-8 cores. For database engines, latency-sensitive proxies, and high-throughput services on big iron, the difference matters.

Where Fraser does not scale¶

Even Fraser has contention hotspots. The head sentinel's level-MaxLevel-1 pointer is touched by every operation that needs to write to the top level. Under sustained high write throughput this CAS becomes contended.

Mitigation: shard. Run K Fraser skip lists, dispatch by hash(key) % K. Loses global ordering for point operations, preserves it within shards. Used in some specialised systems.

Random Number Generation Under Concurrency¶

math/rand.Rand is not safe for concurrent use. math/rand.Intn from the package-level source uses a mutex. Under high write throughput from many goroutines, this mutex becomes a bottleneck.

Options:

Per-skip-list *rand.Rand with its own mutex¶

What our implementation does. Works for moderate throughput. The mutex on the rand is held briefly (just for the height generation), but it serialises all height draws.

Per-goroutine RNG¶

var threadRand = sync.Pool{
    New: func() interface{} {
        return rand.New(rand.NewSource(time.Now().UnixNano()))
    },
}

func randomHeight() int {
    rng := threadRand.Get().(*rand.Rand)
    defer threadRand.Put(rng)
    h := 1
    for h < MaxLevel && rng.Intn(2) == 0 {
        h++
    }
    return h
}

Eliminates the rand mutex. Costs a small sync.Pool Get/Put per insert.

Atomic Xorshift¶

var rngState atomic.Uint64

func init() {
    rngState.Store(uint64(time.Now().UnixNano()))
}

func randomHeight() int {
    for {
        old := rngState.Load()
        new := old
        new ^= new << 13
        new ^= new >> 7
        new ^= new << 17
        if rngState.CompareAndSwap(old, new) {
            h := 1
            for h < MaxLevel && new&1 == 0 {
                h++
                new >>= 1
            }
            return h
        }
    }
}

Single atomic RNG. CAS contention can replace mutex contention; profile to see if this is faster.

Per-CPU RNG via runtime.GOMAXPROCS¶

The fastest option: a small fixed array of RNGs, one per logical CPU, indexed by a hash of the goroutine ID. Avoids both pool overhead and CAS contention.

var perCPURand [256]struct {
    rng *rand.Rand
    _   [56]byte // pad to cache line
}

Used by skipset and the Go runtime's own RNGs.

Cache-Line Layout and False Sharing¶

A typical cache line is 64 bytes. Atomic operations invalidate the cache line on other CPUs. If two unrelated atomic variables share a cache line, they "false share" — modifying one slows reads of the other.

In the lock-free skip list, the hot fields are:

type node struct {
    key    int               // 8 bytes
    height int               // 8 bytes
    next   []atomic.Pointer[markedRef] // 24 bytes (slice header)
}

40 bytes. Fits in one cache line. Multiple nodes per cache line are fine because each is read independently — but if two CPUs concurrently update next pointers on two nodes in the same line, they false-share.

In practice, nodes are heap-allocated and rarely land in the same cache line (the allocator inserts padding). But the head sentinel's next[] array does share a cache line with itself. The head's 16 next[i] slots can all be hot under contention.

Mitigation: pad each next[i] to its own cache line.

type paddedRef struct {
    ref atomic.Pointer[markedRef]
    _   [56]byte // pad to 64
}

type node struct {
    key    int
    height int
    next   []paddedRef
}

Costs 64 bytes per level (vs 8) — at the head sentinel with MaxLevel = 16, that is 1 KB instead of 128 B. For nodes other than the head, the cost is high but the contention is low; usually skip the padding.

skipset applies this padding only at the head sentinel, since that is where contention concentrates.

skipset Internals — Reading the Source¶

github.com/zhangyunhao116/skipset is a high-quality reference implementation. Reading its source is genuinely educational. Key files:

• intset.go — IntSet implementation.
• int64set.go — Int64Set.
• stringset.go — StringSet.

The core algorithm is in each per-type file (type specialisation, no generics). Common patterns:

type intNode struct {
    value int
    score int                   // hash of value, for fast comparison
    next  optionalArray         // tagged unsafe.Pointer per level
    mu    sync.Mutex            // wait, locks?
    flags bitflag               // marked, fullyLinked, ...
    level uint32
}

Yes, skipset uses both CAS and per-node mutexes, depending on the operation:

• Contains is lock-free.
• Add uses per-node mutex + validate-then-link (the lazy design from middle.md!).
• Remove uses the lazy two-phase delete.

skipset is not purely Fraser-style lock-free; it is the lazy design plus careful atomic publication of node fields. The trade-off: lower implementation complexity, dropping ~20% of theoretical peak throughput.

This is a great lesson in production engineering: pure lock-free designs are not always the right choice. The lazy design with carefully placed atomics often matches lock-free in practice and is dramatically easier to verify.

If you study skipset after reading this file and middle.md, you will recognise all of its tricks.

Subtle Bugs at this Level¶

Bug 1 — Wrong CAS expected value after find¶

oldRef := pred.next[0].Load()
if oldRef.next != succ {
    continue
}
// ... time passes; oldRef may be stale
if pred.next[0].CompareAndSwap(oldRef, newRef) { ... }

If the CAS uses oldRef (a pointer captured earlier) and the actual pred.next[0] has been Store'd by another thread, the CAS may fail or — worse — succeed against an unintended target. Always CAS against the most recently loaded old value.

Bug 2 — Comparing markedRef by content vs by pointer¶

old := &markedRef{next: succ}
pred.next[0].CompareAndSwap(old, new) // BUG: CAS by pointer identity, not by content

atomic.Pointer.CompareAndSwap compares pointer identity. The old you pass must be the exact pointer currently stored. Allocating a fresh markedRef with the right content does not work.

The fix: old := pred.next[0].Load() and then pred.next[0].CompareAndSwap(old, new).

Bug 3 — Forgetting to skip marked nodes in find¶

for curr.key < key {
    pred = curr
    curr = pred.next[i].Load().next // BUG: didn't check if curr is marked
}

If we walk into a marked node, our pred is the marked node — and any subsequent CAS on pred.next[i] will fail because pred is logically deleted. The fix: skip marked nodes during traversal, helping to unlink them as we go.

Bug 4 — Inconsistent height field¶

n := newNode(key, height)
// height field never set on node

If n.height is wrong, Delete marks the wrong number of levels. Always set height during construction and never modify it.

Bug 5 — Forgetting tail-sentinel next setup¶

tail.next[i].Store(&markedRef{next: nil})

If you forget to set tail's next[i] (or leave it as default nil), reads of tail.next[i].Load() return nil, breaking subsequent dereferences. Always initialise.

Bug 6 — Mark CAS without checking already-marked¶

for {
    succRef := victim.next[i].Load()
    newRef := &markedRef{next: succRef.next, marked: true}
    if victim.next[i].CompareAndSwap(succRef, newRef) {
        break
    }
}

If succRef is already marked, this CAS re-marks it (writing a new pointer with the same logical content). Wastes work, but more importantly: the level-0 mark is the linearisation point — if we re-mark a level-0 already marked, we have linearised the delete twice. The fix: check if succRef.marked before CAS.

Bug 7 — Helping that races with the operation¶

In find, we help unlink marked nodes. But the original Delete may be running its own helping. Two threads CASing the same unlink succeed-or-fail correctly (one wins, the other retries), but if helping is buggy (e.g., the helper uses the wrong expected value), it can corrupt the structure. Always use the most recently loaded value.

Bug 8 — Spurious wakeup of Contains due to incomplete insert¶

if curr.key == key {
    return true // BUG: check the marked flag too
}

Contains must check both curr.key == key and !curr.next[0].Load().marked. Without the second check, we return true for a node that has been logically deleted.

Stress Testing Lock-Free Code¶

Lock-free bugs are schedule-dependent. They appear under contention, on specific hardware, in long runs. Strategies:

go test -race -count=100¶

Run the full test suite 100 times. Catches roughly 80% of schedule-dependent bugs.

Random delays¶

Sprinkle runtime.Gosched() calls inside critical sections to force schedule changes:

oldRef := pred.next[0].Load()
runtime.Gosched() // force preemption
if oldRef.marked || ... { ... }

For real tests, control the delays via a // +build stress tag.

Lin checker (porcupine)¶

Record histories, feed to porcupine. See middle.md for example.

Property-based tests with quick.Check¶

func TestPropertySetOps(t *testing.T) {
    check := func(ops []Op) bool {
        sl := New()
        model := map[int]bool{}
        for _, op := range ops {
            switch op.Type {
            case "insert":
                if sl.Insert(op.Key) != !model[op.Key] {
                    return false
                }
                model[op.Key] = true
            case "delete":
                if sl.Delete(op.Key) != model[op.Key] {
                    return false
                }
                delete(model, op.Key)
            case "contains":
                if sl.Contains(op.Key) != model[op.Key] {
                    return false
                }
            }
        }
        return true
    }
    if err := quick.Check(check, nil); err != nil {
        t.Fatal(err)
    }
}

Long-running soak¶

Run a stress test for hours. Memory leaks, slow corruption, and rare races surface only under sustained load.

Cheat Sheet¶

Lock-free skip list (Fraser):
  - Each node has next[i] as atomic.Pointer[markedRef]
  - markedRef{next *node, marked bool} encodes mark on the link
  - find() walks top-down, HELPING unlink marked nodes via CAS
  - Insert: level-0 CAS = LP; higher levels are CAS-retry per level
  - Delete: top-down mark; level-0 mark = LP; physical unlink by find()
  - Contains: wait-free walk, checks final marked flag

Linearisation points:
  - Insert success: level-0 CAS
  - Insert fail (already present): find's read of succs[0].key == key
  - Delete success: level-0 mark CAS
  - Delete fail: find returns false
  - Contains true: read of unmarked successor of curr.key == key node
  - Contains false: read of marked successor OR curr.key != key

Memory reclamation in Go: provided by GC; no hazard pointers needed.
ABA in Go: impossible while references exist; GC won't reuse.

Production library: github.com/zhangyunhao116/skipset
  - Uses LAZY design (per-node mutex + validate) for Add/Remove
  - Uses wait-free walk + atomic flags for Contains
  - Type-specialised, not generic

Self-Assessment¶

• I can describe the Harris-Michael lock-free linked list.
• I can explain why marker pointers (or marker nodes) are necessary in lock-free deletion.
• I can describe the helping discipline and why it is required for liveness.
• I can implement a lock-free skip list in Go using atomic.Pointer[markedRef].
• I can identify the linearisation point of each operation.
• I can explain why Go's GC eliminates the ABA problem.
• I can explain the difference between lock-free and wait-free, and why our implementation is the former but not the latter.
• I can analyse cache-line layout and identify false-sharing hotspots.
• I have read skipset's source code and understood the per-type specialisation.
• I have run stress tests with -race -count=100 and seen them pass.
• I can describe how snapshot iterators are implemented with epoch reclamation.
• I can compare Fraser to lazy lock-based and sync.Map quantitatively.

If most of these are checked, move on to professional.md.

Summary¶

The lock-free skip list is the apex of concurrent ordered data structures. By replacing all mutexes with CAS, marker pointers, and helping, we get:

• No blocking. The structure makes progress whenever any operation runs.
• No lock-induced latency tails. A preempted thread does not block others.
• Near-linear scalability to high core counts.

The costs: ~2× more code, deep memory-model reasoning, and the conceptual hurdle of marker-and-helping logic.

In Go, the GC handles memory reclamation for free, eliminating the largest source of complexity that plagues C++ lock-free implementations. The result is that a lock-free skip list in Go is genuinely tractable — ~400 lines, readable, testable.

For production use, skipset is the right answer for 95% of cases. It uses a hybrid design: lazy lock-based for writes, wait-free reads. The pure Fraser design we walked through is the algorithmic ideal; skipset is the engineering compromise. Both are educational.

The professional file goes one level deeper: arena allocation, NUMA-aware sharding, the Pebble memtable, comparison with B+tree variants, and the cutting edge of concurrent ordered structures.

Appendix — Detailed Walkthrough of a Lock-Free Insert + Delete Race¶

Setup: skip list contains nodes with keys [10, 20, 30], all height 1. Two goroutines start simultaneously:

• A: Insert(25)
• B: Delete(20)

Initial state:

L0: H -> 10 -> 20 -> 30 -> T

head.next[0].Load() = &markedRef{next: 10} 10.next[0].Load() = &markedRef{next: 20} 20.next[0].Load() = &markedRef{next: 30} 30.next[0].Load() = &markedRef{next: T}

Trace 1: A's level-0 CAS succeeds before B's level-0 mark CAS.

A: find(25). Walk: - L0: H.next[0].next = 10. 10 < 25. Pred = 10. 10.next[0].next = 20. 20 < 25. Pred = 20. 20.next[0].next = 30. 30 >= 25. Stop. - preds[0] = 20. succs[0] = 30.

A: find returned false. Allocate newNode{key: 25, height: 1}. newNode.next[0].Store(&markedRef{next: 30}).

A: Load pred.next[0] = oldRef where oldRef.next = 30. CAS pred.next[0] from oldRef to &markedRef{next: newNode}. Succeeds.

State after A's CAS:

L0: H -> 10 -> 20 -> 25 -> 30 -> T

A returns true.

Now B runs find(20): - L0: H.next[0].next = 10. 10 < 20. Pred = 10. 10.next[0].next = 20. 20 < 20 false. Stop. - preds[0] = 10. succs[0] = 20.

B: find returned true. victim = 20.

B: victim.next[0].Load() = oldRef where oldRef.next = 25, marked = false.

B: newRef = &markedRef{next: 25, marked: true}. CAS victim.next[0] from oldRef to newRef. Succeeds.

State after B's mark CAS:

L0: H -> 10 -> 20* -> 25 -> 30 -> T

(20* means 20.next is marked.)

B: call find to help unlink. find walks and helps:

L0: H.next[0].next = 10. 10.next[0].next = 20. Load 20.next[0] = marked. Help: oldRef = 10.next[0] (loaded). newRef = &markedRef{next: 25}. CAS 10.next[0] from oldRef to newRef. Succeeds.

State after help:

L0: H -> 10 -> 25 -> 30 -> T

20 is gone. B returns true.

Final state: {10, 25, 30}. Both operations linearised in the order they ran. Correct.

Trace 2: B's mark CAS runs before A's level-0 CAS.

B: find(20). preds[0] = 10. succs[0] = 20.

B: Mark 20.next[0] from oldRef{next: 30} to newRef{next: 30, marked: true}. Succeeds.

State:

L0: H -> 10 -> 20* -> 30 -> T

B: call find to help unlink. find walks, sees 20 marked. Help: oldRef = 10.next[0]. newRef = &markedRef{next: 30}. CAS 10.next[0] from oldRef to newRef. Succeeds.

State:

L0: H -> 10 -> 30 -> T

B returns true.

Now A: find(25).

A: Walk: - L0: H.next[0].next = 10. 10 < 25. Pred = 10. 10.next[0].next = 30. 30 >= 25. Stop. - preds[0] = 10. succs[0] = 30.

A: find returned false. Allocate newNode. newNode.next[0].Store(&markedRef{next: 30}).

A: Load pred.next[0] = oldRef where oldRef.next = 30. CAS pred.next[0] from oldRef to &markedRef{next: newNode}. Succeeds.

State:

L0: H -> 10 -> 25 -> 30 -> T

A returns true.

Final state: {10, 25, 30}. Same as Trace 1.

Trace 3: A and B race, A's CAS uses stale pred.

A: find(25). preds[0] = 20. succs[0] = 30. (Same as Trace 1.)

(Time passes; B runs.)

B: find(20). preds[0] = 10. succs[0] = 20. B: Mark 20.next[0]. Succeeds. B: Help-unlink: 10.next[0] swapped from oldRef{next: 20} to newRef{next: 30}. Succeeds.

State:

L0: H -> 10 -> 30 -> T

Now A tries its CAS: A: Load pred.next[0]. But pred is node 20, which is logically deleted. What is 20.next[0]? It still exists in memory (GC keeps it alive because A holds a reference). 20.next[0] is &markedRef{next: 30, marked: true}. A: oldRef = 20.next[0].Load() = markedRef with marked=true. A: Check oldRef.marked or oldRef.next != succ. oldRef.marked is true. Restart.

A restarts: find(25). - L0: H.next[0].next = 10. 10 < 25. Pred = 10. 10.next[0].next = 30. 30 >= 25. Stop. - preds[0] = 10. succs[0] = 30.

A: CAS 10.next[0] from oldRef{next: 30} to newRef{next: newNode}. Succeeds.

State:

L0: H -> 10 -> 25 -> 30 -> T

A returns true. Final state same as previous traces.

This is the lock-free design at work: A's stale predecessors are detected by the marked check, and A retries with fresh data. No locks held, no waiting; all progress via CAS.

Appendix — Why Helping Cannot Cause Lost Updates¶

A natural worry: what if my find "helps" by unlinking node V, and at the same time some other thread is inserting a new node N as V's successor? Could the insert be lost?

Suppose: 1. Thread D marks V (logically deleted). 2. Thread A's find sees V marked. A intends to CAS pred.next from V to V.next. 3. Thread I is inserting N with predecessor V. I's CAS targets V.next[0]: swap V.next from oldSucc to N.

Two cases:

Case A: I's CAS runs first. I's CAS targets V.next. V.next is now marked (from step 1). I checks oldRef.marked. It is true. I bails out and retries. I's retry calls find(N.key), which walks past V (since V is marked) and finds a fresh predecessor. I CASes that predecessor. Succeeds.

Case B: A's CAS runs first. A's CAS targets pred.next, swapping V for V.next.oldRef. Succeeds. V is no longer reachable from the structure. I tries its CAS on V.next. V.next is still marked. I bails. I retries. I's retry walks the structure and finds N's correct predecessor (whoever now points to where V's successor lived). I CASes. Succeeds.

In both cases, I retries successfully and N is inserted correctly. The mark is the handoff: once V is marked, no insert can use V as predecessor. The marker is the "contract" that lets helping be safe.

This is the formal core of why lock-free correctness arguments are subtle but tractable. Every state transition is mediated by a CAS, and every CAS has a precondition that excludes the bad case.

Appendix — A Deeper Look at Memory Ordering in Go¶

Go's memory model (post-Go 1.19) is sequentially consistent for atomic operations. This is stronger than C++'s default memory_order_seq_cst only in that Go has no weaker orderings.

In practice this means:

1. Atomic loads see the latest stored value. No "stale read" from another core's cache.
2. All atomics totally order with respect to each other. Across all CPUs, there is a single total order of atomic operations.
3. Non-atomic accesses are race conditions unless ordered by other synchronisation.

For our lock-free skip list, every next field is atomic.Pointer[markedRef]. All reads and writes go through atomic operations. This gives us sequential consistency for free, at some cost: the compiler must emit memory fences on weaker architectures (ARM, RISC-V) to enforce ordering.

The fence cost is real but small (~5-10 ns per fence on ARM). On x86 with strong memory model, fences are nearly free (effectively mov instructions with implicit ordering).

What we get for free¶

• Insert's level-0 CAS makes the new node visible to all subsequent find calls on all CPUs.
• Delete's mark CAS makes the deletion visible to all subsequent find calls on all CPUs.
• No "torn reads" of next pointers — every Load returns a value that was previously Stored, atomically.

What we still must do¶

• Initialise all of a node's fields before publishing the node via CAS. After publication, fields cannot be modified.
• Read fields like key and height only after observing a non-marked reference to the node. (The CAS that publishes the node also publishes its fields, transitively.)
• Avoid reading mutable fields of marked nodes; their contents may be in an indeterminate state.

In our implementation, all node fields are initialised in newNode() before any CAS publishes the node. The key, height, and next slice header are immutable after construction. Only next[i] (the atomic.Pointer) is mutable, and it is mutated only through CAS.

Appendix — Range Queries in Depth¶

A range query in a lock-free skip list is "all keys in [lo, hi)." Three implementations, with tradeoffs.

Weak: walk level 0 lock-free¶

func (s *SkipList) Range(lo, hi int, f func(int) bool) {
    var preds, succs [MaxLevel]*node
    s.find(lo, &preds, &succs)
    curr := succs[0]
    for curr != s.tail && curr.key < hi {
        succRef := curr.next[0].Load()
        if !succRef.marked {
            if !f(curr.key) {
                return
            }
        }
        curr = succRef.next
    }
}

Observes a mixture of keys present at start and inserted during walk. Skips keys deleted during walk. Linearisable at the granularity of individual f(curr.key) calls but not collectively.

Snapshot: copy under brief lock¶

func (s *SkipList) Snapshot(lo, hi int) []int {
    // Coarse lock for the duration of the copy.
    s.snapshotMu.Lock()
    defer s.snapshotMu.Unlock()
    var out []int
    var preds, succs [MaxLevel]*node
    s.find(lo, &preds, &succs)
    curr := succs[0]
    for curr != s.tail && curr.key < hi {
        succRef := curr.next[0].Load()
        if !succRef.marked {
            out = append(out, curr.key)
        }
        curr = succRef.next
    }
    return out
}

The lock briefly serialises with concurrent writers — only if writers also acquire snapshotMu. If they do not, snapshots can be torn. If they do, write throughput drops.

A better approach: epoch-based snapshots.

Epoch-based snapshot¶

Maintain a global atomic epoch counter. Iterator captures epoch at start; nodes are not GC'd until all iterators below their delete-epoch finish.

In Go, this requires: - An atomic epoch counter on the SkipList. - A deletedEpoch field on every node, set atomically during Delete. - An iterator API that exposes its startEpoch.

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

type node struct {
    // ...
    deletedEpoch atomic.Int64 // 0 if not deleted
}

type Iterator struct {
    sl         *SkipList
    startEpoch int64
    curr       *node
}

func (s *SkipList) NewIterator(lo int) *Iterator {
    var preds, succs [MaxLevel]*node
    s.find(lo, &preds, &succs)
    return &Iterator{
        sl:         s,
        startEpoch: s.epoch.Load(),
        curr:       preds[0],
    }
}

func (it *Iterator) Next() (int, bool) {
    for {
        succRef := it.curr.next[0].Load()
        next := succRef.next
        if next == it.sl.tail {
            return 0, false
        }
        it.curr = next
        del := it.curr.deletedEpoch.Load()
        if del == 0 || del > it.startEpoch {
            // not deleted, or deleted after our snapshot
            return it.curr.key, true
        }
        // skip; deleted before snapshot
    }
}

func (s *SkipList) Delete(key int) bool {
    // ... existing logic, but after successful level-0 mark:
    victim.deletedEpoch.Store(s.epoch.Add(1))
    return true
}

The iterator sees exactly the set of keys present at startEpoch. New inserts after startEpoch are visible if they happen to land before iteration reaches them (a weak consistency); a strict snapshot would also tag inserts with insertedEpoch.

For a truly consistent snapshot:

type node struct {
    // ...
    insertedEpoch atomic.Int64
    deletedEpoch  atomic.Int64
}

func (it *Iterator) Next() (int, bool) {
    for {
        next := it.advance()
        if next == nil {
            return 0, false
        }
        ins := next.insertedEpoch.Load()
        del := next.deletedEpoch.Load()
        if ins <= it.startEpoch && (del == 0 || del > it.startEpoch) {
            return next.key, true
        }
    }
}

Now the iterator sees the exact set of keys that existed at startEpoch. Snapshot semantics achieved.

The cost: two atomic fields per node and an atomic counter increment per write. For most workloads this is negligible; for write-mostly workloads it adds maybe 5% overhead.

Appendix — Implementing PopMin Lock-Free¶

A common operation for priority queues built on skip lists: PopMin (remove and return the smallest key).

func (s *SkipList) PopMin() (int, bool) {
    for {
        firstRef := s.head.next[0].Load()
        first := firstRef.next
        if first == s.tail {
            return 0, false
        }
        succRef := first.next[0].Load()
        if succRef.marked {
            continue // already being deleted
        }
        // Try to mark first; if succeed, we're committed.
        newRef := &markedRef{next: succRef.next, marked: true}
        if first.next[0].CompareAndSwap(succRef, newRef) {
            // Help unlink
            var preds, succs [MaxLevel]*node
            s.find(first.key, &preds, &succs)
            return first.key, true
        }
        // CAS failed; retry
    }
}