AChord 2

P2P

といいつつちょっとだけ続きを。。

次はSuccessorリストとPredecessorリストについて説明します。
通常Chordではスキップリストと呼ばれる2^iごとのノードを管理した
フィンガーテーブルという情報を管理していますが、この他にもいくつかのリストを管理しています。
そのひとつにSuccessorリストとPredecessorリストというのがあります。
Successorはあるハッシュ値を管理するノードという意味で使っていましたが
ネットワークに参加した後のことを考えてみると、自分のノードの次のノードにあたります。
逆にPredecessorというのは自分のノードの一つ手前のノードになりますね。
これを管理するということで、各ノードは自分の前後のノードとつながっていることになります。
　
何故前後のノードが必要かというのは、実際の運用を考えればわかります。
具体的には、ノードがネットワークから離脱する場合のことを想定してみます。
各ノードは自分の管理しているハッシュ値に対応するデータを保持していますから
離脱する前にあらかじめ今後そのデータを管理することになるSuccessorに知らせる必要があります。
つまり引き継ぎ作業が必要になってきます。
ところがここはネットワークです。怒った彼女がパソコンのコンセントを突然引き抜いたりすることもあるかも？
当然ネットワークは突然切れてしまいますから引継ぎが行えません。
そうなるとネットワークは一部のデータを失って壊れてしまうでしょう。
　
こういった事態に対応するために各ノードは前後ノードの情報をコピーして保持しています。
これによって例えばPredecessorが突然ネットワークから離脱しても対応できることになります。
ここでは前後１つのノードを考えていましたが、これを前後k個のノードに広げることで
さらにネットワークの環境を保全することができ、壊れる確立を1/kにまで下げてくれます。
そしてこの前後k個のSuccessorとPredecessorのリストがSuccessorリストとPredecessorリストとなります。