DHTのアルゴリズム

分散ハッシュテーブル - Wikipedia
DHTは、ピュアP2Pであってもネットワーク負荷はそれほど上がらず、ネットワーク上のコンテンツを漏れなくかつ高速に探索することを可能にする。従来のピュアP2Pで採用されていた通信では、数10万ピアぐらいが限界だとされているが、DHTを使うと数10億ピアを探索範囲とすることが可能となる。しかし、実装がむずかしいことが欠点となる。
DHTの欠点は、一般的に完全一致探索しか行えないことである。特に正規表現のような複雑な検索をDHTのみで実現することは不可能である。

代表的なDHTのアルゴリズムを説明している日本語文献を探してみた．

Chord

この節では，DHT の代表的なアルゴリズムであるChord について説明する．Chordのハッシュ空間上での距離の定義は，ハッシュ値の差の絶対値である．図3.5のように，データ保有ノード (図中の青点) を，それぞれ生成したハッシュ値を基に円形のトポロジにマップし，右まわりだけで距離を考える．
そして，（中略）各データは，データのハッシュ値とハッシュ空間上で最も距離が近いデータ保有ノードに管理される．具体的には，まず円形のハッシュ空間におけるデータのハッシュ値の位置にそのデータをマップし，その位置から時計周りに辿って最初に発見されるノードがそのデータを管理するデータ保有ノードとなる．

例えば，図3.5に示す6ビットのハッシュ空間で，ハッシュ値が24のデータ (K24) を登録する場合，24の位置から時計周りに辿って，最初に辿りつくハッシュ値32のノード (N32) がそのデータを管理する．

Chordの各ノードは，Successor・Predecessor ListやFinger Tableと呼ばれる経路表を持つ．あるノードのSuccessorとは，Chordの円上で，自身のハッシュ値よりも大きく，最も近いノード (次ノード) を示し，逆にPredecessorとは，自身のハッシュ値より小さく，最も近いノード (前ノード)を示す．データ検索にはSuccessor List とFinger Table を使う．まずSuccessor Listについて以下に説明する．

図3.6のように，ハッシュ値 8のノード (N8) がハッシュ値 54のデータ (K54) をSuccessorListを使って検索する場合は，データ検索用のクエリがハッシュ値の大きい隣のノードに順番に転送され，目的のデータを持つノードが発見されるまで繰り返される．しかし，この方法はノードを一つずつ順々に問い合わせるため効率が悪く，全ノード数N に対して検索ホップ数がO(N)になる．

そこで，この問題を解決しホップ数を減少させるために，各ノードはFinger Tableと呼ばれる，ハッシュ空間上で2のk乗ずつ距離の離れたノードへの経路表を持つ．例えば図3.7のようにハッシュ値 8のノード (N8) のFinger Tableには，8に1, 2, 4, 8, 16, 32を足したハッシュ値への経路表が格納されている．図3.7は6ビットのハッシュ空間を用いたChordの例であり，Finger Tableの行数は6個となる．
図3.8 は，ハッシュ値 8 のノード (N8) がK54 を検索する例を示している．図3.8 での，データの検索から取得までの流れを以下に示す．

N8のFinger Table の第二列で，54より小さく，かつ，最も近い値を調べる．

54より小さく，かつ最も近い値はN42である．よってN42にクエリを転送する．

N42もまた自身のFinger Tableを持っており，同様のアルゴリズムによってN51にクエリを転送する．

N51のSuccessor Listには，54より値の大きいN56への経路がエントリされているため，N56 がK54保有ノードであることがわかる．よって，N56にクエリを転送する．

N56 がK54を検索要求元のノードN8に送信する．

このようにして，ChordではFinger Table を使うことにより，一回のクエリ転送毎に検索範囲を1/2 ずつ狭めることができ，全ノード数N に対して検索ホップ数をO(log2 N)に抑えることができる．
『負荷分散を目的とした半構造型P2Pネットワーク』

Chord

Chord は環状のハッシュ空間上で二分探索に似た探索を行うことで log(N)の探索効率を実現したルーティングアルゴリズムで、確実な探索とノードの参加・離脱に対応している。Chord は全体として単純な構造であり、アルゴリズムの正しさなどの性質のいくつかが証明されている。

Chord ではハッシュ空間は 160bit の円の形に例えられ、ノードおよびデータは円周上の点として定義される。図では時計回りにハッシュ値が配置された様子を表している。 Chordでは距離をこの円周上の正方向の数値差で定義している。これによってデータは最も距離の小さいノード、つまりあるノード x が担当する区間は反時計回りに隣接するノードまでとなる。そして各ノードは正方向に隣接するノードのアドレス、つまりノード x は隣接するノードとして数字の増加する方向に次に存在するノード succ(x)を保持することで円を維持している。

