Chord（ピアツーピア）

コンピューティング において、Chord はピアツーピアの分散ハッシュ テーブル用のプロトコルとアルゴリズムです。分散ハッシュ テーブルは、異なるコンピューター (「ノード」と呼ばれる) にキーを割り当てることによってキーと値のペアを格納します。ノードは、自分が担当するすべてのキーの値を保存します。Chord は、キーをノードに割り当てる方法と、ノードが最初にそのキーを担当するノードを見つけて、特定のキーの値を検出する方法を指定します。

Chordは、 CAN、Tapestry、Pastryとともに、 4つのオリジナルの分散ハッシュテーブルプロトコルの1つです。2001年にIon Stoica、Robert Morris、David Karger、Frans Kaashoek、Hari Balakrishnanによって導入され、MITで開発されました。^[1] 2001年のChord論文^[1]は、2011年にACM SIGCOMM Test of Time賞を受賞しました。^[2]

その後のパメラ・ザベの研究では、オリジナルのChordアルゴリズム（2001年のSIGCOMM論文^[1] 、 2001年の技術レポート^[3] 、 2002年のPODC論文^[4]、2003年のTON論文 ^[5]で指定）は、リングの順序を間違えて複数のリングを生成し、リングを壊す可能性があることが明らかになりました。^[6]

ノードとキーには、コンシステント ハッシュ法を使用してビットの識別子が割り当てられます。SHA -1アルゴリズムは、コンシステント ハッシュ法の基本ハッシュ関数です。コンシステント ハッシュ法は、キーとノード (実際にはIP アドレス) の両方が同じ識別子空間に均一に分散され、衝突の可能性がほとんどないため、Chord の堅牢性とパフォーマンスに不可欠です。したがって、ノードは中断することなくネットワークに参加したり、ネットワークから離脱したりできます。プロトコルでは、ノードという用語は、ノード自体とその識別子 (ID) の両方を明確に指すために使用されます。キーという用語も同様です。 ${\displaystyle m}$

Chord 検索プロトコルを使用すると、ノードとキーは、最大からまでのノードを持つ識別子円内に配置されます。 （衝突を回避するのに十分な大きさである必要があります）。これらのノードの一部はマシンまたはキーにマップされますが、その他（ほとんど）は空になります。 ${\displaystyle 2^{m}}$${\displaystyle 0}$${\displaystyle 2^{m}-1}$${\displaystyle m}$

各ノードには、後続ノードと先行ノードがあります。ノードの後続ノードは、識別子の円内で時計回りの次のノードです。先行ノードは反時計回りです。可能な ID ごとにノードがある場合、ノード 0 の後続ノードはノード 1 で、ノード 0 の前続ノードはノード です。ただし、通常、シーケンスには「穴」があります。たとえば、ノード 153 の後続ノードはノード 167 である可能性があります (ノード 154 から 166 は存在しません)。この場合、ノード 167 の前続ノードはノード 153 になります。 ${\displaystyle 2^{m}-1}$

後継ノードの概念はキーにも使用できます。キーの後継ノードは、ID が と等しいか、識別子円内でに続く最初のノードであり、 で示されます。すべてのキーは後継ノードに割り当てられ (保存され) ているため、キーを検索するには を照会します。 ${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle 後継者(k)}$${\displaystyle k}$${\displaystyle 後継者(k)}$

ノードの後継ノード (または先行ノード) はネットワークから消える場合があるため (障害や離脱のため)、各ノードは、そのノードが中心にあるノードのアークを記録します。つまり、そのノードの前のノードと後続ノードのリストです。このリストにより、ネットワークの障害率が高くても、ノードが後継ノードまたは先行ノードを正しく見つけられる可能性が高くなります。 ${\displaystyle 2r+1}$${\displaystyle r}$${\displaystyle r}$

Chord プロトコルの中心的な用途は、クライアント (通常はノードも) からキーを照会すること、つまり を見つけることです。基本的なアプローチは、キーをローカルで見つけられない場合に、ノードの後継ノードにクエリを渡すことです。これにより、クエリ時間が発生します。ここで はリング内のマシンの数です。 ${\displaystyle 後継者(k)}$${\displaystyle O(N)}$${\displaystyle N}$

上記の線形検索を回避するために、Chord は、各ノードに最大エントリを含むフィンガー テーブルを保持することを要求することで、より高速な検索方法を実装します。 はハッシュ キーのビット数であることを思い出してください。ノード のエントリには が含まれます。フィンガー テーブルの最初のエントリは、実際にはノードの直後の後続エントリです (したがって、追加の後続フィールドは必要ありません)。ノードがキー を検索するたびに、ノードは、そのフィンガー テーブル内の の最も近い後続エントリまたは先行エントリ (フィンガー テーブルによって異なります) (円上で ID が より小さい「最大の」エントリ) にクエリを渡します。これは、ノードがキーが直後の後続エントリに格納されていることを検出するまで続きます。 ${\displaystyle m}$${\displaystyle m}$${\displaystyle i^{th}}$${\displaystyle n}$${\displaystyle後継者((n+2^{i-1})\,{\bmod {\,}}2^{m})}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

