BPF LPMのパフォーマンスと最適化を深掘り

このコンテンツは自動機械翻訳サービスによる翻訳版であり、皆さまの便宜のために提供しています。原本の英語版と異なる誤り、省略、解釈の微妙な違いが含まれる場合があります。ご不明な点がある場合は、英語版原本をご確認ください。

それは、本番環境の不可解なソフトロックアップメッセージから始まりました。当社が使用している最も基本的なデータ構造の1つであるBPF LPMトリ

BPFトライマップ（BPF_MAP_TYPE_LPM_TRIE）は、ネットワークパケットをルーティングする際のIPおよびIP+ポートのマッチングなどのために多用され、リクエストが結果を返す前に適切なサービスを通過するようにします。このデータ構造のパフォーマンスはお客様にサービスを提供するために重要ですが、現在の実装のスピードは多くの不満を残しています。BPF LPMトライマップに数百万のエントリーを保存する際、エントリーの検索時間が数百ミリ秒かかったり、マップが10秒以上にわたってCPUをロックアップするなど、いくつかのボトルネックに遭遇しました。たとえば、BPFマップは、CloudflareのMagic Firewallルールを評価する際に使用されますが、これらのボトルネックが、一部のお客様ではトラフィックパケット損失につながっています。

この記事では、試行とプレフィックスの一致の仕組み、ベンチマークの結果、そして現在のBPF LPMトライの実装の欠点のリストについて再確認します。

最後にトライデータ構造を見てからしばらく経った場合（あるいは、これまでご覧になったことがない場合）、トライはツリーデータ構造（バイナリツリーと同様）で、データを保存し、検索することができます。指定されたキーを処理し、各ノードがいくつかのキービットを保存します。

検索はパスを横断することによって実行されます。つまり、ノードはトラバーサルパスからキーを再構築するため、ノードはフルキーを保存する必要がありません。この点は、左子ノードが現在のノードより小さいキーを持ち、右子ノードがより大きいキーを持つという一次不変量が存在する従来のバイナリ検索ツリー（BST）とは異なります。BSTでは、検索ステップごとに比較ができるように、各ノードが完全なキーを保存する必要があります。

以下は、BSTがキーの値をどのように保存するかを示す例です。

• ABC

• ABCD

• ABCDEFGH

• DEF

ちなみに、同じキーのセットを保存しようとすると、これは次のようになります。

このようにビットを分割する方法は、データに冗長性がある場合、たとえば、共有データに必要なノードのセットは1つだけであるため、キーには一般的なものがあります。このため、文字列を効率的に格納するために、試行がよく使用されます。例：単語の辞書。文字列「ABC」と「ABCD」の格納には、3バイト＋4バイト（ASCIIを仮定）の必要はなく、3バイト＋1バイトで済みます。これは、「ABC」が両者（正確なビット数）で共有されるためです。実装によって異なる）。

また、試行することで、より効率的な検索が可能になります。たとえば、キー「CAR」がBSTに存在したかどうかを知りたい場合、ルートの正しい子（キー「DEF」を持つノード）に移動し、その左子をチェックする必要があります。存在すれば、なおさらです。トライはプレフィックス順に検索するため、より効率的です。この例では、トライはそのキーがトライにあるかどうかをルートで知ることができます。

この設計は、最も長いプレフィックスの一致を実行したり、CIDRを使用したIPルーティングで作業するのに最適です。CIDRは、IPアドレス空間をより効率的に使用するために導入されました（クラスを8ビットの4バケットに分類する必要がなくなりました）が、IPアドレスのネットワーク部分がどこにでも位置づけられる可能性があるため、複雑さが増しています。IPルーティングテーブルでCIDRスキームを処理するには、完全一致の検索を実行するのではなく、テーブル内の最も長い（最も具体的な）プレフィックスのマッチングが必要です。

