Concurrent Readers on a Mutating Trie

A trie lookup is a chain of dependent loads: the address of each node comes from the previous node’s contents. Any locking discipline that acquires a lock per node turns one memory latency into a lock acquisition plus a memory latency, at every level, and turns a structure that is read constantly and written rarely into a contention point. The alternative is to let readers run without locks and constrain writers to publish changes in an order that no reader can observe mid-update. That constraint is achievable for insertion in a trie, expensive for deletion, and it determines most of the design.

What a reader can observe

Take the simplest mutable trie: each node has a fixed array of child pointers and a terminal flag. An insertion allocates a path of new nodes below an existing node and stores a pointer into that node’s child array. A reader descending the same path either sees the new pointer or does not, and both outcomes are consistent: the key is present or absent. No lock is needed, because the only write is a single aligned pointer store.

Two conditions make that true, and both are easy to break.

The first is initialization order. The new child must be fully constructed — its child array zeroed, its terminal flag set — before its address becomes reachable. On a weakly ordered machine, a store to the parent’s child slot can become visible before the stores that filled the child, and a reader can then follow the pointer into a half-built node. The fix is a release store on publication and an acquire load on consumption, which on x86 costs nothing extra at runtime because the hardware orders stores before later stores, but which must be written explicitly because the compiler is free to reorder otherwise.

#include <stdatomic.h>

typedef struct node {
    _Atomic(struct node *) child[256];
    bool terminal;
} node;

/* Writer: publish a fully built child. */
static void publish_child(node *parent, unsigned char c, node *child)
{
    atomic_store_explicit(&parent->child[c], child, memory_order_release);
}

/* Reader: consume a child pointer. */
static node *load_child(node *parent, unsigned char c)
{
    return atomic_load_explicit(&parent->child[c], memory_order_acquire);
}

The second condition is that nodes never move. A structure that widens a node — as ART does when a 4-node becomes a 16-node — cannot overwrite the old node’s storage, because a reader may already hold a pointer to it. The writer must build the wider node, copy the children into it, publish the new address in the parent, and leave the old node intact until no reader can still be holding it. The old node remains a valid, if stale, 4-node; a reader that loaded it before the swap sees four children and finds its key if the key was among them. A reader that loaded it after the swap sees the new node. Neither sees a torn node.

This is the property that makes the ART node-growth scheme workable under concurrent reads, and it is worth noting what it costs: every growth leaks a node until reclamation, and the parent’s child slot must be written atomically at the correct width. If child pointers are not naturally aligned or the node type tag is stored separately from the pointer, the swap is no longer a single atomic operation and readers can observe a pointer of the old type paired with a tag of the new one.

Deferred reclamation is the hard part

Insertion only adds reachable state. Deletion removes it, and a reader may be standing on the node being removed. Freeing that node immediately corrupts the reader: it may read freed memory, or the allocator may hand the block to another structure and the reader follows a pointer into unrelated data.

The standard answer is to separate unlink from free. The writer unlinks the node with a single store, then waits until every reader that could have observed the old state has finished, then frees. Waiting is the interesting part, and the mechanisms form a ladder of cost.

An epoch-based scheme has each reader announce that it is inside a critical section, cheaply, without any shared write in the common case. The writer advances a global epoch, waits for all readers that were active at the start of the previous epoch to leave, and then frees everything unlinked before that point. The cost to a reader is a per-thread counter and a periodic check; the cost to a writer is a wait, which is unbounded if a reader is preempted while inside its section. That unbounded wait is why such schemes require readers not to block or sleep inside the section.

Hazard pointers have readers publish the addresses they are currently using, and writers scan those slots before freeing. Readers pay one store per pointer they protect, which in a trie is one per level, and writers pay a scan proportional to the number of reader threads. The trade reverses: readers do more work, writers wait less.

Reference counting on nodes is the third option and the worst for this shape of structure. A reader descending a trie would have to increment and decrement a count at every level, which converts two reads into two read-modify-write operations per level and puts every reader in contention on the same cache lines.

