DHTシステムの仕組みと性能と課題について

報告者 : 駒井秀一
2008 年 9 月 30 日

株式会社ライブドア ネットワーク事業部
通信環境技術研究室

1

はじめに

2

現代インターネットアーキテクチャ

当報告書では、インターネットシステム、オーバレイネット

近 年 、 FTTH(Fiber to The Home) や DSL(Digital

ワークの概念を整理し、その基礎技術として分散ハッシュテ

Subscriber Line)をはじめとするブロードバンドの急進展や、ーブルと呼ばれる手法を紹介する。分散ハッシュテーブルを複製/記録/保存などのハード面での劇的なコスト低下により、用いたオーバレイネットワークの具体的な一例として、数値

情報流通の性質には変化が生まれてきた。

的に探索空間の分割を行う Chord[1]と、経路表を用いる

単位ユーザあたりのトラフィック量の増大は、都市部など

Pastly[2]について詳細に解説する。また、分散ハッシュテーのエリアを限定でするものではなく、P2P などを利用する極ブルの応用例として、Pastry アルゴリズムをベースにしてい端なユーザや、企業ユーザに限定した状況とはいえなくなっる BambooDHT[3]実装方法や、実装時の動作について解説てきた。平行して、インターネットに流通するコアコンテンする。

ツとは、音や動画などの重量マルチメディアコンテンツへシフトが加速した。現代流ともいえる、この情報流通の側面を分散ハッシュテーブルに注目が集まる要因の１つは簡潔さ垣間見れば、その中には IP システムという１つの共通したや効率性の高さによる。

アーキテクチャデザインに、以下であげられるような排他性

分散システム在り方の利点である、耐障害性、規模拡張性、を否定する自由な情報の流通側面を共通して確認できる。

可塑性を想定する上で、冗長性の確保が必要であることは容易に想像できるところだが、分散ハッシュテーブルでは、ハ・ ハード/ソフト両面でオープンなシステム。

ッシュテーブルという考え方をネットワーク上に拡張し、原・ 代替的で、選択肢が多様であること。

則的に代替することを可能とする各機能をネットワークに・ 競争原理がありコスト性や協調性に富む。

参加するノード間で分担する事により、負荷の分散を行える
点で冗長性を共有できる。

これら性質を一貫して保持し、事業や経営の変化にも強く、利用者や利用方法を単調に制限しない自由な情報流通が可

また、IP システムアーキテクチャにおけるグローバル空間

能な特徴を持つことになったのであろう。つまり、IP シス

内での到達可能性は、ユーザが自由に活動する目的を達成す

テムは自律的なシステムの提供が実現出来ているわけだ。

る必要条件にあたる。分散ハッシュテーブルのアーキテクチ

インターネットがグローバル規模なアーキテクチャとしてャデザインにて、人気のあるコンテンツを保有している特定

成長維持される背景であるこれら要因を踏まえ、IP システ

ノードへの大きなアクセス負荷を見直し、より公平な分散ハ

ム上へ展開されるオーバーレイネットワークという存在がッシュテーブルネットワークを構築する可能性を検討する。

技術と政策の両面で持続的提供が可能なシステムアーキテ

以上を当報告書の目的とする。

クチャの 1 つである旨の認識へと到達する。また、オーバー
レイネットワークは分散性という特徴も併せ持つ。インター
ネットの原型とされる ARPANET が分散型システムであったように、オーバーレイネットワークにおいては一部に破壊や障害があったとしても全体としての最低限の機能は維持される機構を持つ。また、ネットワークの規模レベルは、原則として中央コンピュータの性能に比例する側面を持つため、ネットワークにおけるノードの数や通信量に応じて増加するステートの管理の負荷にも悩まされる事がない。コンピ

両者の最大の違いはサーバやクライアントは１つの点でュータの技術向上は日進月歩であり、コスト面でも性能面である必要が無く、ISP も企業もユーザも、ネットワークに参も輝かしい成長をとげてはいるが、ノード数や通信量に応じ加する全ての機器がサーバであり、クライアントにもなりう

た中央コンピュータの拡張に追いつくものでもないだろう。

る事である。それ故、サービスプロバイダが主役となるクラ

中央集権タイプのアーキテクチャデザインでは、システム規

イアントサーバモデルとは異なり、耐障害性、拡張性、可塑

模は一定の範囲内で収束するだろう。一方、分散型システム

性を実現する対等な peer 同士の協調作業を実現する。

においては、それぞれのノードマシンが参加する通信の量とP2P アーキテクチャについては、その検索方法の違いからいうものは中央コンピュータ程のものではない。分散的側面

クライアント・サーバモデルを融合させサーバを使用するをもつオーバーレイネットワークが注目を集めるに値する「ハイブリッド P2P」 と、完全な分散環境である「ピュアアーキテクチャであることは妥当なわけだ。

P2P」 に分類できる。透明性の高い基盤の上に自由な「エンド・ツー・エンド」 なサービスを展開可能にする P2P ア

3

DHT オーバレイネットワーク

