PaPoo
cover
technews
Author
technews
世界の技術ニュースをリアルタイムでキャッチし、日本語でわかりやすく発信。AI・半導体・スタートアップから規制動向まで、グローバルテックシーンの「今」をお届けします。

fbtreeは何を速くしたのか、どこで割り切ったのか

この記事は後半です。前半は Qiita にあります: Valkeyがsorted setをB+木に替えた日──5百万要素で見えた50.3B→28.5Bの差

速くなったのは「探す」より「待たない」こと

前半で見たとおり、Valkey の大きな sorted set は、順序を保つための付帯情報が重くなりすぎていました。fbtree はその負担を、葉に要素を詰める B+木の形へ寄せ直した実装です。重要なのは、単に木を使ったことではなく、ひとつのノードに多くを載せて、CPU が何度も別アドレスへ飛ばなくて済むようにした点でした。

画像: github.com より
画像: github.com より

その結果、平均計算量の見かけはどちらも O(log n) のままでも、実際の待ち方が変わります。skiplist は次のノードがどこにあるかを毎回ひとつずつ辿るのに対し、fbtree は 61-way fanout で一気に候補を絞れます。しかも inner node には feature が入り、SIMD でまとめて比較できるので、子ノードへ降りる前にかなりの分岐を片付けられる。理屈の上では同じログでも、メモリ階層を何回往復するかが違うわけです。

数字はコマンドごとに表情が違う

この変更がいちばん効いたのは、ZADD と ZREM でした。公式ブログのベンチマークでは、ZADD のスループットが 105% 向上し、ZREM は 76% 向上しています。どちらも ordered index の中で要素を動かす操作なので、浅い木構造と少ないポインタ更新の恩恵をそのまま受けています。更新系ほど差が大きい、というのは納得しやすいところです。

一方で、全部が大きく速くなったわけではありません。ZRANK は 19%、ZCOUNT は 27% の改善ですが、ZRANGE は 6%、ZRANGEBYSCORE は 1% にとどまります。ZRANDMEMBER と ZSCORE はどちらも 2% 程度です。ここから見えてくるのは、木の差がそのまま出る場面と、そうでない場面の境目です。索引をたどるコストが支配的なら効く。だが返すデータ量が大きい、あるいはそもそも hashtable 側で完結する処理では、構造変更の恩恵は薄い。

ZPOPMIN が 0% だったのも示唆的です。端の要素を取って新しい要素を足す操作では、fbtree 側で左端・右端の leaf を持っているため、もともとの skiplist とあまり変わらない。ここは「木にしたから全部速い」ではなく、「どこを O(1) に寄せ、どこを O(log n) のままにしたか」が効いています。

変わらないものを先に知っておく

利用者から見ると、機能は基本的に変わりません。sorted set のコマンドや振る舞いはそのままで、見える違いは large sorted set の OBJECT ENCODING が skiplist から btree に変わることです。監視やテスト、ツールがこの文字列を見ているなら、そこだけは直す必要があります。

逆に言うと、small sorted set は今回の話の外です。listpack のしきい値以下なら、もともと skiplist を使っていません。だから「Valkey の sorted set 全体が新実装に置き換わった」と捉えると外します。影響するのは、順序付き集合が大きく育ったときだけです。

また、fbtree の設計には割り切りもあります。GitHub の pull request では、削除時の merge や compaction は後続の作業として残されていました。つまり、葉が一時的に疎になる可能性はある。完全に詰め直すところまで最初から入れず、まずは読み書きの効率を優先したわけです。ここは実装上の潔さでもあり、限界でもあります。

自分なら、こういう場面で効かせる

この変更が刺さるのは、メモリに余裕がないのに、大きいランキングや時系列順の集合を抱える場面です。遅延キュー、スコア付きの上位 N 件、期限順の掃き出しのように、順序アクセスが日常的に走るなら fbtree の恩恵は大きい。特に 20 バイト級の member が大量にあるなら、50.3B から 28.5〜32.0B への差は無視できません。要素本体より管理コストが目立つ世界では、十数バイトの改善がそのまま台数や再配置コストに効きます。

ただし、member が大きくなるほど相対効果は縮みます。公式ブログも、節約は「要素が小さい集合ほど相対的に大きい」と述べています。つまり、なんでもかんでも効く万能薬ではない。スコア順の集合を多用していて、しかもメモリ圧が苦しいなら採る。そうでなければ、まずは現状維持でも困らないことが多いはずです。

Valkey の面白さは、B+木にしたこと以上に、CPU が嫌う待ち方を減らしきったところにあります。skiplist は理論上すっきりしていましたが、実装上は「散らばった 1 要素ずつの部屋」でした。fbtree はそこを、まとめて置き、まとめて読む形へ寄せ直した。大きい sorted set を本気で扱うなら、この差はかなり現実的です。

同じ著者の記事