bbtreeがLSM-treeのskiplistを最大6.83倍高速化
Bbtree: Fastest Ordered Map
Rust製の順序付きマップ「bbtree」は、キャッシュミスを最小化するB-tree設計により、LSM-treeのmemtableで使われるskiplistを置き換えると最大6.83倍高速になる。fjall、SlateDB、Tonbo、Lanceの4システムで検証され、インメモリDBのインデックスやmmapによる再起動後の即時応答でも大きな効果を発揮する。Stringキーにはinline_keysとprefix_keysで対処し、バッチ検索ではキャッシュミスをFutureとして扱う独自のasync実行器を実装している。
キャッシュミスには約100nsかかるため、我々のFutureは可能な限り軽量でなければならない。つまりtokioや汎用のasyncランタイムは使えない。それらのオーバーヘッドはすでにキャッシュミスより大きいからだ。
- geraneum
形式的検証、モデル検査、決定論的シミュレーション、ファジング、そして大量のテストによって本番運用可能。
ここでいうモデル検査とはどういう意味ですか？
- tyilo
「LLMより優れたコードを書ける人間はいない」
大胆な主張だな……
- jared_hulbert
とても素晴らしい仕事ですね。私もこれに……隣接する分野と言えるものをやっています。私はずっと、もっと積極的にintrinsicsに手を伸ばすべきだ、キャッシュラインに徹底的に注目すべきだ、DRAMをもっと非同期ブロックデバイスのように扱うべきだ、と繰り返し主張してきました。でも、コヒーレンストラフィックの影響を示そうと思いつかなかったなんて信じられません！時間ができたら、自分のトリックのいくつかをbbtreeに適用してみようと思います。DMしてください。そのときはぜひ連絡を取りたいです。