あるノードがキーのハッシュ値を用いた探索を行う場合、開始ノードから succ を用いて円周を時計回りに探索する方法が考えられる。 Chord では Successor ノードに加えて、二個以上先のノードも記録した Successor List を定義して耐故障性を高めている。この方法によって正しい探索は行えるが、ノード数 N に対して O(N)の探索時間がかかるため効率的とはいえない。

そこで Chord では Finger Table と呼ばれるショートカットを導入している。 Finger Table では succ とは別にノード x に対して x+2i のノードも保持しておき、最大で円周の対角に位置する値までおおざっぱなアクセスが可能となる。キーを探索する場合、 Finger Table はそれぞれ２のべき乗になっているため一度引くことで目的の値が存在しうる値域を半分に絞ることができ、探索に要するホップ数を O(log(N))に抑えられる。

ノードが新たに参加・離脱する場合には自分が参加する ID 周辺のノードに通知し、 succとして周辺のノードの更新を行うが、ノードが故障した場合には正常な離脱処理が行えない場合がある。 Finger Table やSuccessor List など効率化のためのデータに不整合が発生しても検索結果に影響を与えないが、 Successor が誤ったノードを指した場合正常な探索結果が得られなくなる。そこで Chord では Successor ノードをはじめとする Finger Table など安定化処理を定期的に行い、正しい円構造を維持している。この安定化処理は DHT の重要なパラメタ一つであり、その頻度を高くすると常に最新の情報を維持できる反面、トラフィックが増大する。
『P2Pを用いたWeb動向集計フレームワーク』

CAN

CANは，物理ネットワーク上にあるファイルやコンテンツの位置はd次元座標空間であるハッシュ空間上のハッシュキーに対応させ，参加ピアがハッシュ空間の部分（ゾーン）を受け持ちつつリソースを管理する方式である．各ゾーンを受け持つピアは，自分自身の持つキー情報に加え隣接ピア（辺を接している）がだれであるかを指し示すルーティング情報を保持する．
図はに二次元のハッシュ空間の例で，五つのピアにより分割管理されている状態である．
各ゾーンは，左下と右上の座標の２点を用いて表現され，ピア1の領域は(0,0.5)-(0.5,1)，ピア2は(0.5,0.5)-(0.75,1)である．また，管理されるリソースのある位置も座標で表される．また，ピア2の隣接は，辺を接するピア1，3，5であり，ルーティングテーブル内に座標情報が保持される．

あるピアが検索要求を受け取ると，隣接ピアの領域から目的地までの距離（直線近似）を判断し，近い方のピアに転送する依頼する．この例では，ピア3が，(0.3,0.4)で表させるリソースへのディスカバリ要求を受けると，隣接するピア2の領域の中心座標と(0.3,0.4)の直線距離，及びもう一つ隣接するピア5と(0.3,0.4)の直線距離を比較して，後者の方が短いことからピア5にリレーされている．ピア5は，(0.3,0.4)を管理する隣接のピア4に引渡し，ディスカバリは終了する．

新規ピアを追加する場合は，新規ピアは空間上ランダムな点を選び，それを管理するピアを検索する．この既存ピアは新規ピアに対して，ゾーンの半分を割り当て，自分らのルーティング情報を書き換えるとともに，隣接ピアに新規ピアが参加したことを伝える．脱退の場合は，自分のゾーンを隣接ピアに引き渡す．新規ピアは，ランダムに座標を選ぶことから，管理ゾーンの大きな既存ピアの管理ゾーンが分割される確立が高くなり，確率的に管理ゾーン空間は平均化される．

本方式，この図からも分かるとおり，隣接のピアに関する情報を管理すればいいので，d次元空間の場合O(d)個のオーダの状態を管理すればよく，検索のためのコスト（処理ステップに相当）は， $O(dN^{1/d})$ となる．
『CiNii 論文 - P2P総論[II] : P2Pテクノロジー』

Pastry

Pastry はハッシュ空間での距離として ID の共通プレフィックス長を用い、ツリー構造を用いて探索を行うアルゴリズムである。 Pastry での共通プレフィックスは各ノードに割り当てられた 128 ビットの ID を b bit で区切り、 b bit単位で数えた共通プレフィックスの長さ（共通部分が長いほど距離が短い）が用いられる。この距離を用いて、 Pastry は遠い ID へ到達する経路表、隣接するノードを保持する leaf set 、距離的に近いノードを保持するneightborhood set を管理している。

