P2Pと分散ハッシュテーブル～その１

さて、P2Pでは最近「分散ハッシュテーブル」というキーワードをよく聞きます。分散ハッシュテーブルついては後で紹介しますが、これを用いるとルーティング、検索が高速に、しかもP2Pネットワーク全体に対して適用することができます。例えば既にeMuleと呼ばれるファイル共有システムでは分散ハッシュテーブルの一種であるkademliaが使われています。ではそもそも分散ハッシュテーブルとはどういうものなのでしょうか？それを説明するにはまず検索で使われるハッシュ法を説明する必要があります。

[お知らせ]分散ハッシュテーブル（ＤＨＴ）についてわかりやすく解説したページを作りました。ＤＨＴに興味のある方はまずこちらをご覧下さい。
分散ハッシュテーブル（ＤＨＴ）入門～その１
DHTの詳細については拙著「P2P教科書」をご覧下さい。

ハッシュ法

今、あるデータベースを考えてください。ここには人の名前と身長が書いてあるテーブルとしましょう。例えば

table_1={name,tall}=[｛佐藤,156},{田中,178},{伊藤,185},{村山,167}・・・]

というものがあったとします。このテーブルが大きければ「伊藤」という人の身長を見つけるにはデータベースのnameフィールドの文字を全てマッチングするか判断させる必要があります。これは計算を行うのに非常に負荷がかかります。

そこでハッシュ関数を使う事にします。ハッシュ関数hash()は一般に次のことが言えます。

A≠Bの時、hash(A)≠hash(B)

このハッシュ関数を使って、先ほどの名前のテーブルのところをhash(name)に置き換えましょう。すなわち、

table_2={hash(name),tall}=[{162706,156},{189029,178},{294678,185},{792356,167}・・・}

となります。ただし、今hash関数は6桁の数字を返す事と仮定しました。hash(name)で昇順でテーブルを配列しとけば、高速にある人の身長を検索することができます。これがハッシュ法です。

分散ハッシュテーブル

それでは今度は分散ハッシュテーブル（ＤＨＴ）についてです。先ほどの分散ハッシュテーブルを応用して、Napster のような中央サーバを使ってファイル共有をしようとしましょう。その時に必要なのは、コンテンツとそれを所有している端末のIPアドレスが必要です。例えば次のようなデータを中央サーバに格納する必要があるでしょう。

table_contents={contents_name,IP_adress}=[{桜,1.2.3.4},{もみじ,100.111.112.113},
{ふるさと,200.201.202.203}・・・]

そこで、先ほどのハッシュ法を使ってコンテンツを所有している人のIPアドレスが高速でわかるシステムを作りましょう。

table_hash={hash(contents_name),IP_adress}=[{162367,1.2.3.4),{582719,100.111.112.113},
{826781,200.201.202.203}・・・]

これで検索スピードは向上したことになります。ついでに言うと、中央サーバはどのようなコンテンツ流通がされているか把握することもできない匿名性の高いシステムになります。さて、このtable_hashをユーザに分割して所有させてみましょう。ユーザにテーブルを所有する方法、検索方法は次のとおり。

（１）ユーザはP2Pネットワークにはいるとき、ランダムなNode_IDを決定し保持します。Node_IDは端末毎にユニークなナンバーです。
（２）ユーザがコンテンツの名前がAというコンテンツを持っている場合、Node_ID=hash(A)であるノードに{hash(A),IP_Adress}を通知します。もしNode_ID=hash(A)となるノードがなければ、hash(A)に一番近いNode_IDであるノードが{hash(A),IP_Adress}を保持します。
（３）ユーザがコンテンツの名前がCというコンテンツが欲しい場合、Node_ID=hash(C)であるノードに問い合わせをすれば、それを所有しているノードのIPアドレスがわかります。

これが分散ハッシュテーブルの大枠です。このようにすれば、Napsterのような中央サーバが無くても高速にコンテンツを検索することができ、そのコンテンツを所有する人のIPアドレスを見つける事ができます。

では分散ハッシュテーブルをその方法から分類してみましょう。

Chord：円状スキップリスト
CAN：N次元トーラス
Kademlia,P-Grid:２分木
Tapestry,Pastry：Plaxtonアルゴリズム

分散ハッシュテーブル「CAN」

では、実際に分散ハッシュテーブルがどのように動作するのか、説明していきましょう。まずは直感的に説明しやすく、機構がシンプルなCANです。

