Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications (2001)
November 23, 2023\(N\)個のノードからなるChordのクラスタは、キーによるノードの問い合せに、\(O(\log N)\)のノードを介して応答できるPeer-to-peerのプロトコルである。 Consistent Hashingを応用しており、\(2^{m-1}+1\)以上\(2^m\)以下のノードが参加するconsistent hashingクラスタは、\(\mod(2^m)\)の非負の整数をIDとしてキーとノードを管理し、IDの空間上で隣接するノードにキーをわりあてる。 Consistent hashingはキーをほぼ均等に配置でき、ノードの参加、離脱時に移動すべきキー数は\(O(1/N)\)に収まる。
参加、離脱するノードと隣接するノード間でのみキーの移動が生じる。 Chordは、多くのノードが参加できるように、各ノードにもたせるルーティング情報を\(m\)個のほかのノードのみに限定する。 クライアントや別のノードからキーを受信したノードは、ルーティング情報にあるノードと自分のID \(\textit{n}\)をキー\(\textit{key}\)と比較する。 このとき、\(\textit{key} + x \equiv n_i\mod 2^m\)をみたす最小の非負の整数\(x\)に対応する\(n_i\)が自分のIDであれば、そのノードがキーに対応する。 それ以外の場合は、最小の値になるIDをもつノードにキーを転送する。
Consistent Hashingにおけるキーは\(m\)ビットのデータである。 SHA-1をノードのIPアドレスやキーに対応するデータに適用すれば、IDやキーを生成できる。
ノードがもつルーティング情報は、finger tableといい、\(m\)個のエントリからなる。 IDが\(n\)のノードは、\(k\)番目のエントリに、\(n+2^{k-1} \mod 2^m\)から値を増やして最初に見つかるノードのIPアドレスを保存する。 \(1\le k\le m\)であり、とくに\(k=1\)に対応するノードは\(\textit{successror}\)ともよばれる。 また、finger tableだけでなく、ノード \(n\)は一つの前にあるノードのIPアドレスも管理し、それを\(\textit{predecessor}\)としてあつかう。
これからChordに参加するノードは参加済のノードのIPアドレスをすくなくとも1つ知っておかねばならない。
以下の疑似コードは、論文中から引用であり、これから参加するノード\(n\)が参加済のノード\(n’\)を介してプロシージャn.join(n')でChordに参加する手続きを示す。
// ask node n to find id's successor.
n.find_successor(id)
n' = find_predecessor(id);
return n'.successor;
// ask node n to find id's predecessor
n.find_predecessor(id)
n' = n;
while (id not in (n', n'.successor])
n' = n'.closest_preceding_finger(id);
return n';
// return closest finger preceding id
n.closest_preceding_finger(id)
for i = m downto 1
if (finger[i].node in (n,id))
return finger[i].node;
return n;
// node n joins the network;
// n' is an arbitrary node in the network
n.join(n')
predecessor = nil
successor = n'.find_successor(n);
n.stabilize()
x = successor.predecessor;
if (x in (n, successor))
successor = n;
successor.notify(n);
// n' thinks it might be our predecessor.
n.notify(n')
if (predecessor is nil or n' in (predecessor, n))
predecessor = n';
// periodically refresh finger table entries.
n.fix_fingers()
i = random index > into finger[];
finger[i].node = find_successor(finger[i].start);
ノードは定期的にn.stabilizeとn.fix_fingersを実行し、あたらしく参加、離脱したノードをfinger tableに反映する。
ただし、Chordが複数のChordに分裂してしまった場合には、プロシージャは正しく機能しない。
また、Chordが分裂する条件については論文中では明らかにされていない。