[P2P]分散ハッシュ（DHT)入門～その４

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

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

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

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

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

ということができる。

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

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

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

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

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

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

ハッシュ値　　　ハッシュに対応したデータ
０　　　ドラえもん
１　　　ワンピース
２　　　ドラゴンボール
３　　　こち亀
４　　　島耕作
５　　　マリア様がみてる
６　　　ジパング

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

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

　　０　　　　ドラえもん
　　１　　　　ワンピース

ノード「２」のハッシュテーブル
　　
　　２　　　　ドラゴンボール
　　３　　　　こち亀
　　４　　　　島耕作

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

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

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

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

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