CANでは分散ハッシュテーブルの空間としてN次元トーラスを使いますが、今回は簡単に説明するため、(1,0)×(0,1)の2次元正方形を分散ハッシュテーブルの空間とします。

まずノードを追加したときの分散ハッシュテーブル空間のエリアのカバーの仕方を説明しましょう。ネットワークに新たに参加するノードは乱数(rand_x,rand_y)を発生します。ただし、０＜rand_x,rand_y＜１です。これが先ほど述べたNode_ID=(Node_ID_x,Node_ID_y)=(rand_x,rand_y)とします。今、ハッシュ空間のエリアが下図のようになっているとします。☆印は各ノードのNode_IDを示しています。

今、新しくノードDがネットワークに参加する時、Node_ID=(0.8,0.8)としましょう。ノードDはノードのIPアドレスを事前に知っていたとします。するとまずノードDはノードBにNode_ID=(0.8,0.8)のエリアをカバーしているノードはだれか検索します。一般にCANではエリアが隣接しているノードのIPをお互いに知っています。ノードはノードCがNode_ID=(0.8,0.8)をカバーしている事を知ります。（※エリアにおけるもっと複雑な場合のノード検索については後述します。）その次にノードDはノードCに（Node_IDを含む）エリアを半分下さいと要求します。これでノードD は下図のようにノードCの元のエリアの半分をカバーすることになります。（このとき、渡したエリアのハッシュ空間もノードC⇒ノードDに渡す。）ノードCがノードDにエリアが委譲した後のハッシュ空間が次の図です。

ノードDがネットワークからいなくなる場合には、自分のエリアをノードCに返します。このとき、もちろん管理しているハッシュ空間もノードD⇒ノードCに渡します。（※ここではノード退出に対するこれ以上の説明は省略します。）

これでノードがハッシュ空間をどのようにカバーするかを説明しました。さて肝心のハッシュ関数を導入します。今ハッシュ関数を2つ用意し、これをhash_x(),hash_y()とします。ただし、0＜hash_x(),hash_y()＜1としましょう。まず、コンテンツの名前とIPアドレスの登録の仕方ですが、あるコンテンツの名前がAとすれば、(x,y)=(hash_x(A),hash_y(A))を含むエリアをカバーしているノードにハッシュ値とIPアドレスの情報を渡します。

では、具体的に検索の方法を説明します。下図を見て下さい。今A～Fのノードがいます。☆印は各ノードのNode_ID=(Node_ID_x,Node_ID_y)です。

ではノードAが「春が来た」と言うコンテンツを持つノードを検索する方法を書きます。

(1)まず、hash_x(春が来た）hash_y(春が来た）を計算する。ここでは(x,y)= (hash_x(春が来た）、hash_y(春が来た））＝(0.9,0.9)としよう。
(2)Aは(x,y)=(0.9,0.9)のハッシュ空間をカバーするノードを検索したい。しかしながら、CANでは隣接しているエリアのノードのIP情報しかしらない。 すなわち、AはBとCとDのIPアドレスを知っている。そこで、より(0.9,0.9)に近い Dへ検索を依頼する。
(3)DはA,C,E,FのIPアドレスを知っている。(0.9,0.9)に近いFに検索を渡す。
(4)Fは自分がカバーしているエリアに(0.9,0.9)があるので、{0.9,0.9,IP_adress}というテーブルから、「春よ来い」というIPアドレス（ここではノードBとする）をDに返す
(5)Dは検索結果をAに返す。
(6)Aは検索結果からノードBとP2P通信を行い、「春よ来い」というコンテンツを入手する。

これが一連の流れです。今の流れを図示したのが次の図です。

これで、CANの概要は説明しました。

さて、CANを見ればわかるように、P2Pのネットワークに参加している全てのノードのコンテンツが高速に検索できることがわかるでしょう。Winnyやgnutellaではブロードキャストできる範囲でしかコンテンツが検索できず、さらに検索にかかる処理が重いことがあげられます。ここで分散ハッシュテーブルのメリットを書いておきましょう。

スケーラビリティが非常に良い。大規模ネットワークに向いている。
高速な検索、ルーティングが可能。
頻繁なノードの参加・離脱に対しても対応可能。
全てのノードのコンテンツ検索が可能。
負荷分散の効果がある。

このため、将来大規模なP2Pは分散ハッシュテーブルを適用する事がスタンダートになることが考えられます。

次に分散ハッシュテーブルで有名なChordの説明をします。

P2Pと分散ハッシュテーブル～その１

NEXT

TOPページに戻る