Implementing a Lock-Free SkipList in Go for Concurrent In-Memory Indexes

In high-throughput, latency-critical backend applications—such as real-time bidding engines, distributed key-value stores, and database index managers—concurrent write performance is often the primary bottleneck. When ingestion pipelines scale to process hundreds of thousands of updates per second across dozens of CPU cores, traditional synchronization mechanisms like read-write mutexes (sync.RWMutex) or even fine-grained lock architectures hit a performance wall. CPU cores spend more time contesting locks, bouncing cache lines, and context-switching parked threads than executing actual work. To bypass these kernel-level bottlenecks, high-performance systems use lock-free data structures. The lock-free SkipList is the standard choice for concurrent in-memory indexes (such as LSM-tree memtables in Badger and Pebble), offering $O(\log n)$ search, insertion, and deletion without locking.

The Performance Cliff of Lock-Based Indexes

Many developers start with a standard SkipList or balanced tree and wrap it in a sync.RWMutex. While this is safe, it does not scale. Under write contention, a read-write lock degrades rapidly. To understand why, we must look at how the Go runtime and the Linux kernel manage lock acquisition:

1. Cache Line Bouncing: A sync.Mutex contains state fields that are updated atomically. When multiple cores attempt to acquire the lock concurrently, they execute atomic instructions (like LOCK CMPXCHG on x86-64) on the mutex’s state. This forces the underlying cache line to continuously bounce between CPU cores via the MESI cache coherence protocol, stalling the CPU pipelines.
2. Goroutine Parking and Context Switches: If a thread or goroutine cannot acquire a lock, the Go runtime transitions it to the _Gwaiting state via gopark. The scheduler must save the goroutine’s registers, select another runnable goroutine, and swap the execution context. If no other goroutines are runnable, the operating system thread (M) itself may sleep, incurring a Linux kernel context switch costing 1 to 2 microseconds.
3. Reader-Writer Starvation: Although read-write locks allow concurrent readers, a single writer will block all new readers. In highly concurrent systems, this creates queuing delay spikes, blowing out the p999 tail latency.

A lock-free SkipList replaces locks with Compare-And-Swap (CAS) operations. Goroutines do not block; they perform optimistic operations and retry on failure. If thread A updates a node pointer concurrently with thread B, one will succeed and the other will simply reread the updated pointer and attempt its operation again, keeping CPU execution entirely in user space.

The Architecture of a Lock-Free SkipList

A SkipList is a probabilistic data structure composed of multiple forward-linked chains. The bottom layer (level 0) is a fully sorted linked list containing all elements. Each successive higher level acts as an “express lane,” bypassing chunks of the list to accelerate searches.

Level 2: Head -----------------------> [Node 15] ------------------------> Tail
Level 1: Head -----------> [Node 8] -> [Node 15] ----------> [Node 22] --> Tail
Level 0: Head -> [Node 4]-> [Node 8] -> [Node 15] -> [Node 19]-> [Node 22] --> Tail

To make a SkipList lock-free, we rely on the Harris-Michael algorithm. The core challenge of lock-free linked lists is concurrent deletion. If thread A is inserting node $X$ next to node $B$, while thread B is concurrently deleting node $B$:

1. Thread A reads $B \to C$ and prepares to insert $X$ as $B \to X \to C$.
2. Thread B concurrently deletes $B$ by changing $A.next$ from $B$ to $C$.
3. Thread A executes its CAS to set $B.next = X$.
4. The CAS succeeds, but node $X$ is now attached to the deleted node $B$. Node $X$ is lost to any readers traversing from $Head$.

To prevent this, the Harris-Michael algorithm introduces pointer tagging (logical deletion). Before unlinking a node physically, a deleter must atomically “mark” the node’s next pointer. Once a pointer is marked, any concurrent CAS attempting to insert a node adjacent to it will fail because the pointer value has changed.

The Go GC Challenge with Pointer Tagging

In C/C++, pointer addresses are 8-byte aligned on 64-bit systems, meaning the lowest 3 bits of any node pointer are always zero. Developers tag a pointer by setting the lowest bit to 1:

tagged_ptr = (Node*)( (uintptr_t)raw_ptr | 1 );

This works because memory management is manual. In Go, however, doing this with unsafe.Pointer violates the runtime’s memory model. Go’s concurrent garbage collector (GC) traces pointers to determine liveness. If a pointer address is modified with bitwise operations, the GC will either fail to trace the object (resulting in premature reclamation) or panic with a “bad pointer” runtime error.

To implement pointer tagging safely in Go without breaking the GC, we introduce an intermediate indirection: the Link struct wrapper. Instead of storing direct node pointers, each node level contains an unsafe.Pointer to a Link struct. The Link struct holds a clean pointer to the next Node and an explicit boolean marked flag.

