Augmentation des performances de la RIB d'Akvorado grâce au sharding
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 routes1. C’est un défi de longue date2, 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 :
- un arbre de préfixes et
- 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’AS65402, 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’AS65401 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émoire3. 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 meilleure4. 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 partiel5, 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()etEqual()6 ; - 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 ?
Note
Pour l’AS 12322, nous n’utilisons pas encore BMP7. Mais Gerhard Bogner a eu la patience, la disponibilité et les compétences techniques pour m’aider à déboguer ce 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 Kafka8. 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 routes9. 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 plausibles10, 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 vide11. 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. 🪓
-
Chaque routeur exportant des flux n’a pas besoin d’envoyer ses routes. Quand Akvorado ne trouve pas de route pour un équipement donné, il se rabat sur une route envoyée par un autre équipement. C’est à l’opérateur de juger si cette approximation est acceptable. ↩
-
J’ai effectué de nombreuses tentatives pour augmenter l’efficacité du composant BMP. Voir par exemple les PR #254, PR #255, PR #278, PR #2244 et PR #2245. Malgré ces efforts, ce composant est resté problématique pour certains utilisateurs. Voir la discussion #2287 comme exemple le plus récent. ↩
-
Cela continue de s’améliorer : bart 0.28.0 introduit une implémentation alternative qui troque un peu de mémoire contre de meilleures performances en recherche. Je ne l’ai pas encore essayée car cela fait déjà quelques mois que je prépare ce billet. ↩
-
Akvorado préfère la route dont le prochain saut correspond exactement. Sinon, il se rabat sur n’importe quelle autre route. C’est une approximation. Une alternative consisterait à maintenir un arbre de préfixes par pair BGP, mais il faudrait alors configurer tous les routeurs pour qu’ils exportent leurs routes. Le démon BMP de pmacct adopte cette approche. ↩
-
Si nous considérons la RIB BGP comme une base de données, le NLRI (Network Layer Reachability Information) en constitue la clé primaire. Son contenu dépend de la famille BGP. Pour IPv4 ou IPv6 unicast, il s’agit du préfixe. Pour les familles VPNv4 et VPNv6, il inclut le route distinguisher. Si l’extension ADD-PATH est activée, le NLRI contient également un identifiant de chemin.
Dans notre implémentation, nous ne stockons pas le préfixe : nous le reconstituons à partir de l’adresse IP recherchée et de la longueur de préfixe stockée séparément. ↩
-
Les méthodes
Hash()s’appuient sur les paquetshash/maphashetunsafepour une meilleure performance. Voir par exemple la fonctionHash()de la structurenlri. ↩ -
Bien qu’auteur ou co-auteur des premières RFC liées à BMP depuis 2016 (RFC 7854, RFC 8671, RFC 9069), Cisco n’a pas fourni d’implémentation utilisable dans IOS XR avant la version 24.2.1. Il nous reste encore quelques routeurs à mettre à jour pour activer cette fonctionnalité. ↩
-
La KIP-932 introduit, dans Kafka 4.2, la notion de groupes partagés pour permettre la consommation coopérative d’une même partition. Akvorado ne la prend pas encore en charge. ↩
-
BMP peut être configuré pour envoyer les routes de chaque pair BGP avant ou après l’application des politiques entrantes. Dans ce dernier cas, plus d’un million de routes peuvent arriver par transit. BMP peut aussi être configuré pour envoyer la RIB locale, qui ne contient que le meilleur chemin pour chaque préfixe. ↩
-
Les préfixes sont aléatoires, mais la distribution de leurs tailles et celle des longueurs de chemin AS suivent les données fournies par Geoff Huston. ↩
-
Une alternative aurait été de réessayer la recherche, mais cela n’aurait pas de sens : la RIB est une structure cohérente à terme et une liste de routes vide est bien un état qui s’est produit récemment. ↩
24 May, 2026 07:00PM by Vincent Bernat






