Log in
Vincent Bernat: Scaling Akvorado BMP RIB with sharding
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.
Previous implementation
Akvorado connects 2 elements to build its RIB:
- a prefix tree, and
- a list of routes attached to each prefix.
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 path65402, community65402: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 path65401 65402, community65402: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.
Storing routes in a map
The list of routes for each prefix is not stored directly in the prefix tree: it would put too much pressure on the garbage collector by allocating per-prefix arrays.
Instead, the RIB assigns a unique 32-bit prefix identifier for each prefix,
either by picking the last available prefix identifier from the freePrefixIDs
array if any, or using the nextPrefixID value before incrementing it. Then,
the routes are stored in the routes map, leveraging the optimized Swiss
table in Go. To retrieve routes attached to a prefix, we look them up
one by one in the routes map with a 64-bit key combining the 32-bit prefix
index with a 32-bit route index matching the position of the route in the list.
Akvorado scans routes from the first to the last to find the best one.4 It
knows there is no more route if the route key returns no result.
type prefixIndex uint32 type routeIndex uint32 type routeKey uint64
Interning routes
A route contains a BGP peer identifier, a partial NLRI5, the next hop, and the attributes.
type route struct { peer uint32 nlri intern.Reference[nlri] nextHop intern.Reference[nextHop] attributes intern.Reference[routeAttributes] prefixLen uint8 } type nlri struct { family bgp.Family path uint32 rd RD } type nextHop netip.Addr type routeAttributes struct { asn uint32 asPath []uint32 communities []uint32 largeCommunities []bgp.LargeCommunity }
To save memory and allocations, NLRI, next hops, and route attributes are
“interned”: a 32-bit integer replaces the real value. The mechanism predates the
unique package introduced in Go 1.23. We keep it because it has
different trade-offs:
- It uses explicit reference counting instead of relying on weak pointers.
- It works with non-comparable values implementing
Hash()andEqual()methods.6 - It uses explicit pool instances. This will be useful for sharding.
- It has better performance. See for example this benchmark.
- It consumes half the memory thanks to unsigned 32-bit references instead of pointers.
- But it is not safe for concurrent use.
Why does it not scale?
Note
At AS 12322, we don’t use BMP yet.7 But Gerhard Bogner had the patience, availability, and technical skills to help me debug this issue.
The global read/write lock is a bottleneck in this implementation. But how? There are several users of the RIB, each with its own set of constraints:
-
The Kafka workers look up the RIB to enrich flows with routing information. They are bound by the number of Kafka partitions.8 Akvorado also adjusts their number to ensure efficient batching to ClickHouse. On our setup, the number of workers oscillates between 8 and 16. As we want to observe the latest data, we cannot afford for the Kafka workers to lag too much.
-
The monitored routers send route updates through the BMP protocol. When connecting, they can send millions of routes.9 After the initial synchronization, updates are sent continuously and may spike from time to time. The router detects a stuck BMP station when its TCP window is full and resets the session in this case. While Akvorado implements a large incoming buffer, it still needs to update the received routes with the write lock held fast enough to avoid being detected as stuck.
-
When a remote BGP peer goes down, Akvorado flushes the associated routes by walking the RIB with the write lock held. When a monitored router goes down, Akvorado waits a bit but eventually flushes all the associated routes.
In short: on a busy setup, lock contention is high for both readers and writers, and neither can lag too much behind.
RIB sharding
First step: basic sharding
To remove the global lock, the RIB is split into several “shards,” each one handling a subset of the prefixes:
The prefix tree stays global and is protected by a single lock. Each shard gets
its read/write lock, its route map, and its intern pools to store NLRIs, next
hops, and route attributes, which would not have been possible with Go’s
unique package. The prefix indexes are also sharded: the 8 most
significant bits are the shard index and the 24 remaining bits are the local
prefix index.
Gerhard confirmed that after this blind change, the BMP receiver chugged steadily. 🎉
Later, I wrote a concurrent benchmark over half a million synthetic but plausible routes10 partitioned over 0 to 8 writers, churning routes as fast as possible, while 1 to 16 readers continuously look up a set of 10,000 routes. I don’t know if this benchmark is realistic, but it confirms the improvements for both read and write latencies:
It also shows that a high number of writers degrades read latency.
Second step: lock-free reads
The single read/write lock protecting the prefix tree is the next target. The bart package provides alternative mutation methods returning an updated tree using copy-on-write. Readers don’t need the global lock any more, leaving it only to synchronize writers. The prefix tree is boxed in an atomic pointer.
Without a lock, readers can now fetch a stale prefix index when walking their copy of the tree if a concurrent writer removes the last route attached to this prefix index and recycles it for another prefix. To avoid this issue, we combine the prefix index with a generation number and store them in the tree:
type generation uint32 type prefixRef struct { idx prefixIndex gen generation } type rib struct { mu sync.Mutex tree atomic.Pointer[bart.Table[prefixRef]] shards []*ribShard }
Each shard stores the generation number for each local prefix index. The
generation number increases by one if the associated prefix index is freed. When
looking up the routes attached to a prefix index, the reader checks if the
generation number matches. Otherwise, it assumes the index was recycled and the
list of routes is empty.11 You can see this case in the diagram above for
prefix index 5, stored with a generation index of 3, while the current value in
the []generations array is 4. The generation number could overflow, but it is
not a problem as lookups are quick.
Running the concurrent benchmark against this new implementation shows the improvements for the read latency as soon as the cost of the copy-on-write prefix tree is amortized.
Among the multiple attempts to optimize the BMP component, RIB sharding is one of the more satisfying. Akvorado 2.2 implements the first step. PR #2433, drafted while writing this blog post, implements the second step and was released with Akvorado 2.4. 🪓
-
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. ↩
-
I made many attempts to scale the BMP component. See for example PR #254, PR #255, PR #278, PR #2244, and PR #2245. Despite these efforts, this component remained problematic for some users. See discussion #2287 as the latest example. ↩
-
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. ↩
-
Akvorado prefers the route matching the exact next hop. Otherwise, it falls back to any other route. This is an approximation. An alternative would be to have one prefix tree for each BGP peer but it would require configuring all routers to export their routes. pmacct’s BMP daemon implements this approach. ↩
-
If we consider the BGP RIB as a database, the Network Layer Reachability Information (NLRI) is the primary key. Its content depends on the BGP family. With IPv4 or IPv6 unicast, this is the prefix. For VPNv4 and VPNv6 families, it includes the route distinguisher. If you enable the ADD-PATH extension, the NLRI also contains a path identifier.
In our implementation, we don’t store the prefix as we get it from the looked-up IP address using the prefix length stored separately. ↩
-
The
Hash()methods rely on thehash/maphashpackage and on theunsafepackage to avoid memory copies. See for example theHash()function for thenlristructure. ↩ -
Despite being an author or co-author of the first BMP-related RFCs since 2016 (RFC 7854, RFC 8671, RFC 9069), Cisco did not implement it in a usable way in IOS XR until version 24.2.1. We still need to upgrade a few routers to enable this feature. ↩
-
KIP-932 introduces, in Kafka 4.2, the concept of share groups to enable cooperative consumption on the same partition. This is not supported in Akvorado yet. ↩
-
You can configure BMP to send routes for each BGP peer before or after applying the incoming policies. In this case, you can get more than one million routes for each transit peer. You can also tell BMP to send the local RIB, which only contains the best path for each prefix. ↩
-
The prefixes are random, but the prefix size distribution and the AS path length distribution follow the data provided by Geoff Huston. ↩
-
Alternatively, we could retry the lookup, but it would be pointless: the RIB is an eventually consistent database, and an empty list was a correct answer at some point in the recent past. ↩