トライを検索する際に各ノードでシングルビットの比較を行う場合、それはバイナリトライです。検索でより多くのビットを比較する場合、これをマルチビットトライと呼びます。IPやサブネットアドレスなど、何でもわかります。すべて、0と1だけになります。

マルチビットトライアルのノードは、バイナリトライのノードよりも多くのメモリを使用しますが、コンピューターはいずれにせよマルチビットワードで動作するため、マイクロアーキテクチャの観点からは、マルチビットトライを使用した方がビットをより速く横断することができ、比較する回数を減らすことができるため、より効率的です検索に使用できますこれは古典的なスペースと時間のトレードオフです。

ほかにも、試行で使用できる最適化があります。トリガーに保存するデータの分布は一様ではなく、人口がまばらな地域である可能性があります。例えば、文字列「A」と「BCDEFGHI」をマルチビットトライアルに格納した場合、ノードの数が想定されていますか？ASCIIを使用している場合、ルートノードと左にある「A」または右にある「B」の分岐でバイナリトライを構築することができます。8ビットノードの場合、「C」、「D」、「E」、「F」、「G」、「H」、「I」を格納するには、さらに7つのノードが必要です。

トライアルには他の文字列がないので、これはかなり最適とは言えません。「B」で一致した後最初のレベルに到達すると、そのプレフィックスを持つトライ新しい文字列が1つだけであることがわかり、パス圧縮を使用することで、他のすべてのノードを作成することなく回避できます。パス圧縮は、ノード「C」、「D」、「E」などを「I」のような単一のノードに置き換えます。

ツリーを横断して「I」をヒットした場合でも、検索キーをスキップしたビットと比較して、検索キーが文字列と一致することを確認する必要があります。スキップされたビットをどこにどのように格納するかは実装によって異なります。BPF LPMは、単純にキー全体をリークノードに格納しようとします。データの密度が増すにつれて、パス圧縮の効果が低下します。

データ分布が密度で、たとえば、トライアルの最初の3レベルがすべて完全に入力されている場合はどうなるでしょうか。その場合は、レベル圧縮を使用して、そのレベルのすべてのノードを2**3個の子を持つ単一ノードに置き換えることができます。これは、LinuxカーネルでIPルートルックアップに使用されるLevel-Compressed Triesの動作の仕組みです（net/ipv4/fib_trie.cを参照）。

他の最適化もありますが、この記事ではこの簡単な迂回は、カーネルのBPF LPMトライ実装は先ほど説明した3つの方法を十分に使用していないため、この記事では十分です。

ここでは、AMD EPYC 9684X 96-CoreマシンでBPFセルフテストベンチマークを実行したときの数字をいくつか紹介します。ここでは、トライは10,000のエントリー、32ビットのプレフィックス長、範囲[0, 10,000]内のすべてのキーのエントリーがあります。

1万件のエントリーがあるBPF LPMトライアルを解放するまでの時間が非常に大きいです。最近、これに時間がかかりすぎ、ソフトロックアップメッセージが本番環境で大量に発生する問題が発生しました。

このベンチマークから、最悪の場合の動作がある程度想定できます。キーは非常に密接に使用されているため、パス圧縮はまったく効果がありません。次のセクションでは、関連するボトルネックを理解するために、ルックアップ操作について説明します。

kernel/bpf/lpm_trie.c の LPM トライの実装には、冒頭で説明した最適化が2つあります。エッジノードでマルチビットの比較が可能ですが、各内部ノードには子ポインタが2つしかないため、ツリーが1ビットしか異なる多くのデータが密に挿入されている場合、これらのマルチビット比較は1ビットの比較にまで劣化します。

ここで例を紹介します。0、1、3の数字をBPF LPMトライに格納するとします。これらの値は32ビットまたは64ビットの機械語に収まるため、単一の比較で、トライの中の次のノードを決めることができると思うかもしれません。しかし、これは、trie実装に3つの子ポインタが現在のノードに3つの子ポインタがある場合にのみ可能です（これは当然のことながら、ほとんどのtrie実装で行われています）。言い換えると、3方向の分岐を決定したいのに、BPF LPMには2つの子しか与えないため、2方向の分岐に限定されます。

