Building a Zero-Allocation Garbage-Collector-Aware Skip List in Go for High-Throughput In-Memory Indexes

Imagine your Go-based distributed key-value store is serving 100,000 write requests per second. The memtable is backed by a standard pointer-based Skip List, holding 50 million active keys. Suddenly, tail latencies (p99.9) spike from 2ms to over 250ms, and your CPU profiles show runtime.gcDrain consuming 45% of all CPU cycles. You aren’t allocating new memory rapidly; the data is relatively stable. What you are experiencing is the silent killer of high-throughput Go systems: Garbage Collector (GC) scan overhead. Because the Go GC must traverse every pointer in your heap to find live objects, a pointer-heavy skip list with hundreds of millions of edges forces the GC to inspect every single node on every cycle, regardless of whether the data has changed. To scale beyond these limits, we must bypass the GC entirely without leaving safe Go code. We do this by designing an index-based, pointer-free Skip List backed by a contiguous arena.

The Production Nightmare of Pointer-Heavy Indexes

In high-throughput databases and caches, in-memory indexes must offer fast lookups, ordered scans, and concurrent writes. The Skip List is a popular data structure for this role (famously used in LevelDB and RocksDB memtables) because it provides $O(\log N)$ search, insertion, and deletion without the complex rebalancing math of AVL or Red-Black trees.

However, implementing a naive Skip List in Go is a recipe for production instability at scale. A typical node implementation looks like this:

type Node struct {
    key   []byte
    value []byte
    next  []*Node
}

If your index holds 50 million nodes, you have at least 150 million heap objects (the node struct, the slice header, the backing array of next pointers, and the key/value byte slices). In Go, the garbage collector is a concurrent, tri-color mark-and-sweep collector. The duration of the GC mark phase scales with the number of live pointers (edges in the object graph) in the heap, not just the raw volume of allocated bytes.

During every GC cycle, the collector starts at roots (stacks, globals) and traverses every single pointer to mark objects as reachable. A pointer-heavy Skip List represents a massive graph of millions of edges. The CPU cores spend more time running runtime.scanobject and traversing pointers than executing database transactions. Under profiling with Go’s pprof, you will see this as a large block of CPU usage dominated by runtime.gcDrain and runtime.gcBgMarkWorker.

To eliminate this overhead, we must hide the data from the garbage collector.

The Go GC and the Magic of Pointer-Free Slices

The Go garbage collector is highly optimized, but it is not magic. It relies on type information generated by the compiler. If an allocation contains no pointers (e.g., a slice of integers, or a slice of structs containing only primitive types), the compiler flags the backing array of the slice as noscan.

When the GC encounters a noscan memory block during the mark phase, it marks the block itself as live but does not scan its contents for pointers. This is a powerful hook for systems engineers. By storing our nodes and data in pre-allocated slices of primitive types and referencing them using integer array indices instead of raw memory pointers (*Node), we can store gigabytes of data while keeping the GC mark overhead at zero. The GC sees a few large slice headers, scans them in less than a microsecond, and moves on.

To build a pointer-free Skip List, we will structure our memory into three distinct arenas:

1. Byte Arena (buf []byte): Stores the raw keys and values sequentially.
2. Node Arena (nodes []Node): Stores fixed-size structures representing each node’s metadata.
3. Link Arena (links []uint32): Stores the forward links for the Skip List levels.

Let’s design these pointer-free structs.

By reserving index 0 in our node and link arenas as NULL, we can treat 0 exactly like a nil pointer. Any index lookup returning 0 indicates the end of a chain.

The Arena Allocation Architecture

Because we are bypassing Go’s default memory allocator (new or literal initialization), we must write our own simple allocator methods for the Arena. We want this allocator to support concurrent allocation safely. We use Compare-and-Swap (CAS) loops to ensure that multiple threads can allocate memory from the same arenas without race conditions.

This CAS allocator performs zero allocations on the heap. All operations occur in-place on pre-allocated slices, meaning that calling these methods has zero impact on Go’s GC cycle.

Pointer-Free Lookup Traversal

To traverse our index, we replace standard pointer dereferences (node = node.next[level]) with slice index offsets. Here is the search traversal implementation for looking up a key in our ConcurrentSkipList.

Notice that the return slice is sliced directly from s.arena.buf. This operation is extremely fast and allocates no heap memory, but it does mean the caller must be careful: the slice points directly to internal arena memory. If the arena is recycled or cleared, referencing this returned slice will read stale or corrupt data.

Concurrent Writes and the Publication Pattern

To keep the system performant under concurrent workloads, we design a single-writer, concurrent-reader model. Readers execute lookup queries lock-free, while write operations (insertions) are serialized using a sync.Mutex on the Skip List.

