==============================================================
独自マークアップの定義
[*image*] : 画像の希望
[*table*] : 表の希望('|'が列区切り)
[*footnote*] : 脚注
[*refer*] : 別章への参照(岩田さんの記事に依存)
[*backnum*] : 過去の号に記事があれば参照を追加してほしい箇所
==============================================================
構成
- 探索技術の概要
- Gnutella探索の説明
- Freenet探索の説明
- Chord(DHT)探索の説明
- Kademlia(DHT)探索の説明
となっています。

分量が予定(4ページ)の倍近くあるので、適当に削ってください。
==============================================================


* P2Pの探索とは
探索技術は、P2Pの要素技術の中で最も注目に値する分野だ。
インターネットの動向を見ても、サーチエンジンに代表される全文検索機能、セマンティックWebに代表されるメタデータ検索、UDDI(Webサービス)に代表される広域サービス発見、UPnPやランデブーに代表される近距離サービス発見など、探索技術を広義に捉えると、活発な分野であることが分かる。

探索技術の評価基準は色々あるが、本記事では、スケーラビリティ、耐障害性、アドホック性という3点の評価基準に着目する。スケーラビリティの高さは、探索対象(コンテンツ)の数や探索クライアントの数に関して、規模に対していかに効率良く探索できるかの観点を見る。耐障害性の高さは、ネットワークやコンピュータの故障に対する耐性の観点を見る。アドホック性の高さは、いかに準備期間や設計期間が少ない状態で、いかに新しい(up-to-dateな)対象を探索可能か、という観点を見る。これらの評価基準をもとに、探索技術の概観とP2Pが求められる背景を説明する。

最も単純な構成 ([*footnote*]構成が単純であっても、運用や実装が容易とは限らない点に注意)は、単一のインデックスサーバを立てる構成だ。探索対象の情報を、必ず単一のインデックスサーバに登録する。各クライアントは、インデックスサーバに探索要求を出して探索結果を受ける。単一インデックスサーバ構成は、単一障害点を持つことと負荷が集中する欠点を持つ。
単一インデックスサーバが持つスケーラビリティの問題を解決する方法に、サーバの冗長化がある。一般に、ミラーリングやレプリケーションと呼ばれる複製機能で、同じ構成を持った複数のインデックスサーバを運用する。この構成は、負荷の集中と単一障害点の回避に有効に機能する。しかし、サーバ数のスケーラビリティを上げることは難しく、運用のノウハウや費用は高くつく。また、管理権限の分散性は低いままだ。この構成は、P2Pブームの先駆けとなったNapsterで使われた構成だ([*footnote*]この記事は、Napsterは転送技術にP2P技術を利用したが、探索技術にはP2P技術を使っていない、というスタンスに立っている)。
サーバ数のスケーラビリティと管理の分散性を高める方法として有効なのが、階層化構造だ。よく知られた例にDNSがある。DNSは、FQDNというホストの名前からIPアドレスというホストの位置情報をひく探索技術の一種だ([*footnote*]インターネットで最も成功した探索技術と言っていいだろう)([*backnum*]DNSの過去記事)。階層化したサーバによる探索のスケーラビリティは、一般に高い。階層構造を持った探索システムを作るためには、探索の名前空間(DNSで言えば FQDN)を階層化する設計が必要になる。このためアドホック性が高いとは言えない。階層のルートサーバに単一障害点がある問題や不均一な負荷の問題も残っている(DNSではルートサーバを複製することで単一障害点を回避している)。