ーキテクチャは、自律性や分散性を持ったスケールフリーなアルゴリズムであると言える。今回、当報告書ではオーバレ前章で既に述べたインターネットシステム拡張の背景を踏まえると、透明性の高い基盤の上に自由なプロトコルやトイネットワークの１つのシステムデザインとして、分散ハッシュテーブル(DHT)に着目し報告を行う。

ポロジを定義、形成可能なネットワークを構成することはとても大切な考え方の 1 つであろうという結論に到達するだろ3-1

クライアント・サーバモデルの問題点う。
ここでは、コンテンツを流通するにあたり、中央集権タイ

先に説明を行った通り、現状のネットワークで主流となる

プのアーキテクチャデザインであるクライアントサーバア

クライアント・サーバモデルは単一サーバであるため，クラーキテクチャと分散性を持つ P2P アーキテクチャという両イアント数の増加に伴いサーバの負荷が増大し、中継ネット

者の大きな差異点について考える。

ワークでボトルネックが生じてしまう。また、サーバに障害が起きた場合、サービス全体が停止してしまう。
そこで解決策に Peer-to-Peer(P2P)が挙げられる。P2P ではピアと呼ばれる端末が、サーバとクライアントの両方の機能を持ちホスト上でパケットの複製・配信が行うことができる。これにより、サーバの負荷分散、帯域の有効利用が可能
になる。

3-2

peer to peer(P2P)モデル

ピアという単語には互いに等しいという意味が潜在するので、対等なレイヤでそれぞれの協調的な活動実体が考えられる。ピア同士の協調作業を想定する上では、動的に変化する幅の広い条件に依存せずに分散システムが全体として現
図 3.1

Hybrid P2PとPure P2P状の性質を維持できることが必要である。当条件の実現を視

野に、システムが冗長的であり、互いにオープンでリカーシーズ検索のような「あいまい検索」や「前方一致」といったブルに相互通信を実現するノードで構成がされ、状態や機能検索処理ではなく、key に対応するデータ(value)が一意に決面でのキャッシュ機能が出来る必要性がある。

定される。これが通常取り扱われている「検索」機能と「Lookup」との違いに該当する。 Lookup で取得されるデ■ータ(value)は、検索結果であるコンテンツ自体の場合も想定

耐障害性の実現
サーバに障害が発生した場合、その直後から何ら通常と変できるが、IP アドレスのリストなどが記録されており、コ化の無いサーバコンテンツの送受信を行うためには、該当サ

ンテンツの場所を指し示すためのポインタとしても用いらーバのキャシュが存在し、互いがトランスピアレントな状態れる。実装次第では検索主が行うコマンド処理は 1 回にするであることが必要条件といえる。P2P モデルでは、耐障害性ことも可能だが、プロセスとしては、コンテンツの IP アドを実現できる。

レスのリストを取得し、その後に当該 IP アドレスへ直接に接続し、コンテンツを取得するという 2 回の処理を行うステ■ップが要される。

再帰性の実現(リカーシブル)
分散システム内の一部が消失してしまった場合、オーバー

レイネットワーク内の残数のノードネットワークが、消失前

4

分散ハッシュテーブル

の状態を保持するために、消失した代替的システムを複製実

4-1

Chord アルゴリズム

現する事が必要条件といえる。また、再帰性が確実に実現されるために、システム内に指揮全般を取り仕切るスーパーノ

分散システムにより検索を実現する方法として Chord ネードが存在するのではなく、システム内のそれぞれが自律的ットワークを解説する。Chord アルゴリズムは、"Ion Stoica"に再構築に参加し、回復への道が進行する 必要性がある。

氏[4]らにより提案されたオーバレイネットワークの１つでP2P モデルでは、耐障害性を実現できる。

ある。

3-3

4-1-1.

分散ハッシュテーブル

ID 空間

Chord では、ネットワーク全体が ID サークルという円状
表 3.3 分散ハッシュテーブルの特徴比較の仮想空間として定義され、全てのノードと全てのデータは、

Chord

Pastryこの ID サークル上に配置される。

Path Length

Log2N

logbN

Chord のネットワーク空間の大きさは、最大 2m 個のノード

NeightborState

Log2N

logbN

から構成される。Chord では、ノード及びデータを ID サー

InsertO(Log22N)

O(logbN)

クル円状均等に配置するにあたり、ハッシュ関数(SHA-1)を用い、160 bit のうち m bit (1 ≦m ≦160; m ∈ N)を ID 空

先に述べたオーバーレイネットワークの基礎技術として、間に使用する。

分散ハッシュテーブル(DHT)が提案されている。その具体例
として、Chord、Pastrly が例に挙げられるが、それらアル・ノード ID：SHA-1(IP アドレス)

ゴリズムの特徴を次章及び表 3.3 にて示し解説する。分散ハ・key：SHA-1(キーワード)

ッシュテーブルを用いたネットワークにおいては、key 値に対応するデータ(value)の取得を行う事が可能であり、これを

160bit の ID 空間の場合、3.40*1038 の ID が存在する事に

