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

snippet-1.go

package main

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

// Node represents a pointer-free Skip List node. 
// All fields are primitive types, allowing Go to flag the node array as noscan.
type Node struct {
	keyOffset  uint32
	keyLen     uint16
	valOffset  uint32
	valLen     uint32
	height     uint8
	nextOffset uint32 // Offset into the links slice
}

// Arena manages pre-allocated slices of memory for keys, nodes, and links.
type Arena struct {
	buf        []byte
	nodes      []Node
	links      []uint32
	bufOffset  uint32
	nodeOffset uint32
	linkOffset uint32
}

// NewArena initializes an Arena with fixed limits.
func NewArena(bufSize, maxNodes, maxLinks int) *Arena {
	return &Arena{
		buf:        make([]byte, bufSize),
		nodes:      make([]Node, maxNodes),
		links:      make([]uint32, maxLinks),
		bufOffset:  0,
		nodeOffset: 1, // Index 0 is reserved as the NULL sentinel
		linkOffset: 1, // Index 0 is reserved as the NULL sentinel
	}
}

snippet-2.go

// AllocateBytes reserves size bytes in the byte arena.
func (a *Arena) AllocateBytes(size uint32) (uint32, error) {
	for {
		curr := atomic.LoadUint32(&a.bufOffset)
		if curr+size > uint32(len(a.buf)) {
			return 0, errors.New("byte arena overflow")
		}
		if atomic.CompareAndSwapUint32(&a.bufOffset, curr, curr+size) {
			return curr, nil
		}
	}
}

// AllocateNode reserves a Node and its corresponding links space in the arenas.
func (a *Arena) AllocateNode(keyOffset uint32, keyLen uint16, valOffset uint32, valLen uint32, height uint8) (uint32, error) {
	var nodeIdx uint32
	for {
		curr := atomic.LoadUint32(&a.nodeOffset)
		if curr >= uint32(len(a.nodes)) {
			return 0, errors.New("node arena overflow")
		}
		if atomic.CompareAndSwapUint32(&a.nodeOffset, curr, curr+1) {
			nodeIdx = curr
			break
		}
	}

	h := uint32(height)
	var linkIdx uint32
	for {
		curr := atomic.LoadUint32(&a.linkOffset)
		if curr+h > uint32(len(a.links)) {
			return 0, errors.New("link arena overflow")
		}
		if atomic.CompareAndSwapUint32(&a.linkOffset, curr, curr+h) {
			linkIdx = curr
			break
		}
	}

	// Write the node metadata. Since nodeIdx is not yet linked, 
	// this write is safe from concurrent reader interference.
	a.nodes[nodeIdx] = Node{
		keyOffset:  keyOffset,
		keyLen:     keyLen,
		valOffset:  valOffset,
		valLen:     valLen,
		height:     height,
		nextOffset: linkIdx,
	}
	return nodeIdx, nil
}

snippet-3.go

type ConcurrentSkipList struct {
	mu        sync.Mutex
	arena     *Arena
	head      uint32
	maxHeight int
	height    int32
}

// Get performs a lock-free lookup of a key.
func (s *ConcurrentSkipList) Get(key []byte) ([]byte, bool) {
	currIdx := s.head
	level := int(atomic.LoadInt32(&s.height)) - 1

	for level >= 0 {
		currNode := &s.arena.nodes[currIdx]
		// Load the next node index atomically to guarantee memory visibility.
		nextIdx := atomic.LoadUint32(&s.arena.links[currNode.nextOffset+uint32(level)])

		if nextIdx == 0 { // NULL sentinel
			level--
			continue
		}

		nextNode := &s.arena.nodes[nextIdx]
		nextKey := s.arena.buf[nextNode.keyOffset : nextNode.keyOffset+uint32(nextNode.keyLen)]
		cmp := bytes.Compare(nextKey, key)

		if cmp < 0 {
			currIdx = nextIdx
		} else if cmp == 0 {
			// Found the key, return the value slice directly from the arena buffer.
			return s.arena.buf[nextNode.valOffset : nextNode.valOffset+nextNode.valLen], true
		} else {
			level--
		}
	}
	return nil, false
}

snippet-4.go

// NewConcurrentSkipList creates a skip list and initializes its dummy head.
func NewConcurrentSkipList(arena *Arena, maxHeight int) *ConcurrentSkipList {
	headIdx, _ := arena.AllocateNode(0, 0, 0, 0, uint8(maxHeight))
	return &ConcurrentSkipList{
		arena:     arena,
		head:      headIdx,
		maxHeight: maxHeight,
		height:    1,
	}
}

