Sharding a routing table for lock-free reads in Go

Vincent Bernat

To as­so­ciate rout­ing in­for­ma­tion—like AS paths or BGP com­mu­ni­ties—to flows, Akvo­rado can im­port routes through the BGP Mon­i­tor­ing Pro­to­col (BMP). As the In­ter­net rout­ing ta­ble con­tains more than 1 mil­lion routes, Akvo­rado needs to scale to tens of mil­lions of routes.1 This has been a long-stand­ing chal­lenge,2 but I ex­pect this is­sue is now fixed by us­ing RIB shard­ing, a method that splits the rout­ing data­base into sev­eral parts to en­able con­cur­rent updates.

Previous implementation#

Akvo­rado con­nects 2 el­e­ments to build its RIB:

  1. a pre­fix tree, and
  2. a list of routes at­tached to each prefix.
Akvorado BMP RIB implementation before sharding with the memory layout of each
structure and a single lock.
Akvorado BMP RIB implementation without sharding. One single read/write lock.

In the di­a­gram above, the RIB stores five IPv4 pre­fixes and two IPv6 pre­fixes. One of them, 2001:​db8:1::/48, con­tains three routes:

  • from peer 3, next hop 2001:​db8::​3:1, AS 65402, AS path 65402, com­mu­nity 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, com­mu­nity 65402:31.

The rib struc­ture is de­fined 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 pre­fix tree uses the bart pack­age, an adap­ta­tion of Don­ald Knuth’s ART al­go­rithm. The bench­marks demon­strate it out­per­forms other pack­ages for lookups, in­ser­tions, and mem­ory us­age.3 Plus, the au­thor is quite helpful.

Storing routes in a map#

The list of routes for each pre­fix is not stored di­rectly in the pre­fix tree: it would put too much pres­sure on the garbage col­lec­tor by al­lo­cat­ing per-pre­fix arrays.

In­stead, the RIB as­signs a unique 32-bit pre­fix iden­ti­fier for each pre­fix, ei­ther by pick­ing the last avail­able pre­fix iden­ti­fier from the freePrefixIDs ar­ray if any, or us­ing the nextPrefixID value be­fore in­cre­ment­ing it. Then, the routes are stored in the routes map, lever­ag­ing the op­ti­mized Swiss ta­ble in Go. To re­trieve routes at­tached to a pre­fix, we look them up one by one in the routes map with a 64-bit key com­bin­ing the 32-bit pre­fix in­dex with a 32-bit route in­dex match­ing the po­si­tion of the route in the list. Akvo­rado 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 re­turns no result.

type prefixIndex uint32
type routeIndex uint32
type routeKey uint64

Interning routes#

A route con­tains a BGP peer iden­ti­fier, a par­tial NLRI,5 the next hop, and the at­tributes.

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 mem­ory and al­lo­ca­tions, NLRI, next hops, and route at­tributes are “in­terned”: a 32-bit in­te­ger re­places the real value. The mech­a­nism pre­dates the unique pack­age in­tro­duced in Go 1.23. We keep it be­cause it has dif­fer­ent trade-offs:

  • It uses ex­plicit ref­er­ence count­ing in­stead of re­ly­ing on weak pointers.
  • It works with non-com­pa­ra­ble val­ues im­ple­ment­ing Hash() and Equal() methods.6
  • It uses ex­plicit pool in­stances. This will be use­ful for sharding.
  • It has bet­ter per­for­mance. See for ex­am­ple this benchmark.
  • It con­sumes half the mem­ory thanks to un­signed 32-bit ref­er­ences in­stead of pointers.
  • But it is not safe for con­cur­rent use.

Why does it not scale?#

Note

At AS 12322, we don’t use BMP yet.7 But Ger­hard Bogner had the pa­tience, avail­abil­ity, and tech­ni­cal skills to help me de­bug this issue.

The global read/write lock is a bot­tle­neck in this im­ple­men­ta­tion. But how? There are sev­eral users of the RIB, each with its own set of con­straints:

  • The Kafka work­ers look up the RIB to en­rich flows with rout­ing in­for­ma­tion. They are bound by the num­ber of Kafka par­ti­tions.8 Akvo­rado also ad­justs their num­ber to en­sure ef­fi­cient batch­ing to Click­House. On our setup, the num­ber of work­ers os­cil­lates be­tween 8 and 16. As we want to ob­serve the lat­est data, we can­not af­ford for the Kafka work­ers to lag too much.

  • The mon­i­tored routers send route up­dates through the BMP pro­to­col. When con­nect­ing, they can send mil­lions of routes.9 Af­ter the ini­tial syn­chro­niza­tion, up­dates are sent con­tin­u­ously and may spike from time to time. The router de­tects a stuck BMP sta­tion when its TCP win­dow is full and re­sets the ses­sion in this case. While Akvo­rado im­ple­ments a large in­com­ing buf­fer, it still needs to up­date the re­ceived routes with the write lock held fast enough to avoid be­ing de­tected as stuck.

  • When a re­mote BGP peer goes down, Akvo­rado flushes the as­so­ci­ated routes by walk­ing the RIB with the write lock held. When a mon­i­tored router goes down, Akvo­rado waits a bit but even­tu­ally flushes all the as­so­ci­ated routes.

