f99aq8ove's blog

DHT ショートクイズに挑戦

tag: DHT and P2P
21 November 2005

このエントリは 2005-11-21 に書かれました。 内容が古くなっていたり、もはや正しくないこともありますので、十分検証を行ってください。

Tomo’s HotLine: [P2P]DHT(分散ハッシュテーブル)ショートクイズ に挑戦してみた、けど…。

クイズ1:

DHT(分散ハッシュ)でハッシュ関数hash_Aを使用していた。しかし、ハッシュ関数hash_Aが不完全で、異なる数字y,zに対してhash_A(y)=hash_A(z)になる場合があることがわかった。この時にDHT系全体としてどのような問題が生ずるだろうか?

ハッシュ関数hash_A が不完全であるという前提でシステムを構築していない場合、DHT に登録するデータに付与する 一意 な ID として dataID = hash_A(data) を用いている可能性がある。

dataID = hash_A(y) = hash_A(z) が付与されたデータを管理するノードB, C があるとする。ノードB, C には既に数字y を登録しているものとする。いま、ノードB に数字z を登録すると、dataID が同じであるためノードB に既に登録されている数字y は上書きされて消えてしまう(上書きを許さない設計なら数字z は DHT に登録できませんね)。また、この状態で DHT から dataID をもとにデータの取得を行うと、ノードB, C がそれぞれ異なる数字を返すことになる。

クイズ2:

ノードAの名前をA_nameとする。ノードAの保持するハッシュ値(hash_IDとしよう)を完全なハッシュ関数hash()を使って

hash_ID=hash(name)

で定義する時、しばしばDHT系として不具合が生じる可能性がある。それはどうしてか?またそれを回避する方法を考えて下さい。ただし、回避方法としてなるべくnameを活用して欲しい。

ここで言う完全なハッシュ関数とは異なる数字y,zの時にhash(y)とhash(z)が異なる事を指す。

DHT にデータを登録していくにあたって、最良の場合でも登録可能なデータ数はノード数を超えることが出来なくなる(ってことですか? わかりません orz)。hash() は完全なハッシュ関数であるから、ノードA が保持する hash_ID は唯一のものである。これから、ノードAは唯一の hash_ID を生成するデータ、A_name しか保持できない(あれれ、問題ではそこまで言ってない…)。

はい、わかりませーん…。

もしかして、hash_ID = hash(name + rand()) ってこt、、、それでもハッシュ関数が完全かどうかは関係ありませんね…。

これは、やはりチラシの裏に留めておくべきでしたか、いろんな意味で。どう見ても勉強不足です。本当にありがとうございました。

Related Posts