Valkeyがskiplistを廃止、sorted setのメモリオーバーヘッドを最大43%削減
Valkey kills the skiplist, cuts sorted set overhead by up to 43%
Valkey 9.2で、大きなsorted setの内部構造がskiplistから61分岐のB+木「fbtree」に置き換わる。要素ごとに散らばるアロケーションとポインタ追跡を、連続配置とSIMDによる探索で解消。500万要素のテストでメンバーあたりのオーバーヘッドが36〜43%減り、最大109MBを節約。ZADDは105%、ZREMは76%のスループット向上も報告されている。コマンドの挙動は変わらない。
sorted setは、要素そのものを格納するよりも、要素の順序を記述するほうにより多くのメモリを使うことがある。
HNでの議論
34- hinkley
正直に言うと、Bill Pugh(ミスターSkiplist)についてはずっと判断に迷っていた。彼の並行性に関するアイデアのいくつかはかなり良かったが、Skip Listが出てきたのはちょうど、性能のための理論的設計と実用的設計が乖離し始めたと私が気づいた時期と重なっていて、skiplistはキャッシュミスを招く大きな負債だった。私が知る限り何人かが試した後、実環境での性能分析が否定的または結論が出ずに別のものへ戻ったというのも、判断を後押しした(一方が他方より優れていると証明できないなら、よりシンプルな方を使うべきで、skiplistはシンプルではない)。
- tyre
余談めくが、この機能の最終PRのPRセクションがなかなか良い[0]。推奨される読む順序、明確な設計上の決定、そして意図的に含めていない範囲についての境界が示されたレビューガイドがある。これはLLMが非常に得意とする類のもので、人間のレビュアーにとってROIが高い。
- dreamcompiler
> すべてのノードが後方ポインタを持つ
興味深い。skiplistは後方ポインタを必要としない。目標ノードにできるだけ近づきつつ行き過ぎない、レベルnからレベル0までのノード群である「フィンガー」を保持しておけば、skiplistを後方にもほぼ前方と同じ速さでたどれる。これらのノードを保持する理想的な場所はスタック上だ。後方にたどるには、開始ノードを通常どおり探索するが、ポインタのレベルを下げるたびに最後のポインタをまずスタックにプッシュする。そうすれば後方へのたどりはスタックのポップと、左に寄りすぎたポインタまでポップで戻ったときの適切な前方再帰呼び出しになる。アイデアは英語よりコードで伝えた方が簡単だが、親指でスマホにアルゴリズムを打ち込む気はない。
- rsalus
CPQにはずっと前からMultiQueueアルゴリズムに移行していて、SkipListのユースケースは今やごくわずかしか残っていないように思える…
- reconditerose
Redisは歴史的にソート済みインデックスを維持するためにskiplistを使っていた。Valkeyはそれが現代のハードウェアでは非効率で遅いことを示し、代わりにB+木へ移行した。