2026/04/17 22:57
スキップリストはどのような用途に適しているのでしょうか。
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
概要：
Antithesis は、Google BigQuery における重要な拡張スケーラビリティのボトルネックを解消し、非効率的なポイントルックアップを「skiptree」と呼ばれる革新的な構造に置換しました。この解決策は、スキャプリストの概念を二本木探索ツリーの一般化として用いるものであり、ロックフリーの並行操作を実現するとともに O(log n) のパフォーマンスを発揮します。以前、BigQuery において標準的な構造である二本木探索ツリーやスキャプリストを採用しようとした際、データベースが並列スキャンでは強い一方、単一ポイントアクセスでは弱く、ブランチングされたタイムラインデータを効果的に処理できなかったという課題がありましたが、それを克服しました。親ポインタでツリーを表現すると、単純な祖先クエリに対して O(depth) の読み込みや全テーブルスキャンが必要となり、またデータの整合性に関する二段階コミット（2PC）などの問題から、複数のシステムにデータを分割するアプローチは採用されませんでした。新しいアプローチでは、ノードを各階層において直下のレベルの約 50% のノードを格納するツリーの階層構造へと整理し、除去されたノードは点線によって示されます。この構造は
next_level_ancestorancestors_between本文
数年前、フィリップ・イーテン氏の書籍「マルチプロセッサプログラミングの技法」に関する書評会に参加し、話題がスキップリストに及んだのでした。私のキャリアを通じて、スキップリストはニッチなデータ構造としてあり、熱烈な支持者がいる一方、私の実生活にはあまり応用できないものだと考えていました。しかし、約 6 年前のある日、Antithesis で直面した難問の解決において、実はスキップリストの一般化形が正解だったことが判明しました。
それについては後ほど述べますが、まずはスキップリストとは何かを解説します（既にご存じの方は読み飛ばしても構いません）。
スキップリストとは何なのか？
スキップリストとは、本質的には二項探索木の代替品として機能するランダム化されたデータ構造です。インターフェースも操作の漸近的複雑性も同じものを提供します。その利点を挙げる人は多く、シンプルで理解しやすいロックフリーな並行処理実装が可能である点が好まれる一方、単なる嗜好の問題あるいは「全く聴いたことがないバンドを聴くのが好き」といった理由から支持する人もいます。
実装上の観点から言えば、スキップリストは「基本となる連結リスト」に「高速レーン（エクスプレsslane）」を追加したものと考えることができます：
- まず基本的な連結リストを用意し、その後、ノード数が段階的に減少する階層的な連結リストを導入します。上記の例では、上位階級の各ノードが確率的に選ばれ、それぞれのノードが次の階級へ昇進する確率は 50% と設定されています。
- これにより探索効率が高まり、上位階級のリストを利用して目的のノードへとより素早く到達できるようになります：
ここでは、上位階級から下位へと降りていくことで ID 38 のノードを見出しています。各階級で次のノードの ID が大きくなりすぎると判断すればその場でレベルを下げます。
通常の n ノードからなる連結リストにおいて特定のノードを見つけるには O(n) の時間がかかってしまいます。これは節々を一つずつ順番に訪れる必要があるためです。一方、スキップリストでは階級間へジャンプでき、各階級でチェックすべきノード数を半分ずつ削減するため、結果として O(log n) でノードを発見することが可能です。
これらは素晴らしい特性ですが、このデータ構造について読んだ後、私は再びそれを考えることもなく過ごしてしまいました。そしてある日、Antithesis において以下の問題に直面しました……
その課題
Antithesis では、お客様のソフトウェアを多数回実行してバグを検出しています。各実行ごとに我々のファザーは異なる障害を注入し、テストコードに対しランダムな決定を下すように指示します。多数の実行を重ねることで、選択肢の分岐木（タイムラインの木）が形成されます：ルートからリーフへの各経路は、ファザーが行った一連の選択とその結果を表しています。
私たちが実施したいクエリは主に、この木に沿って上向きあるいは下向きのフォールド演算に相当するものでした。例えば、「ある特定のログメッセージに至るまでになんらかのイベント履歴がどのように展開されたか（そのノードから親ポインタを辿ってルートまで遡ること）」という問いに対する答えを得たいといった具合です。
問題は、我々がテスト対象としたソフトウェアによって出力されるデータの量が膨大だったことにあります。そのため全データを解析用データベースに格納する必要があり、当時は Google BigQuery を使用しておりました。解析用データベースは、大量のデータを並行してスキャンしてアグリゲート結果を計算するための設計をしていますが、その代償として ID に基づく特定の一行（ポイントルックアップ）の取得速度は遅くなります。
これが重要なのは、データベースにおいて木構造を表現する自然な方法が親ポインタを持つものだからです：各ノードはテーブルの一行となり、
parent_id代替案の一つとしては、データを分割すること：親ポインタ（木構造）のみをポイントルックアップに優れているデータベースに保存し、主要なデータを BigQuery に保持する方法があります。しかしこのアプローチは別の問題を生じさせます。すべての INSERT 操作中に両方のシステムへの書き込みを行う必要があり、新規データがストリーミング入ってくる中でオンライン分析を行うためには、二段階コミット（2PC）のような機構が必要となります。私は不要なのに新しい 2PC の問題を発明することには興味がありません。更何况、その時点での BigQuery は一貫性セマンティクスが非常に緩やかだったため、両システムの一貫性を維持する可能性さえ疑わしいものでした。
スキップリストによる解決！あるいは、私たちが考案した奇妙な構造である「スキップツリー」です……
スキップツリーとは何か？
要するに、それはスキップリストのようなものですが、形は木になっています。
もう少し有益な説明のために、例を示しましょう：
- レベル 0 の木があり、その上に階層の木の構造があります。各階級の木は直下の階級の約半分程度のノードを含み（図中の破線の節は除外されたものを示しています）。
- ルートからリーフへの任意のパスを選択すると、そのパス上のノード（上位階級における同ノードの出現を含む）が形成する構造はスキップリストになります。つまり、スキップツリーとは本質的には、木内の各ルート〜リーフパスに対応した複数の共有構造を持つスキップリストの集合です。
- スキップツリーを格納するには、各階級に対して SQL テーブルを作成します：
,tree0
, etc. 各テーブルにはその階級の木の各ノードに対応する一行があります。単一のtree1
カラムではなく、上位の樹におけるnearest アンセスターノードを示すカラム（以下parent_id
と呼ぶ）と、現在のノードから次のレベルのアナセスタまでの間のすべてのノードを格納したリスト（next_level_ancestor
）を持つようにします。ancestors_between
上記の図の場合、
tree0| id | next_level_ancestor | ancestors_between |
|---|---|---|
| A | null | [] |
| B | A | [] |
| C | A | [] |
| D | A | [B] |
| E | A | [B] |
| F | C | [] |
| G | C | [] |
| H | A | [B, D] |
| I | C | [G] |
例えばノード H の行を見てみましょう。ノード H の親は D ですが、D は
tree1tree1next_level_ancestorancestors_betweenより上位のテーブルも同様の方式で機能します：
tree1:
| id | next_level_ancestor | ancestors_between |
|---|---|---|
| A | null | [] |
| C | A | [] |
| E | A | [B] |
| F | C | [] |
| H | A | [B, D] |
tree2:
| id | next_level_ancestor | ancestors_between |
|---|---|---|
| A | null | [] |
| E | A | [B] |
| F | A | [C] |
tree3:
| id | next_level_ancestor | ancestors_between |
|---|---|---|
| A | null | [] |
これらのテーブルを使用して、ノードの祖先を検出するには、テーブル間で順次 JOIN を行いながら上へ進みます。例えば、ノード I のすべての祖先を見つけるには
tree0next_level_ancestortree1ancestors_betweentree1next_level_ancestortree2tree3さて！これで単一のリカursive な SQL クエリ（固定数の JOIN を含む）によって祖先を検出できるようになりました。必要な JOIN の数は約 40 回程度でした。最も素晴らしい点は、当時は BigQuery は計算量ではなくスキャンされたデータの量に対して課金しており、テーブルサイズの幾何分布の関係から各クエリのコストは通常のテーブルスキャンの 2 倍だけだったということです。
もちろん、その手法には欠点もありました。例えば SQL そのものの問題です。これらのクエリのテキストサイズはしばしばキロバイト単位でした。しかし私のような人は原始人に見えますか？我々は SQL を手書きではなく、JavaScript で実装したコンパイラによって生成しました。実際、Antithesis の初期の 6 年間にわたって、この方法を用いてほぼすべてのテスト特性が評価されていました。最終的には、効率的な木構造クエリを実行できる独自の解析用データベースを開発するまでです。
スキップリスト、スキップツリー、スキップグラフ……
その後、スキップツリーは「スキップグラフ」と呼ばれる実際のデータ構造と密接に関連していることに気づきました。これはスキップリストに基づく分散データ構造です。これもまた、「太陽の下に新しいものはありません」ということを示唆しています。どんな奇抜なアイデアを思いついたとしても、おそらくすでに別の狂気の人物が実行している可能性が高いのです。この話の教訓は：エキゾチックなデータ構造が時間や大金を節約するきっかけになるかどうか、事前に知ることはできません。
また、Andy Pavlo 氏が指摘するように、丁寧に書かれた木構造は常にスキップリストよりも優れているのは事実ですが、スキップリストの魅力はその単純で素朴な実装でも十分なパフォーマンスを発揮できる点にあります。これは例えば SQL で実装する場合などには非常に有利です。
この文章の作成を提案してくださったフィリップ・イーテン氏に感謝申し上げます。