スキップグラフ

スキップグラフは、スキップリストに基づく分散データ構造の一種です。2003年にジェームズ・アスペンスとガウリ・シャーによって発明されました。ほぼ同一のデータ構造であるSkipNetは、同じく2003年にニコラス・ハーベイ、マイケル・ジョーンズ、ステファン・サロイウ、マーヴィン・タイマー、アレック・ウォルマンによってそれぞれ独立して発明されました。^{[ 1 ]}

スキップグラフは、分散システムにおけるバランスツリーの完全な機能を備えています。スキップグラフは主にピアツーピアネットワークの検索に使用されます。キー順序によるクエリ機能を提供するため、ハッシュテーブル機能のみに基づく検索ツールよりも優れています。スキップリストやその他のツリーデータ構造とは対照的に、スキップグラフは非常に回復力があり、ノード障害の大部分に耐えることができます。さらに、障害ノードによって乱されたスキップグラフの構築、挿入、検索、修復は、簡単なアルゴリズムで実行できます。^[²^]

説明

スキップグラフは、バランス検索木に似せて設計されたスキップリストに基づく分散データ構造です。これは、分散ハッシュテーブルを実装するいくつかの方法の 1 つであり、リソースの名前 (またはキー) を指定して、ネットワーク全体のさまざまな場所に格納されているリソースを見つけるために使用されます。スキップグラフには、Chord (ピアツーピア)やTapestry (DHT)などの他の分散ハッシュテーブルスキームに比べて、追加と削除が対数時間の予測時間で実行できること、インデックス情報を格納できるようにリソースごとに対数スペースを確保できること、セット内のノードの数に関する知識が不要であること、複雑な範囲クエリをサポートしていることなど、いくつかの利点があります。Chord や Tapestry との主な違いは、リソースの検索キーのハッシュが行われないことです。これにより、スキップグラフ内で関連リソースが互いに近くに存在できます。この特性により、指定された範囲内での値の検索が可能になります。スキップグラフのもう 1 つの強みは、ランダム障害モデルと敵対的障害モデルの両方において、ノード障害に対する耐性があることです。

実装の詳細

スキップリストと同様に、ノードは複数のレベルで昇順に並べられます。レベルiの各ノードは、レベルi +1 に確率 p (調整可能なパラメータ) で含まれます。レベル 0 は、セット内のすべてのノードを含む1 つの双方向リンクリストで構成されます。リストはレベルが上がるにつれて次第にまばらになり、リストは 1 つのノードだけで構成されるようになります。スキップグラフがスキップリストと異なるのは、レベルi ≥ 1 の各レベルに複数のリストが含まれることです。リスト内のキーxのメンバーシップは、メンバーシップベクトル⁠ ⁠ $m(x)$ によって定義されます。メンバーシップベクトルは、固定アルファベット上の無限のランダムな単語として定義され、スキップグラフの各リストは同じアルファベットからの有限の単語wによって識別されます。その単語が⁠ ⁠ $m(x)$ の接頭辞である場合、ノード x はリストのメンバーです。^{[ 2 ]}

オペレーション

スキップグラフは、検索、挿入、削除といった基本的な操作をサポートします。また、より複雑な範囲検索操作もサポートします。

検索

スキップグラフの検索アルゴリズムはスキップリストの検索アルゴリズムとほぼ同じですが、分散システムで実行できるように変更されています。検索は最上位レベルから開始され、構造全体を走査します。各レベルでは、次のノードにより大きいキーが含まれるまで、リストを走査します。より大きいキーが見つかると、検索は次のレベルに進み、キーが見つかるか、キーがノードセットに含まれていないと判断されるまで続きます。キーがノードセットに含まれていない場合は、検索キーよりも小さい最大値が返されます。

リスト内の各ノードには次のフィールドがあります。

key: ノードの値。
neighbor[R/L][level]: レベル i で二重にリンクされたノードの右隣と左隣へのポインターを含む配列。

