A high-performance, memory-efficient IP routing table library for Go, optimized for ACL, RIB, and FIB use cases.
BART (Balanced Routing Table) is a Go library implementing an adaptation of Donald Knuth's ART algorithm for IP prefix matching. It provides three specialized routing table types optimized for different performance and memory trade-offs, making it ideal for firewalls, routers, and systems requiring large-scale IP lookups.
Network engineers and developers building firewalls, routers, routing daemons, or any system that needs high-performance, memory-efficient IP prefix matching (e.g., for ACLs, RIB, or FIB).
Developers choose BART for its unique combination of constant-time per-level lookups, novel path and fringe compression for memory efficiency, and three optimized table types (Table, Lite, Fast) to precisely match their speed vs. memory requirements.
The Balanced Routing Table is an adaptation of D. Knuth's ART algorithm and requires significantly less memory and has an even better lookup speed.
Open-Awesome is built by the community, for the community. Submit a project, suggest an awesome list, or help improve the catalog on GitHub.
Uses bitmask operations accelerated by CPU instructions like POPCNT, achieving O(1) performance per trie level, with benchmarks showing ~10 ns per lookup for full routing tables.
Implements novel path and fringe compression, reducing memory consumption by nearly two orders of magnitude compared to classical ART, as detailed in the NODETYPES.md file.
Offers bart.Table for balance, bart.Lite for 35% less memory in prefix-only operations, and bart.Fast for 50-100% faster lookups, allowing precise speed vs. memory trade-offs.
Supports lock-free reads with synchronized writes, making it suitable for routing daemons with multiple readers, as demonstrated in the concurrent test examples.
The package is in a pre-v1 version, meaning backward compatibility isn't guaranteed and breaking changes could occur, as explicitly stated in the Compatibility Guarantees section.
Uses a mutex for synchronized writes, allowing only one writer at a time, which can limit performance in scenarios with frequent concurrent updates, unlike fully lock-free structures.
For optimal speed, users must compile with specific CPU feature flags like GOAMD64=v3, adding complexity to the build process and potentially reducing portability.