Scaling Akvorado BMP RIB with sharding

# Scaling Akvorado BMP RIB with sharding Source: [https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding) To associate routing information—like AS paths orBGPcommunities—to flows,[Akvorado](https://github.com/akvorado/akvorado)can import routes through the[BGPMonitoring Protocol](https://www.rfc-editor.org/rfc/rfc7854)\(BMP\)\. As the Internet routing table contains more than[1 million routes](https://bgp.potaroo.net/), Akvorado needs to**scale to tens of millions of routes**\.[1](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#sidenote-optimize)This has been a long\-standing challenge,[2](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#sidenote-past)but I expect this issue is now fixed by using**RIBsharding**, a method that splits the routing database into several parts to enable concurrent updates\. - [Previous implementation](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#previous-implementation)- [Storing routes in a map](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#storing-routes-in-a-map) - [Interning routes](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#interning-routes) - [Why does it not scale?](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#why-does-it-not-scale) - [RIB sharding](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#rib-sharding)- [First step: basic sharding](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#first-step-basic-sharding) - [Second step: lock\-free reads](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#second-step-lock-free-reads) ## Previous implementation[\#](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#previous-implementation) Akvorado connects 2 elements to build itsRIB: 1. a**prefix tree**, and 2. a**list of routes**attached to each prefix\.  Akvorado BMP RIB implementation without sharding\. One single read/write lock\.In the diagram above, theRIBstores 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`, sameASN, 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](https://github.com/gaissmai/bart/)package, an adaptation of Donald Knuth’s[ART algorithm](https://www.hariguchi.org/art/art.pdf)\. The[benchmarks](https://github.com/gaissmai/iprbench)demonstrate it outperforms other packages for lookups, insertions, and memory usage\.[3](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#sidenote-performance)Plus, the author is quite helpful\. ## Storing routes in a map[\#](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#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, theRIBassigns 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](https://go.dev/blog/swisstable)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](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#sidenote-scan)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[\#](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#interning-routes) A route contains aBGPpeer identifier, a partialNLRI[5](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#sidenote-nlri), 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](https://go.dev/blog/unique)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\(\)`and`Equal\(\)`methods\.[6](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#sidenote-hash) - It uses**explicit pool instances**\. This will be useful for sharding\. - It has**better performance**\. See for example this[benchmark](https://github.com/akvorado/akvorado/pull/2244/changes/682b6063af50780dcd64e46b39d5e66c5074d9ab)\. - 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?[\#](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#why-does-it-not-scale) The global read/write lock is a bottleneck in this implementation\. But how? There are several users of theRIB, each with its own set of constraints: - The**Kafka workers**look up theRIBto enrich flows with routing information\. They are bound by the number of Kafka partitions\.[8](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#sidenote-KIP-932)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 theBMPprotocol\. When connecting, they can send millions of routes\.[9](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#sidenote-bmpconfig)After the initial synchronization, updates are sent continuously and may spike from time to time\. The router detects a stuckBMPstation 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**remoteBGPpeer goes down**, Akvorado flushes the associated routes by walking theRIBwith 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\. ## RIBsharding[\#](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#rib-sharding) ## First step: basic sharding[\#](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#first-step-basic-sharding) To remove the global lock, theRIBis split into several “shards,” each one handling a subset of the prefixes:  Akvorado BMP RIB implementation with sharding\.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](https://go.dev/blog/unique)\. 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](https://github.com/akvorado/akvorado/discussions/2287#discussioncomment-16020731)that after[this blind change](http://github.com/akvorado/akvorado/commit/7e6bbf2210fdf7116d2ee168b307b9906cc223c0), theBMPreceiver chugged steadily\. 🎉 Later, I wrote a[concurrent benchmark](https://github.com/akvorado/akvorado/blob/0811c40cc2065380e3a6230c2796312838e57850/outlet/routing/provider/bmp/concurrent_test.go)over half a million synthetic but plausible routes[10](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#sidenote-plausible)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:  Read and write latency performance improvement after sharding\.It also shows that a high number of writers degrades read latency\. ## Second step: lock\-free reads[\#](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#second-step-lock-free-reads) The single read/write lock protecting the prefix tree is the next target\. The[bart](https://github.com/gaissmai/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\.  Akvorado BMP RIB implementation with sharding and lock\-free reads\.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](https://vincent.bernat.ch/en/blog/2026-akvorado-rib-sharding#sidenote-retry)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\.  Read and write latency performance improvement after lock\-free reads\. The middle column shows the cumulative improvements of both steps\. --- Among the multiple attempts to optimize theBMPcomponent,RIBsharding is one of the more satisfying\.[Akvorado 2\.2](https://github.com/akvorado/akvorado/releases/tag/v2.2.0)implements the first step\.[PR \#2433](https://github.com/akvorado/akvorado/pull/2433), drafted while writing this blog post, implements the second step and will be released with Akvorado 2\.4\. 🪓