* DHTの実装
** Pastryの実装
前号でDHTの理論と具体的アルゴリズムのひとつであるPastryを説明しました。今回は、 DHTの具体的な実装を見て、サンプルコードを説明します。Pastryアルゴリズムをベースにしたフリーな実装としては、FreePastryと Bambooが知られています(*脚注)。どちらもJavaによる実装です。両者の違いを説明します。FreePastryはPastryアルゴリズムの忠実なフリー実装を提供することが目的です。Pastry本家のWebサイト<http://research.microsoft.com/~antr/Pastry/> からもリンクがあり、両者の補完関係が推測できます。前号で説明したようにDHT自体はキーをベースにした探索という低レベルの機能のみを提供するものです。Pastry研究グループは、Pastry上で動くミドルウェアを研究、提案しています。例えば、分散ストレージシステムのPASTや、分散メールシステムのePOSTなどです。FreePastryはこれらのミドルウェアのフリーな実装基盤にもなっています。一方、BambooはPastryアルゴリズムをベースにしながら、そこに留まらず独自拡張も続けています。ソフトウェア的にはPastryの派生と見なす方が適切かもしれません(*脚注)。
FreePastry とBambooは、どちらもBSD風ライセンスで提供されています。Pastryアルゴリズムの評価が目的であったり、Pastryに対する研究提案を行いたいのであれば、FreePastryを使うのが良いでしょう。もし、DHTの開発への参加や、名前にこだわらずに新しい機能の実装などに興味があれば、Bambooが良いと思います。私見ですが、FreePastryが大学の研究開発なのに対し、Bambooは開発コミュニティ的な開発体制のようです。本記事ではBambooを取り上げます。

[*footnote*]
+ FreePastry <http://freepastry.rice.edu/FreePastry/>
+ Bamboo <http://bamboo-dht.org/>
+ ePOST <http://www.epostmail.org/>

[*footnote*] Pastryの使える部分を取り込んだ、と言う方がより適切かもしれません。


** Bambooのコンパイル
原稿執筆時点で、Bambooの配布ソースコードで正式にリリース番号がついているのはバージョン1.0.1です。しかし、v1.0.1のソースコードはとても古いので、CVSの最新ツリーまたはスナップショットを使うことをお勧めします。本記事では、2005年7月1日のCVSスナップショット版を使います。2004年末以降、BambooのソースコードはJava1.5ベースになっています。これは、Java1.5でも動くというレベルではなく、 Java1.5のJDKでしかコンパイルできないというレベルです(*脚注)。Bambooの最新版をコンパイルするには、JDK1.5以降が必要です。 JDK1.5以降のインストールの説明は省略します。Webサイトや書籍などを参考にしてください。Bambooのコンパイルは、次のように環境変数 JAVAHOMEを適切に設定後、makeを実行するだけです。

[*footnote*] Java1.5のGenerics機能を使っています。

[*console*] Bambooのコンパイル方法
$ export JAVAHOME=/usr/local/jdk1.5.0_04
$ tar zxf bamboo-cvs-2005-07-01.tgz
$ cd bamboo
$ make
[*console*]


** テストコードの実行
Bamboo のテストコードを実行して、実際に動作することを確認しましょう。以下、実行例を見やすくするために、Bambooのソースツリーの先頭パスをセットした環境変数BAMBOO_DIRを仮定します。特に断りが無い限り、実行例はソースツリーの先頭で実行しています。
テストコードの実行には設定ファイルが必要です。Bamboo(DHT)ネットワークを構成するノードひとつずつに設定ファイルを用意します。最もシンプルな設定ファイル例を次に示します。

