Scaling Akvorado BMP RIB with sharding

Summary

To associate routing information—like AS paths or BGP communities—to flows, Akvorado can import routes through the BGP Monitoring Protocol (BMP). As the Internet routing table contains more than 1 million routes, Akvorado needs to scale to tens of millions of routes.1 This has been a long-standing challenge,2 but I expect this issue is now fixed by using RIB sharding, a method that splits the routing database into several parts to enable concurrent updates. 1 Each router exporting flows doesn’t need to send its routes. When Akvorado does not find a route from a specific device, it falls back to a route sent by another device. It is up to the operator to decide if this is a good enough approximation. ❦ Previous implementation Akvorado connects 2 elements to build its RIB: a prefix tree, and a list of routes attached to each prefix. Akvorado BMP RIB implementation without sharding. One single read/write lock. In the diagram above, the RIB stores five IPv4 prefixes and two IPv6 prefixes. One of them, 2001:db8:1::/48, contains three routes: from peer 3, next hop 2001:db8::3:1, AS 65402, AS path 65402, community 65402:31, from peer 4, next hop 2001:db8::4:1, same ASN, AS path, and community, from peer 5, next hop 2001:db8::5:1, AS 65402, AS path 65401 65402, community 65402:31. The rib structure is defined in Go as follows: type rib struct { tree *bart.Table[prefixIndex] routes map[routeKey]route nlris *intern.Pool[nlri] nextHops *intern.Pool[nextHop] rtas *intern.Pool[routeAttributes] nextPrefixID prefixIndex freePrefixIDs []prefixIndex } The prefix tree uses the bart package, an adaptation of Donald Knuth’s ART algorithm. The benchmarks demonstrate it outperforms other packages for lookups, insertions, and memory usage.3 Plus, the author is quite helpful. 3 It keeps improving: bart 0.28.0 features a new implementation that trades a bit of memory for greater lookup performance. I did not test it yet, as I have been preparing this blog post for a couple of months already...