Pour associer des informations de routage, telles que les chemins d’AS ou les communautés BGP, aux flux, Akvorado peut importer des routes via le BGP Monitoring Protocol (BMP). Comme la table de routage Internet contient plus d’un million de routes, Akvorado doit gérer des dizaines de millions de routes¹. C’est un défi de longue date², mais je pense que ce problème est désormais résolu grâce au sharding de la RIB, une méthode qui découpe la base de routage en plusieurs parties afin de permettre les mises à jour concurrentes.

Implémentation précédente#

Akvorado associe deux éléments pour construire sa RIB :

1. un arbre de préfixes et
2. une liste de routes attachée à chaque préfixe.

Dans le diagramme ci-dessus, la RIB stocke cinq préfixes IPv4 et deux préfixes IPv6. L’un d’eux, 2001:db8:1::/48, contient trois routes :

• depuis le pair 3, via 2001:db8::3:1, AS 65402, chemin d’AS 65402, communauté 65402:31 ;
• depuis le pair 4, via 2001:db8::4:1, mêmes ASN, chemin d’AS et communauté ;
• depuis le pair 5, via 2001:db8::5:1, AS 65402, chemin d’AS 65401 65402, communauté 65402:31.

La structure rib est définie en Go de la manière suivante :

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
}

L’arbre de préfixes s’appuie sur le paquet bart, une adaptation de l’algorithme ART de Donald Knuth. Les benchmarks montrent qu’il surpasse les autres implémentations pour les recherches, les insertions et la consommation mémoire³. De plus, l’auteur est d’une grande aide.

Stocker les routes dans une table associative#

La liste des routes de chaque préfixe n’est pas stockée directement dans l’arbre de préfixes : cela mettrait trop de pression sur le ramasse-miettes en allouant un tableau par préfixe.

À la place, la RIB attribue un identifiant de 32 bits unique à chaque préfixe, soit en prenant le dernier identifiant disponible dans le tableau freePrefixIDs, soit en utilisant la valeur nextPrefixID avant de l’incrémenter. Les routes sont ensuite stockées dans la table associative routes, qui s’appuie en Go sur une structure particulièrement optimisée. Pour récupérer les routes attachées à un préfixe, nous les cherchons un par un dans la table routes via une clef de 64 bits qui combine l’index de 32 bits du préfixe avec l’index de 32 bits représentant la position de la route dans la liste. Akvorado parcourt les routes de la première à la dernière pour trouver la meilleure⁴. Il sait qu’il n’y a plus de route lorsque la clé ne renvoie aucun résultat.

type prefixIndex uint32
type routeIndex uint32
type routeKey uint64

Canonisation des routes#

Une route contient un identifiant de pair BGP, un NLRI partiel⁵, le prochain saut et les attributs.

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
}

Pour économiser la mémoire et les allocations, les NLRI, les prochains sauts et les attributs de route sont canonisés : un entier de 32 bits remplace la valeur réelle. Ce mécanisme est antérieur au paquet unique introduit dans Go 1.23. Nous le conservons car ses compromis sont différents :

• il utilise un comptage de références explicite plutôt que des pointeurs faibles ;
• il fonctionne avec des valeurs non comparables implémentant les méthodes Hash() et Equal()⁶ ;
• il utilise des instances explicites pour la canonisation, ce qui se révèlera utile pour le sharding ;
• il offre de meilleures performances. Voir par exemple ce benchmark ;
• il consomme deux fois moins de mémoire grâce à des références 32 bits plutôt que des pointeurs ;
• mais il n’est pas utilisable de manière concurrente.

Qu’est-ce qui pose problème ?#

Le verrou global en lecture/écriture est le goulot d’étranglement de cette implémentation. Mais pourquoi ? Plusieurs composants utilisent la RIB, chacun avec ses propres contraintes :

• Les consommateurs Kafka consultent la RIB pour enrichir les flux avec des informations de routage. Leur nombre est bornée par la somme des partitions Kafka⁸. Akvorado ajuste également ce nombre afin de garantir un export groupé efficace des flux vers ClickHouse. Sur notre installation, la quantité de consommateurs oscille entre 8 et 16. Comme nous voulons observer les données récentes le plus tôt possible, nous ne pouvons pas nous permettre que les consommateurs Kafka prennent trop de retard.

