bbtree: スキップリストに対して最大6.83倍を主張するRustの順序付きマップ、そしてコメンテーターが疑う点
bbtreeはRustの順序付きマップ（B-tree）で、著者はキャッシュ境界のワークロードにおいてスキップリストやstd::collections::BTreeMapを上回ると主張し、4つの本番LSMツリーでメムテーブルとして使用した際に1.37〜6.83倍の高速化、インメモリデータベースインデックスとして挿入が2.22倍高速、ディスクからメモリマップした際の最初の応答が160〜2,500倍高速であると報告しています。この投稿はHacker Newsに「Bbtree: Fastest Ordered Map」として登場し（153ポイント、21コメント）、bbtree.xiangpeng.systemsでホストされ、ユーザーaoli-alによって提出されました。
bbtreeが主張すること
中心となる議論は、B-treeがほとんどのビッグデータシステムの基盤であるため、より高速なB-treeがあれば、その上に構築されるすべてのものを改善できるというものです：エージェントメモリ、LLMトレーニング、RAG、KVストア、状態キャッシュ、ベクトル検索。この投稿では、ベンチマーク数値を用いて3つの代表的なユースケースを提示しています。
1. LSMツリーメムテーブルでのスキップリストの置き換え
すべてのLSMツリーは、最近の書き込みをメムテーブルと呼ばれる順序付きマップとしてメモリに保持します。Rustでは、そのマップは通常crossbeam-skiplistのようなスキップリストです。この投稿では、bbtreeが各システム独自のベンチマークで、シングルスレッド、Ryzen 9 9900X上で、マップのみを変更して、1.37〜6.83倍の速度で置き換えると報告しています：
- fjall: gets 2.47倍、inserts 1.61倍、write batches 3.00倍
- SlateDB: gets 1.71倍、puts 1.65倍、write batches of 10 rows 2.36倍
- Tonbo: 10M行の書き込み6.83倍、競合チェック付きトランザクション4.10倍
- LanceのMemWALインデックス（独自のスキップリスト）：ポイントルックアップ2.19倍、バッチルックアップ3.94倍、バッチput 4.21倍
述べられているインターフェースの利点は、bbtreeがcrossbeam-skiplistに似ているがよりシンプルなAPIを公開し、エポックがなく、いつピン留めするか、いつエポックに再入するかを考慮する必要がないことです。メモリ管理もより制御可能です：カスタムアロケータが初日からサポートされ、アロケーションが不規則な（2のべき乗でない）サイズで発生することはなく、外部フラグメンテーションを回避し、アロケーション失敗を優雅に処理できます。
2. インメモリデータベースインデックス
Tursoのスキップリストを置き換えて、挿入が2.22倍高速、インデックス付きSELECTが1.90倍高速と報告しています。
3. ディスクからのbbtreeのメモリマッピング
bbtreeは直接mmapできるため、再起動後の再構築ステップがありません。この投稿では、stdのBTreeMapよりも最初の応答が160〜2,500倍早く到着すると報告しています。
設計の背後にあるコストモデル
この投稿では、すべての最適化を3つのコストを中心に構成しており、優先順位順にリストされています：
- チェーンされたキャッシュラインの数。キャッシュミスは約100ナノ秒かかります。
- 実行される命令の数。命令は約0.5ナノ秒かかります。
- キャッシュコヒーレンストラフィック。これは並行アクセスに最も重要です。キャッシュミスを強制し、100ナノ秒よりわずかに多くかかります。
キャッシュミスは命令の約200倍のコストがかかるため、支配的な目標はキャッシュミスを最小限に抑え、各ミスについて検索空間を可能な限り狭めることです。
約16項目未満では線形検索がバイナリ検索に勝る
この投稿では、u64値のソート済み配列について思考実験を行っています。バイナリ検索はキャッシュミスごとに残りの検索空間を半分にします。線形検索はミスごとにcache_line_size / item_size項目を除外します。u64の場合、64 / 8 = 8です。したがって、損益分岐点は約16項目であり、両方の戦略で最大2回のキャッシュミスが発生します。2つの注意点が実際の損益分岐点を押し上げます：CPUプリフェッチャーが後続のキャッシュラインを独自にフェッチする可能性があり、線形検索に有利に働きます。また、線形検索はより単純で、CPUパイプラインの並列性をより多く可能にします。この投稿では、64個のソート済みu64値（キャッシュラインあたり8個）でこれを示しています：そのサイズではバイナリ検索は3回のミス、線形検索は6回のミスが必要ですが、16項目では両方とも最大2回で済みます。
これがbbtreeがノードを約16〜32項目にサイズ設定する理由であり、線形検索を常に使用でき、SIMDも可能にします。この設計は、キャッシュを意識したB+ツリーに関する初期の研究（Rao and Ross, SIGMOD 2000）に従っています。
inline_keys: ヒープ割り当てキーをキャッシュフレンドリーにする
文字列キーは上記の算術を壊します。Stringのバイトはヒープ上にあり、ノードにインラインではないため、1つのキーをロードすることは、1回のミスで8つのキーを得るのではなく、独自のキャッシュミスになります。したがって、Stringキーの場合は通常バイナリ検索が望ましいです。
bbtreeの答えはinline_keysであり、この投稿ではデータベースが何十年も使用してきたアイデアであり、German stringsやApache ArrowのStringViewに似ていると説明しています。各キーから導出された固定幅コードがノードにインラインで格納されます。固定サイズのインラインキーを使用すると、1回のキャッシュミスで再び8つ以上のキーがロードされ、比較がタイブレークした場合にのみフルキーがロードされます。
prefix_keysは長い共有プレフィックスを処理します
URLやファイルパスなどのキーは長いプレフィックスを共有することが多いため、最初の8バイトだけをインラインキーとして取得しても、有用な比較ができない場合があります。bbtreeはprefix_keys値を格納します：ノード内のすべてのキーの共通プレフィックスです。ノードはそれらのバイトを明示的に格納する必要はありません。ノード内のすべてのキーは、親の両側の2つのセパレータの間にソートされるため、それらの2つのセパレータが最初の20バイトを共有する場合、子ノード内のすべてのキーは同じ20バイトで始まります。したがって、各ノードはプレフィックスの長さのみを格納し、各キーの直後のウィンドウを保持します。この手法はPrefix B-Trees（Bayer and Unterauer, TODS 1977）に遡ります。
整数キーも恩恵を受ける
u64やu128などの整数キーは、ビッグエンディアンで格納され、そのバイトが数値と同じ順序でソートされる場合、同じトリックを使用できます。
InlineKeyトレイトとRustの型システム
ユーザーは、複合構造体キーを含む独自のキータイプに対してInlineKeyトレイトを実装できます。このトレイトは、2、4、または8のバイト幅と、指定されたオフセットでキーのエンコーディングの8バイトを返す関数（ビッグエンディアン、末尾を超えてゼロパディング）を宣言します：
pub trait InlineKey: Ord {
/// ノードが保持する各インラインキーのバイト数：2、4、または8。
const WIDTH: InlineWidth = InlineWidth::Eight;
/// キーのエンコーディングのバイト `offset..offset + 8`、ビッグエンディアン、
/// 末尾を超えてゼロ、キーと同じ順序になります。
fn inline_key_at(&self, offset: usize) -> InlineWord;
}
この投稿では、Rustの型システムが最もトリッキーな部分であると指摘しています。すべてのキータイプにInlineKeyの実装を要求すると、bbtreeがstdのBTreeMapやBTreeSetのドロップイン置換として機能しなくなります。Nightly Rustには、まさにこの目的のための特殊化（RFC 1210、2016年から不安定）があります。安定版Rustの場合、bbtreeは一般的なタイプを手動で特殊化します：u64、i64、u128、i128、String、str、&str、Vec
バッチモード: キャッシュミスをFutureとして扱う
2番目のクラスの最適化は、レイテンシを削減するのではなく隠すことです。ソフトウェアプリフェッチは役立ちますが、Bツリーには十分ではありません。Bツリーのメモリアクセスは根本的にチェーンされているためです：現在のノードが検索されるまで次のノードをフェッチできません。
bbtreeは、Bツリーがバッチで読み取られるか構築されることが多いという事実を利用します。get_many_copiedやinsert_manyなどのバッチAPIは、キーの配列を入力として受け取り、回答の配列を出力として返します。内部的には、bbtreeはキャッシュミスをFutureとして扱い、RustコードがIO操作を待機するのと同じようにそれを待機します。コードの形状はおおよそ次のとおりです：
fn get_many<const N: usize>(&self, keys: [&K; N]) -> [Option<V>; N] {
let lanes = keys.map(|key| self.search(key));
block_on(join_all(lanes))
}
async fn search(&self, key: &K) -> Option<V> {
let mut node = self.root();
while node.is_internal() {
let edge = node.search(key);
node = node.child(edge);
prefetch(node.header()).await;
}
node.get(key)
}
実装を形作る3つの制約があります。まず、キャッシュミスは約100ナノ秒かかるため、Futureは非常に軽量でなければなりません。tokioのような汎用ランタイムは、キャッシュミス自体よりもオーバーヘッドがかかるため、bbtreeは独自の小さなエグゼキュータでレーンをポーリングし、アロケーションを行わず、ランタイムを使用しません。次に、コンパイル時に生成される関数ごとのasyncステートマシンは、状態遷移が安価になるように可能な限り小さくなければなりません。第三に、キャッシュラインがすでに常駐しているかどうかを知る方法がないため、bbtreeは推測します：リーフがL2キャッシュを超えて成長すると、リーフはほぼ常にミスですが、小さなツリーはキーを一度に1つずつルックアップします。この投稿では、データベース研究がこの方法でルックアップを何年もインターリーブしてきたと述べています（手動およびコルーチンを使用）。
正しさ
この投稿では、速度は簡単で正しさは難しいと明示しています：パフォーマンスは測定可能であり、LLMはワークロードを反復処理できますが、正しさは暗黙的であり、すべてのDON'Tをリストするプロンプトはなく、テストスイートがコードの正しさを証明することはなく、誰もすべての望ましいプロパティを列挙することはできません。この投稿では、bbtreeには正しさに近づくための3つのガードがあると述べています。コメンテーターは、プロジェクト自身のその作業の枠組みを次のように引用しています：「正式検証、モデルチェック、決定論的シミュレーション、ファジング、および多くのテストによる本番準備完了。」このセクションの周辺で引用されている参考文献は、線形ゴーストタイプでRustプログラムを検証するためのVerus、並行RustコードをテストするためのAWSのShuttle、およびフォークベースの決定論的並行性テストツールであるffsを指しています。
主張が反発に直面する場所
Hacker Newsの議論は「最速」という言葉に顕著に懐疑的であり、複数のコメンテーターが反対データを提供しています。
スワップが遅くなる実際のワークロード
コメンテーターvirtualritzは、3Dブールメッシュカーネルでbbtreeをテストし、std::BTreeMapを他のコード変更なしでスワップアウトし、リグレッションを報告しました：96〜1536面のメッシュでの和集合と差集合の操作が11％〜21％遅くなり、交差ステージが16％〜34％遅くなりました。より大きなフィクスチャでは、100万の頂点IDを持つNefertitiバストスキャン（3回のベスト、秒）：
| ケージ操作 | std | bbtree |
|---|---|---|
| difference | 84.2 | 83.0 |
| union | 83.2 | 85.6 |
| intersection | 61.3 | 67.1 |
| limit-surface difference (2回のベスト) | 123.9 | 147.2 |
導き出された結論は、bbtreeの利点はおそらく特定の、そしておそらく狭いユースケースのセットでのみ有効であり、std::BTreeMapのような汎用マップは、任意のワークロードにわたって持ちこたえるために妥協を余儀なくされるというものでした。
トライが本当の競争相手
コメンテーターnicknashは、Bツリーの自然な競争相手はトライベースの構造であり、バーストトライ、最適化されたq-fastおよびp-fastトライ、レベル圧縮トライ、バケットトライ、パス圧縮トライ、およびキー長が許す場合のvan Emde Boasレイアウトなどの最適化された層状ツリーを含むと主張しました。完全に比較ベースの構造はめったに必要ないと主張しました。整数、浮動小数点数、文字列は辞書式構造で処理できるためであり、トライは対数対数時間の操作で一様ランダムデータに特に優れていると述べました。コメンテーターは、その作業を良いと呼びながらも「最速」というラベルには懐疑的でした。
文字列キーでのメモリ使用量
コメンテーターytxmは、/usr/share/dict/words上のStringからusizeへのマップ（値は辞書オフセット）を測定し、bbtreeがstd::collections::BTreeMapよりも約40％多くのRAMを使用すると報告しました。これは反駁ではなくデータポイントであると述べました。なぜなら、投稿の低メモリ主張は特に整数キーに関するものだったからです。同じコメンテーターは、アニメーション化されたウェブペーパー形式を批判し、動的要素が読むのと同じくらいスキップする必要があると述べました。
フレーミングへの懐疑
他のコメントはプロジェクトのポジショニングに疑問を呈しました。あるコメンテーターは「人間はLLMよりも優れたコードを書くことはできない」と引用し、大胆な主張と呼びました。別のコメンテーターは、この文脈でモデルチェックが何を意味するのか尋ねました。別のコメンテーターは、この記事を「AIスロップ」と一蹴し、冒頭の引用に異議を唱えました。あるコメンテーターは単にソースを求めました。
実務家の関心
すべての反応が否定的だったわけではありません。コメンテーターelendilmは、システムDipの「スマートバッチング」のスキャッターフェーズで作業を重複排除するためにBTreeMapを使用していると説明し、この重複排除は、単一リクエストでの200k以上の挿入のほとんどのバルク書き込みワークロードで最も遅いフェーズであり、ファンアウト、データベース書き込み、コミット、および収集の合計時間の最大3倍かかることがあると述べました。彼らはそこでbbtreeを試す予定でした。コメンテーターjared_hulbertは、隣接する問題に取り組んでおり、投稿のコヒーレンストラフィックの扱いを強調し、独自の技術をbbtreeに適用するつもりであると述べました。
重要なポイント
- bbtreeは、std::BTreeMapおよびBTreeSetのドロップイン置換として提示されるRustの順序付きマップであり、LSMツリーメムテーブルのスキップリストも置き換えます。
- その見出しの数値は、各システム独自のベンチマークでの4つのLSMツリー統合（最大6.83倍）、インメモリデータベースインデックス（挿入2.22倍、インデックス付きSELECT 1.90倍）、およびmmapされたディスク常駐ツリー（stdのBTreeMapよりも最初の応答が160〜2,500倍高速）から得られています。
- 設計は、3つのメカニズムを介してキャッシュミスを中心に構成されています：線形に検索される16〜32項目のノード、固定幅のキーコードをノードに保持するinline_keys、およびノードのキーの共有プレフィックス長のみを格納するprefix_keys。
- バッチAPIは、ミスを待機可能なFutureとして扱い、tokioではなく目的に合わせて構築されたアロケーションフリーのエグゼキュータでレーンをポーリングすることにより、キャッシュミスのレイテンシを隠します。
- 独立したテストでは、3Dブールメッシュカーネルでのリグレッションと、Stringキーマップでのメモリ使用量が約40％高いことが報告されたため、パフォーマンスの主張は普遍的ではなくワークロード依存であるように見えます。
- この投稿は公開前に、Andrew Lamb（InfluxData）、Zac Farrell、Eddie Tejeda、Divya Ranganathan（Hotdata）、Jacopo Tagliabue（bauplan）、Wanxiang Zhong、Junxuan Liaoによってレビューされました。
SUMMARY: bbtreeはRustのBツリー順序付きマップであり、著者は4つのLSMツリーでスキップリストに対して1.37〜6.83倍の高速化、データベースインデックスとして挿入が2.22倍高速、mmap時に最初の応答が160〜2,500倍高速であると報告していますが、Hacker Newsのコメンテーターはメッシュ処理と文字列中心のワークロードでのリグレッションを報告しています。
TITLE: bbtree: スキップリストに対して最大6.83倍を主張するRustの順序付きマップ、そしてコメンテーターが疑う点