
2026/11/18 1:58
Valkey はシリアルリストを廃止し、ソート済みセットのオーバーヘッドを最大 43%削減
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
Valkey 9.2 は、従来の高メモリ消費型の skip list 構造を、大規模なソート済み集合用として新しい効率的なデータ型である fbtree に置き換えることで、主要なパフォーマンス向上を実現します。この構造変化は、前回の設計に見られる決定的なボトルネック、すなわち過剰なメモリ使用量と複雑なポインタ管理によって引き起こされる頻発するキャッシュミスに直接対応しています。B+ 樹を灵感を得たアーキテクチャを採用した新しい fbtree は、パックされたストレージ値と高度な SIMD 検索技術を駆使し、速度を大幅に向上させています。
実用的な影響は即時かつ著しく、Valkey 9.2 を導入するユーザーは、メンバーあたりのメモリオーバーヘッドが約 36〜43% 減少し、500 万件のメンバーを持つデータセットでは最大 109 MB の節約が可能であることを確認します。さらに、動作パフォーマンスも飛躍的に向上しており、ZADD コマンドのスループットは +105% の増加を示し、ZREM 操作は 76% の改善が見られます。内部エンコーディング文字列が"skiplist"から"btree"に変更されるものの、この最適化により、メモリ制約のある環境においても、以前よりも速くより大規模なデータセットをホストできるようになりました。
本文
Valkey 9.2「fbtree」実装の技術的深掘り:B+ ツリーへの転換とパフォーマンス向上
日付: 2026 年 11 月 16 日
著者: Rain Valentine, Dragos Andriciuc
背景と概要
Valkey 9.2 では、ソート済みセット(Sorted Set)のバックエンドとして、従来の「スキップリスト」を 「fbtree」 に置き換える大きな変更を行いました。
- fbtree の定義: 「Feature-based B+ Tree」の略称であり、高い分岐因子を持つ B+ ツリーの変種です。
- 採用理由: スキップリストは要素ごとの順序付けメタデータ(メモリ使用量)が大きかったため、より効率的なデータ構造への変更が必要でした。
- fbtree の特徴:
- 従来の B+ ツリーの「高い分岐因子」と「連続的なメモリ配列」の利点を活きます。
- Valkey のワークロードやメモリアロケータに合わせて最適化されています。
- 主な機能: 特徴ベースのルックアップ、SIMD による検索、葉ノードの連結リスト化、連続操作への高速パスなど。
実験結果(500 万要素規模):
- メモリオーバーヘッド削減:36%〜43%
- 最大メモリ節約量:109 MB (連続挿入時)
なぜスキップリストを置き換える必要があるのか?
リストパック(Listpack)の閾値を超えたソート済みセットは、ハッシュテーブルとスキップリストの組み合わせで構成されています。ハッシュテーブルはメンバー名の
O(1) ルックアップ、スキップリストはスコアによる順序付きルックアップ O(log n) を担当します。
メモリオーバーヘッドの問題
Valkey のスキップリストには大きな「生メモリ(raw memory)」のコストがかかります。
- ノード構造: 各ノードは exactly 1 つの要素のみを持ち、ポインタで連結されますが、メモリの散在した異なる場所(allocations)に配置されます。
- 計算上のコスト:
- 後方ポインタ: 8 バイト
- ポインタ + スパン値: レベルあたり平均約 1.33 (確率的な追加のため) → 合計でノードあたり約 29 バイト のオーバーヘッド。
- スコア用データ (+8 バイト) を含むと、メンバー文字列以前にノードあたり約 37 バイト が発生します。
キャッシュミスと依存付きフェッチの課題
現代の CPU は L1/L2/L3 ハードウェアキャッシュを活用しています(DRAM アクセス約 100 ns vs L1 ヒット約 1 ns)。しかし、スキップリストには以下のような欠点があります。
- 分散アロケーション: 各ノードはヒープ上の任意の場所に配置されるため、構造を辿る際に不関係なメモリアドレスからのデータフェッチを繰り返す必要があり、キャッシュミスが発生します。
- 依存付きアクセス: 各ステップが次のステップの場所を決定するため、メモリエアーキテクチャへの往復回数が多くなり、コアが待機する余地があります。
- 比較研究: 2025 年のインメモリインデックス同時実行性研究では、従来のスキップリストは同等の B ツリーと比較してキャッシュミスを約 2.4〜4.8 倍多く、スループットが 2〜8 倍低い傾向があることが示されました。
その代わりとなったもの:fbtree
fbtree は固定サイズのノードを持ち、葉ノードにエントリを、内部ノードに進路データを格納します。1 ノードあたり最大 61 個のエントリ(61 ウェイ)を詰め込むことで、以下の問題を解決しました。
メモリ配置の最適化
- 高密度な設計: 64 ビットビルドでは jemalloc のアロケーションクラスに収まるサイズで設計され、空間を無駄にしていません。32 ビットビルドでは
が 1280 バイトのクラスに丸め上げられます。innerNode - 値の共有化: 512 バイトの葉ノードで最大 61 個の値ポインタを共有します(1 ノード = 61 メンバー)。
- データ統合: スコアとメンバー名を別々に格納せず、正規化された 8 バイトのスコアにメンバーバイト列を付加した単一のパック済み値として格納します。これにより比較に必要なデータをまとめ、ポインタ間接化のレベルを削減しました。
メモリフェッチ回数の削減
- 分岐因子の違い: スキップリスト(有効分岐因子約 4)に対し、fbtree のファノアウトは 61 です。
- 検索パスの短縮:
を保ちつつ、traversing するレベル数が劇的に減少したため、高コストなメモリフェッチ回数が大幅に減りました。O(log n) - 連続メモリアクセス: データが連続配置されているため、現代 CPU のハードウェアプリフェッチにより、隣接するキャッシュラインを効率的にフェッチできます。数個のキャッシュラインで複数のノードを読み取ることが可能になります。
高度な最適化機能
fbtree は特定の実行操作に向けた独自の最適化も備えています。
- 特徴ベースのルックアップ (Feature-based Lookups):
- 問題:子ノードを選定する際、文字列(アンカー)を毎回フェッチして比較する必要がありました。
- 解決:内部ノードに 4 バイトの「特徴(feature)」とアンカーを格納。共有プレフィックスを別で保存し、特徴バイト列だけで子ノードを識別します。
- 効果:SIMD を活用して並列比較でき、正しい子ノードをフェッチする前に特定できます。
- 葉ノードの連結リスト化:
などの範囲コマンドで順序読み進める際、木を上昇せずに葉から葉へ移動可能(二重連結リスト構造)。ZRANGE- 最大 61 個の項目を並列処理しつつ、次の葉ノードをフェッチすることでスキャン効率を高めます。
- 両端操作への高速パス:
などで左右の葉ノードをキャッシュ保持。ZPOPMIN- 検索コストは通常 B+ ツリーの
ですが、fbtree ではキャッシュ保持によりO(log n)
に近づきます。O(1)
ユーザーにとって実際に何が変化したのか
- 機能面: コマンドの機能自体には変更はありません。ソート済みセットのコマンド動作は維持されています。
- エンコーディング表記: 大規模なソート済みセットに対して、
コマンドの戻り値がOBJECT ENCODING
からskiplist
に変更されました。btree- ⚠️ 注意: 監視システムやテストツールで文字列
を検証している場合はアップデートが必要です。"skiplist" - リストパック閾値未満の小規模セットは影響がありません(元々スキップリストではなかったため)。
- ⚠️ 注意: 監視システムやテストツールで文字列
ベンチマーク結果
メモリ効率性
順序インデックスのみを比較(ハッシュテーブル等は変更前)です。
| 挿入パターン | 変化前 (オーバーヘッド) | 変化後 (オーバーヘッド) | 削減率 | 節約メモリ (500 万要素) |
|---|---|---|---|---|
| 連続的挿入 | 50.3 バイト | 28.5 バイト | 43% | 約 109 MB |
| ランダム挿入 | 50.3 バイト | 32.0 バイト | 36% | 約 92 MB |
- 補足: 削減率は「バイト単位の保存量」ではなく「メンバー単位」です。メンバーが小さいセットほど相対的な削減率は大きくなります。
コマンドパフォーマンス
テスト環境:Graviton3 c7g.metal (64 コア)、I/O スレッド 9 つ、ソート済みセットサイズ 30 万件。 ※信頼区間はコマンドのほとんどで ≤2% です。
| コマンド | ワークロード | スループット改善率 |
|---|---|---|
| ZADD | スコア更新(全ヒット) | +105% |
| ZREM | ランダムな追加/削除 (50/50) | +76% |
| ZCOUNT | スコア範囲カウント | +27% |
| ZRANK | ポイントランクルックアップ | +19% |
| ZRANGE | 100 要素分のランクスキャン | +6% |
| ZRANDMEMBER | 100 のランダムサンプリング | +2% |
| ZSCORE | ポイントスコアルックアップ | +2% |
| ZRANGEBYSCORE | 100 要素分のスコラスキャン | +1% |
| ZPOPMIN | 最小値の POP と新しいメンバー追加 | ~0% |
- 改善の理由:
/ZADD
は要素位置再配置に伴うポインタ更新コストが大幅に減少したため。一方、範囲操作は巡回自体が安価になったが、要求処理の割合が大きいため改善率は小さいです。ZREM - 変化なし:
やZSCORE
はハッシュテーブルを利用しているため、順序インデックスへの依存度が低く変化がありません。ZRANDMEMBER
GA 前の Valkey 9.2 テストと今後の動き
重要な結論
- コマンド機能は変更されていません。
- 大規模ソート済みセットにおいて、各要素あたりのオーバーヘッドが 36〜43% 減少。
およびZADD
のスループットがそれぞれ **105%**と **76%**向上。ZREM- fbtree は既存の環境下でベンチマークを重ね、スキップリストと同等かそれ以上のパフォーマンスを示すまで最適化を続行しました。
リリース情報
Valkey 9.2 は現在**リリース候選(release-candidate)**テスト中です。
- 推奨: 特に大規模ソート済みセットや
,ZADD
,ZREM
,ZRANK
を多用するワークロードは、GA 前にリリース候補版を試すことを強く推奨します。ZCOUNT - フィードバック: テストで問題を見つけた場合は Issue を作成してください。これにより最終リリース前のバグを表面化させることができます。