Le travail en profondeur (deep work en anglais) est l’énorme oublié de l’activité sur site. Étant donné l’organisation actuelle des bureaux, il n’est aujourd’hui possible (quasiment) qu’en télétravail.
Pour rappel, le travail en profondeur s’incarne dans des plages de temps de travail ininterrompues, de 1h à 4h. Vous commencez à voir le problème.
Impossible de se concentrer dans un open space. Les discussions au téléphone incessantes vous en empêchent. Des réunions démarrent tous les demi-heures, parfois tous les quarts d’heure, et viennent briser votre concentration.
Entre les deux, des collègues discutent de différents projets, mais aussi de la pluie et du beau temps sous votre nez, vous interpellent directement s’ils ont une question, perturbant les calculs complexes que vous étiez laborieusement en train d’essayer de mener à leur terme.
À midi, c’est le grand départ, des groupes se joignent, il faut courir pour manger avec untel ou unetelle, ou on vient vous chercher sans vergogne à votre bureau, sans se soucier du rythme de travail qui est nécessaire pour mener à bien votre étude en cours.
Bien sûr, tous les métiers n’ont peut-être pas besoin de travail en profondeur. Les métiers réactifs, ou on se met en avant en réagissant à tout ce qui se passe dans l’entreprise (et souvent à rien), sont ceux qui permettent d’être le plus visible et donc de se mettre en avant. Mais beaucoup le nécessitent. Le développement d’applications, la conception d’architecture complexe, et sûrement beaucoup d’autres demandent un travail en profondeur pour être mené à bien et dans les meilleures conditions.
Et vous ? Comment gérez-vous vos plages de travail en profondeur ? Vous y arrivez sur site ou vous attendez vos jours de télétravail ? Dites moi tout en commentaires 
Je suis architecte infrastructure cloud (AWS et Azure) senior freelance, adepte du télétravail et du travail en profondeur, et conçois les infrastructures dont vous avez besoin pour faire tourner les services IT de vos entreprises. Disponible pour une nouvelle mission dès mi-janvier 2026. N’hésitez pas à me contacter si je peux vous aider dans vos projets.















































Mon rapport mensuel couvre une grande partie de mes contributions au logiciel libre. Je l’écris pour 









Les trolls, une activité prisée des Libristes

L’octocat, mascotte de Github
Windows, qui reste le logiciel privateur par excellence, même si d’autres l’ont depuis rejoint
L’uniforme évoque l’armée, ici l’armée des clones


FreeBSD, principal projet des BSD sous licence BSD
Issues, le suivi de bug propriétaire de Github
Debian, l’un des principaux projets du Logiciel Libre avec autour de 1000 contributeurs officiels

Le « lion » devant la cheminée
Premiers pas plutôt festifs le vendredi soir avec le SysAdmin Day dans un bar à Manhattan puis direction Brooklyn pour une Debian Party organisée par
C’est donc le dimanche 1er août que commence la DebConf avec des présentations orientées grand public pour cette première journée appelée le “Debian Day”. Un
Deuxième jour, on a le droit à un
Troisième jour et l’on débute par un
Le quatrième jour, c’est le Day Trip. Il s’agit classiquement d’une journée consacrée à des activités touristiques extérieures. Nous avons été visiter l’église Trinity Church à Manhattan où le drame du 11 septembre 2001 a mis un superbe orgue hors d’usage, remplacé temporairement par un orgue électronique “Powered by Linux”… qui a finalement été conservé en raison de sa qualité. Keith Packard, l’un des gourous de X.org employé chez Intel, a joué quelques minutes sur cet orgue. Ensuite, direction la plage de Coney Island. Puis un match de baseball où Stefano Zacchiroli lancera la première balle du match.
Cinquième jour, on reprend avec un
Sixième jour, on débute par
Septième et dernier jour, encore de nombreuses présentations. J’ai notamment assisté à celle de Philippe Kern, membre de la Release Team, qui