func (s *ConcurrentSkipList) randomHeight() uint8 {
	h := uint8(1)
	// P = 1/4 is standard to maintain logarithmic search depth with low memory overhead.
	for h < uint8(s.maxHeight) && rand.Float32() < 0.25 {
		h++
	}
	return h
}

// Insert writes a key-value pair into the skip list.
func (s *ConcurrentSkipList) Insert(key, value []byte) error {
	s.mu.Lock()
	defer s.mu.Unlock()

	update := make([]uint32, s.maxHeight)
	currIdx := s.head
	level := int(s.height) - 1

	// Traverse to locate insert position at all levels.
	for level >= 0 {
		currNode := &s.arena.nodes[currIdx]
		nextIdx := atomic.LoadUint32(&s.arena.links[currNode.nextOffset+uint32(level)])

		if nextIdx != 0 {
			nextNode := &s.arena.nodes[nextIdx]
			nextKey := s.arena.buf[nextNode.keyOffset : nextNode.keyOffset+uint32(nextNode.keyLen)]
			if bytes.Compare(nextKey, key) < 0 {
				currIdx = nextIdx
				continue
			}
		}
		update[level] = currIdx
		level--
	}

	keyOffset, err := s.arena.AllocateBytes(uint32(len(key)))
	if err != nil {
		return err
	}
	copy(s.arena.buf[keyOffset:], key)

	valOffset, err := s.arena.AllocateBytes(uint32(len(value)))
	if err != nil {
		return err
	}
	copy(s.arena.buf[valOffset:], value)

	h := s.randomHeight()
	nodeIdx, err := s.arena.AllocateNode(keyOffset, uint16(len(key)), valOffset, uint32(len(value)), h)
	if err != nil {
		return err
	}

	currHeight := atomic.LoadInt32(&s.height)
	if int(h) > int(currHeight) {
		for i := int(currHeight); i < int(h); i++ {
			update[i] = s.head
		}
		atomic.StoreInt32(&s.height, int32(h))
	}

	newNode := &s.arena.nodes[nodeIdx]

	// Publication step:
	// Set the outgoing links of the new node first.
	// Since the new node is not yet referenced by any other nodes in the skip list, 
	// this is entirely safe from reader interference.
	for i := 0; i < int(h); i++ {
		predNode := &s.arena.nodes[update[i]]
		predNext := atomic.LoadUint32(&s.arena.links[predNode.nextOffset+uint32(i)])
		s.arena.links[newNode.nextOffset+uint32(i)] = predNext
	}

	// Link the predecessors to the new node using atomic stores.
	// Once these stores execute, the node is "published" and becomes visible to readers.
	for i := 0; i < int(h); i++ {
		predNode := &s.arena.nodes[update[i]]
		atomic.StoreUint32(&s.arena.links[predNode.nextOffset+uint32(i)], nodeIdx)
	}

	return nil
}

snippet-5.go

// Iterator enables zero-allocation range scans across the index.
type Iterator struct {
	list    *ConcurrentSkipList
	currIdx uint32
}

// NewIterator creates a stack-allocatable iterator starting at the head.
func (s *ConcurrentSkipList) NewIterator() Iterator {
	return Iterator{
		list:    s,
		currIdx: s.head,
	}
}

// Next moves the iterator to the next sequential node in the list (Level 0).
func (it *Iterator) Next() bool {
	if it.currIdx == 0 {
		return false
	}
	currNode := &it.list.arena.nodes[it.currIdx]
	nextIdx := atomic.LoadUint32(&it.list.arena.links[currNode.nextOffset])
	if nextIdx == 0 {
		it.currIdx = 0
		return false
	}
	it.currIdx = nextIdx
	return true
}

// Key returns the byte slice representing the key of the current node.
func (it *Iterator) Key() []byte {
	if it.currIdx == 0 {
		return nil
	}
	node := &it.list.arena.nodes[it.currIdx]
	return it.list.arena.buf[node.keyOffset : node.keyOffset+uint32(node.keyLen)]
}

// Value returns the byte slice representing the value of the current node.
func (it *Iterator) Value() []byte {
	if it.currIdx == 0 {
		return nil
	}
	node := &it.list.arena.nodes[it.currIdx]
	return it.list.arena.buf[node.valOffset : node.valOffset+node.valLen]
}