階層構造サーバが持つ単一障害点の問題やアドホック性の欠如に対して、P2Pが適用可能だ。P2Pの各ノードは全体に関する特別な知識(階層構造など)を持たずに対称的に動作する。理論上、単一障害点が無くなる。全体に関する知識を持たないノードは、言い替えると、部分や近傍に関する知識だけで動作するノードだ。全体の整合性の同期を軽減できるので、アドホック性が高い。
P2P探索の最も単純な構成はフラッディングと呼ばれる構成だ。GnutellaやFreenetで使われている。フラッディング探索はアドホック性が高い。また探索対象の数に関するスケーラビリティも高い。しかし、後述するように、ノード数の増加に対してトラフィック量が増える欠陥を抱える。動作原理と具体例は後述する。
近年、P2P探索で注目されているのが、DHT(Distributed Hash Table:分散ハッシュテーブル)と呼ばれる技術だ。単一障害点の回避とスケーラビリティの高さに特徴がある。ハッシュという言葉が示唆するように、探索対象が一様にばらまかれる性質がある。このため、均一に近い負荷分散を得られる特性がある。研究段階の技術なので、現実的なアプリケーションへの適用への課題は残るが、興味深い技術だ。動作原理と具体例は後述する。


[*table*] 比較表
|区分|例|特長|主な問題点|
|単一インデックスサーバ|多くの初期的なインターネットサービス|構成が単純。管理が容易|単一障害点。負荷の集中|
|サーバの複製|Napster|単一障害点の回避。負荷分散|管理コストが高い。サーバ数のスケーラビリティが高くない|
|階層化サーバ|DNS,LDAP|スケーラビリティが高い。管理権限の委譲が可能|不均一な負荷集中。名前空間の設計が必要|
|P2Pフラッディング|Gnutella,Freenet|単一障害点の回避。アドホック性が高い|ノード数に対してトラフィック数が増大|
|DHT(分散ハッシュテーブル)|Chord,CAN,Pastry,Tapestry,Kademlia|単一障害点の回避。ノード数に対するスケーラビリティの高さ|現実的な適用(ノード離脱への耐性。下位ネットワーク層の考慮)が不透明|


* 本記事の注意点
探索技術を広義にとらえると、数ページでは説明が足りないほど広い範囲に渡ってしまう。本記事は、探索技術を次のように狭義に限定することで説明を簡略化する。

- 探索対象を(ファイル)コンテンツに限定
- コンテンツ名からコンテンツの位置(アドレス)の探索に限定
-- WebサーチエンジンやP2Pファイル共有アプリに代表される、キーワード検索や全文検索は扱わない
-- コンテンツの位置は、(P2Pがオーバーレイする)下位ネットワーク層のアドレスで示す([*refer*]第1章:P2P概論+基礎)。この記事は、 TCP/IPネットワーク上にオーバーレイすることを前提に、IPアドレスとポート番号の組で位置を記述する([*footnote*]理論的には、 DNS上にオーバーレイすればFQDNで位置が記述され、Web上にオーバーレイすればURLで位置が記述されるなど、が考えられる)。

更に、次のような省略と仮定を行う。
- 探索に関係しない通信プロトコルの説明を省略する。例えば、接続セッション確立プロトコルなどの説明は省略する。
- コンテンツの位置を発見した後のコンテンツ転送に関する説明は省略する。
- P2Pに参加する全ノードはグローバルIPを持っていると仮定する。NATやFireWallに関する技術も省略する([*refer*]第3章:NAT越えの技術)。
- 最初のノードを知る、いわゆるP2Pブートストラップ問題の説明を省略する([*footnote*]P2Pとは別の仕組み、例えば、DNS、Web、ディレクトリシステム、IPマルチキャストなどで最初に接続すべきノードの存在を知る。)
- その他、探索と直接関係しない要素(セキュリティ、冗長性の確保、キャッシュなど)の説明は省略する。

以下の説明で、探索コマンドのリクエストをlookupと呼び、探索結果のレスポンスをhitと呼ぶ。前者をqueryと呼ぶシステムも多いが、この記事はlookupに統一する。


* Gnutellaの探索
P2Pフラッディング探索技術の具体例として、Gnutellaの探索の説明をする。

