package bart

Overview

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.

The CBT is implemented as a bit-vector, backtracking is just a matter of fast cache friendly bitmask operations.

The bart.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 and has an even better lookup speed.

The algorithm is also excellent for determining whether two tables contain overlapping IP addresses.

A bart.Lite version is also included, this is ideal for simple IP access-control-lists, a.k.a. longest-prefix matches with plain true/false results.

For all more complex tasks, the powerful bart.Table must be used.

Example

func ExampleLite_Contains() {
	lite := new(bart.Lite)

	// Insert some prefixes
	prefixes := []string{
		"192.168.0.0/16",       // corporate
		"192.168.1.0/24",       // department
		"2001:7c0:3100::/40",   // corporate
		"2001:7c0:3100:1::/64", // department
		"fc00::/7",             // unique local
	}

	for _, s := range prefixes {
		pfx := netip.MustParsePrefix(s)
		lite.Insert(pfx)
	}

	// Test some IP addresses for black/whitelist containment
	ips := []string{
		"192.168.1.100",      // must match, department
		"192.168.2.1",        // must match, corporate
		"2001:7c0:3100:1::1", // must match, department
		"2001:7c0:3100:2::1", // must match, corporate
		"fc00::1",            // must match, unique local
		//
		"172.16.0.1",        // must NOT match
		"2003:dead:beef::1", // must NOT match
	}

	for _, s := range ips {
		ip := netip.MustParseAddr(s)
		ok := lite.Contains(ip)
		fmt.Printf("%-20s is contained: %t\n", ip, ok)
	}

	// Output:
	// 192.168.1.100        is contained: true
	// 192.168.2.1          is contained: true
	// 2001:7c0:3100:1::1   is contained: true
	// 2001:7c0:3100:2::1   is contained: true
	// fc00::1              is contained: true
	// 172.16.0.1           is contained: false
	// 2003:dead:beef::1    is contained: false
}

API

Release v0.18 requires at least go1.23 and we use the iter.Seq2[netip.Prefix, V] types for iterators. The lock-free versions of insert, update and delete are added, but still experimentell.

  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. Either the update operations must be protected by an
    // external lock mechanism or the various ...Persist functions must be used
    // which return a modified routing table by leaving the original unchanged

    // A Table must not be copied by value, see Table.Clone.

  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]) Insert(pfx netip.Prefix, val V)
  func (t *Table[V]) Delete(pfx netip.Prefix)
  func (t *Table[V]) Update(pfx netip.Prefix, cb func(val V, ok bool) V) (newVal V)

  func (t *Table[V]) InsertPersist(pfx netip.Prefix, val V) *Table[V]
  func (t *Table[V]) DeletePersist(pfx netip.Prefix) *Table[V]
  func (t *Table[V]) UpdatePersist(pfx netip.Prefix, cb func(val V, ok bool) V) (pt *Table[V], newVal V)

  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]) GetAndDeletePersist(pfx netip.Prefix) (pt *Table[V], val V, ok bool)

  func (t *Table[V]) Union(o *Table[V])
  func (t *Table[V]) Clone() *Table[V]

  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)   iter.Seq2[netip.Prefix, V]
  func (t *Table[V]) Supernets(pfx netip.Prefix) iter.Seq2[netip.Prefix, V]

  func (t *Table[V]) All()  iter.Seq2[netip.Prefix, V]
  func (t *Table[V]) All4() iter.Seq2[netip.Prefix, V]
  func (t *Table[V]) All6() iter.Seq2[netip.Prefix, V]

  func (t *Table[V]) AllSorted()  iter.Seq2[netip.Prefix, V]
  func (t *Table[V]) AllSorted4() iter.Seq2[netip.Prefix, V]
  func (t *Table[V]) AllSorted6() iter.Seq2[netip.Prefix, V]

  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]

  type Lite struct {
  	// Has unexported fields.
  }
  //  Lite is the little sister of Table. Lite is ideal for simple IP
  //  access-control-lists, a.k.a. longest-prefix matches with plain
  //  true/false results.
  //
  //  For all other tasks, the much more powerful Table must be used.
  
  func (l *Lite) Insert(pfx netip.Prefix)
  func (l *Lite) Delete(pfx netip.Prefix)
  func (l *Lite) Contains(ip netip.Addr) bool

benchmarks

Please see the extensive benchmarks comparing bart with other IP routing table implementations.

Just a teaser, Contains and Lookup against the Tier1 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
BenchmarkFullMatch4/Contains         	80015762	        14.54 ns/op
BenchmarkFullMatch6/Contains         	93395781	        12.78 ns/op
BenchmarkFullMiss4/Contains          	264677362	         4.562 ns/op
BenchmarkFullMiss6/Contains          	250739491	         4.802 ns/op
PASS
ok  	github.com/gaissmai/bart	11.834s

goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatch4/Lookup         	52176051	        22.44 ns/op
BenchmarkFullMatch6/Lookup         	82442416	        14.50 ns/op
BenchmarkFullMiss4/Lookup          	174474836	         6.881 ns/op
BenchmarkFullMiss6/Lookup          	164121382	         7.340 ns/op
PASS
ok  	github.com/gaissmai/bart	12.399s

Compatibility Guarantees

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.

CONTRIBUTION

Please open an issue for discussion before sending a pull request.

CREDIT

Standing on the shoulders of giants.

Credits for many inspirations go to

• the clever guys at tailscale,
• to Daniel Lemire for his inspiring blog,
• to Donald E. Knuth for the ART routing algorithm and
• to Yoichi Hariguchi who deciphered it for us mere mortals

And last but not least to the Go team who do a wonderful job!

LICENSE

MIT