Chord

Chordは、分散ハッシュテーブルを実現するアルゴリズムの一つ。P2P ネットワークにおいて、サーバを用いることなく高速にコンテンツの検索、ルーティングを行う手法。

[編集] アルゴリズム

Chordでは、コンテンツのハッシュ値を求める関数にSHA-1を採用するのが一般的である。ネットワークに参加するノードは、SHA-1のハッシュ値の値域 $0 \le NodeID \le 2^{160}-1$ を満たす一意な $N o d e I D$ が割り当てられる。

ここで、 $n e x t (x)$ という関数を定義する。この関数は、ハッシュ値 $x$ が与えられたとき、値を増加させる方向で次に存在しているノードの $N o d e I D$ を返す。なお、 $2160 - 1$ と $0$ は接続されていると考える。

ネットワークで情報を共有する際には、共有したい情報のハッシュ値を $x$ として $N o d e I D = n e x t (x)$ を満たす $N o d e I D$ を持つノードが、実際に情報を保持しているノードの位置を示すIPアドレス等の情報を保持する。

また、ネットワークに参加するノードは、自身の $N o d e I D$ を $M y N o d e I D$ とした場合、

$n e x t (Z)$ , ただし $Z=MyNodeID+2^{i}mod2^{160}(0 \le i < 160)$

の $N o d e I D$ をもつノードのIPアドレスをルーティングテーブルとして保持する。

共有されている情報を検索する際には、検索したい情報のハッシュ値を $y$ としたとき、 $N o d e I D$ として $n e x t (y)$ が割り当てられているノードを各ノードのルーティングテーブルを利用して検索することになる。

Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan (2001). “Chord: A scalable peer-to-peer lookup service for internet applications”. ACM SIGCOMM Computer Communication Review 31 (4): 149 - 160. New York, NY, USA: ACM Press. DOI: 10.1145/964723.383071.