シャーディングによるAkvorado BMP RIBのスケーリング
Scaling Akvorado BMP RIB with Sharding (vincent.bernat.ch)
要約
AkvoradoはBGP Monitoring Protocol (BMP) を通じてルーティング情報をフローに関連付けるツールであり、数千万のルートを処理するためにRIB (Routing Information Base) のスケーリングが課題となっていました。この課題を解決するため、ルーティングデータベースを複数の部分に分割して同時更新を可能にするRIBシャーディングが導入されました。さらに、ロックフリー読み込みの実装へと進化させることで、読み取りと書き込みの両方のレイテンシが大幅に改善されています。
全文翻訳
Goにおけるロックフリー読み取りのためのルーティングテーブルのシャーディング
ASパスやBGPコミュニティなどのルーティング情報をフローに関連付けるために、Akvorado は BGP Monitoring Protocol (BMP) を介してルートをインポートできます。インターネットのルーティングテーブルには 100万件以上のルート が含まれているため、Akvorado は 数千万件のルートにスケーリング する必要があります。1 これは長年の課題でしたが2、ルーティングデータベースを分割して並列更新を可能にする手法である RIBシャーディング を使用することで、この問題は解決されたと期待しています。
以前の実装#
Akvorado は、その RIB を構築するために 2 つの要素を接続します。
- プレフィックストゥリー、および
- 各プレフィックスに関連付けられたルートのリスト。
[画像: シャーディング前の Akvorado BMP RIB 実装。各構造体のメモリレイアウトと単一のロックが表示されています。]
シャーディングなしの Akvorado BMP RIB 実装。単一の読み書きロック。
上記の図では、RIB は 5 つの IPv4 プレフィックスと 2 つの IPv6 プレフィックスを格納しています。そのうちの 1 つ 2001:db8:1::/48 には 3 つのルートが含まれています。
- peer 3 から、ネクストホップ
2001:db8::3:1、AS 65402、AS パス65402、コミュニティ65402:31 - peer 4 から、ネクストホップ
2001:db8::4:1、同じ ASN、AS パス、コミュニティ - peer 5 から、ネクストホップ
2001:db8::5:1、AS 65402、AS パス65401 65402、コミュニティ65402:31
rib 構造体は Go で以下のように定義されています。
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
}
プレフィックストゥリーは bart パッケージを使用しており、これは Donald Knuth の ART アルゴリズム の適応版です。ベンチマーク では、ルックアップ、挿入、メモリ使用量において他のパッケージを上回ることが示されています3。さらに、作者は非常に協力的です。
マップへのルート格納#
各プレフィックスのルートリストは、プレフィックストゥリーに直接格納されません。これは、プレフィックスごとに配列を割り当てることでガベージコレクタに過度の負荷がかかるためです。
代わりに、RIB は各プレフィックスに一意の 32 ビットプレフィックス識別子を割り当てます。これは、freePrefixIDs 配列から利用可能な最後のプレフィックス識別子を取得するか、nextPrefixID の値をインクリメントする前に使用します。その後、ルートは routes マップに格納され、Go の 最適化された Swiss table を活用します。プレフィックスに関連付けられたルートを取得するには、32 ビットプレフィックスインデックスと、リスト内のルートの位置に対応する 32 ビットルートインデックスを組み合わせた 64 ビットキーを使用して、マップで 1 つずつ検索します。Akvorado は、最適なルートを見つけるために、最初のルートから最後のルートまでスキャンします4。ルートキーで結果が得られない場合、それ以上ルートがないことを認識します。
type prefixIndex uint32
type routeIndex uint32
type routeKey uint64
ルートのインターニング#
ルートには、BGPピアID、部分的な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 ビット参照を使用するため、メモリ使用量が半分になります。
- ただし、並列使用には安全ではありません。
なぜスケールしないのか?#
グローバルな読み書きロックはこの実装のボトルネックです。しかし、どのようにでしょうか?RIB のユーザーはいくつかあり、それぞれに制約があります。
-
Kafka ワーカーは、ルーティング情報でフローをリッチにするために RIB をルックアップします。これらは Kafka パーティション数に制約されます8。Akvorado は ClickHouse への効率的なバッチ処理を保証するために、それらの数も調整します。私たちのセットアップでは、ワーカー数は 8 から 16 の間で変動します。最新のデータを観測したいので、Kafka ワーカーが遅延しすぎることは許容できません。
-
監視対象ルーターは、BMP プロトコルを通じてルート更新を送信します。接続時に、数百万件のルートを送信できます9。初期同期後、更新は継続的に送信され、時折スパイクする可能性があります。ルーターは、TCP ウィンドウがいっぱいになると BMP ステーションが停止したと検出し、その場合はセッションをリセットします。Akvorado は大きな受信バッファを実装していますが、書き込みロックを十分に速く保持して受信ルートを更新し、停止したと検出されるのを避ける必要があります。
-
リモート BGP ピアがダウンすると、Akvorado は書き込みロックを保持したまま RIB をウォークして関連ルートをフラッシュします。監視対象ルーターがダウンすると、Akvorado は少し待ってから、関連するすべてのルートをフラッシュします。
要するに、ビジーなセットアップでは、リーダーとライターの両方でロックの競合が高くなり、どちらも遅延しすぎることは許容できません。
RIBシャーディング#
第一段階:基本的なシャーディング#
グローバルロックを削除するために、RIB は複数の「シャード」に分割され、それぞれがプレフィックスのサブセットを処理します。
[画像: シャーディング後の Akvorado BMP RIB 実装。各構造体のメモリレイアウトとシャードごとのロックが表示されています。]
シャーディングされた Akvorado BMP RIB 実装。
プレフィックスツリーはグローバルなまま維持され、単一のロックで保護されます。各シャードには、読み書きロック、ルートマップ、および NLRI、ネクストホップ、ルート属性を格納するためのインターンプールが用意されています。これは Go の unique パッケージ では不可能でした。プレフィックスインデックスもシャーディングされます。上位 8 ビットがシャードインデックスとなり、残りの 24 ビットがローカルプレフィックスインデックスとなります。
Gerhard は、このブラインドな変更 の後、BMP レシーバーが着実に処理できるようになったことを確認しました。 🎉
その後、半百万件の合成的だがもっともらしいルート10 を 0 から 8 のライターに分割し、可能な限り速くルートを churn させながら、1 から 16 のリーダーが 10,000 件のルートセットを継続的にルックアップする、並列ベンチマークを作成しました。このベンチマークが現実的かどうかはわかりませんが、読み取りと書き込みのレイテンシの両方で改善が確認されました。
[画像: 2 つのヒートマップ。1 つは読み取りレイテンシ比、もう 1 つは書き込みレイテンシ比。どちらも、シャーディング前のコードとシャーディング後のコードの速度向上を色付きのタイルで比較しています。ほとんどのタイルは緑色です。]
シャーディング後の読み取りおよび書き込みレイテンシパフォーマンスの改善。
また、多数のライターが読み取りレイテンシを低下させることも示しています。
第二段階:ロックフリー読み取り#
プレフィックスツリーを保護する単一の読み書きロックが次のターゲットです。bart パッケージは、更新されたツリーをコピーオンライトで返す代替のミューテーションメソッドを提供します。リーダーはもはやグローバルロックを必要としなくなり、ライターの同期のためだけにロックを残します。プレフィックスツリーはアトミックポインタにボックス化されます。
[画像: シャーディングのための Akvorado BMP RIB 実装で、ロックフリー読み取りを行います。各構造体のメモリレイアウトが表示されています。]
シャーディングとロックフリー読み取りを備えた 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 です。世代番号はオーバーフローする可能性がありますが、ルックアップは迅速なため問題にはなりません。
この新しい実装に対して並列ベンチマークを実行すると、コピーオンライトプレフィックスツリーのコストが償却されるとすぐに、読み取りレイテンシの改善が示されます。
[画像: 6 つのヒートマップ。3 つは読み取りレイテンシ比、他の 3 つは書き込みレイテンシ比。これらは、シャーディングなし、シャーディングあり、ロックフリー読み取りありの数値をペアごとに比較しています。読み取りレイテンシでは、ほとんどのタイルが緑色で、第 2 ステップの改善を示しています。書き込みレイテンシでは、リーダー数が少ない場合に速度向上はマイナスになります。]
ロックフリー読み取り後の読み取りおよび書き込みレイテンシパフォーマンスの改善。中央の列は、両方のステップの累積的な改善を示しています。
BMP コンポーネントを最適化するための数多くの試みの中で、RIB シャーディングは最も満足のいくものの一つです。Akvorado 2.2 は第一段階を実装しています。この記事の執筆中にドラフトされたPR #2433 は第二段階を実装しており、Akvorado 2.4 と共にリリースされました。🪓