To ensure readers never see an invalid state or half-initialized node during concurrent insertions, we must use a publication pattern. We write the new node and its outgoing links completely before executing the atomic stores that hook the new node into the active traversal path.

This insertion design completely avoids data races. Even though a reader might traverse the list while Insert updates indices, the new node’s outgoing links are established before the predecessor transitions to pointing at it. The reader will either traverse to the old successor or seamlessly jump through the new node to the old successor, without encountering half-initialized values or dead ends.

Stack Allocation and Zero-Allocation Range Scans

In-memory database engines heavily rely on range scans (e.g. scanning all keys between “a” and “z”). Allocating iterator objects or returning a slice of keys during these scans would create massive allocation spikes.

We can design a zero-allocation Iterator struct. By returning the iterator struct by value, Go’s compiler will use escape analysis to determine that the iterator does not escape the current function stack frame. The runtime stack-allocates the iterator, bypassing the heap entirely.

You can use the iterator in hot loops like this:

it := list.NewIterator()
for it.Next() {
    process(it.Key(), it.Value())
}

Because Iterator is small and returned by value, and because Key() and Value() return sub-slices of a pre-allocated buffer without forcing heap escapes, this entire loop runs with exactly 0 B/op heap allocation.

Instant Snapshots: Zero-Copy Serialization

Because all links and pointers inside our Skip List are relative offsets (indices) rather than absolute memory addresses, we gain a massive secondary benefit: instant serialization.

With a pointer-based data structure, serialization requires traversing the entire graph, translating pointers into arbitrary IDs, writing them, and doing the inverse (plus allocating millions of objects) upon load. With our index-based skip list, we can write the raw slices directly to disk as linear byte streams. Loading the index back into memory is as fast as reading a file back into our three pre-allocated arrays.

For ultra-high-performance architectures, you can combine this with POSIX mmap. Instead of reading the bytes into a Go-allocated slice using io.ReadFull, you can map a database snapshot file directly into memory using syscall.Mmap, point your buf, nodes, and links slices at those memory-mapped regions using unsafe, and have an instantly loaded, zero-allocation database index.

Production Benchmarks & Performance Metrics

We benchmarked a standard pointer-based Skip List implementation against our pointer-free Arena Skip List. The workload consisted of inserting 10 million distinct keys (16-byte random strings) with 64-byte values, followed by 10 million lookup operations.

By avoiding the GC mark phase and packing data tightly into sequential cache lines, we achieved a significant speedup in both read and write operations. The reduction in heap size stems from pointer compression: instead of 8-byte 64-bit pointers and 24-byte slice headers, our offsets are compact 4-byte integers.

Real-world Failure Modes and Mitigation Strategies

While this architecture yields incredible performance gains, it changes Go’s safety guarantees and introduces specific runtime failure modes that must be designed around:

1. Arena Exhaustion (OOM)

Because the arenas are fixed-size slices, they will eventually run out of space.

• Failure Mode: An Insert call returns an out-of-memory error (e.g. "byte arena overflow").
• Mitigation: Your database manager must wrap the Skip List in a memtable controller. When an insert returns an OOM error, the controller freezes the current Skip List, marks it as read-only, rolls over to a new active Arena-based Skip List, and spawns a background goroutine to flush the frozen index onto disk as an SSTable.

2. Fragmentation on Deletion

Our arena allocator works strictly via sequential offsets. There is no free() operation.

• Failure Mode: Deleting elements from the Skip List unlinks them structurally, but the raw bytes and node metadata still occupy space in the arena, leading to eventual memory exhaustion even if the list has very few active items.
• Mitigation: Arena-based skip lists are ideal for write-once, flush-frequently architectures like LSM memtables. If you require a long-running, in-memory cache with frequent updates and deletions, you must implement a thread-safe free list targeting the node and link slices to recycle index numbers, or trigger periodic in-memory compactions where a new arena is constructed by copying over only the active nodes.

3. Lifetime Violations (Use-After-Free)

Since memory is managed manually within the arena, the lifetime of returned byte slices must be strictly bounded.

• Failure Mode: An application calls Get(key), receives the value slice, and passes it to another goroutine. Meanwhile, the index is cleared or serialized, corrupting the memory read by the other goroutine.
• Mitigation: Implement a strict rule in your codebase: any slice returned by the index’s Get or Iterator APIs must either be processed immediately or copied (copy()) if it needs to outlive the database transaction boundary.

Conclusion

At scale, standard Go pointer-heavy data structures become a liability due to GC overhead. By replacing raw memory pointers with relative offsets inside contiguous, pointer-free slices, we completely eliminate GC scanning cost and cache-line misses.

This approach converts memory allocation to simple offset additions, allows lock-free publication safety patterns, and unlocks zero-copy serialization and instant memory-mapped startup times. When building high-performance Go storage engines or cache systems, managing your own pointer-free memory layout is the ultimate key to p99 latency stability.