goart: High-Performance Concurrent Adaptive Radix Tree in Go

goart is a highly optimized, thread-safe implementation of an Adaptive Radix Tree (ART) written in Go. Designed specifically for in-memory databases and high-throughput systems, it leverages Optimistic Lock Coupling (OLC) and Epoch-Based Reclamation (EBR) to provide near-linear read scalability across CPU cores without the overhead of read-write locks.

Unlike standard lock-based trees, goart is built for extreme concurrency, minimal GC pressure, and ultra-fast range scans.

Key Architecture Highlights

Optimistic Lock Coupling (OLC): Read operations (Get, Ascend) do not acquire locks. They read node versions optimistically, retrying only if a concurrent mutation is detected, allowing massive parallel read throughput.

Epoch-Based Reclamation (EBR): Safe, deferred memory reclamation for deleted nodes ensures that lock-free readers never encounter invalid memory pointers or race conditions.

Wait-Free Range Scans: Leaf nodes are threaded into a lock-free linked list. Methods like AscendRange, AscendGreaterThan, and AscendLessThan bypass tree traversal entirely, scanning sequentially at hardware-memory speeds.

Zero-Allocation Fast Paths: Inline buffering for prefixes and zero-allocation integer comparisons (binary.BigEndian) eliminate heap escapes during hot-loop iterations.

Custom Node Pooling: Aggressive use of sync.Pool for all node sizes (Node4, Node16, Node48, Node256) drastically reduces Garbage Collection pauses in write-heavy workloads.

Generics Support: Fully typed via Go 1.18+ generics ([T any]).

Performance Tricks

The iteration loops are meticulously optimized. I use early pointer loading to issue memory requests to RAM immediately, effectively hiding cache latency while the CPU processes the current node. For 8-byte numeric keys (like timestamps or IDs), the iterator uses zero-allocation inline uint64 comparisons.

Usage Example

package main

import (
	"encoding/binary"
	"fmt"
	"github.com/banditmoscow1337/goart"
)

func main() {
	// Initialize a new thread-safe Adaptive Radix Tree
	tree := goart.New[string]()

	// 1. Insert data (Safe for concurrent use)
	keyBuf := make([]byte, 8)
	binary.BigEndian.PutUint64(keyBuf, 100500)
	tree.ReplaceOrInsert(keyBuf, "ServerNode-Alpha")

	// 2. Lock-free Retrieval
	val, found := tree.Get(keyBuf)
	if found {
		fmt.Printf("Found: %s\n", val)
	}

	// 3. Blazing fast wait-free range scan
	startKey := make([]byte, 8)
	binary.BigEndian.PutUint64(startKey, 100000)
	
	goart.AscendGreaterThan(tree, startKey, func(v string) bool {
		fmt.Println("Scanned:", v)
		return true // continue iteration
	})
}