Lookup と呼ぶ。この Lookup 処理では、一般的にいうフレなり、コンテンツと IP アドレスをマッピングしても衝突しなことが前提とされる。もし衝突する場合には、任意の数字

interval = [start, end)とノード ID を加えた値(anyID + SHA-1(ip))が用いられる。

start =(N + 2 k-1)mod 2m

Chord の ID 空間がリング状につながっており、ノード ID

end =(N + 2k)mod 2mと keyID がランダムに分散した状態となっている。

※ N = 当該ノード ID

ここでは、説明しやすいように 7bit(0-127)の ID 空間を用いて説明を行う。距離の定義は ID の単純な差である。ネット

2 つ目のルーティングテーブルは precedessor のルートを持

ワークの近さを全く考慮しない下層的なネットワークであつルーティングテーブルである。

る。従って、Chord のトポロジーは数直線の最小値と最大3 つ目は以下に解説する finger テーブルと呼ばれるルーテ

値を結んだ円形である。各ノードはノード ID に基づき IDィングテーブルである。

サークル上に配置される。

finger テーブルは、
自分より 2k (0 ≦ k ≦ m -1; k ∈ N) 個離れたノードを保

4-1-2

参照処理

持するテーブルである。これを使用することにより、1 ホッ
プ毎に探索範囲を少なくとも 2 つに分割しながらノードを

Chord の参照処理はどのように行われるのかについて述べる。Chord での探索は ID が大きくなる方向に順に処理が絞っていくので、ノード数全体を N とすると探索のホップ数は O(logN)相当 になる。

実行される。あるノードの存在を考えた場合、ノード ID が大きくなる方向で見た場合に最近接のノードを successorといい、それとは反対に、ID 値が小さくなる方向で最近接の ID を predecessor という。また、Chord では以下に解説する 3 種類のルーティングテーブルを用いる。これらのルー
ティング情報を持つことで、最終的に各ノードは ID サーク
ル全体をカバーすることになり、任意の問い合わせに対して、
適切なルーティング処理を行う事ができる。

まず 1 つは successor リストと呼ばれるルーティングテ
ーブルである。successor リストは後続ノードのルートを r

図 4.1 keyIDのマッピング(r ∈ N) 個だけ保持する.
各 interval に含まれるオブジェクト ID のオブジェクトを検参照時の処理の流れを図を使用し解説する。図 4.1 では、索する際に、次にどのノード(successor ノード)に検索要求を

ノード 5→ノード 10→ノード 45→ノード 90→ノード 105→

フォワードすべてきかが示されている。ただし、intareval

ノード 120→ノード 5 の様に接続される。この接続はルータとは具体的に次式で定義される時計回りの区間をさす。

同士の接続ではなくノード同士で作られる接続である。
そのため、ノード間には複数のノードが存在し、ノードに格納され、このノードを代表ノードと呼ぶ。key20、key38
は時計回りに最も近い node45 に格納される。同じように、
key80 のデータは node90、key110 は node120 に格納される。そして、key の値とデータのペアは、ネットワークに参加しているノードのみに保存される。
図 4.2 は基本的な参照方法を表している。探索者である

既にネットワーク に参加しているノードと通信できる状態であるとする。

node45 が、key110 に対応するデータを取得した場合、参加ノードは自ノードのハッシュ key を計算し、既存ノー

node45→node90→node105→node120 へと検索クエリが転ドと通信を行う事で、自分が Chord の円上のどこに位置す送される。

べきか判断を行う。次に、 successor と predecessor のル

node120 は keye110 を保持しえるため、key110 に対応するーティングテーブルを利用して、自分のルーティングテーブ

データを node45 へ送信する。

ルを構築する。合わせて successor から自分が担当するべき
HashTable の要素を受け取る。最後に、自分が参加した通知を Chord のネットワークに転送させることで、他ノードのルーティングテーブルを更新する。

図 4.3 は ID が 26 のノードが参加する場合を示している。
ノード 21 とノード 32 の間に位置することが分かるので、
ノード 26 がしなければいけないことは優先順に次のようになる。

(1)ノード 26 の successor list にノード 32 を追加。
(2)ノード 32 から、ノード 26 が保有すべき key 集合を譲り
受ける。
図 4.2

基本的な参照処理(key80 を探索)

(3)ノード 21 の successorlist にノード 26 を追加。
(4)ノード 26 の finger table を構築。

4-1-3

join(追加)(5)ノード 26 を finger table に持つべき ノードへ finger
table の更新依頼。(理論上，最大 160 個)

ノード 32 の探索は、ハッシュキー26 に対するキー保有ノードの探索そのものであり、successor list の更新は，近傍ノードの間の通信で済むのでコストは低い。finger table の構
築は理論的には 160 回の探索を行う必要がある。しかし、
ノード 32 の finger table を参照することで、探索の多くを省略できる。他ノードの finger table を更新することは更に面倒で、2 の i 乗ずつ半時計まわりに遠いノードへ更新依頼を行う必要がある。更新依頼を受けたノードは，必要なら
図 4.3 ノード参加時の様子

finger table を更新する。更新依頼は半時計まわりに伝播を続ける必要がある。

