Implementing a Lock-Free B-Link Tree in Go for Concurrent Indexing

If you are running a high-throughput write-heavy application—such as a custom time-series database or an in-memory caching engine—on modern 64-core or 128-core cloud instances, you have likely run into the limits of standard locking structures. Under heavy concurrent write and read pressure, a standard B-Tree protected by a read-write lock (sync.RWMutex) or even fine-grained latch coupling becomes a major performance bottleneck. As CPU cores scale, thread contention on the root and upper-level internal nodes causes massive tail latency spikes (p99.9 exceeding 150ms) and wastes up to 45% of CPU cycles on cache line bouncing and lock acquisition.

While pure lock-free B-Trees (such as those using multidimensional CAS or hardware transactional memory) are notoriously complex and often perform poorly due to persistent retry loops under contention, the Lehman-Yao B-Link Tree offers a highly practical middle ground: completely lock-free reads, single-node locking for writes, and no lock-coupling during traversal.

This post details how to implement a production-ready, concurrent B-Link Tree in Go, overcoming Go-specific runtime and memory model challenges along the way.

The Bottleneck: Why Traditional B-Trees Fail at Scale

Traditional B-Tree implementations (such as Go’s bolt or standard in-memory B-Trees) protect their structural invariants using page-level or node-level locks. When a thread searches for a key, it must perform latch coupling (also known as lock crabbing): it acquires a read lock on the parent, finds the child pointer, acquires a read lock on the child, and only then releases the lock on the parent.

This protocol guarantees that no concurrent write can modify a node while a reader is traversing it. However, this creates severe issues under concurrent write-heavy workloads:

1. Root Bottleneck: Every single operation (read or write) must touch the root node. Although readers acquire shared locks, the constant acquisition and release of read locks write to the lock’s internal state, invalidating CPU caches across cores. This causes massive cache line invalidation traffic (cache line bouncing).
2. Write Starvation: If a writer needs to split a node, it must acquire an exclusive lock. If readers are constantly flowing down, the writer is starved. Conversely, if writers are prioritized, readers experience significant latency spikes.
3. Deadlocks: Propagating node splits upward requires acquiring locks in a bottom-up direction, while search operations traverse top-down. Without complex deadlock-detection algorithms or lock-release cycles, this leads to fatal deadlocks.

The Lehman-Yao B-Link Tree solves these issues by introducing two modifications to the standard B-Tree structure:

• Right-Sibling Links: Every node (both leaf and internal) contains a pointer to its immediate right sibling on the same level.
• High Keys: Every node contains a “high key,” which is the maximum key value stored in that node’s subtree.

These two additions change the structural invariants. If a reader visits a node searching for a key $K$, and finds that $K$ is greater than the node’s high key, it knows the node has been split by a concurrent writer and the key has moved to the right. Instead of backtracking or failing, the reader simply traverses horizontally to the right sibling using the right-sibling link. Consequently, readers do not need to acquire any locks whatsoever during traversal. They can traverse down the tree completely lock-freely.

Node Design and Atomic Traversals in Go

Implementing lock-free reads in Go is challenging because Go’s slices are not thread-safe. A slice header in Go is a 24-byte struct containing a pointer to the underlying array, a length, and a capacity:

type sliceHeader struct {
    Data unsafe.Pointer
    Len  int
    Cap  int
}

If a writer updates a node’s keys slice in place (e.g., inserting a new key or deleting one), and a reader accesses that slice concurrently without locks, the reader may read an inconsistent slice header. This results in data races, memory corruption, or index-out-of-bounds panics.

To prevent this without using read locks, we must treat a node’s state as immutable. When a writer modifies a node, it copies the node’s state, modifies the copy, and replaces the old state atomically using unsafe.Pointer and sync/atomic.

Below is the production-grade node structure for our B-Link Tree.

With this immutable state pattern, we can now implement the lock-free read path. If a reader encounters a node that is undergoing a split, it checks the high key. If the target key is greater than the high key, it follows the right pointer.

Managing Structural Modifications (Node Splits)

The B-Link Tree allows write operations to lock only one node at a time. When a node becomes full and must be split, the split is performed in a way that preserves the correctness of concurrent searches, even before the parent node is updated to point to the new right sibling.

To split a node:

