README
¶
Golang Adaptive Radix Tree
Radix is a fully adaptive radix tree written in Go. A radix tree is space-optimized prefix tree (trie). An adaptive radix tree uses nodes of variable sizes to minimize memory use. The radix (r) for this implementation is 256.
For details on radix tree see https://en.wikipedia.org/wiki/Radix_tree
For background on adaptive radix trees, see the original ART paper https://db.in.tum.de/~leis/papers/ART.pdf
The tree is safe for concurrent use, and batch operations using multiple goroutines scales pretty well. Especially, concurrent lookups are look-free making them blazingly fast.
For performance reasons the tree uses multiple allocators, each working on it's own memory arena and having its own recycling data. The number of allocators is configurable, but defaults to runtime.NumCPU(). To safeguard concurrent reads, the allocators are used for all operations, including Lookups.
As an example 49 million URL:s, with an average length of 60 bytes, can be indexed using 10.21 bytes per key (including the 55 bit value pointer). This way billions of keys can be indexed in memory on a single server.
Features
- Safe for concurrent use
- Lock-free lookups
- Extremely memory efficient
- No garbage collection overhead
- Very fast to persist to disc
- Snappy compression of memory blocks written to disc
- Keeps data sorted
- Ordered iteration
- Ordered prefix iteration
- Min/max searches
- Prefix counting
Limitations
-
To save memory, this tree does not store the full keys. It only stores as much information as needed to distinguish between the different keys. It is assumed the full keys are retrievable by the user. In the typical use case they would be stored on a permanent storage.
-
Max 55 bits are available for storing values associated with the inserted keys. The values could be offsets to permanent storage or maybe compressed memory pointers.
-
The tree accepts any []byte data as keys, but in case you want to use range or min/max searches, the key data needs to be binary comparable. For uint64 all you need to do is store them in big-endian order. For int64 you also flip the sign bit. ASCII strings are trivial, but floating point numbers requires more transformations. UTF8 is rather complex (see golang.org/x/text/collate).
-
When indexing keys of variable length (like strings) the requirement is that no key may be the prefix of another key. A simple solution for this is to append a 0 byte on all keys (given 0 is not used within the keys).
Installation
go get -u github.com/jayloop/radix
Setup
trie := radix.NewTree(nil)
To specify the number of allocators.
trie := radix.NewTree(&radix.Options{
NumAllocators: 1,
})
Operations
Since the tree doesn't store the full keys, you need to verify that the value returned points to the correct key. It could otherwise be another key sharing a prefix with the lookup key.
key := []byte("foo")
v := trie.Lookup(key)
if v == 0 {
// nothing found
return NotFound
}
record := fetchRecordFromSomeStorage(v)
if string(key) != string(record.Key) {
// mismatch
return NotFound
}
// Match!
// do something with record
Update and delete operations are a multi-step process.
found, op := trie.PrepareUpdate(key)
If v is non-zero we must fetch the key associated with it and compare it to the insert key.
if found {
op.FetchedKey = fetchKeyFromSomeStorage(op.FetchedKey[:0], op.Value)
if string(key) == string(op.FetchedKey) {
// this is an update
// do some update logic or abort if we only wanted to insert
op.Match = true
} else {
// this is an insert
// do some insert logic or abort if we only wanted to update
}
}
if !op.Finalize(3) {
// write conflict, we need to restart with a new PrepareUpdate
}
Delete operations are similar:
found, op := trie.PrepareDelete(key)
if !found {
// nothing found
return
}
op.FetchedKey = fetchKeyFromSomeStorage(op.FetchedKey[:0], v)
if string(key) != string(op.FetchedKey) {
// mismatch
op.Abort()
return
}
if !op.Finalize() {
// write conflict, we need to restart with a new PrepareDelete
}
Using allocators
To speed up batch data operations, you can require an allocator and use it for all operations, then release it.
a := trie.GetAllocator()
defer trie.ReleaseAllocator(a)
a.Lookup(key)
a.PrepareUpdate(key)
a.PrepareDelete(key)
// ...
Iterators and range scans
To iterate the whole index in lexicographic order:
i := NewIterator(trie, nil)
for i.Next() {
v := i.Value()
// ...
}
To iterate part of the index, or make range searches, pass the prefix to NewIterator
i := NewIterator(trie, []byte("prefix"))
Documentation
¶
Overview ¶
Package radix implements a memory efficient and concurrency safe adaptive radix tree (ART).
The typical use case is an in-memory database index where the tree stores a pointer to where an object is stored on a permanent storage.
The data structure is free of memory pointers so the overhead from garbage collection is minimal.
Limitations ¶
1. To save memory, this tree does not store the full keys in the leaves. It only stores as much information as needed to distinguish between the different keys. It is assumed the full keys are retrievable by the user. In the typical use case they would be stored on a permanent storage.
2. Max 55 bits are available for storing values associated with the inserted keys. The values could be offsets to permanent storage or compressed memory pointers.
3. The tree accepts any []byte data as keys, but in case you want to use range or min/max searches, the key data needs to be binary comparable. For uint64 all you need to do is store them in big-endian order. For int64 the sign bit also needs to be flipped. ASCII strings are trivial, but floating point numbers requires more transformations. UTF8 is rather complex (see golang.org/x/text/collate).
4. When indexing keys of variable length (like strings) the requirement is that no key may be the prefix of another key. A simple solution for this is to append a 0 byte on all keys (given 0 is not used within the keys).
Unsafe usage ¶
For improved performance unsafe operations are used in two cases: when persisting uint64 slices to a state file and when accessing []byte prefixes within the uint64 slices.
Index ¶
- type Allocator
- type Counter
- type DeleteOperation
- type Iterator
- type Options
- type Tree
- func (idx *Tree) Admin(out io.Writer, argv []string)
- func (idx *Tree) Close()
- func (idx *Tree) Count(searchPrefix []byte) (nodes, leaves int)
- func (idx *Tree) GetAllocator() *Allocator
- func (idx *Tree) Len() (count int)
- func (idx *Tree) Lookup(key []byte) (value uint64, found bool)
- func (idx *Tree) MaxKey(searchPrefix []byte) (v uint64, ok bool)
- func (idx *Tree) MinKey(searchPrefix []byte) (v uint64, ok bool)
- func (idx *Tree) NewIterator(searchPrefix []byte) *Iterator
- func (idx *Tree) PrepareDelete(key []byte) (found bool, op *DeleteOperation)
- func (idx *Tree) PrepareUpdate(key []byte) (found bool, op *UpdateOperation)
- func (idx *Tree) ReleaseAllocator(a *Allocator)
- func (idx *Tree) Start()
- func (idx *Tree) Stats(stats map[string]interface{})
- func (idx *Tree) Stop()
- func (idx *Tree) WriteState(out io.Writer) (n int, err error)
- type UpdateOperation
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Allocator ¶
type Allocator struct {
// contains filtered or unexported fields
}
An Allocator is responsible for allocating new uint64 slots for storing tree nodes and manages the recycling of removed nodes. Since lookups are lock free an node might be recycled through an update operation while a reader is accessing it. To prevent the node from being used again until the read operation is done readers reserve the current epoch using the allocator. It's normally not needed to work directly with an allocator, but for bulk lookup/delete/update operations you will get better performance by acquiring an allocator and using it directly.
a := trie.GetAllocator()
for {
v := a.Lookup(key)
...
}
trie.ReleaseAllocator(a)
An allocator is not safe for concurrent use.
func (*Allocator) FlushStats ¶
func (a *Allocator) FlushStats()
FlushStats updates tree global stats with the allocators private counters.
func (*Allocator) Lookup ¶
Lookup searches the tree for a key and if a candidate leaf is found returns the value stored with it. The caller needs to verify that the candidate is equal to the lookup key, since if the key didn't exist, the candidate will be another key sharing a prefix with the lookup key.
func (*Allocator) PrepareDelete ¶
func (a *Allocator) PrepareDelete(key []byte) (found bool, op *DeleteOperation)
PrepareDelete prepares an delete operation on the given key. It returns if it did find a candidate key and an DeleteOperation used to finalize or abort the operation. If returns a nil op if and only if found is false. In this case there is nothing to delete.
found, op := a.PreparDelete([]byte("hello"))
if !found {
// key didn't exist
}
If a candidate is found the caller must fetch the full key for op.Value into the op.FetchedKey field. The caller should compare this value to the update key (op.Key) to verify we are deleting the right key. If they don't match, call op.Abort. Since operation structs are pooled it's best to reuse the slice at op.FetchedKey.
if found {
op.FetchedKey = fetchKeyFromSomeStorage(op.FetchedKey[:0], op.Value)
if bytes.Equal(op.Key, op.FetchedKey) {
// it was a match, go ahead with delete
if deleted := op.Finalize(); !deleted {
// write conflict, we need to restart with a new PrepareDelete
}
} else {
// wrong key, abort
op.Abort()
}
}
func (*Allocator) PrepareUpdate ¶
func (a *Allocator) PrepareUpdate(key []byte) (found bool, op *UpdateOperation)
PrepareUpdate prepares an update operation for the given key. It returns if it did find a key candidate and an UpdateOperation used to finalize or abort the operation. If not found it's a simple insert operation:
found, op := a.PrepareUpdate([]byte("hello"))
if !found {
// this is an insert
if inserted := op.Finalize(NEW_VALUE); !inserted {
// write conflict, we need to restart with a new PrepareUpdate
}
}
If a key candidate is found the caller must fetch the full key for op.Value into the op.FetchedKey field. The caller should compare this value to the update key (op.Key) and set op.Match accordingly before finalizing. Since operation structs are pooled it's best to reuse the slice at op.FetchedKey.
if found {
op.FetchedKey = fetchKeyFromSomeStorage(op.FetchedKey[:0], op.Value)
if bytes.Equal(op.Key, op.FetchedKey) {
// this is an update
// do some update logic
op.Match = true
if updated := op.Finalize(NEW_VALUE); !updated {
// write conflict, we need to restart with a new PrepareUpdate
}
} else {
// this is an insert
// do some insert logic
if inserted := op.Finalize(NEW_VALUE); !inserted {
// write conflict, we need to restart with a new PrepareUpdate
}
}
}
type Counter ¶
type Counter struct {
NodesWithPrefix int
NodeSizes []int
TotalPrefixLength int
TotalPrefixBytes int
LargePrefixes int
Elapsed time.Duration
// contains filtered or unexported fields
}
A Counter counts objects in a Tree
type DeleteOperation ¶
type DeleteOperation struct {
// the value of the found item, if any
Value uint64
// FetchedKey is not used during a delete operation, but is provided as a convienance to the caller
// to avoid having to allocate a new slice for fetching the key (the DeleteOperation is pooled)
FetchedKey []byte
// contains filtered or unexported fields
}
DeleteOperation represents the action to remove a key from the tree. A delete operation is initiated through calling PrepareUpdate on a Tree or an Allocator
func (*DeleteOperation) Abort ¶
func (op *DeleteOperation) Abort()
Abort aborts the delete operation, unlocking any locks taken during the prepare call and recycles the *DeleteOperation. The *DeleteOperation may not be used again after the call.
func (*DeleteOperation) Finalize ¶
func (op *DeleteOperation) Finalize() (deleted bool)
Finalize finalizes the delete operation. It returns true if the delete was successful. If false, there was a write conflict and the operation must be restarted. The *DeleteOperation may not be used again after the call.
func (*DeleteOperation) String ¶
func (op *DeleteOperation) String() (s string)
type Iterator ¶
type Iterator struct {
// contains filtered or unexported fields
}
An Iterator is used to scan all or parts of a Tree in lexicographical order. Iterators run concurrently with updates or deletes. Items inserted or deleted during the iteration may or may not be seen. Iterator is not safe for concurrent use.
func NewIterator ¶
NewIterator returns an Iterator on tree for listing all items having the prefix (prefix may be nil to list all items). To recycle the Iterator struct, call Iterator.Close once you are done with it.
func (*Iterator) Close ¶
func (i *Iterator) Close()
Close returns the Iterator the the pool. It must not be used after this call.
func (*Iterator) Next ¶
Next prepares the next item for reading with the Value method. It returns true on success, or false if there are no more values.
Every call to Value, even the first one, must be preceded by a call to Next.
type Options ¶
type Options struct {
NumAllocators int // default is runtime.NumCPU()
}
Options are used when creating a new Tree.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
A Tree is a concurrent safe adaptive radix tree.
func NewTree ¶
NewTree creates a new Tree.
Example ¶
package main
import (
"github.com/jayloop/radix"
)
func main() {
_ = radix.NewTree(&radix.Options{
NumAllocators: 4,
})
}
Output:
func NewTreeFromState ¶
NewTreeFromState initiates a Tree from state data previously written by
func (*Tree) Admin ¶
Admin provides some index debug and admin functions for use by a CLI or terminal. It takes a writer and a slice with the command and arguments.
func (*Tree) Close ¶
func (idx *Tree) Close()
Close stops the index, and then terminates the memory allocation goroutine, which will otherwise leak.
func (*Tree) Count ¶
Count returns the number of nodes and leaves in the part of tree having the given prefix, or the whole tree if searchPrefix is nil.
func (*Tree) GetAllocator ¶
GetAllocator reserves an allocator used for bulk Lookup/Update/Delete operations.
Example ¶
package main
import (
"github.com/jayloop/radix"
)
func main() {
t := radix.NewTree(nil)
a := t.GetAllocator()
_, _ = a.Lookup([]byte("hello"))
t.ReleaseAllocator(a)
}
Output:
func (*Tree) Len ¶
Len returns the current number of items in the tree It needs to query all allocators for their counters, so it will block if an allocator is constantly reserved...
func (*Tree) Lookup ¶
Lookup searches the tree for a key and if a candidate leaf is found returns the value stored with it. The caller needs to verify if the candidate is equal to the lookup key, since if the key didn't exist, the candidate will be another key sharing a prefix with the lookup key.
func (*Tree) MaxKey ¶
For example, if we store temperature readings using the key "temp_TIMESTAMP" where timestamp is an 8 byte BigEndian ns timestamp MaxKey([]byte("temp_")) returns the last made reading.
func (*Tree) MinKey ¶
MinKey returns the minimum key having the given searchPrefix, or the minimum key in the whole index if searchIndex is nil. Minimum means the first key in the lexicographic order. If keys are uint64 in BigEndian it is also the smallest number. If ok is false the index is empty.
func (*Tree) NewIterator ¶
NewIterator returns an Iterator for iterating in order over all keys having the given prefix, or the complete index if searchPrefix is nil.
func (*Tree) PrepareDelete ¶
func (idx *Tree) PrepareDelete(key []byte) (found bool, op *DeleteOperation)
PrepareDelete reserves an allocator and uses it to prepare a delete operation. See Allocator.PrepareDelete for details
func (*Tree) PrepareUpdate ¶
func (idx *Tree) PrepareUpdate(key []byte) (found bool, op *UpdateOperation)
PrepareUpdate reserves an allocator and uses it to prepare an update operation. See Allocator.PrepareUpdate for details
func (*Tree) ReleaseAllocator ¶
ReleaseAllocator returns an allocator previously reserved using GetAllocator
func (*Tree) Start ¶
func (idx *Tree) Start()
Start releases all allocators withdrawn through a previous call to Stop. In case the indexed is not stopped in returns silently.
type UpdateOperation ¶
type UpdateOperation struct {
// points to key data used in call to PrepareUpdate
Key []byte
// the value of the found item, if any
Value uint64
// the key data fetched by the caller after call to PrepareUpdate (and before FinalizeUpdate)
FetchedKey []byte
// set true by caller if FetchedKey equals Key
Match bool
// contains filtered or unexported fields
}
UpdateOperation represents the action to insert a new value or update on existing value in a tree. An update operation is initiated through calling PrepareUpdate on a Tree or an Allocator.
func (*UpdateOperation) Abort ¶
func (op *UpdateOperation) Abort()
Abort aborts the update operation, unlocking any locks taken during the prepare call and recycles the *UpdateOperation. The *UpdateOperation may not be used again after the call.
func (*UpdateOperation) Finalize ¶
func (op *UpdateOperation) Finalize(value uint64) (updated bool)
Finalize performs the update or insert in the tree, storing the given value at the prepared location. In case the value is larger than 55 bits it will be truncated. It returns true if the update was successful. If false, there was a write conflict and the operation must be restarted. The *UpdateOperation may not be used again after the call.
func (*UpdateOperation) String ¶
func (op *UpdateOperation) String() (s string)
String returns a description of the operation
Source Files
Directories