Chord ネットワークにおいてノードの追加及び削除があった場合の処理について説明する。このとき最低 1 ノード、

4-1-4 Chord の特徴

4-1-6

ノード数 N の場合を想定した Chord ネットワークにおける諸性質を以下に示す。

考察

Chord ネットワークは、ハッシュ関数を用いて各ノードに規則的に役割を持たせている。そのため、アドホック的なネットワークに比べ状態遷移が多く、ネットワークの維持にか・ネットワークの維持には他の O(logN)ノードのかる処理は複雑化することが予想される。

情報を所持する必要がある。

しかし一方、分散アプリケーションでは、どこにデータを・O(logN)のメッセージ数で参照が可能である。

格納するか問題となるが、その解決方法の１つとして、分散・join/leave する際のメッセージ数は O(log2(N))

ハッシュテーブルである Chord を用いた参照処理が利用できる。そのため、今後様々な分散アプリケーションに適用でChord では参照やネットワークへの join/leave にサーバをきると考えられる。

必要とせず、各ノードが完全に分離して処理が進行する。検索可能ノード数 N の増加に伴い線形のパケット増加が起こ

5

Pastryる。一方、Chord ではパケット数の増加は O(logN)、ホップ
数は O(logN)にすぎず、規模拡張性に優れている。また、BambooDHT が利用するアルゴリズムである Pastry の前Freenet[5]などにおいては、検索時にデータが存在しない事に、Pastry アルゴリズムの土台となっている Plaxton[6]構を判断するには、検索時の遅延を推測しデータの不在を判断造について説明する。

していたが、Chord ではデータが存在しない場合であっても、Plaxton は経路表を用いる同様に経路表を用いるオーバレイ

明示的にデータが存在しないことをしることが可能である。

ネットワークの関連研究に、マイクロソフト社/ライス大学に

前述の通り 1 ノードを参照するには、O(logN)メッセージ

よる Pastry である。

数(ホップ数)がかかる。そのため、ネットワークの参加へはそ の 後 、 Pastry ア ル ゴ リ ズ ム の 一 例 と し て 有 名 な

自ノードを参照される O(logN)個のノードに変更を行うため、BambooDHT に関して、情報の少ないその具体的な実装方法

参加時に生じるメッセージ数は 0(log2N)となる。

を解説し、サンプルコードの解説や検索挙動についての説明も合わせて行う。

4-1-5 Chord API
5-1

Plaxton 構造

・insert（key, value）:ネットワークに key と valueを挿入する。

Plaxton 構造では、全てのノードがサーバであり、ルータ

・lookup(key)：key に対応する value を返す。

であり、クライアントである。つまり、オブジェクトを格納

・update(key,value)：key と newval をネットワー

し、経路制御を行い、探索要求を発行できる。他の分散ハックに挿入する。

シュテーブルアルゴリズムと同様に、Plaxton 構造でも全て

・join()：Chord ネットワークに自分を追加する。

のノード及びオブジェクトに識別子が割り当てられており、・leave()：Chord ネットワークから退出する。

SHA-1 のハッシュアルゴリズムにより、均等に ID 空間に分布する機構となっている。
Plaxton 構造における、オブジェクト毎にそのネットワー
ク上の位置を知る。探索の際には当該ノードを頂点とする

tree 構造を逆に辿るというものである。この際の経路制御は、のルーティングステップでメッセージを、プレフィックスが各ノードと近隣ノードとの論理的なリンクを表す経路制御

最長一致する ID を選び出す処理は、上位から 1 行ずつ文字を参照する事により行われる。経路表のエントリには、与えを揃えていく処理に相当する。

られた目的地の識別子とプレフィックスが最長一致する近隣ノードに中継する事で最終的に目的地に到達する。
この方法では、N 個の可能な要素から成る名前空間で、識別子お基数を b として解釈する場合、最大でも logN ホップ
で目的のノードに到達でき、経路表のサイズは b・logN の固■ID が R***であるノード→

ID が RJ**であるノード→

ID が RJO*であるノード→

ID が RJOK であるノード

定サイズとなる。
これ以上のプレフィックス長の一致する key がない場合は、遅延を短縮し、帯域の有効活用を促進すると共にシステム

メッセージは現在のノードと同じ長さの key プレフィック

信頼性を向上する上で最も重要である。

スを共有するが、数として自身の持つ key より近いノード ID(通信の経路が長ければデータが失われたり、壊れる可能性を持つノードに転送を進める。

が増大するし、データやサービスが近傍に存在していれば、世界のほかの部分から分断されたとしてもアクセスできる)

Pastry ではノードに 128bit のハッシュ値から構成される
ノード ID が割り当てられる。そのノード ID は、どこか特5-2-1 Pastry アルゴリズム

定の中央サーバから割り当てられる ID ではなく、各ノードが独立に計算して取得する ID による。Join(参加) する際にノードの IP アドレスなどから暗号ハッシュをランダムに割り当てる。また、N 個のノードが存在する場合、logN ステ
ップ以下で与えられた key にメッセージを送信する事ができる。Plaxton アルゴリズムに従うルーティングテーブルとはまた別に、「leaf set」と「neighbor set」となる補助的なテーブルを保持している。leaf set については、当該ノードの近辺に存在するノードの ID を保持するための表である。
距離が近いノードへの経路を、通常の経路表とは別に一定数

