Partitionner une table de routage pour des lectures sans verrou en Go

Vincent Bernat

Pour as­so­cier des in­for­ma­tions de rou­tage, telles que les che­mins d’AS ou les com­mu­nau­tés BGP, aux flux, Ak­vo­rado peut im­por­ter des routes via le BGP Mo­ni­to­ring Pro­to­col (BMP). Comme la table de rou­tage In­ter­net contient plus d’un mil­lion de routes, Ak­vo­rado doit gé­rer des di­zaines de mil­lions de routes1. C’est un défi de longue date2, mais je pense que ce pro­blème est dé­sor­mais ré­solu grâce au shar­ding de la RIB, une mé­thode qui dé­coupe la base de rou­tage en plu­sieurs par­ties afin de per­mettre les mises à jour concurrentes.

Implémentation précédente#

Ak­vo­rado as­so­cie deux élé­ments pour construire sa RIB :

  1. un arbre de préfixes et
  2. une liste de routes at­ta­chée à chaque préfixe.
Implémentation de la RIB BMP d'Akvorado avant le sharding, avec la disposition
mémoire de chaque structure et un unique verrou.
Implémentation de la RIB BMP d’Akvorado sans sharding. Un unique verrou en lecture/écriture.

Dans le dia­gramme ci-des­sus, la RIB stocke cinq pré­fixes IPv4 et deux pré­fixes IPv6. L’un d’eux, 2001:​db8:1::/48, contient trois routes :

  • de­puis le pair 3, via 2001:​db8::​3:1, AS 65402, che­min d’AS 65402, com­mu­nauté 65402:31 ;
  • de­puis le pair 4, via 2001:​db8::​4:1, mêmes ASN, che­min d’AS et com­munauté ;
  • de­puis le pair 5, via 2001:​db8::​5:1, AS 65402, che­min d’AS 65401 65402, com­mu­nauté 65402:31.

La struc­ture rib est dé­fi­nie en Go de la ma­niè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’ap­puie sur le pa­quet bart, une adap­ta­tion de l’al­go­rithme ART de Do­nald Knuth. Les bench­marks montrent qu’il sur­passe les autres im­plé­men­ta­tions pour les re­cherches, les in­ser­tions et la consom­ma­tion mé­moire3. De plus, l’au­teur est d’une grande aide.

Stocker les routes dans une table associative#

La liste des routes de chaque pré­fixe n’est pas sto­ckée di­rec­te­ment dans l’arbre de pré­fixes : cela met­trait trop de pres­sion sur le ra­masse-miettes en al­louant un ta­bleau par préfixe.

À la place, la RIB at­tri­bue un iden­ti­fiant de 32 bits unique à chaque pré­fixe, soit en pre­nant le der­nier iden­ti­fiant dis­po­nible dans le ta­bleau freePrefixIDs, soit en uti­li­sant la va­leur nextPrefixID avant de l’in­cré­men­ter. Les routes sont en­suite sto­ckées dans la table as­so­cia­tive routes, qui s’ap­puie en Go sur une struc­ture par­ti­cu­liè­re­ment op­ti­mi­sée. Pour ré­cu­pé­rer les routes at­ta­chées à un pré­fixe, nous les cher­chons un par un dans la table routes via une clef de 64 bits qui com­bine l’in­dex de 32 bits du pré­fixe avec l’in­dex de 32 bits re­pré­sen­tant la po­si­tion de la route dans la liste. Ak­vo­rado par­court les routes de la pre­mière à la der­nière pour trou­ver la meilleure4. Il sait qu’il n’y a plus de route lorsque la clé ne ren­voie au­cun résultat.

type prefixIndex uint32
type routeIndex uint32
type routeKey uint64

Canonisation des routes#

Une route contient un iden­ti­fiant de pair BGP, un NLRI par­tiel5, le pro­chain saut et les at­tributs.

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 éco­no­mi­ser la mé­moire et les al­lo­ca­tions, les NLRI, les pro­chains sauts et les at­tri­buts de route sont ca­no­ni­sés : un en­tier de 32 bits rem­place la va­leur réelle. Ce mé­ca­nisme est an­té­rieur au pa­quet unique in­tro­duit dans Go 1.23. Nous le conser­vons car ses com­pro­mis sont dif­férents :

  • il uti­lise un comp­tage de ré­fé­rences ex­pli­cite plu­tôt que des poin­teurs faibles ;
  • il fonc­tionne avec des va­leurs non com­pa­rables im­plé­men­tant les mé­thodes Hash() et Equal()6 ;
  • il uti­lise des ins­tances ex­pli­cites pour la ca­no­ni­sa­tion, ce qui se ré­vè­lera utile pour le sharding ;
  • il offre de meilleures per­for­mances. Voir par exemple ce benchmark ;
  • il consomme deux fois moins de mé­moire grâce à des ré­fé­rences 32 bits plu­tôt que des pointeurs ;
  • mais il n’est pas uti­li­sable de ma­nière concurrente.

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

