Tomo’s HotLine

前回はDHTにノードが参加する場合にどのようにすれば良いのか説明した。今回はノードがDHTから離脱する場合の処理について書きたい。

「あいうえお」DHTで、ノード「う」がDHTに参加する場合、隣接しているノード、すなわちノード「い」とノード「え」に自分の存在を知らせれば良かった。そして、ノード「う」が管理すべき情報をノード「い」から引継ぎする事も必要である。

そうなると離脱する場合には同じように隣接するノード、つまりノード「い」とノード「え」にノード「う」が離脱するよ、と事前に連絡すれば良いことになる。

具体的には、
１.ノード「い」に対してノード「う」が離脱することを伝える。このときに、ノード「い」の隣接ノードがノード「え」になることを確認する。
２.ノード「え」に対してノード「う」が離脱する事を伝える。このときに、ノード「え」の隣接ノードがノード「い」になることを確認する。

これでルーティングテーブルについては受け渡しが完了した訳だが、肝心のノード「う」が持っているデータを受け渡すことを忘れている。ということで、
３.ノード「い」に対してノード「う」のデータを受け渡しする。（なぜなら、ノード「い」は「い」「う」のデータを管理するようなルールにしたから。）

と言う処理を忘れてはならない。

これでメデタシメデタシ。。と言いたい事だが、残念ながらそういうわけにはいかない。
というのは、今の離脱の処理はノードが前もって離脱する意志があって、事前に離脱処理を出来た場合に相当する。実際にはネットワークやノードの関係で急にノードが離脱する可能性もある。（例えばPCの電源断、ルータの故障など）そういう場合にはこのような処理をする事が出来ない。

ということは、ノードが急に離脱してもDHTがうまく働く処理をしないといけない。これがDHTの実装での難関の一つである。ではどのようにすれば良いのだろうか？

例えば、今ノード「う」が急に抜けたとする。その時に隣接ノード、ノード「い」ノード「え」は定期的に自分のルーティングテーブルのノードにpingなどの試験を行って相手のノードの確認をすれば、ノード「う」が急に居なくなってもルーティングテーブルの更新については対応できそうだ。つまり、先ほどの１、２の処理はなんとかなりそうな気がする。

とはいえ、３の処理であるノード「う」が持っているデータを他のノードが引き継ぐのはとても大変そうである。
そこで一工夫する。

今、各ノードの保持しているデータは、隣接ノードにも絶えずコピー（正確には同期）することとしよう。
例えば、ノード「う」はノード「い」とノード「え」にも同じデータのコピーを持っているとする。
すると、例えノード「う」が居なくなっても、そのノード「う」のデータはノード「い」とノード「え」にあるので、データ自体は消去されないということになる。後はルーティングテーブルが復旧すれば、ノード「う」にあったデータはノード「い」でアクセスする事が出来るようになる。

実際のDHTではこのコピーを色々なノードにコピーする事によって、同時に複数のノードがDHTから離脱しても問題なく作動するように設計されている。

分散ハッシュ（DHT）入門その２～その７で簡単にDHTの仕組みについて説明してみた。
Blogに絵がないので少し説明が分かりにくかったかもしれないが、本内容は第２回P2P勉強会で講演する予定なので後日プレゼン資料を作成する。資料が出来次第、ご紹介する予定である。

次回は分散ハッシュ（DHT）入門の最終回。DHTの応用と未来について書いていきたい。