図 5.2

Plaxtonにおけるルーティング例

保持し探索を効率化する役目を持つ。探索においては、まず始めに leaf set を参照するため、leaf set を適切に維持する

Pastry はマイクロソフト社とライス大学で開発された

過程はトポロジの適切な維持に重要な役目を果たす。テーブ

DHT の実装を目的とした P2P システムである。目的の ID

ル内で保持される対象ノード ID の数については実装時に設を探索するために、Plaxton のアルゴリズムを採用している。

定する事が可能である。

メッセージを目的の ID へルーティングするためには、目的

neighbor set には、ネットワーク内での物理的に近い距離の ID とプレフィックス長が最長一致した近隣のノードへ選にある対象ノードの ID を保持してる。ハッシュ値の論理空択し、そのノードを中継するといった処理を行う。

間上の距離とは別の尺度として、IP として近傍のノードの例えば、ノード KJFK を出発点として、ノード RJOK に到経路を保持している。leaf set 同様に実装時に設定を変更す達するためには以下の手順をたどる。具体的には、それぞれることが可能である。Plaxton と比較した際、IP としての物

理的距離の親和性をルーティングの際に取り入れることがているのが確認できる。

出来る点が、大きく異なる点である。以上より、例えば以下のようなルーティングを繰り返して目的のノードへ到達す・新規ノード X は neighbor set に関してノード A のものることになる。

を使用する。

(A) 対象とする key が、leaf set 内のノード ID が保持する範・Z は X に近いノード ID を持っているので、leaf set はノ囲に含まれているかを確認し、距離として最近接と考えられ

ード Z ものを使用する。

るノードに対してメッセージを転送する。
(B) leaf set 内に対象ノードの存在を確認できなかった際、保・次に、ルーティングテーブルを考慮する。最後にノード X

持するルーティングテーブルより転送を行うノー ドを探索

は作成し終えたテーブルを neighbor set・leaf set・routing

し、対象ノードへメッセージの転送を開始する。

table の作成に用いたノードに対して複製を送信する。複製(C) ルーティングテーブルにさえ、対象のノードを確認できを受信した ノードはその情報を元に自分のテーブルに更新なかった際、リーフセットの中から改めて自分よりは対象ノを行う。

ードに ID として距離の近接するノードを探索し、当該ノードに対してメッセージの転送を開始する。

反対に、離脱ノードが発生した場合はどうなのか。各のノ(D) ID として近接する ID が１つも存在しない際、自ら目的

ードは定期的に生存メッセージをテーブル内のノードに送ノードとなりうる。

信している。そして leaf set のノードの離脱の場合には leaf
set 内のノードに、neighbor set のノードの場合は neighbor

前述の通り、Pastry でルーティングに要するホップ数はset のノードに問い合わせを行い埋め合わせをする。また(1/b)logN 、 ル ー テ ィ ン グ ・ テ ー ブ ル の エ ン ト リ ー 数 は

routing table の場合には、例えば 1 行目にある A 列目のノ[(2b-1)/d]logN と考えられる。(但し、N は全ノード数とする)

ードが離脱した場合、1 行目の他のノードに問い合わせる。
その問い合わせを行ったノードの l 行目 A 列目を埋め合わ

5-2-2

Join

せに用いるノードにする。1 行目 A 列目が空の場合は(L+1)
行目のノードに問い合わせ、そのノードの l 行目 A 要素のノ

新規ノードが join する際、テーブルを更新し他のノードードで、離脱分のノードの埋め合わせを行う。

への通知をする必要がある。新規ノードは物理的近傍にあると仮定するノード A を記憶していた場合、自らノード ID を

Routeing table

自律的に決定しマルチキャストを用いて参加位置を判断す-0-*******

1-2-*******-3-*******

る。新規ノードのノード ID を仮に X とした場合、X と等し

01-1-******

1-2-******

1-3-******い key と共に join メッセージを転送しノード A に対して依10-0-*****

10-1-32102

210-3-*****

頼を行う。ノード X と数字的に最も等しいノードをノード Z

102-0-****

102-1-****

102-2-****

3とすると、join メッセージを受け取ったノード A と Z、及び1023-0-***1023-1-***1023-2-***

3

A と Z の間にあるノードはノード X にテーブルを送信する。

10233-0-**

110233-2-**

新規ノード X は送信されたテーブルを基にテーブルを次の0102331-2-*

方法で初期化する。つまり、ノード X の経路表構築であると1023310-0-

2

同時に、ノード A からノード Z の経路表の更新処理も兼ね

表 5.3 テーブル情報例

また、bamboo ディレクトリ下にある Makefile 内には、

5-3-1 BambooDHT

bamboo の home ディレクトリを規定する箇所がある。念のPastry アルゴリズムをベースにしたフリーな実装として

