« [ヴァイオリン]タルティーニのソナタ | トップページ | [IT]NET&COMに行ってきました »

2005.02.01

[P2P]分散ハッシュ(DHT)入門~その4

前回はDHTとしてハッシュ関数を使う理由を書いてみた。
今回はノード数とハッシュ空間の大きさ、そして分散ハッシュの本質について書いていきたい。

まず、いつものように「あいうおえおDHT」を考えてみよう。「あいうえお」は50音だから、ノードが50個あれば丁度一つの文字に対して一つのノードが対応するわけである。では、ノードが20個ならばそれぞれのノードはどのように管理すれば良いのだろうか?

今、「か」~「さ」行を考えてみよう。「か」行にはノード「か」、ノード「く」、ノード「け」、ノード「す」の4つがあったとする。
それぞれのノードはどの文字を管理すれば良いのだろうか?

このルールは「あいうえおDHT」を作った人にまかされているのだが、例えば次のノードの直前までの文字まで管理すると言うルールにしよう。そうすると、

・ノード「か」は「か」と「き」が始めの文字列のデータを管理する
・ノード「く」は「く」が始めの文字列のデータを管理する
・ノード「け」は「け」、「こ」、「さ」、「し」が始めの文字列のデータを管理する

ということができる。

このように、全てのノードは自分が管理するデータをノード数に応じて「動的に」変化することができる。これはDHTの全てに当てはまる基本だ。
DHTでは、ノードが本来割り当てられているハッシュ値だけでなく、DHTのルールに応じてその付近のデータも管理することになる。そのルールはDHT毎に異なる。

(※ちなみに先ほどの「あいうえお」DHTのルールである次のノードの直前(つまり次のノードのハッシュ値の1つ前)まで管理する方法は実はDHTの代表格「Chord」と全く同じである。)

では話を抽象化してハッシュ空間で考えてみよう。

今、ハッシュ関数Fが0~6までのハッシュ値を取るとする。

◇ノード数が1の場合、そのノードは全てのデータを管理する事になる。
この時全てのデータに関してハッシュ値とそれに対応されたデータの表が一つできるはずである。
このようなデータとハッシュ値を対応した表を「ハッシュテーブル」と呼ぶ事にしよう。
なお、テーブルとは英語で「表」を表わす。

コミックを例に取るとハッシュテーブルとはこんな感じの表になる。

ハッシュ値   ハッシュに対応したデータ
0   ドラえもん
1   ワンピース
2   ドラゴンボール
3   こち亀
4   島耕作
5   マリア様がみてる
6   ジパング

では、ノード数が2の場合にはどうなるのであろうか?
例えば、ノード「0」とノード「2」、ノード「5」の3つのノードが存在する場合にはそれぞれが保持するハッシュテーブルは以下の通りになる。

ノード「0」のハッシュテーブル

  0    ドラえもん
  1    ワンピース

ノード「2」のハッシュテーブル
  
  2    ドラゴンボール
  3    こち亀
  4    島耕作

ノード「5」のハッシュテーブル
  
  5    マリア様がみてる
  6    ジパング

このように「ハッシュテーブル」が各ノードに分散して配置される事になる事が分かるだろう。この技術が
「分散ハッシュテーブル」すなわちDHTと呼ばれることになる。
ようやく語源の理由まで説明する事ができることになった。

今のようにすれば、例えばハッシュ空間が非常に巨大になってノードが数億参加しても同じようなルールで各ノードが分散してハッシューテーブルを持つことになる。

既にピンと来ている人がいると思うが、例えばワンピースのデータが欲しければノード「0」、ジパングのデータがほしければ「ノード5」に問い合わせをすればよい。

ところで、ノード「0」や「ノード5」のノードと通信するにはどうすれば良いのだろうか?全てのノードのIPアドレスを集中管理をするのは大変だ。そこで、ルーティングと言う手段を使って巧妙にこのことを解決している。
次回は「あいうえおDHT」を使ってDHTのルーティングについて触れてみたいと思う。


|

« [ヴァイオリン]タルティーニのソナタ | トップページ | [IT]NET&COMに行ってきました »

パソコン・インターネット」カテゴリの記事

コメント

回答ありがとうございました。勉強になりました。

投稿: KIyoshi | 2005.02.10 11:45

>DHTのDとTは何の略ですか
DHT(Distributed Hash Tables)
です。まさに分散・ハッシュ・表
ですね。

投稿: Tomo | 2005.02.06 21:00

DHTのDとTは何の略ですか。

投稿: Kiyoshi | 2005.02.06 13:27

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/18781/2764190

この記事へのトラックバック一覧です: [P2P]分散ハッシュ(DHT)入門~その4:

» [program][p2p]分散ハッシュテーブル(DHT) [NIES - 白線オール]
という技術があるらしい。P2Pノードを、効率よく管理する技術で、ネットワーク負荷を抑え、理論上数億ノードの参加が可能で、その全てと通信が可能になり、しかもノード... [続きを読む]

受信: 2005.02.02 09:31

« [ヴァイオリン]タルティーニのソナタ | トップページ | [IT]NET&COMに行ってきました »