博士

ロボ子、CloudflareがBPF LPM trieの性能問題に取り組んでるのじゃ。知っておるか？

ロボ子

はい、博士。IPルーティングで重要なデータ構造ですよね。でも、数百万のエントリを格納すると性能問題が起きると。

博士

そうなんじゃ。CloudflareのMagic Firewallでパケットロスが発生したらしいぞ。大変じゃな。

ロボ子

トライ木って、キーのビットをノードに格納する木構造のことですよね？プレフィックスが共通なデータの格納に効率が良いと。

博士

その通り！マルチビットトライ木は、一度に複数のビットを比較できるから、もっと速いんじゃ。

ロボ子

パス圧縮やレベル圧縮といった最適化手法もあるんですね。疎な領域や密な領域でノード数を削減する、と。

博士

ふむ。10KエントリのBPF LPM trieに対するベンチマーク結果を見ると、lookupが7.423M ops/s、updateが2.643M ops/sじゃな。deleteは0.712M ops/sか。解放(free)が遅いのが気になるのじゃ。

ロボ子

解放に1.743msもかかると、soft lockupメッセージが出てもおかしくないですね。

博士

BPF LPM trieが遅い理由として、各ノードが2つの子ポインタしか持たないから、マルチビット比較がシングルビット比較に劣化する場合がある、と。

ロボ子

トライ木の高さが増加して、検索に必要な比較回数が増えるのも問題ですね。ノードが動的に割り当てられると、キャッシュミスやdTLBミスも発生しやすいですし。

博士

エントリ数が増加するとlookupスループットが低下する、と。100Kエントリで1.5M ops/sec程度か。最初はL1 dcacheミスが原因だけど、80Kエントリを超えるとdTLBミスがボトルネックになるんじゃな。

ロボ子

dTLBミスは痛いですね。ページテーブルのルックアップが発生するので、オーバーヘッドが大きいです。

博士

Cloudflareは、BPF LPM trieの性能改善、特にlookup関数の最適化を考えているようじゃ。Level Compressed trieの実装も検討中らしいぞ。

ロボ子

Level Compressed trie、良さそうですね。Jesper Brouerさんの追加の性能データも参考になりそうです。

博士

しかし、トライ木も奥が深いのじゃ。まるで私の研究室みたいじゃな。…って、ロボ子！また私のプリン食べたじゃろ！

ロボ子

えへへ。つい…最適化、ということで。