ため bamboo ホームディレクトリが、bamboo をインストー

は Bamboo と FreePastry が有名である。どちらも Java でルしているディレクトリ に設定されているかの確認を済ま

実装がされている。

BambooDHT は Pastry アルゴリズム

せておく必要がある。

をベースにしながら、そこに留まらず独自拡張も続けている
DHT システムだ。Pastry の派生と見なして考えることがで(2)動作のテスト

きるだろう。FreePastry は Pastry アルゴリズムの実装を提BambooDHT には正常なインストールや動作を確認するた

供することが目的である。そのため Pastry アルゴリズムのめの簡単なテストモジュールが下記ディレクトリに用意さ評価や研究が目的である場合には FreePastry が適している。

れている。表示されるメニューに従い複数のノードを立ち上

一方、DHT の開発参加や新機能の実装などが目的である場

げ、ノードステータスなどを確認する。

合は、BambooDHT を利用するのが適切であろう。
[*console*] BambooDHT の動作テスト
5-3-2 BambooDHT の実装$ cd /bamboo/test$ perl -w location-test-menu.pl

BambooDHT の実装方法をここに解説する。当報告書の執Menu:

筆時点で、正式にリリース番号がついているのはバージョン1.

Check node status

1.0.1 である。しかし、v1.0.1 のソースコードはとても古い

2.

Check object pointers

ため、今後、CVS の最新ツリーまたはスナップショットを3.

Check for exceptions

本報告書では、2006 年 3 月 34.

Start a node使うべきであると考える。

日の CVS スナップショット版を使っている。2004 年末以降、Bamboo のソースコードは Java1.5 ベースになっている。

Your choice: [4]Bamboo の最新版をコンパイルするには、JDK1.5 以降の要

Startinglocalhost:3630withgatewaylocalhost:3630.

件を満たす必要がある。Bamboo のコンパイルについては、

cfg=/tmp/experiment-22277-localhost-3630.Cfg

次のように環境変数 JAVAHOME の設定対応を行い make

log=/tmp/experiment-22277-localhost-3630.log

処理を実行するのみで完了される。

pid=22282(1)BambooDHT の公式サイトよりソースをインストールしYour choice: [4]コンパイル作業を行う。

/tmp/experiment-22277-localhost-3630.log:Tapestry:

4

1

ready
[*console*] BambooDHT のコンパイル方法/tmp/experiment-22277-localhost-3633.log:Tapestry:$ export JAVAHOME=/usr/local/1.6.0_07

ready$ tar zxf bamboo-cvs-2006-03-03.tgz[*console*](3)BambooDHT の基礎動作を確認する。

$ cd bamboo$ make[*console*]
BambooDHT を動作させるためにあたっては、BambooDHT

ネットワークを構成するノードひとつずつに設定ファイル[*console*] BambooDHT の実行例

を用意する必要がある。当コンフィギレーションファイルを$ bin/run-java bamboo.lss.DustDevil /tmp/node1 .cfg

通じ、ノードの BambooDHT への動作要件を定める。例え

Sandstorm: Ready

ば、エントリーポイントに該当するブートストラップノード

INFO bamboo.router.Router: Joined through gatewayの指定や、参加時の自身の IP アドレスやポート番号の指定

127.0.0.1:3630を行う。最もシンプルな設定ファイル例を次に示す。

Tapestry: ready[*console*]

ノードをもうひとつ起動して、このノードとネットワークを[*code*] シンプルな設定コンフィギレーションファイル例

構築することも可能になる。

<sandstorm>

2 つ目のノードを立ち上げるならば、前述の通り 2 つ目の<global>ノードの動作を定義するための別のコンフィギレーション<initargs>

ファイルを作成する必要がある。例えば、ローカルホストの

node_id localhost:3630 # このノードのエントリポイントで

ポート 3631 で 2 番目のノードを実行させるならば、設定コ

す。この場合 UDP の 3630 ポートを待つことになる。

ンフィギレーションファイルは以下の通りになる。

</initargs></global>[*code*] 2 番目のノードのコンフィグ例<stages><sandstorm><Network><global>class bamboo.network.Network<initargs></Network>

node_id localhost:3631<Router></initargs>

class bamboo.router.Router</global><initargs><stages>

gateway localhost:3630 # このノードが DHT に参加するた<Network>

めのブートストラップノードを指定する。

class bamboo.network.Network

digit_values 16</Network></initargs><Router></Router>class bamboo.router.Router</stages><initargs></sandstorm>[*code*]gateway localhost:3630 #
digit_values 16

ブートストラップノードに自分自身を指定した場合 1 台のノ</initargs>

ードだけのネットワークになる。2 つ目以降の別ノードがこ</Router>のノードを指定すると、ネットワークが広がっていく。上記</stages>の 設 定 フ ァ イ ル を /tmp/node1.cfg と し て 保 存 す る 。

</sandstorm>

BambooDHT を以下のコマンドで実行できる。

[*code*]このコンフィギレーションファイルを「/tmp/node2.cfg」とクに対して、通信プロトコルでアクセスするプログラミング

