Chord（ピアツーピア）

Protocol for distributed hash table

コンピューティングにおいて、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]修正されたプロトコルは、追加のオーバーヘッドを発生させることなく、これらのエラーを防止します。^[7]

概要

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

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

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

後継ノードの概念はキーにも適用できます。キーの後継ノードとは、識別子円（ で示される）内でIDが に等しいか、 に続く最初のノードです。すべてのキーは後継ノードに割り当てられ（そこに保存され）、キーを検索するには をクエリする必要があります。 ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle successor(k)}$ ${\displaystyle k}$ ${\displaystyle successor(k)}$

ノードの後継ノード（または先行ノード）は、障害や離脱によりネットワークから消滅する可能性があるため、各ノードは、自身が属するノードのアーク、すなわち、自身より前のノードと後続ノードのリストを記録します。このリストにより、たとえネットワークの障害率が高くても、ノードが後継ノードまたは先行ノードを正しく特定できる可能性が高くなります。 ${\displaystyle 2r+1}$ ${\displaystyle r}$ ${\displaystyle r}$

プロトコルの詳細

16ノードのChordネットワーク。ノードの1つに対応する「フィンガー」がハイライト表示されています。

基本クエリ

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

フィンガーテーブル

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

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

ノード結合

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

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

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

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

の先行エントリは、（前の円内の）の先行エントリから簡単に取得できます。そのフィンガーテーブルについては、様々な初期化方法があります。最も単純な方法は、すべてのエントリに対して後続エントリ検索クエリを実行することですが、初期化に時間がかかります。より良い方法は、フィンガーテーブル内のエントリがエントリに対してまだ正しいかどうかを確認することです。これは につながります。最良の方法は、フィンガーテーブルをそのすぐ近くのエントリから初期化し、いくつかの更新を行うことです。これは です。 ${\displaystyle n}$ ${\displaystyle successor(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 ファイル転送クライアント。
• 大規模な組み合わせ検索: キーは問題に対する候補となる解決策であり、各キーは解決策として評価する責任を負うノードまたはコンピュータにマッピングされます。例: コード破り
• 信頼性のために無線センサーネットワークでも使用される^[8]

証明スケッチ

ノード A と B 間のルーティング パス。各ホップは残りの距離を半分 (またはそれ以下) に短縮します。

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 \log N}$ ${\displaystyle 2^{m}/N}$ ${\displaystyle \log N}$ ${\displaystyle \log N}$ ${\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() 前任者 := nil 後継者 := n// ノードn'を含むChordリングを結合します。n.join(n') 前任者 := nil 後継者 := 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 指[次]:=find_successor(n+2 next-1 );// 定期的に呼び出されます。先行処理が失敗したかどうかを確認します。n.check_predecessor () 先行処理が失敗した場合は 前任者 := nil

参照

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

参考文献

1. Stoica, I. ; Morris, R. ; Kaashoek, MF ; Balakrishnan, H. (2001). 「Chord: インターネットアプリケーションのためのスケーラブルなピアツーピア検索サービス」(PDF) . ACM SIGCOMM Computer Communication Review . 31 (4): 149. doi :10.1145/964723.383071.
2. 「ACM SIGCOMM Test of Time Paper Award」 。 2022年1月16日閲覧。
3. Stoica, I. ; Morris, R.; Liben-Nowell, D.; Karger, D.; Kaashoek, MF; Dabek, F.; Balakrishnan, H. (2001). Chord: インターネットアプリケーションのためのスケーラブルなピアツーピアルックアップサービス(PDF) (技術レポート). MIT LCS. MIT. 819. 2012年7月22日時点のオリジナル(PDF)からのアーカイブ。
4. Liben-Nowell, David; Balakrishnan, Hari; Karger, David (2002年7月). ピアツーピアシステムの進化の分析(PDF) . PODC '02: Proceedings of the sixth annual symposium on Principles of distributed computing. pp.  233– 242. doi :10.1145/571825.571863.
5. Stoica, I. ; Morris, R. ; Liben-Nowell, D. ; Karger, D. ; Kaashoek, MF ; Dabek, F. ; Balakrishnan, H. (2003年2月25日). 「Chord: インターネットアプリケーションのためのスケーラブルなピアツーピアルックアッププロトコル」. IEEE/ACM Transactions on Networking . 11 (1): 17– 32. Bibcode :2003ITNet..11...17S. doi :10.1109/TNET.2002.808407. S2CID  221276912.
6. Zave, Pamela (2012). 「軽量モデリングを用いたコードの理解」(PDF) . ACM SIGCOMM Computer Communication Review . 42 (2): 49– 57. doi :10.1145/2185376.2185383. S2CID  11727788.
7. Zave, Pamela (2017). 「識別子空間に関する推論：Chordを正しく動作させる方法」（PDF） . IEEE Transactions on Software Engineering . 43 (12): 1144– 1156. arXiv : 1610.01140 . Bibcode :2017ITSEn..43.1144Z. doi :10.1109/TSE.2017.2655056.
8. Labbai, Peer Meera (2016年秋). 「T2WSN: 無線センサーネットワークの堅牢性と配信率を高める2層コードオーバーレイ」(PDF) .理論・応用情報技術ジャーナル. 91 : 168–176 .

外部リンク

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Chord_(peer-to-peer)&oldid=1317499516"