このようなフィンガー テーブルでは、Nノード ネットワークで後継ノードを見つけるために連絡する必要があるノードの数は です(下記の証明を参照)。 ${\displaystyle O(\log N)}$

新しいノードが参加するたびに、3 つの不変条件が維持される必要があります (最初の 2 つは正確性を保証し、最後の 1 つはクエリを高速に保ちます)。

1. 各ノードの後継ノードは、その直近の後継ノードを正しく指し示します。
2. 各キーは に保存されます。${\displaystyle 後継者(k)}$
3. 各ノードのフィンガー テーブルは正しい必要があります。

これらの不変条件を満たすために、各ノードに対して先行ノードフィールドが維持されます。後続ノードはフィンガー テーブルの最初のエントリであるため、このフィールドを個別に維持する必要はなくなりました。新しく参加したノードに対して、次のタスクを実行する必要があります。 ${\displaystyle n}$

1. ノード（前身ノードとフィンガーテーブル）を初期化します。${\displaystyle n}$
2. 他のノードに、先行ノードとフィンガー テーブルを更新するように通知します。
3. 新しいノードは、後継ノードから担当キーを引き継ぎます。

の先行エントリは、(前の円内の)の先行エントリから簡単に取得できます。そのフィンガー テーブルについては、さまざまな初期化方法があります。最も単純な方法は、すべてのエントリに対して後続エントリの検索クエリを実行することですが、初期化に時間がかかります。よりよい方法は、フィンガー テーブル内のエントリがエントリに対してまだ正しいかどうかを確認することです。これにより、 が実現されます。最良の方法は、フィンガー テーブルをそのすぐ隣から初期化し、いくつかの更新を行うことです。これは です。 ${\displaystyle n}$${\displaystyle 後継者(n)}$${\displaystyle m}$${\displaystyle O(M\log N)}$${\displaystyle i^{th}}$${\displaystyle (i+1)^{th}}$${\displaystyle O(\log ^{2}N)}$${\displaystyle O(\log N)}$

正しい検索を確実に行うには、すべての後続ポインターが最新である必要があります。そのため、フィンガー テーブルと後続ポインターを更新する安定化プロトコルがバックグラウンドで定期的に実行されます。

安定化プロトコルは次のように機能します。

• Stabilize(): n は後続ノードに先行ノードp を問い合わせ、代わりに p がn の後続ノードになるかどうかを決定します(これは、 p が最近システムに参加した場合です)。
• 通知(): n の後継者にその存在を通知し、前継者をnに変更できるようにします。
• Fix_fingers(): 指テーブルを更新します

• 協調ミラーリング:ローカル ネットワークの外部にあるコンピューターが利用できる情報をホストするローカル ネットワークによる負荷分散メカニズム。このスキームにより、開発者は中央サーバーの代わりに多数のコンピューター間で負荷を分散して、製品の可用性を確保できます。
• タイムシェアリング ストレージ: ネットワークでは、コンピューターがネットワークに参加すると、そのコンピューターの利用可能なデータはネットワーク全体に分散され、そのコンピューターがネットワークから切断されたときに取得できるようになります。また、他のコンピューターのデータも、そのコンピューターに送信され、ネットワークに接続されなくなったときにオフラインで取得できるようになります。主に、ネットワークに常時接続できないノード向けです。
• 分散インデックス: 検索可能なデータベース内でネットワーク経由でファイルを取得します。例: P2P ファイル転送クライアント。
• 大規模な組み合わせ検索: キーは問題に対する候補となる解決策であり、各キーは解決策として評価する責任を負うノードまたはコンピュータにマッピングされます。例: コード破り
• 信頼性のために無線センサーネットワークでも使用される^[7]

Chord は高い確率でノードに連絡し、ノード ネットワーク内の後継ノードを見つけます。${\displaystyle O(\log N)}$${\displaystyle N}$