Gnutella のコンテンツ探索は、コンテンツ保有ノード(ローカルディスクに探索対象のコンテンツを保有するノード)によるネットワーク形成(オーバーレイネットワーク)を前提とする。具体的には、各ノードが近接ノードへの経路を保持することを意味する。経路の保持とは、(アプリ層の)コマンドを転送できることを意味する。ここでは、他ノードへの経路を保持した状態を、そのノードとセッションを確立した、と表現する([*footnote*]一般にGnutellaは TCPで実装されるので、この文脈のセッションは、TCPのセッションと等価になる。しかし、概念的にはアプリ層のセッションであり、TCPセッションとは独立したものであることに注意)。
このネットワーク上を、コンテンツ名を含むlookupコマンドがバケツリレーのようにノード間で転送される。

具体的に説明してみよう。
ユーザが、ローカルディスクに無いコンテンツの探索を開始したとする。ユーザのPC(探索開始ノード)は、既に1つ以上のノードとセッションを確立しているとする。これらのノードを近接ノードと呼ぶ。探索開始ノードは、全ての近接ノードにlookupコマンドを転送する。lookupを受信した近接ノードは、各々のローカルディスクでコンテンツを探す。ここでは説明のために、どの近接ノードも探索対象のコンテンツを持っていなかったとする。近接ノードは、それぞれが独自に近接ノードを持っている(その内のひとつは、探索開始ノードだ)。探索開始ノードを除く近接ノードにlookupコマンドを転送する。この転送を繰り返すことで(コマンド伝播)、コンテンツ保有ノードまでlookupコマンドが到達する。コンテンツ保有ノードは、lookupの伝播をする代わりにhitを返す。hitはlookupコマンドが来た経路を逆向きに転送され、探索開始ノードに到達する。hitはコンテンツ保有ノードのアドレスを含むので、探索開始ノードはコンテンツの位置を知る。

[*image*]
ノード間をlookupコマンドが伝播する図。
ノード間をhitが逆伝播する図。

上記動作の成立にまず必要なのが、lookupコマンドがネットワーク全体で一意な識別子を持つことだ。この識別子をUUID(Universally Unique Identifier)という128ビットの数値で実現する([*footnote*]GUID(Globally Unique Identifier)と呼ばれることもある。誰にも聞かずにどこで誰が生成しても、かつて生成されたことの無い新しい数値を生成できる、魔法のような技術だ。現実の実装は、イーサネットのMACアドレス48ビットと時刻と乱数を組み合わせることで、事実上一意であることを保証している。魔法では無い)。 lookupコマンドのUUID識別子は転送の途中で変化しない。転送を担う各ノードは、lookupのUUIDと転送元ノード(近接ノードのひとつ)のアドレスの組を記憶する。この組の集合をコマンド伝播テーブルと呼ぶ。ノードは、コマンド伝播テーブルをふたつの用途に利用する。ひとつは、既に転送した lookupをもう一度転送しないために利用する。もうひとつは、hitを逆向きに伝播する時に利用する。hitは対応するlookupのUUIDを含むので、コマンド伝播テーブルを参照することで逆向きの経路をひくことができる。

lookupコマンドはTTL(Time To Live)という属性値を持つ。TTLはノード間を転送される度に1ずつ減り、TTLがゼロになるとlookupの転送は止まる。Gnutellaの TTLのデフォルト値は7になっている。各ノードが4つの近接ノードを持っている場合、lookupが伝播するノード数の上限は、4の7乗(= 16384)になる。

以上が、Gnutella探索の動作原理の基本だ。ネットワーク全体の知識を持ったノードが無くても、万単位のノードの中で探索を行うことができる。各ノードはごく少数の近接ノードの知識を持つだけでよいので、アドホック性が高く耐障害性に優れている。探索動作は完全に分散した形で進行するため、探索対象のコンテンツ数に対するスケーラビリティが高い。一方、ノード数が増えてlookupコマンドの数が増えると、ネットワークトラフィックが増える欠点がある。また探索の失敗をタイムアウトでしか判別できない欠点もある([*footnote]Gnutellaのスケーラビリティの問題に対する改善の提案が色々ある。代表的なひとつが、Query Routingと呼ばれる技術だ。あるノードから先に対象コンテンツが無いことを判断できた場合、lookupの伝播を抑制してトラフィックを軽減する。この判断のための情報交換を近傍ノード間で行う)。