いうファイル名で保存したとすると、以下のコマンドで 2 番である。Web に例えると、BambooDHT のクラス API を使目のノードを動作実現させることが出来る。

うプログラミィングは Web アプリケーションサーバ上で行
うプログラミングであり、もう片方の後者は Web サービスにおいて API を呼び出すプログラミングであると考えられ[*console*] BambooDHT で 2 つ目のノード起動例

るだろう。当報告書では、BambooDHT のクラス API を使$ bin/run-java bamboo.lss.DustDevil /tmp/node2.cfg

用したプログラミング方法を例に説明を行う。DHT の key

Sandstorm: Readyをベースにした value の登録(put)と取り出し(get)を自779 INFO bamboo.router.Router: Trying to join through

動的に行う事を実現する。コード例は別紙(巻末)のよ

gateway 127.0.0.1:3630

うになり、「/Bamboo_home/src/test」ディレクトリに

131 INFO bamboo.router.Router: Joined through gateway「Pgbd.java」として保存した場合の例になる。

(127.0.0.1:3630, 0x19d5e887)「Pgbd.java」では次のような key と value を DHT ネ

Tapestry: readyットワークに登録する。この登録の可否は、以下のコ

163 INFO bamboo.router.Router: added 127.0.0.1:3630 to

マンドで確認できる。

leaf set
169 INFO bamboo.router.Router: added 127.0.0.1:3630 to・Put する Key：ld_pics

routing table

・Get する Key：ld_wireless[*console*]

・PutするValue：http://pics.livedoor.com/002/3JPG
・TTL:3600

2 番目のノードの経路表と leaf set に、1 番目 のノード[*console*] 登録項目の確認(localhost:3630)が追加されたことが確認できる。
一方、1 番目のノードのコンソール出力を見ると、その経路$ bin/run-java bamboo.dht.Get localhost 3632 ld_pics

表と leaf set に 2 番目のノード(localhost:3631)が追加された・

デバッグメッセージを見つけることができる。ノードは 2 つ・しかないが、DHT のネットワークを構築できたことになる。
この要領で設定ファイルを作成してノードを増やしていけば、理論上はいくらでも巨大な DHT ネットワークを構築が可能である。

5-3-3 BambooDHT プログラミング

BambooDHT プログラミングには主に 2 種類が想定できる。1 つは、BambooDHT のクラス API を使ったプログラ
ミングであり、DHT の機能を組み込んだアプリケーションを作ることができる。もう 1 つは、BambooDHT ネットワー

http://pics.livedoor.com/002/3JPG が表示される。

■ ファイルを１つエントリした後のノード状態

・Node1 の状態

・Node2 の状態[node info][node info]

Hostname:localhost

Hostname:localhost

IP : 127.0.0.1

IP : 127.0.0.1

port : 3630

port : 3631

ID : 0x19d5e887

ID : 0x76663e70

Current Strage:91 Byte

Current Strage:91 Byte

[Leaf Set]

[Leaf Set]

ip

port

ID

￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
127.0.0.13633

0x76663e70[Routing Table]
ip

port
3633

port

ID

￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
127.0.0.13633

0x19d5e887[Routing Table]ID￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
127.0.0.1

ip0x76663e70

ip

port

ID

￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
127.0.0.13633

0x19d5e887

6

今後の課題

の key では更新後のコンテンツを取得できないため、取得者はなんらかの手段で新しい key の知識を手に入れなくて以下に述べるような問題を認識しており、以後我々は、そはならない。

れら問題点を解決する手法を研究し、実験による評価およびそのため、従来の DHT はコンテンツを頻繁に更新するサー考察を行い、情報の爆発的な増加やコンテンツの多様化などビスには適していない。従って, 今後 DHT を実用化していに伴い、スケーラブルかつコンテンツの頻繁な更新にも耐え

くうえでこの問題が妨げとなることが考えられる。また、key

うる P2P ネットワークの構築を目指す。

や value の更新が発生する際には、都度の新しい key や
value の情報に関するオーバーレイネットワーク上での更新

一般にデータへの検索要求の発生頻度は Zipf[7]の法則に対応が必要となる DHT の特徴より、更新頻度の高い blog な従うことが知られている。一部のデータにアクセスが集中す

ど CGM サービスに適用する場合を仮定すると、その負荷はるというデータ要求の分布を示したという経験則で、アクセ極端に大きなものであると想定できるため、コンテンツ情報

スには大きな偏りがあることが実環境では起こっているこの更新取得時におけるトラフィクの最小限 にするための効とが WEB ページのアクセスランキングや、動画投稿サイト率性を向上させるための拡張課題を持つ。

の再生数など様々な事柄に当てはまる法則である。当現象については、自社 blog サービスなどでも同様の現象を確認で

7 まとめ

きる。
これらアクセス頻度の偏りによる一極的で不公平な負荷

各データに対するアクセス分布やネットワークトポロジなを想定し、要求データのアクセス頻度に応じて、複製配置確

どの環境情報や、ピアグループを意識したオーバーレイネッ

