分散ハッシュ(DHT)入門~その6
さて、前回はDHTでのルーティングについて説明した。今回はノードがDHTに参加する場合、どうすれば良いのか説明したい。
「あいうえお」DHTで説明しよう。
このときに、ルーティングの方法は前回説明したルーティング3を用いる事にする。
つまり、
ルーティング3:
◇各ノードは各行の先頭ノードを知っている。また、各ノードは隣あうノードを知っている。
これはノード「う」であれば、
・各行の先頭ノード:ノード「あ」、ノード「か」、ノード「さ」.....ノード「わ」
・自分と隣あうノード:ノード「い」、ノード「え」
を知っている事を意味する。
単純な例を説明するため「あいうえお」DHTでノード「う」だけが現在なく、そこにノード「う」が参加することを考えてみよう。
まず、これからDHTに参加するノード「う」は、既にDHTに参加しているノードの一つを少なくとも知っている必要がある。今そのノードをノード「や」としよう。
手順1:
ノード「う」は自分がノード「う」として振舞うためにはノード「い」とノード「え」に対して自分の存在を知らせる必要がある。そのため、まずノード「う」はノード「や」を通して、ルーティング3を使ってノード「い」とノード「え」のIPアドレスを知る。
手順2:
ノード「う」はノード「い」に対して自分の存在を知らせたい。
ノード「い」に対してノード「う」は自分がノード「う」である事を表明し、また自分のIPアドレスを教える。このコマンドを例えば
Join(ノード「う」⇒ノード「い」)
と定義しよう。
ノード「い」のルーティングテーブルは、隣り合うノードの部分についてはノード「あ」とノード「え」であったが、
これが、ノード「あ」とノード「い」に変更する必要がある。
このコマンドをRoutingTable(ノード「い」、NextNode、ノード「う」)としよう。
手順3:
ノード「う」はノード「え」に対して自分の存在を知らせたい。
ノード「え」に対してノード「う」は自分がノード「う」である事を表明し、また自分のIPアドレスを教える。
つまり、Join(ノード「う」⇒ノード「え」)
ノード「え」のルーティングテーブルは、隣り合うノードの部分についてはノード「い」とノード「お」であったが、
これが、ノード「う」とノード「お」に変更する必要がある。
このコマンドをRoutingTable(ノード「え」、FrontNode、ノード「う」)としよう。
手順4:
ノード「う」はまだルーティングテーブルを完全には構築していない。
すなわち、各行の先頭ノードを知っていない。(例えば、ノード「あ」、ノード「か」、ノード「さ」.......)そのため、
ノード「え」に対して、各先頭ノードのIPアドレスを教えて欲しいと要請する。
つまり、
RoutingTableKnown(ノード「う」、ノード「え」、各行の先頭ノード)
となる。
手順5:
各ノードは全てのルーティングテーブルに入っているノードに対して定期的にping等をしてノードが生きているかどうか調べる。
これでノード「う」がDHTに参加することができるようになった。
ところで、DHTではJoinやRoutingTable,RoutingTableKnownの方法については色々と工夫が施され、バラエティに富んでいる。
ただ、いずれにせよDHTのあるノードに対して自分の存在を知らせ、また自分に必要なルーティングテーブルを他の構成することはほぼ共通事項である。
実はこれだけではノード「う」はDHTに参加した事にならない。というのは、ノード「う」が居ない状態では、ノード「い」が頭文字が「う」で始まるデータを管理していたからである。
ということで、
手順6:ノード「い」からノード「う」が管理すべきデータを引き継ぐ
という処理を行う必要がある。
これでノードの参加処理は全て完了である。
次回はDHTからのノードの離脱とそれに対する工夫について説明したい。
| 固定リンク
「パソコン・インターネット」カテゴリの記事
- iPhoneのスクリーンショットを自動的にメールに投稿するテクニック[IFTTT](2014.11.23)
- WebRTC研究会開催のお知らせ(2014年12月開催予定)(2014.08.24)
- 「Gunosyオフィスツアー」を振り返る〜世界一のニュースアプリを目指すために(2014.06.01)
- Gunosyオフィスツアーの参加者募集を開始しました!(5月9日[金]開催)(2014.04.29)
- 第4回Twitter研究会(5/18[土])の講演スケジュール(2013.05.10)
この記事へのコメントは終了しました。
コメント