« 分散ハッシュ(DHT)入門~その2 | トップページ | [ヴァイオリン]ヴィヴァルディの四季 »

2005.01.27

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

前回は教育用に「あいうえおDHT」というものを導入して、各ノードが決められた範囲のデータを管理することを説明した。

さて、「あいうえおDHT」ではなにが問題なのだろうか?考えてみよう。

「あいうえお」ということは少なくともノードが数10個あれば「あいうえお」で書かれているデータは全て分散管理ができる。

ところで、「あ」で始まるファイル名と「ぬ」で始まるファイル名はどちらの方が多いだろうか?一般的には明らかに「あ」の方が管理しているデータ量が多いはずだ。つまり「あいうえおDHT」では各ノードによってデータの保持している量にばらつきがあって、不公平感があるのだ。つまりノード「あ」とノード「ぬ」では負荷にかなりの違いがある。

もうひとつ問題がある。それはノードの数に拡張性が無い事だ。「あいうえお」は50音だから50個あるわけなので、「あいうえおDHT」では50個ノードがあればデータは管理できる。しかし、ノードが1000個あった場合どうだろうか?
「あいうえお」は50個しかないので、「あいうえおDHT」ではノード数50を超えるノードはデータを管理しなくも良い、というかこの方法では管理できない。なんらかの改良をしなければならない。

このように「あいうえおDHT」では直感的であるのだが上記のような2つの欠点があった。それを解決するのがハッシュ関数だ。

一般にハッシュ関数をfとするとxとyが違えばf(x),f(y)は異なる。もうちょっと言うとxとyが「ほとんど同じ」であってもf(x),f(y)は「全く異なる」。そして、一般に集合Xに対して集合F=f(x)はほぼランダムな要素となる。つまり、xがどんな要素であっても、それが一杯集まって全体要素をハッシュ関数にかけるとその結果はバラバラな集合のように見えるのだ。ちなみにハッシュ関数の出力する値を一般にハッシュ値と呼ぶ。

そのため、先ほど「あいうえおDHT」の欠点であるノード間の不公平な負荷は解消される。
つまり、今、「モナリザ」という名前のデータを管理したいとすれば、x=f(モナリザ)となるxを管理するノードにデータを渡せばよい。

ちょっと例を考えてみよう。今、「モーニング娘。」と「モーニング娘?」と「モーニング娘!」という3つのデータを管理したいとする。ちなみに「あいうえおDHT」なら、もうお分かりの通りノード「も」が全てデータを管理するはずだ。

今、ハッシュ関数をfとし、ハッシュ値が6桁の10進数としよう。すると、

X1=f(モーニング娘。)=301924
X2=f(モーニング娘?)=985820
X3=f(モーニング娘!)=549137

のように関数にかける元、つまり入力が非常に似通っても、出力、すなわちハッシュ値は全く別になる。この結果よりノード「301924」であれば「モーニング娘。」、ノード「985820」であれば「モーニング娘?」、ノード「549137」であれば「モーニング娘!」と言うデータを管理することができる。つまり、例えデータのファイル名などに偏りがあったとしても、そのハッシュ値を使って管理すれば、その偏りはなくす事が出来る、結果的にノードによって保持するデータ件数に偏りが無くなる。これがハッシュ関数を導入した訳である。

もし、ある人が「モーニング娘。」のデータを登録したければ、ノード「301924」にデータを登録すれば良い。
逆に「モーニング娘。」のデータが欲しければノード「301924」にデータを参照すれば良い。これは一般のDHTと同じ考え方だ。

また、ハッシュ値を大きくすれば多くのノードが参加してもうまく負荷分散することがわかるだろう。「あいうえおDHT」では50個までのノードしか上手く機能しないが、今6桁の10進数を出力するハッシュ関数を使えば、10万ノードまでうまく負荷分散ができる。

ちなみにハッシュ関数としてはSHA-1をよく使うが、これは0~数10億までハッシュ値が存在する。つまり数10億ノードが参加しても大丈夫!ということだ。これがDHTでは非常に多くのノードの参加が可能である理由のひとつとなる。

最後にハッシュ関数を使ってハッシュ値を求めるには非常に高速でできることを付け加えておこう。

ハッシュ関数を使うと、各ノード毎にデータ量・件数を公平に管理でき、また非常の多くのノードが参加するDHTが作れる事を説明した。ただし、「あいうえおDHT」については直感的で説明しやすいので今後も何度も登場する。

次回は「あいうえおDHT」と使って、ノードが管理するデータの範囲について説明する。
例えば、「あいうえおDHT」でノードが10個しかなければ各ノードはどのようなデータを管理すれば良いのだろうか?
もちろん、50個あれば、ひとつの文字をひとつのノードが管理すれば良いのだが。
ちょっと考えて見て下さい。

|

« 分散ハッシュ(DHT)入門~その2 | トップページ | [ヴァイオリン]ヴィヴァルディの四季 »

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

コメント

分散ハッシュの前にハッシュテーブルの説明が必要ではないでしょうか。
ハッシュテーブルをうまくネットワークに載せたものがDHTなわけで。

投稿: | 2005.01.28 00:54

この記事へのコメントは終了しました。

トラックバック


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

« 分散ハッシュ(DHT)入門~その2 | トップページ | [ヴァイオリン]ヴィヴァルディの四季 »