[*code*] 最もシンプルな設定ファイル例
# 注意: XML風フォーマットですがXMLではありません。#以降はコメントです。
<sandstorm>
<global>
<initargs>
node_id localhost:3630 # このノードのエントリポイントです。UDPの3630ポートを待ちます。
</initargs>
</global>
<stages>
<Network>
class bamboo.network.Network
</Network>
<Router>
class bamboo.router.Router
<initargs>
gateway localhost:3630 # このノードがDHTに参加するためのブートストラップノードを指定します。自分自身を指定すると1台のノードだけのネットワークになります。2つ目以降の別ノードがこのノードを指定すると、ネットワークが広がっていきます。
digit_values 16 # Pastryアルゴリズムの1digitを決める整数パラメータbです(2のb乗を指定)。整数パラメータbに関しては前号記事を参照してください。bの推奨値4(bit)を使う場合、digit_valuesに2の4乗である16を指定します。
</initargs>
</Router>
</stages>
</sandstorm>
[*code*]

上記の設定ファイルを/tmp/bamboo1.cfgとして保存したとします。次のようにBambooのテストコードを実行してください。

[*console*] Bambooのテストコードの実行例
$ bin/run-java bamboo.lss.DustDevil /tmp/bamboo1.cfg
...デバッグメッセージの後、次のように出力があれば実行は成功しています。
Sandstorm: Ready
2005-07-28 03:45:32,238 INFO bamboo.router.Router: Joined through gateway 127.0.0.1:3630
Tapestry: ready
[*console*]

ノードをもうひとつ起動して、このノードとネットワークを構築してみましょう。設定ファイルで変更するべき部分はnode_idだけです。ポートを3631にすると、設定ファイルは次のようになります。

[*code*] 2番目のノードの設定ファイル例
<sandstorm>
<global>
<initargs>
node_id localhost:3631
</initargs>
</global>
<stages>
# 省略。1番目のノードと同じにしてください
</stages>
</sandstorm>
[*code*]

この設定ファイルを/tmp/bamboo2.cfgというファイル名で保存したとします。実行してみましょう。

[*console*]
$ bin/run-java bamboo.lss.DustDevil /tmp/bamboo2.cfg
...デバッグメッセージの後、次のように出力があれば実行は成功しています。0x19d5e887の部分は実行ごとに異なります。
Sandstorm: Ready
2005-07-28 03:48:09,779 INFO bamboo.router.Router: Trying to join through gateway 127.0.0.1:3630
2005-07-28 03:48:10,131 INFO bamboo.router.Router: Joined through gateway (127.0.0.1:3630, 0x19d5e887)
Tapestry: ready
2005-07-28 03:48:10,163 INFO bamboo.router.Router: added 127.0.0.1:3630 to leaf set
2005-07-28 03:48:10,169 INFO bamboo.router.Router: added 127.0.0.1:3630 to routing table
[*console*]

2 番目のノードの経路表とleaf setに、1番目のノード(localhost:3630)が追加されたことが分かります(Pastryの経路表とleaf setに関しては、前号を参照してください)。一方、1番目のノードのコンソール出力を見ると、その経路表とleaf setに2番目のノード(localhost:3631)が追加されたデバッグメッセージを見つけることができるはずです。ネットワークキャプチャソフトを動かしていれば、UDPのポート3630と3631の間でのパケットのやりとりが見えます(*脚注)。ノードは2つしかありませんが、DHTのネットワークを構築できました。

[*footnote*] 起動直後だけではなく、定期的にメッセージを交換します。相手のノードがダウンしたことも数10秒のオーダーで検出します。

この要領で設定ファイルを作成してノードを増やしていけば、理論上はいくらでも巨大なDHTネットワークを構築可能です。新規に参加するノードは、既存ノードのどれかひとつだけをブートストラップノードとして知っておくだけで充分です。本誌の読者であれば、設定ファイルの自動生成スクリプトを簡単に書けるはずですが、Bambooの配布内にそのようなツールがあるので、テスト目的であればそれを使いましょう。次のようにtestディレクトリの下の location-test-menu.plスクリプトを実行してください。メニュー4.のStart a nodeを選択すると、ノード設定ファイルが新規に作成され、新規ノードが起動します。