Note

Pour l’AS 12322, nous n’uti­li­sons pas en­core BMP7. Mais Ge­rhard Bo­gner a eu la pa­tience, la dis­po­ni­bi­lité et les com­pé­tences tech­niques pour m’ai­der à dé­bo­guer ce problème.

Le ver­rou glo­bal en lecture/écriture est le gou­lot d’étran­gle­ment de cette im­plé­men­ta­tion. Mais pour­quoi ? Plu­sieurs com­po­sants uti­lisent la RIB, cha­cun avec ses propres contraintes :

  • Les consom­ma­teurs Kafka consultent la RIB pour en­ri­chir les flux avec des in­for­ma­tions de rou­tage. Leur nombre est bor­née par la somme des par­ti­tions Kafka8. Ak­vo­rado ajuste éga­le­ment ce nombre afin de ga­ran­tir un ex­port groupé ef­fi­cace des flux vers Click­House. Sur notre ins­tal­la­tion, la quan­tité de consom­ma­teurs os­cille entre 8 et 16. Comme nous vou­lons ob­ser­ver les don­nées ré­centes le plus tôt pos­sible, nous ne pou­vons pas nous per­mettre que les consom­ma­teurs Kafka prennent trop de retard.

  • Les rou­teurs sur­veillés en­voient leurs routes via le pro­to­cole BMP. À la connexion, ils peuvent en­voyer des mil­lions de routes9. Après la syn­chro­ni­sa­tion ini­tiale, les mises à jour ar­rivent en continu et peuvent connaître des pics ponc­tuels. Le rou­teur dé­tecte une sta­tion BMP blo­quée lorsque sa fe­nêtre TCP est pleine. Dans ce cas, il ré­ini­tia­lise la ses­sion. Bien qu’Ak­vo­rado dis­pose d’un im­por­tant tam­pon en en­trée, il doit ap­pli­quer les routes re­çues suf­fi­sam­ment vite pour ne pas être consi­déré comme bloqué.

  • Quand un pair BGP dis­tant tombe, Ak­vo­rado purge les routes as­so­ciées en par­cou­rant la RIB. Quand un rou­teur sur­veillé tombe, Ak­vo­rado pa­tiente un peu, mais fi­nit par pur­ger toutes les routes as­sociées.

En ré­sumé : sur une ins­tal­la­tion char­gée, la conten­tion sur le ver­rou est forte au­tant pour les lec­teurs que pour les écri­vains, et au­cun des deux ne peut prendre trop de retard.

Sharding de la RIB#

Première étape#

Pour sup­pri­mer le ver­rou glo­bal, la RIB est dé­cou­pée en plu­sieurs « shards », cha­cun gé­rant un sous-en­semble des préfixes :

Implémentation de la RIB BMP d'Akvorado après le sharding, avec la disposition
mémoire de chaque structure et un verrou par partition.
Implémentation de la RIB BMP d’Akvorado avec sharding.

L’arbre de pré­fixes reste glo­bal et pro­tégé par un unique ver­rou. Chaque par­ti­tion dis­pose de son propre ver­rou en lecture/écriture, de sa table de routes et de ses blocs de ca­no­ni­sa­tion pour sto­cker les NLRI, les pro­chains sauts et les at­tri­buts de route, ce qui n’au­rait pas été pos­sible avec le pa­quet unique de Go. Les in­dex de pré­fixes sont eux aussi par­ti­tion­nés : les 8 bits de poids fort cor­res­pondent à l’in­dex de la par­ti­tion et les 24 bits de poids faible à l’in­dex lo­cal du préfixe.

Ge­rhard a confirmé que suite à ce chan­ge­ment à l’aveugle, le com­po­sant BMP a com­mencé à ron­ronner. 🎉