The choice interacts with the structure’s height. A trie over 32-bit keys has at most a few dozen levels, so a reader’s critical section is short in time but touches many nodes; hazard pointers at one per level are affordable, and epoch schemes are affordable because the section never blocks. A trie over long strings, where a reader may compare a hundred bytes of edge label per level, has a longer section and pushes toward epochs with the no-blocking discipline enforced by construction.

Path copying instead of in-place mutation

The other way to make a trie safe is to never mutate it. An update copies every node on the path from the root to the change, links the copies, and publishes the new root pointer. The old version remains a complete, valid trie, and a reader that loaded the old root continues to see a consistent snapshot regardless of what writers do.

The cost is one allocation per level per update, and one pointer store to publish. For a key of length L the update allocates L nodes — the same order as the insertion itself, so the asymptotic cost is unchanged, but the constant is a full node copy per level instead of a single pointer store. The benefit is that no reclamation is needed at all for readers: a version that is no longer current can be freed once nothing holds it, and a reader that captured the root at the start of its lookup holds the whole version alive through its traversal.

Path copying also solves the node-growth problem trivially, because a copy of a 4-node can be a 16-node; nothing points at the old one except older versions. And it makes snapshots free: an iterator that captures the root sees a stable view for its entire lifetime, which is exactly what an ordered enumeration needs, since lexicographic traversal visits many nodes and cannot tolerate the tree changing underneath it.

The price is memory retention. Every version that any reader holds keeps its whole path alive, and a burst of updates against a long-lived snapshot accumulates garbage. Systems that use this scheme usually bound the number of retained versions and fall back to copying the snapshot’s contents when the bound is exceeded.

The root pointer as the contention point

Both schemes converge on a single atomic word: the root pointer. Every reader loads it, and every writer stores it. On a machine with many cores, that word lives in one cache line, and the line bounces between cores as writers publish. Readers that only load it do not invalidate the line for other readers, since shared-state loads do not require exclusivity, so read scaling is fine. The problem is writers: two concurrent writers both copying from the same root produce two new versions, and one publication overwrites the other’s changes unless the writers are serialized.

Serializing writers on a single mutex is usually acceptable, because the workload that motivates lock-free reads is read-heavy by a large margin. Where writers must also run concurrently, the update becomes a compare-and-swap loop on the root: read the root, copy the path, attempt to install the new root only if the old one is unchanged, retry otherwise. Under contention the retries cost allocations that are immediately discarded, so a batching layer — accumulate a batch of updates, apply them under one swap — is the usual mitigation.

The compare-and-swap loop has a classic hazard: if a node is freed and a new node allocated at the same address between the load and the swap, the swap succeeds against the wrong version. Deferred reclamation prevents this by ensuring no address is reused until all readers that could have observed the old value have left, which is one more reason the reclamation discipline cannot be skipped even when the structure is copy-on-write at the root.

What breaks in practice

Three failure modes account for most concurrency bugs in these structures.

Torn composite writes. A node type tag stored in the same word as a child count, or a length stored next to a pointer, means an update that writes both fields is not atomic. Readers can observe a new count with an old pointer array. The fix is either to make the whole header a single naturally aligned word that is replaced by one store, or to ensure that any intermediate combination is a valid state — which usually means publishing a new node rather than modifying one.

Reclamation without a grace period. Freeing a node as soon as it is unlinked is correct only if no reader can hold it. In a trie, a reader holds a pointer for the duration of one comparison, so the window is short and a reader that is preempted inside it is the only way the race is lost. A scheme that delays every free until a grace period has passed closes it; shortening the window without closing it leaves a race that is unlikely to reproduce.

Reader-visible deletion of an intermediate node. Removing a key and pruning its now-childless ancestors changes several nodes along a path. A reader partway down the path can see an ancestor unlinked while its descendants are still reachable through the old pointer, or a child freed while its parent still points at it. Pruning must proceed from the leaf upward, each unlink being a single store, and the frees deferred until the whole path is unlinked. A bottom-up pass that frees as it goes has a window at every level.

The structures in adaptive radix tree node layouts and radix trees over fixed-width integer keys both depend on these rules; the integer radix tree in particular is built around the fact that it never relocates a node, which reduces the concurrency problem to publication and reclamation alone.