[*console*] location-test-menu.plコマンドの実行例
$ cd $BAMBOO_DIR/test
$ ./location-test-menu.pl
Menu:
1. Check node status
2. Check object pointers
3. Check for exceptions
4. Start a node
5. Stop a node
6. Quit
Your choice: [4]
[*console*]


** 状態表示
Bamboo ノードには、HTTP経由で状態を問い合わせる機能があります。上記のlocation-test-menu.plスクリプトで、複数のノードを起動した後、"http://localhost:3631"をWebブラウザでアクセスしてみてください。図のようにノードの情報が表示されます。経路表や leaf set内の他のノードにはリンクがあるので、Webブラウザでリンクを辿ることが可能です。図では、このノードの経路表(routing table)に3ノード、leaf setに6ノードあることが見て取れます。前号でいくつか経路表の例を挙げましたが、今回の図ではパラメータbの値が異なります。前号では主にパラメータ bの値は4でしたが、今回の図では1です。つまり1-digitが1-bitです。経路表のlevelは、ノードIDのprefixの一致長を示しています。bit単位でprefix一致長を確認すると、それぞれのlevelの行にそのノードIDが入る仕組みを理解できるでしょう。

[*image*] HTTP経由の状態表示の図 (bamboo-status.png))

ノードのトポロジをグラフ表示するツールがあります。次のようにbamboo.vis.Visを実行してください。

[*console*] グラフ表示ツールの実行例
$ bin/run-java bamboo.vis.Vis http://localhost:3631
[*console*]

[*image*] グラフ (bamboo-vis.png)

ノードは青い点で表示されています。ノードをクリックして選択すると黄色くなります。そのノードのノードIDや経路表、leaf setなどをビジュアルに表示可能です。図では、ノード(0x19d5e887)の経路表を表示しています(赤い矢印)。0xc0000000をキーにして探索を出した時の探索コマンドの流れが、紫の矢印で示されています。これを見ると、ノード(0x19d5e887)は経路表の中から最も近いと思われるノードに探索コマンドを投げていることが分かります。受けたノードは、経路表もしくはleaf setを参照して、より近いノードへ探索コマンドを投げます。ノードの総数が少ないのでホップ数は2です。ただし、前号で説明したように、ノードの総数に対して探索のホップ数はlogオーダーで効いてくるので、ノード数が増えるわりには、ホップ数はあまり増えません。


** 動作確認
location -test-menu.plスクリプトでいくつかのノードを動作させた状態で動作確認を行ってみましょう。それぞれのノードは、3つのネットワークのポートをlistenしています。ひとつはUDPのポートで、設定ファイルのnode_id localhost:3630のように指定されている部分です。DHTの探索コマンドなどをルーティングするために使われるポートです。既に説明したようにHTTPを受け付けるポートもあります。これは状態の問い合わせだけではなく、後述するXML-RPCというHTTP上のRPCも受け付けます。この TCPのポートは設定ファイルに明示されていませんが、UDPのポート番号にプラス1したポートでlistenします。もうひとつ、設定ファイルの <Gateway>で指定されるポートがあります(*脚注)。これはSun-RPCのコマンドを受け付けるポートです。Sun-RPCも XML-RPCも、それぞれDHTに対するネットワークAPIを提供します。最小のAPIは、put(キーと値のペアの登録)とget(キーをベースにした値の獲得)のふたつです。これらを簡単に試すには、次のようにbamboo.dht.Putとbamboo.dht.Getを実行します。内部的には、 Sun-RPCの通信プロトコルを使っています。

[*console*] DHTの動作確認例
fooというキーでbarという値をDHTネットワークに登録します。ttlを300秒にしているので、300秒後にネットワークから消えます。
$ bin/run-java bamboo.dht.Put localhost 3632 foo bar 300

fooというキーでDHTネットワークを探索します。上のコマンドから300秒以内に行えば、barという値を取得できます。
$ bin/run-java bamboo.dht.Get localhost 3632 foo
[*console*]