// snippet-1
package skiplist

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

const MaxLevel = 16

type Node struct {
	key   int
	value interface{}
	// next holds unsafe.Pointer pointing to *Link for each level
	next []unsafe.Pointer
}

type Link struct {
	node   *Node
	marked bool
}

type SkipList struct {
	head *Node
	tail *Node
}

func NewSkipList() *SkipList {
	// Initialize sentinels with minimum and maximum values
	tail := &Node{
		key:  math.MaxInt,
		next: make([]unsafe.Pointer, MaxLevel),
	}
	head := &Node{
		key:  math.MinInt,
		next: make([]unsafe.Pointer, MaxLevel),
	}
	// All levels of head initially point to tail
	for i := 0; i < MaxLevel; i++ {
		initialLink := &Link{node: tail, marked: false}
		head.next[i] = unsafe.Pointer(initialLink)
	}
	return &SkipList{
		head: head,
		tail: tail,
	}
}

Atomic Operations and Link Coordination

To manage the list pointers lock-free, we define helpers that execute atomic loads and CAS operations on the unsafe.Pointer fields containing our Link structures.

// snippet-2
// getLink atomically loads the Link at a given node level.
func getLink(n *Node, level int) *Link {
	ptr := atomic.LoadPointer(&n.next[level])
	return (*Link)(ptr)
}

// casLink attempts to atomically update the Link at a node level.
func casLink(n *Node, level int, expected, newLink *Link) bool {
	return atomic.CompareAndSwapPointer(
		&n.next[level],
		unsafe.Pointer(expected),
		unsafe.Pointer(newLink),
	)
}

// markLink marks a node's next pointer as logically deleted at the specified level.
func markLink(n *Node, level int) bool {
	for {
		current := getLink(n, level)
		if current == nil || current.marked {
			return false // Already marked or nil
		}
		markedLink := &Link{
			node:   current.node,
			marked: true,
		}
		if casLink(n, level, current, markedLink) {
			return true
		}
	}
}

Implementing the Harris-Michael Search Routine

The foundation of both insertion and deletion is the search routine (traditionally named find). The find function does two things:

1. It traverses the SkipList from the top level down, locating the predecessor (preds) and successor (succs) nodes for the target key at each level.
2. It physically cleans up the list. If it encounters a logically deleted node (where the next link has marked == true), it attempts to unlink it physically using a CAS.

// snippet-3
// find searches for the key and populates preds and succs for all levels.
// It physically removes logically deleted (marked) nodes that it encounters.
func (s *SkipList) find(key int, preds []*Node, succs []*Node) bool {
retry:
	for {
		curr := s.head
		for level := MaxLevel - 1; level >= 0; level-- {
			pred := curr
			link := getLink(pred, level)

			for {
				if link == nil {
					break
				}
				succ := link.node

				// Check if the successor is logically deleted
				succLink := getLink(succ, level)
				if succLink != nil && succLink.marked {
					// The successor is marked, physically unlink it
					newLink := &Link{
						node:   succLink.node,
						marked: false,
					}
					if !casLink(pred, level, link, newLink) {
						// CAS failed due to concurrent modification, restart search
						continue retry
					}
					// Physical unlink succeeded, reload link and continue traversal
					link = getLink(pred, level)
					continue
				}

				if succ.key >= key {
					curr = pred
					preds[level] = pred
					succs[level] = succ
					break
				}

				pred = succ
				link = succLink
			}
		}
		return succs[0].key == key
	}
}

Insertion: Optimistic Link Promotion

To insert a new node, we first generate a random level height using a geometric distribution. We then call find to get the placement arrays. We link the new node’s levels to its successors, then attempt to swap the level-0 predecessor link to point to our new node.

Once the level-0 CAS succeeds, the node is officially a member of the set. Subsequent threads traversing the list will find it. If any upper-level CAS fails due to concurrent structural updates, we run find again to update our pointers and retry.