• Les routeurs surveillés envoient leurs routes via le protocole BMP. À la connexion, ils peuvent envoyer des millions de routes⁹. Après la synchronisation initiale, les mises à jour arrivent en continu et peuvent connaître des pics ponctuels. Le routeur détecte une station BMP bloquée lorsque sa fenêtre TCP est pleine. Dans ce cas, il réinitialise la session. Bien qu’Akvorado dispose d’un important tampon en entrée, il doit appliquer les routes reçues suffisamment vite pour ne pas être considéré comme bloqué.

• Quand un pair BGP distant tombe, Akvorado purge les routes associées en parcourant la RIB. Quand un routeur surveillé tombe, Akvorado patiente un peu, mais finit par purger toutes les routes associées.

En résumé : sur une installation chargée, la contention sur le verrou est forte autant pour les lecteurs que pour les écrivains, et aucun des deux ne peut prendre trop de retard.

Sharding de la RIB#

Première étape#

Pour supprimer le verrou global, la RIB est découpée en plusieurs « shards », chacun gérant un sous-ensemble des préfixes :

L’arbre de préfixes reste global et protégé par un unique verrou. Chaque partition dispose de son propre verrou en lecture/écriture, de sa table de routes et de ses blocs de canonisation pour stocker les NLRI, les prochains sauts et les attributs de route, ce qui n’aurait pas été possible avec le paquet unique de Go. Les index de préfixes sont eux aussi partitionnés : les 8 bits de poids fort correspondent à l’index de la partition et les 24 bits de poids faible à l’index local du préfixe.

Gerhard a confirmé que suite à ce changement à l’aveugle, le composant BMP a commencé à ronronner. 🎉

J’ai ensuite écrit un benchmark portant sur un demi-million de routes synthétiques mais plausibles¹⁰, réparties entre 0 et 8 écrivains qui modifient les routes aussi vite que possible, tandis que 1 à 16 lecteurs consultent en boucle un ensemble de 10 000 routes. J’ignore si ce benchmark est réaliste, mais il confirme les améliorations à la fois sur les latences en lecture et en écriture :

Il montre également qu’un grand nombre d’écrivains dégrade la latence en lecture.

Deuxième étape#

L’unique verrou en lecture/écriture protégeant l’arbre de préfixes constitue la cible suivante. Le paquet bart propose des méthodes alternatives pour les mutations. Elles renvoient un arbre mis à jour via une copie partielle. Les lecteurs n’ont plus besoin du verrou global, qui ne sert plus qu’à synchroniser les écrivains. L’arbre de préfixes est encapsulé dans un pointeur atomique.

Sans verrou, un lecteur peut désormais récupérer un index de préfixe périmé en parcourant sa copie de l’arbre, lorsqu’un écrivain concurrent supprime la dernière route attachée à cet index et le recycle pour un autre préfixe. Pour éviter ce problème, nous combinons l’index de préfixe avec un numéro de génération que nous stockons dans l’arbre :

type generation uint32
type prefixRef struct {
    idx prefixIndex
    gen generation
}
type rib struct {
    mu     sync.Mutex
    tree   atomic.Pointer[bart.Table[prefixRef]]
    shards []*ribShard
}

Chaque partition stocke le numéro de génération de chaque index de préfixe local. Ce numéro est incrémenté quand l’index de préfixe associé est libéré. Lors de la recherche des routes attachées à un index de préfixe, le lecteur vérifie que le numéro de génération correspond. Sinon, il considère que l’index a été recyclé et que la liste de routes est vide¹¹. Le schéma précédent illustre ce cas pour l’index de préfixe 5, stocké avec un numéro de génération de 3, alors que la valeur actuelle dans le tableau []generations est 4. Le numéro de génération peut boucler, mais ce n’est pas un problème car les recherches sont rapides.

L’exécution du benchmark sur cette nouvelle implémentation montre les améliorations sur la latence en lecture ainsi qu’en écriture dès que le coût de la copie partielle de l’arbre de préfixes est amorti.

Parmi les nombreuses tentatives d’optimisation du composant BMP, le sharding de la RIB est l’une des plus satisfaisantes. Akvorado 2.2 implémente la première étape. La PR #2433, rédigée pendant l’écriture de ce billet, implémente la seconde et sortira avec Akvorado 2.4. 🪓