[*footnote*] gatewayというキーワードが、設定ファイルの中で異なる意味で2ヶ所に使われています。ひとつはSun-RPCの待ち受けポートの意味です。もうひとつは既に説明した<Router>内でブートストラップノードを指定するキーワードです。注意してください。


** Bambooプログラミング
Bamboo プログラミングには主に2種類あります。ひとつは、BambooのクラスAPIを使ったプログラミングです。DHTの機能を組み込んだアプリケーションを作ることができます。もうひとつは、Bambooネットワークに対して、通信プロトコルでアクセスするプログラミングです。Webに例えると、前者は Webアプリケーションサーバ上のプログラミングに相当し、後者はWebサービスのAPIを呼び出すプログラミングに相当します(*脚注)。DHTをサービスとして見ると、インターフェースは値の登録とキーをベースにした探索のみなので、ディレクトリサービスを利用するプログラミングと見なす方が適切かもしれません。既に説明したように、Bambooが提供する通信プロトコルはSun-RPCとXML-RPCです。通信プロトコルベースのサービスを利用するプログラミングは、次節のOpenDHTと合わせて説明します。この節は、BambooのクラスAPIを使ったプログラミングを説明します。

[*footnote*] Bambooノード自体が探索コマンドを発行するクライアントとしても振る舞うので、2種類のプログラミングはWebほど質的な差はありません

前節に実行したbamboo.lss.DustDevilは、BambooAPIのフレームワーク相当の機能を持っています(*脚注)。本記事は、 bamboo.lss.DustDevilに機能を組み込む形のプログラミングの説明をします。Bambooプログラミングの特徴は非同期IOとイベントドリブンです。最も単純な例として、タイマーイベントで駆動するサンプルコードを示します(Timer.java)。以下、説明を簡単にするために、サンプルコードは、$BAMBOO_DIR/src/my/ディレクトリの下に置くことを仮定します。環境変数CLASSPATHを設定してコンパイルする例を示します。

[*footnote*] かなり原始的なフレームワークです。

[*code*] Timer.java (別ファイル)

[*console*] コンパイル方法
$ cd $BAMBOO_DIR/src/my
$ export CLASSPATH=$BAMBOO_DIR/src/:`echo $BAMBOO_DIR/lib/*.jar|sed -e 's/ /:/g'`
$ javac Timer.java
[*console*]

bamboo.lss.DustDevilの設定ファイルで、クラス名と初期化引数を指定します。次のような設定ファイルを作り、node.cfgとして保存してください。

[*code*] node.cfgの例
<sandstorm>
<global>
<initargs>
node_id localhost:4630 # 空いているポート番号を指定してください。
</initargs>
</global>
<stages>
<My> # このMyは任意の名前です。設定ファイル内のstageを一意に識別できれば良いだけです。
class my.Timer # クラス名です。
<initargs> # my.Timerオブジェクトの初期化引数です。ソースコードとの対応関係を確認してください。
intval 3
msg foobar
</initargs>
</My>
</stages>
</sandstorm>
[*code*]

次のように実行してください。3秒ごとにfoobarというメッセージがコンソールに表示されるはずです。

[*console*] 実行方法
$ cd $BAMBOO_DIR
$ bin/run-java bamboo.lss.DustDevil node.cfg
[*console*]

Timer.java の中身を見てみましょう。Timerクラスはbamboo.util.StandardStageから派生しています。init()メソッドを見ると、設定ファイルの初期化引数の読み込みを行っていることが分かると思います。DustDevil(フレームワーク)は、設定ファイルを読み StandardStageから派生したクラスのインスタンスを作り初期化します。メンバ変数acoreは、イベントドリブンを成り立たせるイベントループを担うオブジェクトです。Timer.javaでは、acore::register_timer()メソッドを呼び、タイマー用のコールバック関数を設定しています。value_obj_tクラスは、コールバック関数にコンテキスト引数を渡すためだけに存在します。

