[P2P][DHT]Pastry入門～その１

今回から数回に渡りＤＨＴでとても有名な方法である「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と並んで著名なＤＨＴシステムです。
ChordがSkiplistと呼ばれるショートカット的なアプローチをするのに対してPastryはPlaxtonアルゴリズムを使って特定のノードへすばやく到達できるように工夫しています。なおＴａｐｅｓｔｒｙもPlaxtonアルゴリズムを使っているのでPastryをチェックした後にTapestryの論文を読むと理解が深まるでしょう。

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

Pastryのノード検索の仕方

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

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

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

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

まずＩD_A=193245は自分の知っているノードでID=2xxxxxと言うノードを探します。(xは任意の数字）つまり、ID_Aのノードの中でID_Zの「一番上の数字」が同じノードを探すのです。
今、ID_AがID_B1=282539を知っていたとします。すると今度はID_B1がID=23xxxxとなるノードを探す事になります。
これは、ＩＤ_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に近づくようにＩＤの数字を上記方法で近づけていく。
(STEP2)ある程度目的ノードに近づいたら、自分の近くのノードの場所を記憶している表(これをLeaf setと呼ぶ）を使って、目的ノードに近いノードへジャンプする。

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

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