search(searchOp, startNode, searchKey, level)、 もし(v.key = searchKey)ならば (foundOp, v) を startNode に 送信、もし(v.key < searchKey)ならばlevel ≥ 0 であれば( v.neighbor[R][level].key ≤ searchKey)ならば(searchOp, startNode, searchKey, level) を v.neighbor[R][level] に 送信、そうでなければbreak する レベル = レベル - 1 そうでなければ、 level ≥ 0 の場合、 ((v.neighbor[L][level]).key ≥ searchKey)であれば、 (searchOp, startNode, searchKey, level) を v.neighbor[L][level] に送信し、 それ以外はbreak する。 レベル = レベル - 1 (level < 0)の場合、 (notFoundOp, v) を startNode に 送信します。

ウィリアム・ピューによる分析によれば、スキップリストと拡張スキップグラフには平均して $p$ の固定値のレベルが含まれる。^[³^]レベルごとに平均して最大でノードが検索されるとすると、送信されるメッセージの総予想数は、検索にかかる予想時間はとなる。^[²^] $したがって、 p$ の固定値の場合、検索操作には $O$ $(log$ $n$ $)個のメッセージを使用してO(log n)$ $時間$ $が$ $かかる$ $こと$ が予想される。^[²^] $O\left({\frac {\log n}{\log(1/p)}}\right)$ ${\frac {1}{1-p}}$ $O\left({\frac {\log n}{(1-p)\log(1-p)}}\right)$ $O\left({\frac {\log n}{(1-p)\log(1-p)}}\right)$

入れる

挿入は2段階で行われ、新しいノード $u が$ 何らかの導入ノード $v$ を知っている必要があります。導入ノードは、現在スキップグラフにある他のノードである可能性があります。最初の段階では、新しいノード $u は$ 導入ノード $v$ を使用して独自のキーを検索します。この検索は失敗し、 $u$ より小さい最大のキーを持つノード $s$ が返されることが予想されます。2番目の段階では、 $u は$ 、最上位レベルのリストでそれが唯一の要素になるまで、各レベルに自分自身を挿入します。^[²^]各レベルでの挿入は、標準的な二重リンクリスト操作を使用して実行されます。左側の隣接ノードの次のポインターは新しいノードを指すように変更され、右側の隣接ノードの前のポインターはノードを指すように変更されます。

入れる（）s L = 0 が 真である間 検索レベルLにsからuを 挿入する。レベルLを スキャンして、最初のL + 1文字 についてuのメンバーシップベクトルと一致するメンバーシップベクトルを持つs'を検索する（ s'が存在しない場合は検索する）。 出口 そうでなければs = s' L = L + 1

検索と同様に、挿入操作にはO (log n )個のメッセージとO (log n )個の処理時間を要すると予想されます。pの値が固定されている場合、フェーズ1の検索操作にはO ( log n )個の時間とメッセージを要すると予想されます。フェーズ2では、各レベルL ≥ 0において、 $uは$ $s$ 'を見つけるために平均1/ p個の他のノードと通信します。これにはO (1/ p )個の時間とメッセージが必要となり、フェーズ2の各ステップにはO (1)個の時間とメッセージが必要になります。 ^[²^]

消去

ノードは各レベルで並列にO (1)の時間とO (log n )のメッセージで削除される可能性がある。 ^{[ 2 ]}ノードがグラフから離脱したい場合、そのノードはすぐ隣のノードにメッセージを送信して、次のポインタと前のポインタを再配置する必要がある。^{[ 2 ]}

L = 1から最大レベルまで、 delete() を各レベルから 並列に 削除します 。レベル 0 から uを削除します。

スキップグラフには平均O (log n )個のレベルが含まれます。各レベルでは、双方向リンクリストの削除操作を完了するために2つのメッセージを送信する必要があります。各レベルの操作は並列に実行できるため、削除操作はO ( 1)の時間と期待されるO (log n )個のメッセージで完了します。

フォールトトレランス

スキップグラフでは、フォールトトレランスは、他のノードの障害によってスキップグラフから切断される可能性のあるノードの数を表します。^{[ 2 ]}ランダム障害と敵対的障害の2つの障害モデルが検討されています。ランダム障害モデルでは、任意のノードが他のノードから独立して、ある確率で障害を起こす可能性があります。敵対的モデルでは、各ステップで最悪の障害が起こるようにノード障害が計画され、スキップグラフ全体の構造がわかっており、ノードの切断が最大化されるように障害が選択されると想定しています。スキップグラフの欠点は、修復メカニズムがないことです。現在、スキップグラフを削除して修復する唯一の方法は、生き残ったノードで新しいスキップグラフを構築することです。

