« [P2P]P2P新年会無事終了! | トップページ | [P2P]P2Pインフラ研究会~「Winnyの技術」著者 金子勇氏講演 ~その1 »

2006.01.22

[P2P][DHT]Pastry入門~その1

今回から数回に渡りDHTでとても有名な方法である「Pastry」について紹介します。
なるべく分かりやすく書くために、部分的には不適切な記述があるかもしれません。そのため、詳細については原論文を見ると良いでしょう。

原論文
Pastry:Scalable,decentralized lbject location and routing for large-scale peer-to-peer systems
http://research.microsoft.com/~antr/PAST/pastry.pdf

Pastryと何か?

PastryはChordやKademliaと並んで著名なDHTシステムです。
ChordがSkiplistと呼ばれるショートカット的なアプローチをするのに対してPastryはPlaxtonアルゴリズムを使って特定のノードへすばやく到達できるように工夫しています。なおTapestryもPlaxtonアルゴリズムを使っているのでPastryをチェックした後にTapestryの論文を読むと理解が深まるでしょう。

Pastryを使ってPAST(分散ストレージ)等のアプリケーションが考えられています。詳細は下記のページをご覧下さい。
http://research.microsoft.com/~antr/Pastry/default.htm

Pastryのノード検索の仕方

DHTで一番重要なのはノードの検索の方法です。どのような方法なのか、ざっくり書いてみます。
ルーティングテーブル等の詳細は後日紹介します。

Pastryでは2のN乗でルーティングテーブルを構築し検索を行います。しかし、これだと分かりにくいので、とりあえず10進法にして「イメージ」を掴んで下さい。

今、ID_A=19325というノードがあります。これがID_Z=233521と通信するにはどうすればよいのでしょうか?

Plaxtonアルゴリズムはとてもユニークな方法でこの通信を可能にします。

まずID_A=193245は自分の知っているノードでID=2xxxxxと言うノードを探します。(xは任意の数字)つまり、ID_Aのノードの中でID_Zの「一番上の数字」が同じノードを探すのです。
今、ID_AがID_B1=282539を知っていたとします。すると今度はID_B1がID=23xxxxとなるノードを探す事になります。
これは、ID_Zで「一番上と2番目が同じ数字」のノードを探す事になります。

つまり、
(1回目の検索)ID_B1=2xxxxx (例えば214256)
(2回目の検索)ID_B2=23xxxx  (例えば234623)
(3回目の検索)ID_B3=233xxx  (例えば233901)
(4回目の検索)ID_B4=2335xx  (例えば233591)
(5回目の検索)ID_B5=23352x  (例えば233527)
(6回目の検索)ID_B6=233521=ID_Z
ということで、IDの桁数と同じ数で検索が可能でした。ですから、Pastryも大体Log(N)のオーダーで検索が可能である事が分かります。

しかしながら、今回のように6回でうまく検索できるとは限りません。Pastryは色々な工夫をしていて、できるだけ早く目的のノードへ到達しようと努力します。

ざっくりとルーティングの方法を書くと
(STEP1)目的のノードのIDに近づくようにIDの数字を上記方法で近づけていく。
(STEP2)ある程度目的ノードに近づいたら、自分の近くのノードの場所を記憶している表(これをLeaf setと呼ぶ)を使って、目的ノードに近いノードへジャンプする。

の2種類でどんどん目的ノードへ近づくことになります。

次回はルーティングテーブル等を実際見ながら、どのような方法でルーティングが行われているか見てみましょう。

|

« [P2P]P2P新年会無事終了! | トップページ | [P2P]P2Pインフラ研究会~「Winnyの技術」著者 金子勇氏講演 ~その1 »

P2P」カテゴリの記事

コメント

コメントを書く



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


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



トラックバック

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

この記事へのトラックバック一覧です: [P2P][DHT]Pastry入門~その1:

« [P2P]P2P新年会無事終了! | トップページ | [P2P]P2Pインフラ研究会~「Winnyの技術」著者 金子勇氏講演 ~その1 »