シャーディングによるAkvorado BMP RIBのスケーリング

ASパスやBGPコミュニティのようなルーティング情報をフローに関連付けるため、AkvoradoはBGPモニタリングプロトコル（BMP）を介してルートをインポートできます。インターネットのルーティングテーブルには100万以上のルートが含まれるため、Akvoradoは数千万のルートに対応できるようスケーリングする必要があります。1 これは長年の課題でしたが、2 ルーティングデータベースを複数の部分に分割して同時更新を可能にする手法であるRIBシャーディングを使用することで、この問題は解決されたと期待しています。以前の実装 マップにルートを保存する ルートのインターン化 なぜスケーリングしないのか？ RIBシャーディング 第一段階：基本的なシャーディング 第二段階：ロックフリー読み込み 以前の実装# Akvoradoは、RIBを構築するために2つの要素を結合します。それは、プレフィックスツリーと、各プレフィックスにアタッチされたルートのリストです。シャーディングなしのAkvorado BMP RIB実装。1つの読み取り/書き込みロック。上記の図では、RIBは5つのIPv4プレフィックスと2つのIPv6プレフィックスを保存しています。そのうちの1つ、2001:db8:1::/48には、3つのルートが含まれています。ピア3から、ネクストホップ2001:db8::3:1、AS 65402、ASパス 65402、コミュニティ 65402:31。ピア4から、ネクストホップ2001:db8::4:1、同じASN、ASパス、およびコミュニティ。ピア5から、ネクストホップ2001:db8::5:1、AS 65402、ASパス 65401 65402、コミュニティ 65402:31。Goでのrib構造は次のように定義されています。 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 } プレフィックスツリーは、ドナルド・クヌースのARTアルゴリズムを応用したbartパッケージを使用しています。ベンチマークでは、ルックアップ、挿入、メモリ使用量において他のパッケージよりも優れていることが示されています。3 さらに、作者は非常に協力的です。 マップにルートを保存する# 各プレフィックスのルートのリストは、プレフィックスツリーに直接保存されていません。これは、プレフィックスごとの配列を割り当てることで、ガベージコレクターに過度の負担をかけるためです。代わりに、RIBは各プレフィックスに一意の32ビットプレフィックス識別子を割り当てます。これは、freePrefixIDs配列から利用可能な最後のプレフィックス識別子を取得するか、nextPrefixIDの値をインクリメントする前に使用することで行われます。その後、ルートはGoで最適化されたSwissテーブルを活用して、routesマップに保存されます。プレフィックスにアタッチされたルートを取得するには、32ビットのプレフィックスインデックスと、リスト内のルートの位置と一致する32ビットのルートインデックスを組み合わせた64ビットのキーを使用して、routesマップ内で1つずつ検索します。Akvoradoは最初から最後までルートをスキャンして最適なものを見つけます。4 ルートキーが結果を返さない場合、それ以上ルートがないと判断します。 type prefixIndex uint32 type routeIndex uint32 type routeKey uint64 ルートのインターン化# ルートには、BGPピア識別子、部分的なNLRI5、ネクストホップ、および属性が含まれます。 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 } メモリとアロケーションを節約するために、NLRI、ネクストホップ、およびルート属性は「インターン化」されています。これにより、実際の値が32ビット整数に置き換えられます。このメカニズムは、Go 1.23で導入された`unique`パッケージよりも古くから存在します。これを維持しているのは、異なるトレードオフがあるためです。弱いポインタに依存するのではなく、明示的な参照カウントを使用します。Hash()およびEqual()メソッドを実装する比較できない値で動作します。6 明示的なプールインスタンスを使用します。これはシャーディングに役立ちます。パフォーマンスが向上します。例えば、このベンチマークをご覧ください。ポインタの代わりに符号なし32ビット参照を使用するため、メモリ消費量が半分になります。しかし、並行使用に対して安全ではありません。 なぜスケーリングしないのか？# 注記 AS 12322では、まだBMPを使用していません。7 しかし、Gerhard Bognerは、この問題のデバッグを手伝ってくれる忍耐力、時間、技術力を持っていました。この実装では、グローバルな読み取り/書き込みロックがボトルネックです。しかし、どのようにでしょうか？ RIBにはいくつかのユーザーがおり、それぞれに独自の制約があります。Kafkaワーカーは、ルーティング情報でフローを充実させるためにRIBを検索します。これらはKafkaパーティションの数に制約されます。8 Akvoradoは、ClickHouseへの効率的なバッチ処理を保証するために、その数を調整します。我々のセットアップでは、ワーカーの数は8から16の間で変動します。最新のデータを観察したいので、Kafkaワーカーが過度に遅延することは許されません。監視対象のルーターは、BMPプロトコルを介してルート更新を送信します。接続時、それらは数百万のルートを送信できます。9 初期同期後、更新は継続的に送信され、時折スパイクすることがあります。ルーターは、TCPウィンドウが満杯になると、BMPステーションがスタックしていることを検出し、この場合セッションをリセットします。Akvoradoは大きな受信バッファを実装していますが、スタックと検出されないように、書き込みロックを保持して受信ルートを十分に速く更新する必要があります。リモートBGPピアがダウンすると、Akvoradoは書き込みロックを保持してRIBを走査することにより、関連するルートをフラッシュします。監視対象のルーターがダウンすると、Akvoradoはしばらく待ってから、最終的にすべての関連するルートをフラッシュします。要するに、ビジーなセットアップでは、読み取り側と書き込み側の両方でロック競合が高く、どちらも過度に遅延することはできません。 RIBシャーディング# 第一段階：基本的なシャーディング# グローバルロックを排除するために、RIBはいくつかの「シャード」に分割され、それぞれがプレフィックスのサブセットを処理します。シャーディングによるAkvorado BMP RIB実装。プレフィックスツリーはグローバルなままであり、単一のロックによって保護されます。各シャードは、独自の読み取り/書き込みロック、ルートマップ、およびNLRI、ネクストホップ、ルート属性を保存するためのインターンプールを取得します。これはGoの`unique`パッケージでは不可能だったでしょう。プレフィックスインデックスもシャーディングされます。最上位の8ビットがシャードインデックスであり、残りの24ビットがローカルプレフィックスインデックスです。Gerhardは、この手探りの変更の後、BMPレシーバーが安定して動作することを確認しました。🎉 後に、私は50万の合成だがもっともらしいルート10に対して、0から8の書き込み側で分割され、可能な限り速くルートを生成し、同時に1から16の読み取り側が10,000のルートセットを継続的に検索する並行ベンチマークを作成しました。このベンチマークが現実的かどうかはわかりませんが、読み取りと書き込みの両方のレイテンシの改善を確認できました。シャーディング後の読み取りおよび書き込みレイテンシのパフォーマンス改善。また、書き込み側の数が多いと読み取りレイテンシが悪化することも示しています。 第二段階：ロックフリー読み込み# プレフィックスツリーを保護する単一の読み取り/書き込みロックが次のターゲットです。bartパッケージは、コピーオンライトを使用して更新されたツリーを返す代替のミューテーションメソッドを提供します。読み取り側はもはやグローバルロックを必要とせず、書き込み側を同期させるためだけにロックを使用します。プレフィックスツリーはアトミックポインタに格納されます。シャーディングとロックフリー読み込みによるAkvorado BMP RIB実装。ロックがない場合、並行する書き込み側がこのプレフィックスインデックスにアタッチされた最後のルートを削除し、別のプレフィックスのためにそれを再利用した場合、読み取り側はツリーのコピーをたどるときに古いプレフィックスインデックスを取得する可能性があります。この問題を回避するために、プレフィックスインデックスを世代番号と組み合わせ、それらをツリーに保存します。type generation uint32 type prefixRef struct { idx prefixIndex gen generation } type rib struct { mu sync.Mutex tree atomic.Pointer[bart.Table[prefixRef]] shards []*ribShard } 各シャードは、各ローカルプレフィックスインデックスの世代番号を保存します。関連するプレフィックスインデックスが解放された場合、世代番号は1増加します。プレフィックスインデックスにアタッチされたルートを検索する際、読み取り側は世代番号が一致するかどうかをチェックします。一致しない場合、インデックスが再利用されたとみなし、ルートのリストは空であると判断します。11 上記の図で、プレフィックスインデックス5のケースを見ることができます。これは世代インデックス3で保存されていますが、[]generations配列の現在の値は4です。世代番号はオーバーフローする可能性がありますが、ルックアップが高速であるため問題ありません。この新しい実装に対して並行ベンチマークを実行すると、コピーオンライトのコストがかかり次第、読み取りレイテンシの改善が示されるp