package bart provides a Balanced-Routing-Table (BART).
BART is balanced in terms of memory usage and lookup time for the longest-prefix match.
BART is a multibit-trie with fixed stride length of 8 bits, using the baseIndex function from the ART algorithm to build the complete-binary-tree (CBT) of prefixes for each stride.
 |
|---|
| example from artlookup.pdf for a 4bit stride |
The CBT is implemented as a bit-vector, backtracking is just a matter of fast cache friendly bitmask operations.
The Table is implemented with popcount compressed sparse arrays together with path compression. This reduces storage consumption by almost two orders of magnitude in comparison to ART with similar lookup times for the longest prefix match.
The API has changed in ..., v0.10.1, v0.11.0, v0.12.0, v0.12.6, v0.16.0
import "github.com/gaissmai/bart"
type Table[V any] struct {
// Has unexported fields.
}
Table is an IPv4 and IPv6 routing table with payload V. The zero value is
ready to use.
The Table is safe for concurrent readers but not for concurrent readers
and/or writers.
func (t *Table[V]) Insert(pfx netip.Prefix, val V)
func (t *Table[V]) Update(pfx netip.Prefix, cb func(val V, ok bool) V) (newVal V)
func (t *Table[V]) Delete(pfx netip.Prefix)
func (t *Table[V]) Get(pfx netip.Prefix) (val V, ok bool)
func (t *Table[V]) GetAndDelete(pfx netip.Prefix) (val V, ok bool)
func (t *Table[V]) Union(o *Table[V])
func (t *Table[V]) Clone() *Table[V]
func (t *Table[V]) Contains(ip netip.Addr) bool
func (t *Table[V]) Lookup(ip netip.Addr) (val V, ok bool)
func (t *Table[V]) LookupPrefix(pfx netip.Prefix) (val V, ok bool)
func (t *Table[V]) LookupPrefixLPM(pfx netip.Prefix) (lpm netip.Prefix, val V, ok bool)
func (t *Table[V]) OverlapsPrefix(pfx netip.Prefix) bool
func (t *Table[V]) Overlaps(o *Table[V]) bool
func (t *Table[V]) Overlaps4(o *Table[V]) bool
func (t *Table[V]) Overlaps6(o *Table[V]) bool
func (t *Table[V]) Subnets(pfx netip.Prefix) func(yield func(netip.Prefix, V) bool)
func (t *Table[V]) Supernets(pfx netip.Prefix) func(yield func(netip.Prefix, V) bool)
func (t *Table[V]) All() func(yield func(pfx netip.Prefix, val V) bool)
func (t *Table[V]) All4() func(yield func(pfx netip.Prefix, val V) bool)
func (t *Table[V]) All6() func(yield func(pfx netip.Prefix, val V) bool)
func (t *Table[V]) AllSorted() func(yield func(pfx netip.Prefix, val V) bool)
func (t *Table[V]) AllSorted4() func(yield func(pfx netip.Prefix, val V) bool)
func (t *Table[V]) AllSorted6() func(yield func(pfx netip.Prefix, val V) bool)
func (t *Table[V]) Size() int
func (t *Table[V]) Size4() int
func (t *Table[V]) Size6() int
func (t *Table[V]) String() string
func (t *Table[V]) Fprint(w io.Writer) error
func (t *Table[V]) MarshalText() ([]byte, error)
func (t *Table[V]) MarshalJSON() ([]byte, error)
func (t *Table[V]) DumpList4() []DumpListNode[V]
func (t *Table[V]) DumpList6() []DumpListNode[V]Please see the extensive benchmarks comparing bart with other IP routing table implementations.
Just a teaser, Contains and Lookups against the full Internet routing table with random IP address probes:
goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatchV4/Contains 38003740 27.69 ns/op
BenchmarkFullMatchV6/Contains 49389355 23.00 ns/op
BenchmarkFullMissV4/Contains 42902048 26.57 ns/op
BenchmarkFullMissV6/Contains 128219610 9.375 ns/op
PASS
ok github.com/gaissmai/bart 12.195s
goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatchV4/Lookup 37453425 30.55 ns/op
BenchmarkFullMatchV6/Lookup 36819931 30.48 ns/op
BenchmarkFullMissV4/Lookup 37223881 30.70 ns/op
BenchmarkFullMissV6/Lookup 94333762 12.32 ns/op
PASS
ok github.com/gaissmai/bart 11.215s
The package is currently released as a pre-v1 version, which gives the author the freedom to break backward compatibility to help improve the API as he learns which initial design decisions would need to be revisited to better support the use cases that the library solves for.
These occurrences are expected to be rare in frequency and the API is already quite stable.
Please open an issue for discussion before sending a pull request.
Standing on the shoulders of giants.
Credits for many inspirations go to
- the clever guys at tailscale,
- to Daniel Lemire, and
- to Donald E. Knuth for the ART routing algorithm and
all the rest of his Art and for keeping important algorithms in the public domain!
And last but not least to the Go team who do a wonderful job!
MIT