もう少しネットワーク的に意味のあるコード例を示します(Lookup.java)。

[*code*] Lookup.java (別ファイル)

設定ファイルをゼロから作るのは大変なので、既に紹介したlocation-test-menu.plスクリプトが自動生成する設定ファイルをベースにすることをお奨めします。元となる設定ファイルの<stages>の中に、次のような行を書き加えてください。実行は今までと同様に行ってください。

[*code*]
<MyLookup> # このMyLookupは任意の名前です。設定ファイル内でstageを一意に識別できれば良いだけです。
class my.Lookup # クラス名
</MyLookup>
[*code*]

Lookup.java の中身を見てみましょう。bamboo.router.Routerオブジェクトを取得しています。このRouterは、前号で説明したPastryの経路表やleaf setの機能オブジェクトと考えてください。後で出るbamboo.dhtクラスパッケージが、bamboo.routerクラスパッケージの上位に DHTの操作、つまりキーをベースにしたgetとputおよびremoveを提供するモジュール関係になっています。
Lookup.javaでは、Routerオブジェクトのlookup()メソッドを呼び出しています。lookupのキーは意味の無い乱数で作っています。第2引数でイベント用のコールバック関数を指定していることに留意してください。lookup()メソッドの第3引数はアプリが渡す任意コンテキストです。サンプルなので、単に現在時刻を渡しています。ノードがDHTネットワークに参加していれば、lookupの探索コマンドはDHT上をルーティングされ適切なノードに到達します(前号記事参照)。探索キーに対応するノードを発見すると、コールバック関数が呼ばれます。まだDHT層(キーと値のペアの登録と探索)は見ていないことに注意してください。ここでやっていることは、言わばノードの探索です。実行して結果を確認してください。

いよいよ、DHTのキーをベースにした値の登録(put)と取り出し(get)を行います。コード例はDht.javaのようになります。

[*code*] Dht.java (別ファイル)

設定ファイルの<stages>に、次のような行を付け加えてください。

[*code*]
<GatewayClient>
class bamboo.dht.GatewayClient
<initargs>
gateway localhost:3632 # 最初に探索コマンドを投げるSun-RPCの口を指定します。同じ設定ファイル内の<Gateway>stageのport引数と同じポートを指定すれば、ローカルノードから探索を開始することを意味します。
</initargs>
</GatewayClient>

<MyDHT> # このMyDHTは任意の名前です。設定ファイル内でstageを一意に識別できれば良いだけです。
class my.Dht
<initargs>
client_stage_name GatewayClient
</initargs>
</MyDHT>
[*code*]

location-test-menu.plスクリプトが生成する設定ファイルを見ると、次のような行があります。

[*code*]
<Gateway>
class bamboo.dht.Gateway
<initargs>
debug_level 0
port 3632
</initargs>
</Gateway>
[*code*]

このport 3632の指定は、DHTのコマンドを受け付けるSun-RPCのポート番号を意味しています。そして、今回新たに加えた< GatewayClient>は、このポートとRPCセッションを行うクラスの指定です。Dht.javaでは、 bamboo.dht.GatewayClientクラスのオブジェクトを生成して、put()やget()のメソッドを呼び出しています。それぞれの呼び出しで、コールバック関数とアプリ側のコンテキスト引数が指定されています。コールバック関数は、curry()という見慣れない形でくるまれています (*脚注)。curryは、関数と引数の積み方を合わせて関数オブジェクトを作るおまじないと思ってください。

[*footnote*] 関数型言語のカリー(curry)化をJava1.5のGenericsで実装しています。Javaでのカリー化について詳しく知りたい人は、http://bamboo-dht.org/async-tutorial/async-tutorial.pdf を参照してください。

Dht.javaでは次のようなキーと値をDHTネットワークに登録します(ttl=300を指定しているので、300秒で消えます)。

[*code*]
String key = "p2p";
String val = "/ascii/unixmagazine/p2p.pdf";
[*code*]