率を変化させ、確率的に複製配置を実施していくなど、アクトワークを構成することにより、システムの耐故障性や規模セスの集中負荷を分散させ、トポロジー全体としての安定性

拡張性、可塑性を改善できる余地がある。

と効率性を向上させるためのる DHT 発展的拡張課題を持つ。

デザイン上、サーバへの問い合わせが集中する箇所の存在を見直し、目的とするデータの検索性能を損なうことなく、
ストレージに発生する負荷をネットワーク全体に分散する事を可能にする手法を検 討する事を当報告書の次期検討課
題とし報告を終える。

k は総データ数。αはアクセス確率を決定するための Zipf
係数であり、この値が大きい程一部のデータが頻繁に要求さ[謝辞]れる事が分かっている。j はランクを示す。

本報告を行うにあたり、日ごろより日頃から議論させていた
だいている通信環境技術室の皆様に感謝する。

またコンテンツの更新においては、古いコンテンツを残しておいたまま新しいコンテンツを追加しているが、従来のDHT の研究ではコンテンツの取得・公開・削除の動作にばかり着目し、更新の動作への配慮が欠けている。例えば、更新前のコンテンツと更新後のコンテンツを同じ key に割り当てた場合、取得者はコンテンツを取得するまでそれらを判別できない。一方、異なる key に割り当てた場合には、元[参考文献][1] Ion Stoica, Robert Morris, David Karger, M. Frans
Kaashoek, Hari Balakrishnan (2001). “Chord: A scalable
peer-to-peer lookup service for internet applications”.
ACM SIGCOMM Computer Communication Review 31(4): 149 - 160. DOI: 10.1145/964723.383071[2] Pastry:Pastry : Scalable,decentralized lbject location
and routing for large-scale peer-to-peer systems(http://research.microsoft.com/~antr/PAST/pastry.pdf)[3] Bamboo：http://bamboo-dht.org/[4] Ion Stoica：
http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sig
comm.pdf[5] Freenet：http://freenetproject.org/[6] PLAXTON, C., RAJARAM, R., AND RICHA, A. W.
Accessing nearby copies of replicated objects in a
distributed environment. In Proceedings of the Ninth
Annual ACM Symposium on Parallel Algorithms andArchitectures (SPAA), June 1997.
[7]G. K. Zipf:“Human Behavior and the Principle of Least
Effort”, Addison-Wesley(1949).

[5-3-3

BambooDHT プログラミング例]

package test;

import java.io.*;import ostore.util.*;import bamboo.dht.*;
import bamboo.util.StandardStage;
import bamboo.lss.ASyncCore;
import bamboo.router.Router;
import seda.sandStorm.api.ConfigDataIF;
import java.security.MessageDigest;
import java.util.Random;
import java.math.BigInteger;

public class pgbd extends StandardStage {protected MessageDigest digest;
protected GatewayClient client;public void init(ConfigDataIF config) throws Exception {super.init(config);
try {digest = MessageDigest.getInstance("SHA");} catch (Exception e) {assert false;}
String client_stg_name = config_get_string(config, "client_stage_name");client = (GatewayClient)lookup_stage(config, client_stg_name);

acore.register_timer(1000, do_put_cb, null);}public ASyncCore.TimerCB do_put_cb = new ASyncCore.TimerCB() {public void timer_cb(Object user_data) {String key = "ld_pics";
String val = "http://pics.livedoor.com/002/3JPG";
bamboo_put_args put_args = new bamboo_put_args();
put_args.application = "my-test";
put_args.key = new bamboo_key();put_args.key.value = digest.digest(key.getBytes());
put_args.value = new bamboo_value();
put_args.value.value = val.getBytes();
put_args.ttl_sec = 3600;// [sec]client.put(put_args, curry(put_done_cb, put_args, null));}};public Thunk3<bamboo_put_args, Object, Integer> put_done_cb =new Thunk3<bamboo_put_args, Object, Integer>() {public void run(bamboo_put_args put_args, Object user_ctx, Integer put_res) {if (put_res.intValue() == bamboo_stat.BAMBOO_OK) {System.out.println("-----------------------------------------");
System.out.println("put success!");System.out.println("-----------------------------------------");
acore.register_timer(1000, do_get_cb, null);} else {System.out.println("DHT put failure. reason=" + put_res);}}};
Public ASyncCore.TimerCB do_get_cb = new ASyncCore.TimerCB() {public void timer_cb(Object user_data) {String key = "ld_wireless";bamboo_get_args get_args = new bamboo_get_args();
get_args.application = "my-test";
get_args.key = new bamboo_key();
get_args.key.value = digest.digest(key.getBytes());
get_args.maxvals = 1;
get_args.placemark = new bamboo_placemark();
get_args.placemark.value = new byte[] {};client.get(get_args, curry(get_done_cb, null));}};public Thunk2<Object, bamboo_get_res> get_done_cb =new Thunk2<Object, bamboo_get_res>() {public void run(Object user_ctx, bamboo_get_res get_res) {if (get_res.values.length > 0) {System.out.println("DHT get value is " + new String(get_res.values[0].value));} else {System.out.println("DHT not found");}}};}