この2-サブネットの図を以下に示します。

リークノードは緑で表示され、キーはバイナリ文字列として中央に表示されます。8ビットの比較だけでも、どのノードがそのキーを持つかを知ることはできますが、BPF LPMの実装では、中間ノード（青）を挿入して、パストラバーサルに2通りのブランチの決定を挿入します。オレンジ色のルートノードには2つの子しかいません。リークノードに到達すると、BPF LPMはマルチビット比較を実行して鍵をチェックします。ノードがより多くの子をサポートする場合、上記のトライはこのように見え、3ウェイ分岐を許可し、検索時間を短縮します。

この2取得が3つの高さに影響を与えます。最悪の場合、完全なトライは基本的に高さlog2(nr_entries)を持つバイナリ検索ツリーになり、トライの高さはキーを検索するために必要な比較の回数に影響します。

上記の例は、BPF LPMがどのようにパス圧縮を実装しようとするかを示しています。キーが1ビットだけ異なる2つのノードがある中間ノードを挿入するだけです。3の代わりに15のキー（0b1111）を挿入した場合でも、トライのレイアウトは変わりません。ルートの正しい子に単一のノードが必要なだけです。

そして最後に、BPF LPMはレベル圧縮を実装しません。これも、3型のノードが子を2人しか保有できないという事実に起因しています。IPルートテーブルは、共通のプレフィックスを多く持つ傾向があり、通常、上位レベルで密に詰め込まれた試行が見られるため、IPルートを含むトライのレベル圧縮は非常に効果的です。

下記は、LPMのルックアップスループット（百万ops/秒で測定）が、エントリー数の増加（1エントリーから最大10万エントリーまで測定）に伴って低下することを示したグラフです。

エントリが100万に達すると、スループットは約150万op/秒で、エントリ数が増えるにつれて減少し続けます。

なぜでしょうか？当初、これはL1のDCキャッシュのミス率のためです。トライアルで通過する必要のあるノードはすべて、キャッシュミスの可能性があります。

グラフからわかるように、L1のDCキャッシュミス率は比較的安定しており、それでも、スループットは減少し続けています。8万前後になると、dTLBのミス率がボトルネックになります。

BPF LPMはカーネルメモリのフリーリストから個々のノードを動的に割り当てようとするため、これらのノードは任意のアドレスに存在する可能性があります。つまり、トライアルを通過すると、ほぼ確実にキャッシュミスが発生し、dTLBミスが発生する可能性があります。エントリーの数とトライの高さが増加するにつれ、この状況はさらに悪化します。

BPF LPMトライの現在の限界を理解することで、インターネットの将来に向けて、よりパフォーマンスと効率的なソリューションの構築に取り組むことができます。

私たちはすでにこれらのベンチマークをアップストリームのLinuxカーネルに貢献していますが、それは始まりに過ぎません。BPM LPM試行のパフォーマンス、特にワークロードによく使用されるルックアップ関数のパフォーマンスを改善する計画があります。この記事では、すでにnet/ipv4/fib_trie.cで使用されている多くの最適化を取り上げています。自然な最初のステップは、一般的なLevel Compressed tryの実装が利用できるように、そのコードをリファクタリングすることです。今後のブログ記事で、本研究を深く掘り下げてみましょう。

より多くのパフォーマンス数値をご覧になりたい方は、Jesper Brouerがこちらでいくつか記録しています：https://github.com/xdp-project/xdp-project/blob/main/areas/bench/bench02_lpm-trie-lookup.org.

Linuxカーネル、パフォーマンス、またはデータ構造の最適化に興味がある方は、当社のエンジニアリングチームが募集しています。