J’ai en­suite écrit un bench­mark por­tant sur un demi-mil­lion de routes syn­thé­tiques mais plau­sibles10, ré­par­ties entre 0 et 8 écri­vains qui mo­di­fient les routes aussi vite que pos­sible, tan­dis que 1 à 16 lec­teurs consultent en boucle un en­semble de 10 000 routes. J’ignore si ce bench­mark est réa­liste, mais il confirme les amé­lio­ra­tions à la fois sur les la­tences en lec­ture et en écriture :

Deux cartes de chaleur. L'une pour le ratio de latence en lecture, l'autre
pour celui de la latence en écriture. Toutes deux comparent l'accélération
entre le code avant et après le sharding via des cases colorées. La plupart des
cases sont vertes.
Amélioration des performances de latence en lecture et en écriture après le sharding.

Il montre éga­le­ment qu’un grand nombre d’écri­vains dé­grade la la­tence en lecture.

Deuxième étape#

L’unique ver­rou en lecture/écriture pro­té­geant l’arbre de pré­fixes consti­tue la cible sui­vante. Le pa­quet bart pro­pose des mé­thodes al­ter­na­tives pour les mu­ta­tions. Elles ren­voient un arbre mis à jour via une co­pie par­tielle. Les lec­teurs n’ont plus be­soin du ver­rou glo­bal, qui ne sert plus qu’à syn­chro­ni­ser les écri­vains. L’arbre de pré­fixes est en­cap­sulé dans un poin­teur atomique.

Implémentation de la RIB BMP d'Akvorado pour le sharding avec lectures sans
verrou, avec la disposition mémoire de chaque structure.
Implémentation de la RIB BMP d’Akvorado avec sharding et lectures sans verrou.

Sans ver­rou, un lec­teur peut dé­sor­mais ré­cu­pé­rer un in­dex de pré­fixe pé­rimé en par­cou­rant sa co­pie de l’arbre, lorsqu’un écri­vain concur­rent sup­prime la der­nière route at­ta­chée à cet in­dex et le re­cycle pour un autre pré­fixe. Pour évi­ter ce pro­blème, nous com­bi­nons l’in­dex de pré­fixe avec un nu­méro de gé­né­ra­tion que nous sto­ckons 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 par­ti­tion stocke le nu­méro de gé­né­ra­tion de chaque in­dex de pré­fixe lo­cal. Ce nu­méro est in­cré­menté quand l’in­dex de pré­fixe as­so­cié est li­béré. Lors de la re­cherche des routes at­ta­chées à un in­dex de pré­fixe, le lec­teur vé­ri­fie que le nu­méro de gé­né­ra­tion cor­res­pond. Si­non, il consi­dère que l’in­dex a été re­cy­clé et que la liste de routes est vide11. Le schéma pré­cé­dent illustre ce cas pour l’in­dex de pré­fixe 5, sto­cké avec un nu­méro de gé­né­ra­tion de 3, alors que la va­leur ac­tuelle dans le ta­bleau []generations est 4. Le nu­méro de gé­né­ra­tion peut bou­cler, mais ce n’est pas un pro­blème car les re­cherches sont rapides.

L’exé­cu­tion du bench­mark sur cette nou­velle im­plé­men­ta­tion montre les amé­lio­ra­tions sur la la­tence en lec­ture ainsi qu’en écri­ture dès que le coût de la co­pie par­tielle de l’arbre de pré­fixes est amorti.

Six cartes de chaleur. Trois pour le ratio de latence en lecture, trois
autres pour celui de la latence en écriture. Elles comparent par paires les
valeurs sans sharding, avec sharding, et avec lectures sans verrou. Pour la
latence en lecture, la plupart des cases sont vertes, ce qui traduit
l'amélioration apportée par la seconde étape. Pour la latence en écriture,
l'accélération est négative pour un faible nombre de
lecteurs.
Amélioration des performances de latence en lecture et en écriture après les lectures sans verrou. La colonne centrale montre les améliorations cumulées des deux étapes.

Parmi les nom­breuses ten­ta­tives d’op­ti­mi­sa­tion du com­po­sant BMP, le shar­ding de la RIB est l’une des plus sa­tis­fai­santes. Ak­vo­rado 2.2 im­plé­mente la pre­mière étape. La PR #2433, ré­di­gée pen­dant l’écri­ture de ce billet, im­plé­mente la se­conde et est sor­tie avec Ak­vo­rado 2.4. 🪓