登録ができているかは、前節の動作確認で使ったサンプルで確認できます。

[*console*] 登録項目の確認
$ bin/run-java bamboo.dht.Get localhost 3632 p2p
/ascii/unixmagazine/p2p.pdf ...が表示されるはず
[*console*]


* OpenDHTでDHTを体験
** planet-lab
今まで説明した実験は、理論上は何百万台のPCが作るP2Pネットワーク上でも動作します(*脚注)。P2Pの特性上、1台から始めて次々にノードをつなげていけばネットワークを拡張可能です。そうは言っても、個人が、百や千のオーダーのPCを用意することは簡単ではありません。一方、組織であっても、 LAN内に閉じた理想的なネットワークを用意するだけのことが多いでしょう。このような動作環境は、P2Pが適用されるであろう、全体を集中管理するサーバが無く、不意にノードが参加や離脱を行う実環境とは差がありすぎます。このような課題に対し、インテルやUSの大学が中心となり、planetlabというネットワーク実働環境を提供しています。このplanetlab上でBambooネットワークが稼働しています。このネットワークはOpenDHTと呼ばれています。

[*footnote*] 実際に何百万台で稼働するには、様々な実装や運用の工夫が必要でしょう。

[*image*] http://www.planet-lab.org/ のWebサイト (別ファイル: planetlab-site.png)


** OpenDHTにアクセス
OpenDHTのWebサイトはhttp://opendht.org/ です。
Bamboo は通信プロトコルとして、Sun-RPCとXML-RPCが利用できます。前節で動作確認に使ったbamboo.dht.Putと bamboo.dht.GetはSun-RPCでDHTの機能を呼び出しています。ここでは、より単純なXML-RPCを使った例を示します。
XML-RPCは次の例のように、メソッド名とメソッドに積む引数をXMLフォーマットに(かなり原始的に)シリアライズします。このXMLメッセージをHTTPに載せてリモートメソッドを呼び出します。

[*code*] XML-RPCの例
XML-RPCの例(HTTPのPOSTメソッドのリクエスト)
<?xml.version='1.0'?>
<methodCall>
<methodName>get</methodName>
<params>
<param><value><base64>3iYscE/+NLuqzSMyAQXickdc+Is=</base64></value></param>
<param><value><int>10</int></value></param>
<param><value><base64></base64></value></param>
<param><value><string>get.py</string></value></param>
</params>
</methodCall>

HTTPのレスポンス
<?xml.version="1.0" encoding="ISO-8859-1"?>
<methodResponse>
<params>
<param><value><array><data><value><array><data><value><base64>aGFwcHktaGFja2luZw==</base64></value></data></array></value><value><base64></base64></value></data></array></value></param>
</params>
</methodResponse>
[*code*]

ここではBambooの配布ソースに含まれているPythonスクリプトを使った例を示します。

[*console*] XML-RPCのPythonスクリプトの実行例
unix-magazineをキーにhappy-hackingという値をOpenDHTに登録しています。ttlは300秒なので、300秒後には消えます。
$ $BAMBOO_DIR/put.py http://alice.cs.princeton.edu:5851/ unix-magazine happy-hacking 300
Success

unix-magazineをキーにOpenDHTから値を探索します。上のコマンドから300秒以内であれば、happy-hackingという値を引けます。別の値があれば、値は複数返ります。
$ $BAMBOO_DIR/get.py http://alice.cs.princeton.edu:5851/ unix-magazine
happy-hacking
[*console*]

http://alice.cs.princeton.edu:5851 はOpenDHTで動作している1ノードです。24時間365日稼働している保証はありません。現在動作中のノードの一覧は、OpenDHTのサイトで確認可能です。P2Pの特性で、ノードが参加や離脱を繰り返しても、サービスは停止しません。このようにOpenDHTのサービスを呼び出すだけの利用であれば、ユーザ登録など面倒な手続きは不要です。