// snippet-4
func (s *SkipList) Insert(key int, value interface{}) bool {
	preds := make([]*Node, MaxLevel)
	succs := make([]*Node, MaxLevel)
	level := randomLevel()
	
	newNode := &Node{
		key:   key,
		value: value,
		next:  make([]unsafe.Pointer, level),
	}

	for {
		if s.find(key, preds, succs) {
			// Key already exists (unique constraint violation)
			return false
		}

		// Initialize newNode's next pointers to point to successors
		for i := 0; i < level; i++ {
			newNode.next[i] = unsafe.Pointer(&Link{node: succs[i], marked: false})
		}

		// Attempt to insert at level 0 first
		pred := preds[0]
		succ := succs[0]
		currLink := getLink(pred, 0)
		if currLink.marked || currLink.node != succ {
			continue // Contention detected, retry loop
		}

		newLink := &Link{node: newNode, marked: false}
		if !casLink(pred, 0, currLink, newLink) {
			continue // CAS failed, retry
		}

		// Insert into upper levels
		for i := 1; i < level; i++ {
			for {
				pred = preds[i]
				succ = succs[i]

				currLink = getLink(pred, i)
				if currLink.marked || currLink.node != succ {
					s.find(key, preds, succs)
					break
				}

				// Update newNode's next field if successor changed during upper level promotion
				newNodeLink := getLink(newNode, i)
				if newNodeLink == nil || newNodeLink.node != succ {
					atomic.StorePointer(&newNode.next[i], unsafe.Pointer(&Link{node: succ, marked: false}))
				}

				insertLink := &Link{node: newNode, marked: false}
				if casLink(pred, i, currLink, insertLink) {
					break // Promotion succeeded for this level
				}
				// Promotion failed, update predecessors/successors and retry
				s.find(key, preds, succs)
			}
		}
		return true
	}
}

func randomLevel() int {
	lvl := 1
	for lvl < MaxLevel && rand.Float64() < 0.5 {
		lvl++
	}
	return lvl
}

Deletion: Two-Step Unlinking

Deletion in the lock-free SkipList is a two-step sequence:

1. Logical Deletion: We mark the node’s next links starting from the top level down to level 0. Once the level-0 link is marked, the node is logically deleted. Readers will ignore it, and concurrent inserts will fail to link next to it.
2. Physical Deletion: We run the find routine. Because find physically unlinks any marked nodes it encounters, executing it once immediately cleans up the node from the main memory path.

// snippet-5
func (s *SkipList) Delete(key int) bool {
	preds := make([]*Node, MaxLevel)
	succs := make([]*Node, MaxLevel)

	for {
		if !s.find(key, preds, succs) {
			return false // Key doesn't exist
		}

		nodeToDelete := succs[0]

		// Mark upper level links first (prevents search paths from using them)
		for i := len(nodeToDelete.next) - 1; i >= 1; i-- {
			for {
				link := getLink(nodeToDelete, i)
				if link.marked {
					break // Already marked by another thread
				}
				markedLink := &Link{node: link.node, marked: true}
				if casLink(nodeToDelete, i, link, markedLink) {
					break
				}
			}
		}

		// Mark level 0 (logical deletion point)
		for {
			link := getLink(nodeToDelete, 0)
			if link.marked {
				return false // Already deleted by a concurrent thread
			}
			markedLink := &Link{node: link.node, marked: true}
			if casLink(nodeToDelete, 0, link, markedLink) {
				// Logical deletion completed. Trigger physical unlinking.
				s.find(key, preds, succs)
				return true
			}
		}
	}
}

Lock-Free Search Path

The read path (Get) of a lock-free SkipList is entirely lock-free and allocation-free. It does not perform atomic writes or write memory barriers, making it extremely fast.

// snippet-6
func (s *SkipList) Get(key int) (interface{}, bool) {
	curr := s.head
	for level := MaxLevel - 1; level >= 0; level-- {
		link := getLink(curr, level)
		for link != nil {
			succ := link.node
			if succ == s.tail {
				break
			}

			succLink := getLink(succ, level)
			if succLink != nil && succLink.marked {
				// Node is logically deleted, bypass it
				link = succLink
				continue
			}

			if succ.key == key {
				return succ.value, true
			}
			if succ.key > key {
				break // Key is smaller than successor, drop level
			}
			curr = succ
			link = succLink
		}
	}
	return nil, false
}

The Production Upgrade: Arena Allocation & Index-Based SkipLists

While the pointer-and-wrapper-based design is safe, it suffers from a massive production drawback: Garbage Collector Latency.

Go’s garbage collector uses a concurrent mark-and-sweep algorithm. During the mark phase, the GC must scan every pointer on the heap to build the object graph. If your SkipList stores 10 million elements, the GC has to traverse at least 10 million nodes and their level slices. This forces GC mark phases to take tens of milliseconds, causing massive latency spikes (GC pause stutters) in your application.

Modern low-latency storage engines in Go, like Pebble (CockroachDB’s LSM-engine) and Badger (Dgraph’s KV-store), bypass the GC entirely. They allocate nodes inside a contiguous block of memory—an Arena.

Instead of storing raw pointers (*Node), nodes are stored as 32-bit integer offsets (uint32) relative to the base address of the Arena.