In short: on a busy setup, lock con­tention is high for both read­ers and writ­ers, and nei­ther can lag too much behind.

RIB sharding#

First step: basic sharding#

To re­move the global lock, the RIB is split into sev­eral “shards,” each one han­dling a sub­set of the prefixes:

Akvorado BMP RIB implementation after sharding with the memory layout of each
structure and one lock per shard.
Akvorado BMP RIB implementation with sharding.

The pre­fix tree stays global and is pro­tected by a sin­gle lock. Each shard gets its read/write lock, its route map, and its in­tern pools to store NLRIs, next hops, and route at­tributes, which would not have been pos­si­ble with Go’s unique pack­age. The pre­fix in­dexes are also sharded: the 8 most sig­nif­i­cant bits are the shard in­dex and the 24 re­main­ing bits are the lo­cal pre­fix index.

Ger­hard con­firmed that af­ter this blind change, the BMP re­ceiver chugged steadily. 🎉

Later, I wrote a con­cur­rent bench­mark over half a mil­lion syn­thetic but plau­si­ble routes10 par­ti­tioned over 0 to 8 writ­ers, churn­ing routes as fast as pos­si­ble, while 1 to 16 read­ers con­tin­u­ously look up a set of 10,000 routes. I don’t know if this bench­mark is re­al­is­tic, but it con­firms the im­prove­ments for both read and write la­tencies:

Two heatmaps. One for read latency ratio, the other for write latency ratio.
Both of them comparing the speedup with colored tiles between the code before
sharding and after sharding. Most tiles are
green.
Read and write latency performance improvement after sharding.

It also shows that a high num­ber of writ­ers de­grades read latency.

Second step: lock-free reads#

The sin­gle read/write lock pro­tect­ing the pre­fix tree is the next tar­get. The bart pack­age pro­vides al­ter­na­tive mu­ta­tion meth­ods re­turn­ing an up­dated tree us­ing copy-on-write. Read­ers don’t need the global lock any more, leav­ing it only to syn­chro­nize writ­ers. The pre­fix tree is boxed in an atomic pointer.

Akvorado BMP RIB implementation for sharding with lock-free reads. It shows
the memory layout of each structure.
Akvorado BMP RIB implementation with sharding and lock-free reads.

With­out a lock, read­ers can now fetch a stale pre­fix in­dex when walk­ing their copy of the tree if a con­cur­rent writer re­moves the last route at­tached to this pre­fix in­dex and re­cy­cles it for an­other pre­fix. To avoid this is­sue, we com­bine the pre­fix in­dex with a gen­er­a­tion num­ber 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 gen­er­a­tion num­ber for each lo­cal pre­fix in­dex. The gen­er­a­tion num­ber in­creases by one if the as­so­ci­ated pre­fix in­dex is freed. When look­ing up the routes at­tached to a pre­fix in­dex, the reader checks if the gen­er­a­tion num­ber matches. Oth­er­wise, it as­sumes the in­dex was re­cy­cled and the list of routes is empty.11 You can see this case in the di­a­gram above for pre­fix in­dex 5, stored with a gen­er­a­tion in­dex of 3, while the cur­rent value in the []generations ar­ray is 4. The gen­er­a­tion num­ber could over­flow, but it is not a prob­lem as lookups are quick.

Run­ning the con­cur­rent bench­mark against this new im­ple­men­ta­tion shows the im­prove­ments for the read la­tency as soon as the cost of the copy-on-write pre­fix tree is amortized.

Six heatmaps. Three for read latency ratio, three others for write latency
ratio. They compare the numbers without sharding, with sharding, and with
lock-free reads, pair by pair. For read latency, most tiles are green, showing
an improvement of the second step. For write latency, the speedup is negative
for a low number of readers.
Read and write latency performance improvement after lock-free reads. The middle column shows the cumulative improvements of both steps.

Among the mul­ti­ple at­tempts to op­ti­mize the BMP com­po­nent, RIB shard­ing is one of the more sat­is­fy­ing. Akvo­rado 2.2 im­ple­ments the first step. PR #2433, drafted while writ­ing this blog post, im­ple­ments the sec­ond step and was re­leased with Akvo­rado 2.4. 🪓