1. Allocate a new right node.
2. Move the second half of the elements from the original node to the new right node.
3. Set the right-sibling pointer of the new node to the old node’s right-sibling pointer.
4. Set the right-sibling pointer of the old node to the new node.
5. Update the old node’s state with the first half of the elements and set its high key to the maximum element of the left node.

The order of step 4 and 5 is critical. We must update the old node’s right pointer before we swap the old node’s state with the new high key.

If we swap the state first, a concurrent reader searching for a key that has moved to the right will see that the key is greater than the new high key. It will attempt to read the right pointer. If the right pointer has not been updated yet, the reader will traverse to the old right sibling, missing the split key entirely. By updating the right-sibling pointer first, we ensure that the new right node is already linked in the level before the old node’s high key is updated.

Concurrent Writes and Latch Crabbing

When a writer descends to insert a key, it does not lock the path down. It records the path traversed in a stack so that it can propagate splits upward if needed. Once it reaches the leaf level, it acquires the lock on the target node.

Because we do not lock the nodes during descent, a concurrent split could have occurred while the writer was traversing or waiting for the lock. Therefore, after locking the node, the writer must verify that the target key is still within the node’s boundaries by checking the high key. If the key is greater than the high key, the node has split. The writer must release the lock, move right, lock the sibling, and repeat this check. This is known as latch crabbing with right-moving correction.

Once the leaf split is complete, we must insert the split key and the new right node pointer into the parent node. Since we tracked the traversal path in a stack, we pop the parent, lock it, move right if concurrent splits affected it, and insert the split key. If the parent is also full, it splits recursively.

Safe Memory Reclamation in Go

A major issue with the lock-free read path is safe memory reclamation. When a writer updates a node’s state, it swaps the State pointer using atomic.StorePointer. The old NodeState struct is retired.

If we pool NodeState structs to avoid garbage collection overhead, we cannot immediately return the retired NodeState to the pool. A concurrent reader might have loaded the old State pointer just before the swap and could still be reading its keys and pointers.

To solve this, we can implement a lock-free Epoch-Based Reclamation (EBR) manager. Readers register their active status in a global epoch, and retired memory is put into a limbo list. Once all readers from the corresponding epoch exit, the memory can be safely recycled.

Real-World Failure Modes & Mitigation

While the B-Link Tree significantly improves performance, running this structure in production reveals several subtle failure modes:

1. The Split Storm (Recursive Split Latency)

When a write causes a node split, and that split propagates up to the parent, grand-parent, and eventually triggers a root split, the inserting thread pays the latency cost of multiple allocations and node locks. Under write-heavy bursts, this causes sudden spikes in tail latency.

• Mitigation: Implement proactive node splitting during descent. If the writer encounters an internal node that is $90\%$ full during its initial descent, it locks it and splits it immediately before descending to the child. This bounds the split chain to a depth of $1$, ensuring no single write thread gets blocked by a cascade of parent splits.

2. High Allocation Rate and GC Pressure

Due to the copy-on-write pattern of NodeState objects, writes generate a large number of short-lived allocations. Under a workload of $500,000$ writes/sec, this triggers Go’s garbage collector constantly, causing CPU throttling.

• Mitigation: Integrate the EpochReclaimer shown in snippet 6 with a specialized block allocator or sync.Pool. Ensure that Keys and Ptrs slices are allocated from pre-allocated arrays rather than being dynamically resized using make().

3. Starvation on Write-Heavy Right-Moving Nodes

If a node is being split repeatedly at a rate that matches or exceeds the speed at which a writer is correcting its path horizontally, the writer can get caught in a long right-moving loop, consuming CPU cycles without successfully applying its update.

• Mitigation: Limit right-moving hops. If a writer performs more than $5$ horizontal hops, it should release its locks, sleep for a brief backoff period (using runtime.Gosched()), and restart the traversal from the root.

Performance Metrics: Lock-Free vs. Latched B-Trees

To benchmark the performance of this implementation, we compared it against a standard concurrent B-Tree implementation that uses sync.RWMutex on each node. The benchmark was run on an AWS c6i.32xlarge instance (128 vCPUs, Intel Xeon Ice Lake) under a mixed $80\%$ read / $20\%$ write workload.

The results show how lock contention impacts scaling:

As the thread count increases, the standard B-Tree’s throughput collapses due to lock contention and cache-line invalidation on the upper nodes. In contrast, the Lehman-Yao B-Link Tree scales linearly with the core count because readers run without locks, avoiding write operations to shared cache lines.