* Freenetの探索
P2Pフラッディング探索の別の例としてFreenetの探索を説明しよう([*footnote*]説明を探索に限定するので、Freenetを特徴づける匿名性保証の説明は省略する。このため、Freenetの総論としては半端であることに注意してもらいたい)。

Freenetではコンテンツ名そのものではなく、コンテンツから生成されるハッシュキーで探索を行う。ここではハッシュキーの生成方法の詳細には立ち入らない。話を探索に限定すれば、ハッシュキーが次の性質を満たしていることを理解すれば充分である。

ハッシュキーの押えておくべき性質(DHTでも言及)
- ハッシュキーは充分に広い160ビットの空間にマップされる([*footnote*]160ビットの広さの説明は困難だが敢えてやってみよう。IPv4 アドレスの32ビットは約43億だ。IPv6アドレスの128ビットは43億に2を96回掛けた数だ。160ビットはそれに更に2を32回掛けた広さだ。イメージできただろうか。Freenetも後述する多くのDHTも、160ビットのハッシュキーを得るために、SHA-1([*backnum*]:ハッシュ関数の過去記事)を利用している)
- ハッシュキーは160ビットの空間の中で均一(一様)に分布している
- 異なるコンテンツのハッシュキーは重ならない

探索コンテンツのハッシュキーを探索キーと呼ぶことにする。Gnutellaの例と同様に、ユーザが、ローカルディスクに無いコンテンツの探索を開始したとする(ユーザは探索キーを知っているとする)。探索開始ノードは近接ノードのアドレスとキーの組の集合を保持している。このテーブルを経路テーブルと呼ぶ。経路テーブルをどう更新するかは後述する。ここでは説明のために、経路テーブルが既にある状態を想定する。ノードは、現在の探索キーと辞書的に最も近いキーを経路テーブルから探す。その近接ノード(ひとつだけ)にlookupコマンドを転送する。lookupを受信したノードは、ローカルディスクでコンテンツを探す。ここでは説明のために、コンテンツを持っていなかったとする。ノードは探索開始ノードと同様に独自の経路テーブルを保持している。探索キーに辞書的に近いキーを経路テーブルから探し、対応する近接ノードにlookupを転送する。このコマンド伝播は、TTLやループなどの形で経路が尽きるまで継続する。探索の経路が尽きると、探索の失敗が逆方向に伝播する。探索失敗を受けたノードは、経路テーブルで次に辞書的に近いキーを探し、再び、近接ノードにlookupを転送する。この転送を繰り返すことで、コンテンツ保有ノードまでlookupが到達する。コンテンツ保有ノードはhitではなくコンテンツ本体を逆向きに伝播する。これは、探索開始ノードとコンテンツ保有ノードの間の中継ノードがすべて同一のコンテンツを保有(キャッシュ)することを意味する。

[*image*] Freenetのlookup伝播の図
http://www.doc.ic.ac.uk/~twh1/academic/papers/icsi-revised.pdf
の7ページの図

Gnutella が言わば幅優先探索的に動作したのに対し、Freenetは深さ優先探索的に動作する。一見すると、Freenetの探索の時間効率はとても悪いように感じるかもしれない。しかし、Freenetは次に説明するメカニズムで、人気のあるコンテンツは素早く拡散し、コンテンツの拡散が自動的にクラスタ化する。このため、深さ優先で探索しても、人気のあるコンテンツが早く見つかる性質を有する([*footnote*]逆に人気の無いコンテンツが見つかりにくいことも分かる。Freenetの実体はもっと過激で、人気の無いコンテンツは勝手に消え、存在すら保証しない)。経路テーブルの更新方法と中継ノードのコンテンツキャッシュがこれを支える。探索が成功した場合に、中継ノードは経路テーブルを更新する。この時、その探索キーと近接ノードを経路テーブルに追加する。探索の時、辞書的に近いキーから転送先ノードを選ぶ仕組みは既に説明した。この結果、類似キーのlookupは特定のノードに集中していく。時間とともに類似キーのコンテンツは特定のノード(群)に集まる。探索キー(ハッシュ値)が辞書的に近いことは、コンテンツの類似性と全く関係無いことには注意したい。コンテンツのクラスタ化は、コンテンツそのものとは無関係に、探索のパターンのみで決まってくる。