leaf set は次に説明する Chord の succ と似た機能を果たし、自身の ID より大きなノードL/2 個と、小さなノード L/2個の合計 L個のノードを隣接ノードとして保持しており、 leat setは最終的に正しいノードを探索するために重要なデータ構造である。経路表は距離の離れた ID の周辺に一気に到達するためのテーブルで、自ノードの ID との共通プレフィックス長i (0 <= i < 128/b)それぞれに対してエントリを持つ。各エントリには自ノードと i 個の共通プレフィックスを持ち i+1 番目が 0 から 2^b （このうち自身の i+1 番目の数字を除いたもの) の計 2^b-1 個のノード情報が格納されている。つまりすべてのエントリに入るノード情報は128/b ･(2^b - 1)個となる。

これらを用いて ID の探索を行う。目的の ID が leaf set に含まれず、目的ノードがわからない場合には、経路表を参照して目的ノードへの距離が最も短い（共通プレフィックスが最も長い）エントリを引いて、そのノードから再度探索作業を行う。最終的には目的 ID が leafset に含まれるまで探索を繰り返して目的ノードを得る。この探索では距離として ID の長さを用いているため、 O(log(N))での探索が可能である。

P2P のような物理的なネットワークの上に構成する論理的なネットワークでは、実ネットワーク上での距離を考慮することが重要である。例えば、物理的に離れているノードに論理的に近い ID が割り当てられると近傍ノードと密接に通信を行うアルゴリズムでは遅延が大きくなり効率が低下するため、耐故障性や匿名性などを考慮しない場合には、物理的なネットワーク上の距離と論理的な距離の差が小さくなることが曇ましい。これを考慮したのが物理的に近いノードの集合を表す neighborhood set である。新しいノードが参加する場合、 P2P に自身の ID を探索するクエリを発行し、その経路ノードから各々の保持する情報を取得する。取得した情報を元に leaf set, neighborhood set を構築し、経路表についてはその経路上のノードが持つエントリを取得して neighborhood set を参照することで物理的に近く共通プレフィックスを持つエントリを構築している。

Pastry では後述の Chord と同様に leaf set の生存確認を常に行い、経路の正しさを維持している。これによって耐故障性に優れたネットワークを構成している。
『P2Pを用いたWeb動向集計フレームワーク』

Pastry（パワーポイントによるプレゼン）

Koorde

Koorde は Chord の finger table の代わりに de Bruijn グラフを利用してルーティングを行うルーティングアルゴリズムである。 Koorde の特徴として、 de Burijn グラフの Degree を変更することでホップ数のオーダーと管理コストの調整が可能な点、書くノードが O(log(n))の枝を持つことで耐故障性を備えながら O(log(N)/loglog(N))のホップ数で探索が行える点が挙げられる。

de Bruijn グラフは b ビットの ID を持つノードが 2b個存在した場合、それぞれのノードから 2m mod 2^b, 2m + 1 mod 2^b のノードに辺を作ることで構成されるグラフである。このグラフの特徴として、ある ID から目的の ID へ探索を行うホップ数が O(log(N))という点がある。
このグラフを Chord で定義されたハッシュ空間に配置して探索を実現している。 Chord のハッシュ空間では各ノードは間隔を持って存在するため、すべての ID を持つノードが定義された de Bruijn グラフは適用できない。そこで Koorde では de Bruijn上の ID を Chord ハッシュ空間上の仮想 ID とし、一つのノードがある区間の ID を担当させている。 ID ： i は pred(i)の実ノードによって管理される。

あるノードが探索を行う場合、送信元 ID を担当するノードから de Bruijn のルーティングアルゴリズムを用いてルーティングを行う。 1 ホップのルーティング後に到達するノードは実ノードの次のノードとして探索されるため、仮想ノードの次のノードとはずれが生じる。これを埋めるため、 Chord 円周上を successor をたどりながら仮想 ID を担当するノードまでルーティングを行う。担当するノードまで到達すると、同様の de Bruijn のアルゴリズムを用いて探索を行う。これによって、 O(log(N))での探索が可能となる。
『P2Pを用いたWeb動向集計フレームワーク』

Kademlia

Kadamlia は他のアルゴリズムとは異なり、ネットワーク維持のための特別なクエリが必要ないという特徴を持つアルゴリズムである。

Kademlia では 160-bit のハッシュ空間上に XOR を用いた距離、具体的には二つのノード ID に対して ID 間の距離をその XOR で定義する。 XOR は対称性を持つため、ノードＡから見たＢの距離と、Ｂから見たＡの距離が等しくなる。この距離を用いて各ホストは、 Chordの Finger Table に似た k-bucket を保持する。 k-bucket では自ノードからの距離 2i 〜 2i+1(0 ≦ i < 160)に存在するノードの IP アドレスを、一つの i に対して最大で k個のノードまで保持する。
探索の際には探索を開始するノードが k-bucket を用いて該当値域のノードにクエリを送信し、そのノードからみた k-bucket のエントリを取得する。そして取得したエントリから再度次のノードにクエリを送信する、これを繰り返すことで Chord の Finger Table と同等の探索が行われ O(log(N))での探索が実現できる。
Kademlia では k-bucket がいっぱいになると、新しいノードからエントリを削除する。これは古くから残るノードほど安定しているというデータに基づいている。

