README
¶
go-immutable-art
An immutable adaptive radix tree for Go.
The tree is a persistent, copy-on-write map from []byte keys to values, with prefix
lookups, ordered iteration in both directions, and a watch channel on every node and leaf
that fires when the subtree beneath it changes. A committed tree never changes, so readers
need no coordination at all.
The API mirrors hashicorp/go-immutable-radix
and is a drop-in replacement for it, down to the CommitOnly/Notify split that lets a
caller publish a new root before waking any watcher. What differs is underneath: inner
nodes come in four sizes and grow and shrink with their child count, instead of every node
paying for one shape.
tree := art.New[string]()
tree, _, _ = tree.Insert([]byte("hello"), "world")
v, ok := tree.Get([]byte("hello")) // "world", true
txn := tree.Txn()
txn.TrackMutate(true)
txn.Insert([]byte("hello/there"), "again")
next := txn.CommitOnly() // new root is readable
txn.Notify() // ...only now are watchers woken
Design notes
Node kinds. A node holds the narrowest of five shapes that fits its children: no children at all, then 4, 16, 48, or 256. Leaves are the overwhelming majority of nodes in any real tree, and the zero-child kind is what makes them cost nothing beyond the header.
The sparse kinds are rank-indexed, not classic ART. node48 keeps its children dense
and label-sorted behind a 256-bit map, so a label's slot is the number of set bits below
it. The classic layout keeps an unordered child array behind a 256-byte label index, which
makes lookup one load instead of a popcount but forces in-order traversal to scan all 256
index entries. The trade is deliberate: prefix scans dominate the workload this was built
for.
Watch channels are created on demand. Every node and leaf carries a notification slot, but the channel behind it is allocated only when a reader actually asks for one — writers allocate nothing. Eagerly allocating them costs roughly 192 bytes per stored entry, which is a large fraction of a tree's footprint, paid whether or not a watcher ever exists.
Nodes are owned by transaction identity. Each node records the transaction that allocated it, and a transaction may mutate a node in place exactly when the identities match. There is no per-transaction cache of writable nodes, which is why this module has no dependencies.
The hazard that creates is real and worth stating: an iterator aliases the children arrays
of the nodes it walks, so mutating an owned node in place underneath a live iterator would
corrupt it. Txn.Root and Txn.Clone therefore retire the transaction's identity before
returning, making every node reachable at that moment foreign to every later write.
TestIteratorIsolatedFromWriter and TestCloneIsolatedFromWriter fail if either seal is
removed.
Differences from go-immutable-radix
Two behaviours are deliberately not reproduced, both cases the original leaves untested:
WalkBackwardsyields true reverse key order. A node's own value is the shortest key in its subtree, so it is visited after everything beneath it. The original visits it first, which is not reverse key order when one key is a proper prefix of another — and disagrees with the original's ownReverseIterator.DeletePrefixreports whether anything matched. Deleting a prefix from an empty tree returnsfalseand wakes nobody. The original returnstrueand wakes the root's watchers.
Testing
The suite is the original's, carried over so this tree is held to the behaviour of the one
it replaces (see ported_*_test.go and NOTICE), plus:
- a differential oracle — a map and a sorted key slice — that every read operation is checked against, over seven key corpora chosen to drive different node shapes;
- fuzz targets (
FuzzTreeOps,FuzzTxnOps) replaying operation sequences against that same oracle; - a structural invariant check run after every mutation in tests, which catches a bad node shape at the operation that caused it rather than as a wrong answer much later;
- node-kind transition tests climbing 0→4→16→48→256 and back down, verified against an oracle at every single step in three insertion orders;
- watch tests with a positive control first. A spurious-wakeup count of zero means
nothing unless watches are known to fire when they should, so
TestWakeupControlasserts exactly that before any zero below it is believed.
go test -race -count=2 ./...
go test -run '^$' -fuzz FuzzTreeOps -fuzztime=10m
License
MPL-2.0. Portions are derived from hashicorp/go-immutable-radix; see NOTICE.
Documentation
¶
Overview ¶
Package art implements an immutable adaptive radix tree.
The tree is a persistent, copy-on-write map from []byte keys to values, with prefix-based lookups, ordered iteration in both directions, and a watch channel on every node and leaf that fires when the subtree beneath it is modified. Readers need no coordination: a committed tree never changes, so a reader holding one has a stable snapshot for as long as it holds it.
The API deliberately mirrors github.com/hashicorp/go-immutable-radix, which this is a drop-in replacement for, down to the split between CommitOnly and Notify that lets a caller publish a new root before waking any watchers. The difference is underneath: inner nodes come in four sizes and grow and shrink with their child count, rather than every node paying for one shape.
Index ¶
- type Iterator
- type Node
- func (n *Node[T]) Get(k []byte) (T, bool)
- func (n *Node[T]) GetWatch(k []byte) (<-chan struct{}, T, bool)
- func (n *Node[T]) Iterator() *Iterator[T]
- func (n *Node[T]) LongestPrefix(k []byte) ([]byte, T, bool)
- func (n *Node[T]) Maximum() ([]byte, T, bool)
- func (n *Node[T]) Minimum() ([]byte, T, bool)
- func (n *Node[T]) ReverseIterator() *ReverseIterator[T]
- func (n *Node[T]) Walk(fn WalkFn[T])
- func (n *Node[T]) WalkBackwards(fn WalkFn[T])
- func (n *Node[T]) WalkPath(path []byte, fn WalkFn[T])
- func (n *Node[T]) WalkPrefix(prefix []byte, fn WalkFn[T])
- type ReverseIterator
- type Tree
- func (t *Tree[T]) Delete(k []byte) (*Tree[T], T, bool)
- func (t *Tree[T]) DeletePrefix(k []byte) (*Tree[T], bool)
- func (t *Tree[T]) Get(k []byte) (T, bool)
- func (t *Tree[T]) Insert(k []byte, v T) (*Tree[T], T, bool)
- func (t *Tree[T]) Len() int
- func (t *Tree[T]) Root() *Node[T]
- func (t *Tree[T]) Txn() *Txn[T]
- type Txn
- func (t *Txn[T]) Clone() *Txn[T]
- func (t *Txn[T]) Commit() *Tree[T]
- func (t *Txn[T]) CommitOnly() *Tree[T]
- func (t *Txn[T]) Delete(k []byte) (T, bool)
- func (t *Txn[T]) DeletePrefix(prefix []byte) bool
- func (t *Txn[T]) Get(k []byte) (T, bool)
- func (t *Txn[T]) GetWatch(k []byte) (<-chan struct{}, T, bool)
- func (t *Txn[T]) Insert(k []byte, v T) (T, bool)
- func (t *Txn[T]) Notify()
- func (t *Txn[T]) Root() *Node[T]
- func (t *Txn[T]) TrackMutate(track bool)
- type WalkFn
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Iterator ¶
type Iterator[T any] struct { // contains filtered or unexported fields }
Iterator walks a set of nodes in key order.
The traversal stack lives inside the iterator rather than on the heap. A pull iterator has to keep its stack between calls to Next, so the obvious implementation allocates one; at the sizes a prefix scan uses, that single allocation costs more than the entire rest of the scan.
The inline array is indexed, never sliced. Slicing it would make the iterator hold a pointer into itself, which forces escape analysis to give up and heap allocate the whole iterator — measurably worse than simply letting a slice grow.
func (*Iterator[T]) SeekLowerBound ¶
SeekLowerBound seeks the iterator to the smallest key that is greater than or equal to the given key.
There is no watch variant: which nodes a change would have to touch to alter the result is not predictable from the structure the way it is for a prefix.
func (*Iterator[T]) SeekPrefix ¶
SeekPrefix seeks the iterator to a given prefix.
func (*Iterator[T]) SeekPrefixWatch ¶
SeekPrefixWatch seeks the iterator to a given prefix and returns the watch channel of the finest granularity reached.
type Node ¶
type Node[T any] struct { // contains filtered or unexported fields }
Node is an immutable node in the tree.
It is also the common header that every sized node kind embeds as its first field, so a *Node[T] can be converted to the concrete kind it heads with an unsafe pointer cast. That is what lets one pointer type serve both as the public handle for read operations and as the internal, kind-dispatched representation, without an interface — an interface-typed child pointer costs an extra word per child and gives back the memory the sized kinds exist to save.
func (*Node[T]) GetWatch ¶
GetWatch looks up a specific key, returning the watch channel, the value, and whether it was found.
func (*Node[T]) Iterator ¶
Iterator returns an iterator that walks the tree from this node forwards.
The stack is primed here rather than on the first call to Next, so that Next has no "have I started yet" flag to test on every call. Every seek re-primes it, so seeking after construction costs one wasted push and nothing else.
func (*Node[T]) LongestPrefix ¶
LongestPrefix is like Get, but instead of an exact match it returns the longest prefix match.
func (*Node[T]) ReverseIterator ¶
func (n *Node[T]) ReverseIterator() *ReverseIterator[T]
ReverseIterator returns an iterator that walks the tree from this node backwards.
func (*Node[T]) WalkBackwards ¶
WalkBackwards walks the tree in reverse key order.
A node's own value is the shortest key in its subtree, so it is visited after everything beneath it. This differs from the radix tree this replaces, whose WalkBackwards visits a node's value before its children and so does not actually produce reverse key order when one key is a proper prefix of another — a case its own tests never cover, and which its ReverseIterator handles correctly. The order here matches ReverseIterator.
func (*Node[T]) WalkPath ¶
WalkPath walks the tree visiting only nodes from the root down to the given path. Where WalkPrefix walks the entries *under* a prefix, this walks the entries *above* it.
func (*Node[T]) WalkPrefix ¶
WalkPrefix walks the entries under a prefix.
type ReverseIterator ¶
type ReverseIterator[T any] struct { // contains filtered or unexported fields }
ReverseIterator walks a set of nodes in reverse key order.
It carries its traversal stack inline for the same reason Iterator does; see the note there.
The radix tree this replaces tracked which internal nodes had already had their children pushed in a map keyed by node pointer, paying a map insert and a map delete for every internal node walked. Here that state is implicit in the frame that is already on the stack.
func NewReverseIterator ¶
func NewReverseIterator[T any](n *Node[T]) *ReverseIterator[T]
NewReverseIterator returns a new ReverseIterator at a node. The stack is primed here rather than on the first call to Previous, so that Previous has no "have I started yet" flag to test on every call. Every seek re-primes it.
func (*ReverseIterator[T]) Previous ¶
func (ri *ReverseIterator[T]) Previous() ([]byte, T, bool)
Previous returns the previous node in reverse order.
func (*ReverseIterator[T]) SeekPrefix ¶
func (ri *ReverseIterator[T]) SeekPrefix(prefix []byte)
SeekPrefix seeks the iterator to a given prefix.
func (*ReverseIterator[T]) SeekPrefixWatch ¶
func (ri *ReverseIterator[T]) SeekPrefixWatch(prefix []byte) (watch <-chan struct{})
SeekPrefixWatch seeks the iterator to a given prefix and returns the watch channel of the finest granularity reached.
func (*ReverseIterator[T]) SeekReverseLowerBound ¶
func (ri *ReverseIterator[T]) SeekReverseLowerBound(key []byte)
SeekReverseLowerBound seeks the iterator to the largest key that is lower than or equal to the given key.
There is no watch variant: which nodes a change would have to touch to alter the result is not predictable from the structure the way it is for a prefix.
type Tree ¶
type Tree[T any] struct { // contains filtered or unexported fields }
Tree implements an immutable adaptive radix tree. It can be treated as a dictionary abstract data type; the advantages over a hash map are prefix-based lookups and ordered iteration. The immutability means it is safe to read from a Tree concurrently without any coordination.
The zero value is not usable; call New.
func (*Tree[T]) Delete ¶
Delete removes a given key. It returns the new tree, the old value if any, and whether the key was set.
func (*Tree[T]) DeletePrefix ¶
DeletePrefix removes all keys starting with the given prefix. It returns the new tree and whether the prefix matched anything.
func (*Tree[T]) Insert ¶
Insert adds or updates a given key. It returns the new tree, the previous value, and whether one was set.
type Txn ¶
type Txn[T any] struct { // contains filtered or unexported fields }
Txn is a transaction on the tree. It is applied atomically and returns a new tree when committed. A transaction is not thread safe and should be used by a single goroutine at a time.
func (*Txn[T]) Clone ¶
Clone makes an independent copy of the transaction.
The new transaction does not track any nodes and has TrackMutate turned off. It contains any uncommitted writes made in the original, but further mutations to either are independent and result in different trees on commit. A cloned transaction may be passed to another goroutine and mutated there, though each transaction may only be mutated from one goroutine at a time.
func (*Txn[T]) Commit ¶
Commit finalizes the transaction and returns a new tree. If mutation tracking is on, notifications are issued as well.
func (*Txn[T]) CommitOnly ¶
CommitOnly finalizes the transaction and returns a new tree, without issuing any notifications until Notify is called.
This split is what lets a caller publish the new root before waking any watcher, so a woken watcher never observes the tree it was told had changed in its pre-change state.
func (*Txn[T]) Delete ¶
Delete removes a given key, returning the old value if any and whether the key was set.
func (*Txn[T]) DeletePrefix ¶
DeletePrefix removes an entire subtree matching the prefix, returning whether anything matched.
func (*Txn[T]) GetWatch ¶
GetWatch looks up a specific key, returning the watch channel of the deepest node reached, the value, and whether it was found.
func (*Txn[T]) Insert ¶
Insert adds or updates a given key, returning the previous value and whether one was set.
func (*Txn[T]) Notify ¶
func (t *Txn[T]) Notify()
Notify triggers the notifications recorded under TrackMutate. It must only be called once a transaction has been committed via CommitOnly, and is called automatically by Commit.
func (*Txn[T]) Root ¶
Root returns the current root of the tree within this transaction. The root is not stable across inserts and deletes, but can be used to read the current state during a transaction.
func (*Txn[T]) TrackMutate ¶
TrackMutate toggles whether mutations are tracked. If enabled, notifications are issued for affected internal nodes and leaves when the transaction is committed.
Source Files