以上がFreenet探索の動作原理の基本だ。Freenetを探索の観点のみで見ると、効率的なコンテンツの拡散で探索を効率化していることが分かる。


* DHT(分散ハッシュテーブル)による探索
P2P フラッディングは、ノード数が増えると、ネットワークトラフィック量が増える。この問題に対するひとつの提案に、分散ハッシューテーブルと呼ばれる探索技術がある([*footnote*]2001年頃に提案され始めた新しい技術だ。CAN、Chord、Pastry、Tapestryの4つが初期の代表的なDHTのシステムと言われている)。
本記事は、DHTの基本的な動作原理を説明し、その後、具体例としてChordとKademliaの動作説明を行う。

DHT の基本アイディアは、ノードとコンテンツの両方にハッシュキーを割り当てることから始まる。ハッシュキーの理解は、Freenetの節の説明を参照してほしい。すなわち、充分に広い空間であること、均一に分布していること、重なりが無いこと、の3点を押えておけばよい。ハッシュキーの生成方法は探索の本質とは関係しない。しかし、具体的なイメージを持つ方が理解しやすいと思うので、以下では、次のように計算して求める前提にする。

[*table*]
|ノードのハッシュキー|ノードのアドレスのSHA-1の計算値|
|コンテンツのハッシュキー|コンテンツ名のSHA-1の計算値|

Gnutella やFreenetと異なり、DHTでは、コンテンツ保有ノードがコンテンツを登録する所から始まる([*footnote*]手順としてはインデックスサーバ型の探索と同じだ)。コンテンツ保有ノードは、コンテンツからハッシュキーを計算する。次に、コンテンツハッシュキーに近いハッシュキーのノードを探索する(このノードをキー保有ノード呼ぶことにする)。コンテンツ保有ノードは、コンテンツハッシュキーとコンテンツ保有ノードのアドレスの組を、キー保有ノードに登録する。コンテンツ保有ノードは、新規コンテンツがローカルディスクに保存されるごとに、この登録作業を行う。キー保有ノードは、コンテンツハッシュキーとそのコンテンツの保有ノードのアドレスの組の集合を保有する([*footnote*]コンテンツ保有ノードがキー保有ノードとしても振る舞うかどうかは実装依存)。
ノードハッシュキーとコンテンツハッシュキーが同じ広さ(SHA-1の場合、160ビット)にマップされていたことは重要だ。「2つのハッシュキーが近い」ことの説明は後述する。
探索は、コンテンツ名からコンテンツハッシュキーを計算することから始まる。コンテンツハッシュキーに近いハッシュキーのノードを探索することは、キー保有ノードの探索を意味する。キー保有ノードを発見すれば、コンテンツ保有ノードのアドレスを得られる。これはコンテンツの位置が探索できたこと意味する。

ここまでの話をまとめると次のようになる。ノードのハッシュキーとコンテンツのハッシュキーを同一空間上に見立てて、近さを定義(距離を定義)する。コンテンツハッシュキーと近いハッシュキーを持つノードは、コンテンツ保有ノードのアドレスを保有する。ノード(キー保有ノード)はP2Pネットワークを形成するので、コンテンツ探索問題は、キー保有ノードの探索問題に置き換わる。以下、DHTでの探索は、キー保有ノードの探索を意味する。

キー保有ノードの探索には、再び、ハッシュキーの近さの概念(距離の概念)が重要になってくる。この記事では、図で示した時に、長さとして目に見える距離だけを扱う。この距離は、TCP/IP層での距離や物理的な距離とは全く関係無いことに注意したい。

キー保有ノードが形成するP2Pネットワークは次の性質を持つ。
- 距離が近いノードに関する知識は密に持つ
- 距離が遠いノードに関する知識は疎に持つ