ノード がキー の後続キーを検索するとします。を の前任キーとします。メッセージを からにルーティングするのに必要なステップ数の上限を検索するとします。ノード はフィンガー テーブルを調べ、要求を の最も近い前任キーにルーティングします。このノードを と呼びます。が のフィンガー テーブルのエントリである場合、と はどちらも識別子円に沿って からまでの距離とから までの距離にあります。したがって、この円に沿ったと間の距離は最大で です。したがって、から までの距離はから までの距離よりも小さくなります。つまり、 への新しい距離は最大で最初の距離の半分になります。 ${\displaystyle n}$${\displaystyle k}$${\displaystyle p}$${\displaystyle k}$${\displaystyle n}$${\displaystyle p}$${\displaystyle n}$${\displaystyle k}$${\displaystyle f}$${\displaystyle f}$${\displaystyle i^{th}}$${\displaystyle n}$${\displaystyle f}$${\displaystyle p}$${\displaystyle 2^{i-1}}$${\displaystyle 2^{i}}$${\displaystyle n}$${\displaystyle f}$${\displaystyle p}$${\displaystyle 2^{i-1}}$${\displaystyle f}$${\displaystyle p}$${\displaystyle n}$${\displaystyle f}$${\displaystyle p}$

残りの距離を半分にするこのプロセスは繰り返されるため、ステップ後には、 までの残りの距離は最大で になります。特に、ステップ後には、残りの距離は最大で になります。ノードは識別子の円に沿って均一にランダムに分散されているため、この長さの間隔内に入るノードの予想数は 1 であり、高い確率で、そのようなノードは より少なくなります。メッセージは常に少なくとも 1 つのノード分進むため、メッセージがこの残りの距離を横断するには最大で ステップかかります。したがって、予想されるルーティング時間の合計は です。 ${\displaystyle t}$${\displaystyle p}$${\displaystyle 2^{m}/2^{t}}$${\displaystyle \logN}$${\displaystyle 2^{m}/N}$${\displaystyle \logN}$${\displaystyle \logN}$${\displaystyle O(\log N)}$

Chordが先行ノード/後続ノードを追跡している場合、各ノードが失敗する確率が1/4であれば、find_successor（下記参照）とfind_predecessor（下記参照）は正しいノードを返す可能性が高い。 ${\displaystyle r=O(\log N)}$

単純に言えば、すべてのノードが故障する確率は であり、これは低い確率です。したがって、高い確率で、少なくとも 1 つのノードは稼働しており、そのノードは正しいポインタを持ちます。 ${\displaystyle r}$${\displaystyle \left({{1} \over {4}}\right)^{r}=O\left({{1} \over {N}}\right)}$

擬似コードの定義

指[k]

成功した最初のノード${\displaystyle (n+2^{k-1}){\mbox{ mod }}2^{m},1\leq k\leq m}$

後継

識別子リング上の問題のノードの次のノード

前任者

識別子リング上の問題のノードの前のノード

ID の 後継ノードを見つけるための疑似コードを以下に示します。

// ノード n に id の後継ノードを探すように依頼します
n.find_successor(id) 
    // はい、これは開き括弧と一致する閉じ角括弧である必要があります。 //
    これは半閉区間です。if
     id ∈ (n, successor] then return successor
     else
        
        // クエリを円周上に転送する
        n0 := 最も近い先行ノード(id)
        n0.find_successor(id)を返す

// ローカルテーブルでIDの最も高い先行ノードを検索
n.closest_preceding_node(id) 
    for i = m downto 1 do 
        if (finger[i] ∈ (n, id)) then
            指を返す[i]
    戻るn

ノードの結合と離脱後にコード リング/サークルを安定させる疑似コードは次のとおりです。

// 新しいコードリングを作成します
。n.create()
    前任者 := なし
    後継者 := n

// ノード n' を含む Chord リングを結合します
。n.join(n')
    前任者 := なし
    後継者 := n'.find_successor(n)

// 定期的に呼び出されます。n は後続のノード
にその前のノードについて問い合わせ、n の直後の
ノードが一貫しているかどうかを確認し、後続のノードに n について伝えます
n.stabilize()
    x = 後継.先行
    x ∈ (n, 後継者)ならば
        後継者 := x
    後継者.通知(n)

// n'はそれが先行者かもしれないと考えています。
先行者がnilまたはn'∈(先行者、n)の場合、n.notify(n')
    
        前任者 := n'

// 定期的に呼び出されます。指のテーブルエントリを更新します。//
次に、修正する指のインデックスを保存します
n.fix_fingers()
    次 := 次 + 1
    次 > mの場合
        次 := 1
    finger[next] := find_successor(n+2 next-1 );

// 定期的に呼び出されます。先行処理が失敗したかどうかを確認します。n.check_predecessor 
()
    先行処理が失敗した場合は
        前任者 := なし

• カデムリア
• コーデ
• OverSim – オーバーレイシミュレーションフレームワーク
• SimGrid – 分散アプリケーションのシミュレーション用ツールキット -

• Chord プロジェクト (リダイレクト元: http://pdos.lcs.mit.edu/chord/)
• Open Chord – オープンソースの Java 実装
• Chordless – もう一つのオープンソース Java 実装
• jDHTUQ - オープンソースの Java 実装。ピアツーピア DHT システムの実装を一般化する API。モード データ構造の GUI が含まれています。