ランダムな失敗

スキップグラフはランダム障害に対して高い耐性を備えています。隣接ノードの状態に関する情報を維持し、冗長リンクを使用して障害が発生した隣接ノードを回避することで、多数のノードで障害が発生しても通常の動作を継続できます。障害が発生したノードの数が少ない場合、スキップグラフは通常の動作を継続できます。^[²^] James Aspnesによるシミュレーションでは、131072ノードを持つスキップグラフは、生き残ったノードが分離されるまでに最大60%のノードの障害に耐えられることが示されています。^[²^]他の分散データ構造ではより高いレベルの回復力を実現できる場合もありますが、それらははるかに複雑になる傾向があります。 $O\left({\frac {1}{\log n}}\right)$

敵対的失敗

大規模ネットワークでは、最悪の障害パターンを見つけることが困難になるため、敵対的障害のシミュレーションは困難です。^{[ 2 ]}理論分析によると、回復力はグラフの頂点拡張率に依存し、次のように定義されます。グラフGのノード集合Aについて、拡張係数は、Aに含まれないがAのノードに隣接するノードの数をAのノード数で割ったものです。スキップグラフの拡張率が十分に大きい場合、最大f個の障害を具体的に対象とした場合であっても、最大で⁠ ⁠個のノードを分離できます。^[²^] $\Omega \left({\frac {1}{\log n}}\right)$ $O(f\log n)$

参考文献

^ Nicholas JA Harvey、Michael B. Jones、Stefan Saroiu、Marvin Theimer、Alec Wolman。「SkipNet：実用的な局所性特性を備えたスケーラブルなオーバーレイネットワーク」（PDF）。
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m James Aspnes; Gauri Shah. 「スキップグラフ」（PDF） .コンピュータサイエンス – イェール大学.スキップグラフは、スキップリストに基づく新しい分散データ構造であり、リソースがいつでも故障する可能性のある個別のノードに格納されている分散システムにおいて、バランスツリーの完全な機能を提供します。ピアツーピアシステムの検索に使用するために設計されており、キーの順序に基づいてクエリを実行する機能を提供することで、ハッシュテーブル機能のみを提供する既存の検索ツールを改良しています。スキップリストや他のツリーデータ構造とは異なり、スキップグラフは非常に高い耐障害性を備えており、接続を失うことなく、多くのノードの故障を許容します。さらに、シンプルで分かりやすいアルゴリズムを使用して、スキップグラフの構築、新しいノードの挿入、検索、そしてノード故障によってスキップグラフに発生したエラーの検出と修復を行うことができます。
^ William Pugh. 「スキップリスト：バランスツリーの確率的代替手段」（PDF） .

[SkipNet-1] Nicholas JA Harvey、Michael B. Jones、Stefan Saroiu、Marvin Theimer、Alec Wolman。「SkipNet：実用的な局所性特性を備えたスケーラブルなオーバーレイネットワーク」（PDF）。

[SG-2] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m James Aspnes; Gauri Shah. 「スキップグラフ」（PDF） .コンピュータサイエンス – イェール大学.スキップグラフは、スキップリストに基づく新しい分散データ構造であり、リソースがいつでも故障する可能性のある個別のノードに格納されている分散システムにおいて、バランスツリーの完全な機能を提供します。ピアツーピアシステムの検索に使用するために設計されており、キーの順序に基づいてクエリを実行する機能を提供することで、ハッシュテーブル機能のみを提供する既存の検索ツールを改良しています。スキップリストや他のツリーデータ構造とは異なり、スキップグラフは非常に高い耐障害性を備えており、接続を失うことなく、多くのノードの故障を許容します。さらに、シンプルで分かりやすいアルゴリズムを使用して、スキップグラフの構築、新しいノードの挿入、検索、そしてノード故障によってスキップグラフに発生したエラーの検出と修復を行うことができます。

[Pugh-3] William Pugh. 「スキップリスト：バランスツリーの確率的代替手段」（PDF） .

[ 1 ]

[

[