ハッシュキーが空間中に均一に分布することを考えると、近いノードは総数が少なく、遠いノードは総数が多いことは容易に想像がつくだろう。
ノードがネットワーク全体に関する知識を持たなくても、上記の性質の(部分的)知識を持つことで、探索を効率的に行えることを示そう。ノードは、ある探索キー (探索対象コンテンツのハッシュキー)を載せたlookupを受けると、自ノードのハッシュキーと比較する。ふたつのキーの距離が近い場合、そのキーの近傍のノードの知識は密に持っている。ノードは、より良いノード(目当てのキー保有ノードである確率が高いノード)にlookupを転送できる。一方、最初の比較で距離が遠い場合を考える。そのキーの近傍の知識は疎なので、最初にlookupを転送するノードはあまり良いノードでは無い。しかし、 lookupを転送されたノードは、最初のノードよりは目当てのキー保有ノードに近い。次にlookupを転送するノードの選択は、最初より良くなる。この転送を繰り返すことで探索範囲が絞られ、正しいキー保有ノードに到達する。lookupの転送ごとに探索範囲が(1/d)(dは2以上の自然数)になる場合、探索がlog時間で収束することが知られている。d=2つまり一回のlookup転送で探索範囲が半分になる場合、グラフのように、横軸の探索ノード数Nが100万近くでも、縦軸のlog2(N)は20以下だ。スケーラビリティの高さが分かるだろう。また、どのノードも全体の知識を持つ必要が無いことと、各ノードが対称的に動作することから、耐障害性が強いことが分かる([*footnote*]実際には、ひとつのコンテンツに対して、キー保有ノードが複数存在しないと耐障害性が強いとは言えない)。

[*image*] 横軸(1から100万)でy=log2(x)のグラフ


** Chordの探索
DHTの具体例としてChordの動作を説明する。

Chord でのハッシュキーの距離の定義は単純だ。ハッシュキーを数直線上に並べてその間の長さを距離とすれば良い。ただ、これでは対称性が無いので、図のようにハッシュキーを円上に並べて、右まわりだけで距離を考える。円上の点はキー保有ノードを示す。キー保有ノードを、それぞれに計算したハッシュキーの値で円上にマップする。160ビットは広すぎるので、図は6ビットのハッシュキー空間上に10個のノードをマップした場合を描いている ([*footnote*]Chordは160ビットのハッシュキー空間で、ノードの数は2の160乗と比較すると圧倒的に小さい数なので、想像を絶するほど巨大な円の中に疎な状態でマップされたノードを想像してもらいたい)。

Chord上で探索対象になるコンテンツもハッシュキーを計算する。距離的に近いハッシュキーのノードが、そのコンテンツのキー保有ノードにある。まず円上にコンテンツをハッシュキーの位置にマップする。その位置から時計まわりに辿って、最初に見つかるノードがキー保有ノードだ(距離的に近いノード)。ハッシュキーが10のコンテンツをK10と呼び、図で考えよう。 10の位置から時計まわりに辿って最初に存在するノード(N14:ノードハッシュキーが14)がキー保有ノードになる([*footnote*] Chordの用語では、successor(10)が14、という言い方をする)。コンテンツのキー保有ノードは一意に決定できる。

[*image*] Chordの円の図
http://www.pdos.lcs.mit.edu/chord/papers/paper-ton.pdf
の4ページのfig2のような図

Chordのノードは、表に示すような他ノードへの経路を持つ([*footnote*]predecessor(前)ノードへの経路も持つが、探索には直接関連しないので省略する)。

[*table*] (Chordのノードが持つ他ノードへの経路)
|名称|説明|探索での役割|
|successor(次)ノードリスト|距離的に最も近いノードへの経路。冗長性の確保のため、複数ノードへの経路を持つ|successorノードにlookupを伝播させて探索可能(非常に遅い)。fingerテーブルに比べると更新のコストが低い|
|fingerテーブル|2のk乗ずつ遠い距離のノードへの経路(kは0以上の整数)|fingerテーブルがすべて正しければ、logオーダーで探索可能。全てのfingerテーブルを正しく保つのはコストが高い|