snippet-6.go

import (
	"encoding/binary"
	"io"
)

// WriteTo serializes the Skip List arenas directly to an io.Writer.
func (s *ConcurrentSkipList) WriteTo(w io.Writer) error {
	s.mu.Lock()
	defer s.mu.Unlock()

	// Write metadata header
	header := make([]byte, 20)
	binary.BigEndian.PutUint32(header[0:4], s.arena.bufOffset)
	binary.BigEndian.PutUint32(header[4:8], s.arena.nodeOffset)
	binary.BigEndian.PutUint32(header[8:12], s.arena.linkOffset)
	binary.BigEndian.PutUint32(header[12:16], uint32(s.height))
	binary.BigEndian.PutUint32(header[16:20], uint32(s.maxHeight))
	if _, err := w.Write(header); err != nil {
		return err
	}

	// Write byte buffer
	if _, err := w.Write(s.arena.buf[:s.arena.bufOffset]); err != nil {
		return err
	}

	// Write nodes array
	for i := uint32(0); i < s.arena.nodeOffset; i++ {
		node := s.arena.nodes[i]
		nodeBytes := make([]byte, 19)
		binary.BigEndian.PutUint32(nodeBytes[0:4], node.keyOffset)
		binary.BigEndian.PutUint16(nodeBytes[4:6], node.keyLen)
		binary.BigEndian.PutUint32(nodeBytes[6:10], node.valOffset)
		binary.BigEndian.PutUint32(nodeBytes[10:14], node.valLen)
		nodeBytes[14] = node.height
		binary.BigEndian.PutUint32(nodeBytes[15:19], node.nextOffset)
		if _, err := w.Write(nodeBytes); err != nil {
			return err
		}
	}

	// Write links array
	for i := uint32(0); i < s.arena.linkOffset; i++ {
		linkBytes := make([]byte, 4)
		binary.BigEndian.PutUint32(linkBytes, s.arena.links[i])
		if _, err := w.Write(linkBytes); err != nil {
			return err
		}
	}
	return nil
}

// ReadSkipList deserializes a Skip List directly into newly allocated arenas.
func ReadSkipList(r io.Reader, bufCap, nodeCap, linkCap int) (*ConcurrentSkipList, error) {
	header := make([]byte, 20)
	if _, err := io.ReadFull(r, header); err != nil {
		return nil, err
	}

	bufOffset := binary.BigEndian.Uint32(header[0:4])
	nodeOffset := binary.BigEndian.Uint32(header[4:8])
	linkOffset := binary.BigEndian.Uint32(header[8:12])
	height := binary.BigEndian.Uint32(header[12:16])
	maxHeight := binary.BigEndian.Uint32(header[16:20])

	arena := &Arena{
		buf:        make([]byte, bufCap),
		nodes:      make([]Node, nodeCap),
		links:      make([]uint32, linkCap),
		bufOffset:  bufOffset,
		nodeOffset: nodeOffset,
		linkOffset: linkOffset,
	}

	if _, err := io.ReadFull(r, arena.buf[:bufOffset]); err != nil {
		return nil, err
	}

	for i := uint32(0); i < nodeOffset; i++ {
		nodeBytes := make([]byte, 19)
		if _, err := io.ReadFull(r, nodeBytes); err != nil {
			return nil, err
		}
		arena.nodes[i] = Node{
			keyOffset:  binary.BigEndian.Uint32(nodeBytes[0:4]),
			keyLen:     binary.BigEndian.Uint16(nodeBytes[4:6]),
			valOffset:  binary.BigEndian.Uint32(nodeBytes[6:10]),
			valLen:     binary.BigEndian.Uint32(nodeBytes[10:14]),
			height:     nodeBytes[14],
			nextOffset: binary.BigEndian.Uint32(nodeBytes[15:19]),
		}
	}

	for i := uint32(0); i < linkOffset; i++ {
		linkBytes := make([]byte, 4)
		if _, err := io.ReadFull(r, linkBytes); err != nil {
			return nil, err
		}
		arena.links[i] = binary.BigEndian.Uint32(linkBytes)
	}

	return &ConcurrentSkipList{
		arena:     arena,
		head:      1,
		maxHeight: int(maxHeight),
		height:    int32(height),
	}, nil
}