Kademlia 最大の特徴はネットワークの維持にある。 XOR の対称性から、あるノードがクエリを受信した場合、送信者から見た距離と受信者から見た距離が等しくクエリの受信者がk-bucket の同じ距離のエントリを最新できるという特徴がある。
Chord ではネットワークを維持するために特別な更新作業を行う必要があったが、 Kademlia ではクエリを受信する度にその更新作業が行えるため、特別な?新は存在しない。最新手続きが不要なためKademlia は実装が比較的容易であるとされる。

この他にも N 次元トーラス上にノードを配置した CAN[15.]など、様々な空間と距離の取り方のアルゴリズムが提案されている。
『P2Pを用いたWeb動向集計フレームワーク』

Tapestry

Tapestry を例に，DHT の動作例を説明する．Tapestryは分散ストレージシステム OceanStore のための DHT である．Tapestry では，ホストは保持するコンテンツのポインタ（コンテンツ名と自身の IP アドレスの組）を分散ストレージに登録する．

Tapestry におけるオーバレイは，NodeID のサフィックスをもとに構築される．例えば，NodeID 7734 のノードは，GUID が下の桁から順に i 桁 (0 ≦ i ≦ 3) だけ一致するノード (NodeID =51E5, 9C34,2A34,A734) を隣接ノードとして論理リンクを張る．
Tapestry におけるコンテンツの登録の様子を図の左に示す．NodeID 39AA のノードは GUID 8734 のコンテンツを登録するために，(GUID = 8734, NodeID = 39AA) というコンテンツの位置情報（ポインタ）を示したクエリーを，コンテンツのルートノード (NodeID 8734) に向けて，隣接ノード D6A4 に送信する．
このクエリーは，GUID の一致する下の桁数が 1 つずつ増加するように，即ち，D6A4 → 1634 → A734 → 7734 という NodeIDをもつノードを転送されていく． *1つまり，サフィックスベースのルーティングを行う．この経路上のノードがこのコンテンツの位置情報を保持する．

Tapestry におけるコンテンツ発見の様子を図の右に示す．NodeID 197E のノードが GUID 8734 のコンテンツを発見する場合，GUID 8734 を指定したクエリーをコンテンツのルートノード (NodeID 8734) に向けて，隣接ノード F4B4 に送信する．
クエリーは，F4B4 → 1634 と転送された時点で，ノード 1634 が保持する (GUID = 8734, NodeID = 39AA) を発見できるため，クエリーはノード 39AA にリダイレクトされる．このようにしてコンテンツ 8734 が発見される．
『ユビキタス環境に向けた分散コンテンツ発見』

Attenuated Bloom Filters

DHT は広域コンテンツ発見には有効であるが，クエリーを出すホストから目的のコンテンツまでのホップ数が小さい場合には有効ではない．そこで，局所的な P2P 分散コンテンツ発見手法として Attenuated Bloom Filters が提案されている．
Tapestry と同様，ホストは保持するコンテンツのポインタ（コンテンツ名と自身の IP アドレスの組）を分散ストレージに登録する．

Attenuated Bloom Filters の動作例を図を用いて説明する．例えば，図の上の図において，保持するコンテンツ ”Box ofRain” をもつホストは，n 個（ここでは n =3）の異なる共通のハッシュ関数を用いて，そのハッシュ値（ここでは {1, 3, 8}）をw bit（ここでは w =8）の Bloom Filter に格納する．他の保持するコンテンツについても同様の処理を行い，1 つのノード内のすべてのコンテンツの情報を 1 つの Bloom Filter に集約させる．
次に，図の下の図のように，各ホストの Bloom Filter を P2Pネットワークの隣接ホスト間で交換して伝播させることにより，アウトプットインタフェース毎に深さ d（ここでは d =3）の BloomFilter の配列 (Attenuated Bloom Filters) を作成する．この配列がルーティングテーブルに相当し，i 列目が i ホップ先のコンテンツを表す．
例えば，ホスト A のホスト B へのリンクの配列 $F_{AB}$ において，1 列目の Bloom Filter では 1 ホップ先のホストB のもつコンテンツのハッシュ値 ({1, 3, 8}) のビットが立ち，2列目では 2 ホップ先のホスト C, D のもつそれぞれのコンテンツのハッシュ値 ({0, 3, 7} と {2, 5, 7}) のビットが立つ．
従って，受信したクエリーを，最短ホップ数で目的のコンテンツまで到着するようなホストに決定的に転送することができ，局所的ネットワークでは高速な透過的コンテンツが実現できる．
『ユビキタス環境に向けた分散コンテンツ発見』