finger テーブルは、図を参照してほしい。2のk乗は、k=0から始めると1,2,4,8,16,32となる。N8(ハッシュキーが8のノード)のfinger テーブルを見てみよう。テーブルは、8に1,2,4,8,16,32,...を足した数を第一列に持ち、第一列の数のキー保有ノードへの経路を第二列に持つ。図は6ビットのハッシュキーの例なので、テーブルの行の数は6個となる([*footnote*]160ビットのハッシュキー空間の場合、 fingerテーブルは160個の行を持つ。ただし、160ビットの空間の中で、ノード数は圧倒的に疎であることを思い出そう。現実的には、多くの行が同じノードへの経路を指す)。

[*image*] (N8の)fingerテーブル
http://www.pdos.lcs.mit.edu/chord/papers/paper-ton.pdf
の5ページのfig4(a)のような図

[*image*] N8がK54(ハッシュキー54のコンテンツ)を探索
http://www.pdos.lcs.mit.edu/chord/papers/paper-ton.pdf
の5ページのfig4(b)のような図

図は、N8がK54(ハッシュキー54のコンテンツ)を探索するケースを示している。N8のfingerテーブルの第一列で、54に最も近い数は8+32の 40になる。40に対応する第二列はN42への経路を持つ([*footnote*]ハッシュキーが42のノード。Chordの用語では successor(40)が42、と表現する。ここまでの説明の用語を使うと、N42はキー40のキー保有ノード)。N8はN42にlookupを転送する。N42はそれ自身が独自のfingerテーブルを持つ。N42は同様のアルゴリズムでfingerテーブルから54に最も近いノードと判断する N51にlookupを転送する。この転送を繰り返し、lookupはN56に到達する。N56は目当てのキー保有ノードである(コンテンツのハッシュキーの位置54から時計まわりに辿って最初に見つかるノードがキー保有ノードであることを思い出そう)。N56は、K54のコンテンツ保有ノードのアドレスをhitで返す([*footnote*]Gnutella風の伝播モデル(Chordでは再帰モデルと呼ぶ)で説明したが、反復モデルでも実装できる。反復モデルは、lookupの応答で次にlookupを投げるべきノードを受けるモデルである)。

ここまで、successorリストとfingerテーブルが、正しい経路を指しているという前提で説明した。この構築に大きなコストがかかるとアドホック性が高いとは言えないだろう。ノードの参加や離脱があると、これらの経路を更新する必要がある。この維持コストが大きすぎると耐障害性が強いとは言えなくなる。

ノードの参加と離脱に対して、Chordがどのように経路を維持するかを簡単に説明する。
参加ノードは自ノードのハッシュキーを計算することで、Chordの円上のどこに位置すべきかが分かる。図は、N26(ハッシュキーが26)が参加する場合を示している。N21とN32の間に位置することが分かるので、N26がしなければいけないことは、優先順に次のようになる。

- N26のsuccessorリストにN32を追加
- N32から、N26が保有すべきキー(とコンテンツ保有ノードのアドレス)集合を譲り受ける
- N21のsuccessorリストにN26を追加
- N26のfingerテーブルを構築
- N26をfingerテーブルに持つべきノード(理論上、最大160個。実際にはそんなに存在しない)へfingerテーブルの更新依頼

[*image*] N26が参加
http://www.pdos.lcs.mit.edu/chord/papers/paper-ton.pdf
の8ページのfig7のような図