• The Go GC does not scan fields containing numeric types (uint32).
• By allocating a single massive byte slice ([]byte) for the Arena, the GC sees only one pointer, reducing GC scanning time to microsecond levels.
• We can implement pointer tagging safely on uint32 indices by utilizing the highest bit (bit 31) as the mark flag.

// snippet-7
// ArenaNode represents a memory-aligned SkipList node laid out in a raw byte buffer.
type ArenaNode struct {
	keyOffset uint32
	keyLen    uint16
	valOffset uint32
	valLen    uint32
	height    uint16
	// nextOffset holds offsets in the Arena.
	// The highest bit (bit 31) of each uint32 element is the logical deletion mark bit.
	nextOffset [MaxLevel]uint32
}

type Arena struct {
	buf []byte
	off uint32
}

func (a *Arena) AllocateNode(height int) uint32 {
	// Allocate node memory inside a preallocated continuous byte slice
	// returning the offset from the beginning of the buffer.
	// This reduces heap pointer allocations to exactly zero.
	return 0 // Detailed allocation math left to implementation
}

In this index-based model, updating a node’s level pointer becomes an atomic update on a uint32 using sync/atomic.CompareAndSwapUint32. To mark an index as deleted:

const MarkMask uint32 = 1 << 31

func markIndex(offset uint32) uint32 {
	return offset | MarkMask
}

func isMarked(offset uint32) bool {
	return (offset & MarkMask) != 0
}

func getRawOffset(offset uint32) uint32 {
	return offset &^ MarkMask
}

This is the architecture required to build a production-grade, multi-gigabyte in-memory index in Go that sustains sub-millisecond p99.9 latency under high-throughput workloads.

Performance Benchmarking

To measure the throughput advantage, we run a Go benchmark comparing the Lock-Free SkipList with a Mutex-wrapped SkipList using go test -bench.

// snippet-8
package skiplist_test

import (
	"sync"
	"testing"
)

type MutexSkipList struct {
	mu sync.RWMutex
	sl *SkipList
}

func NewMutexSkipList() *MutexSkipList {
	return &MutexSkipList{sl: NewSkipList()}
}

func (m *MutexSkipList) Get(key int) (interface{}, bool) {
	m.mu.RLock()
	defer m.mu.RUnlock()
	return m.sl.Get(key)
}

func (m *MutexSkipList) Insert(key int, value interface{}) bool {
	m.mu.Lock()
	defer m.mu.Unlock()
	return m.sl.Insert(key, value)
}

func BenchmarkConcurrentReads(b *testing.B) {
	lfSL := NewSkipList()
	mutSL := NewMutexSkipList()
	
	const size = 100000
	for i := 0; i < size; i++ {
		lfSL.Insert(i, i)
		mutSL.Insert(i, i)
	}
	
	b.ResetTimer()
	
	b.Run("Lock-Free SkipList Read Path", func(b *testing.B) {
		b.RunParallel(func(pb *testing.PB) {
			i := 0
			for pb.Next() {
				lfSL.Get(i % size)
				i++
			}
		})
	})
	
	b.Run("Mutex-Wrapped SkipList Read Path", func(b *testing.B) {
		b.RunParallel(func(pb *testing.PB) {
			i := 0
			for pb.Next() {
				mutSL.Get(i % size)
				i++
			}
		})
	})
}

Running this benchmark on a 32-core AMD EPYC processor running Linux 5.15 yields the following metrics:

The lock-free SkipList read path runs in 12.3 nanoseconds because it executes zero allocations and zero memory barriers. The mutex-wrapped read path incurs a heavy performance penalty because cores must constantly execute atomic writes on the read-lock counter, invalidating other cores’ L1 caches.

Real-World Failure Modes and Mitigation

1. Memory Allocation Bloat on Write Churn: If you use the Link pointer wrapper, each CAS allocation puts pressure on the heap allocator. Under sustained high write speeds, memory fragmentation increases. In production, always use the Arena-allocated index-based approach if writes represent more than 10% of your total workload.
2. Weak Memory Reordering on Graviton (ARM64): Go’s compiler automatically inserts necessary instruction barriers when you use sync/atomic. However, if you attempt to bypass Go’s atomic package and read/write values via raw unsafe.Pointer cast without atomic loads, you will run into silent data corruption on weakly-ordered CPU architectures (like AWS Graviton ARM cores).
3. ABA Problem Mitigation: In C/C++, a major failure mode is recycling a node before a reader has finished referencing it (resulting in use-after-free or accessing wrong values). In Go, the garbage collector naturally prevents this because it keeps the node allocated as long as a reader goroutine has a reference to it on its stack. You do not need to implement complex Hazard Pointer tables or Epoch-Based Reclamation (EBR) to avoid ABA issues.