N32の探索は、ハッシュキー26に対するキー保有ノードの探索そのものだ。successorリストの更新は、近傍ノードの間の通信で済むのでコストは低い。
fingerテーブルの構築は理論的には160回の探索を行う必要がある。しかし、N32のfingerテーブルを参照することで、探索の多くを省略できる(160ビットの空間の中でノード数が充分に疎なので)。
他ノードのfingerテーブルを更新することは更に面倒だ。2のk乗ずつ半時計まわりに遠いノードへ更新依頼を行う必要がある。更新依頼を受けたノードは、必要ならfingerテーブルを更新する。更新依頼は、半時計まわりに伝播を続ける必要がある。
ノードの参加と離脱への耐性を高めるために、ノードはバックグラウンドでstabilize()と呼ばれる作業を行う。図のN21はsuccessor(次) ノードのN32にpredecessor(前)ノードを問い合わせる。N32がN26を返答した場合、N21はN32より近いsuccessorノードの参加を知るので、N26をsuccessorリストに追加する。別の例として、N32がpredecessorノードとしてN19を返答した場合を考える。これはN32がN21の存在を知らないことを意味するので、N32にN21の存在を通知する。

以上がChordの探索の動作原理の基本だ。ノードの数とコンテンツの数に対してスケーラビリティの高い探索を提供できることが分かる。P2P特有の、全体の知識を持たないノードが対称的に協調動作する性質から耐障害性も高い。一方、経路の維持のコストは必ずしも低いとは言えず、アドホック性にはやや疑問も残る。


** Kademliaの探索
DHTの別の例として、Kademliaを紹介しよう。

紙面の都合で説明は概要だけに留めるが、ここまで読んで、DHTの基本的な考え方が分かれば、動作の雰囲気はつかめると思う。
Kademliaのハッシュキーの距離の定義は、ハッシュキー同士のXORの値を計算し、最左に1が立つビットの位置で決まる。
例として、4ビットのハッシュキーを考える([*footnote*]実際にはChord同様、SHA-1の160ビットを使う)。0011から近い順に並べると表のようになる。

[*table*] Kademliaの距離
|ハッシュキー|0011とのXOR|0011からの距離(最左の1の位置)|
|0010|0001|1| <== 距離が1のハッシュキーは1個
|0001|0010|2| <== 距離が2のハッシュキーは2個
|0000|0011|2|
|0111|0100|3| <== 距離が3のハッシュキーは4個(0100から0111)
|0110|0101|3|
....
|1011|1000|4| <== 距離が4のハッシュキーは8個(1000から1111)
|1010|1001|4|
....


図のように2分木で考えると、距離がより目に見える形で現われる。

[*image*] Kademliaの2分木
http://pompone.cs.ucsb.edu/~msa/reading/maymounkov_kademlia.pdf
のfig1

距離が遠いほど、空間が広いことが分かるだろう。
kademlia は、距離k(kは1から160の整数)ごとにノードへの経路を最大20個まで保持する。この経路表をk-バケツと呼ぶ([*footnote*]理論上、 k-バケツの行の最大数は160個で、最大160x20の経路を保持する必要がある。しかし、160ビットの広大な空間に比べてノードの数は圧倒的に小さいので、実際の経路表はずっと小さく抑えられる)。探索は、k-バケツから探索キーに距離が近い行を選び、その行からノードを選びlookupを転送する。近い距離のノードの知識は密なのでlookupが当たる可能性が高い。遠い距離のノードの知識は疎なのでlookupが当たる可能性は低い。 lookupの転送ごとに(1/2)ずつ距離が縮まるので、探索はlog時間で終了する。

[*image*] kademliaの探索範囲の絞り方
http://pompone.cs.ucsb.edu/~msa/reading/maymounkov_kademlia.pdf
のfig2

距離の計算にXORを使う意義を説明する。ノードは転送するlookupに自ノードのハッシュキーを載せる。XORの対称性により、lookupを受けたノードは、相手ノードへの経路を(相手と)同じ距離でk-バケツに追加できる([*footnote*]kademliaは反復モードで動作する。反復モードに関してはChordの脚注を参照)。lookupの転送で、経路表(k-バケツ)を自動的に更新できる。Chordのsuccessorリストや fingerテーブルの更新と比較すると、これは大きな利点だ。

以上がkademliaの探索の動作原理の簡単な説明だ。Chordと同様のスケーラビリティや耐障害性があることが分かる。経路の維持コストを軽減する工夫は特筆すべき点だろう。