ログインしてさらにmixiを楽しもう

コメントを投稿して情報交換!
更新通知を受け取って、最新情報をゲット!

分散ハッシュテーブル(DHT)コミュのリリース: Overlay Weaver

  • mixiチェック
  • このエントリーをはてなブックマークに追加

コミュ内全体

Overlay Weaver というソフトウェアをリリースしました。
コミュニティ: http://mixi.jp/view_community.pl?id=555162

オーバレイ構築ツールキット Overlay Weaver
http://overlayweaver.sf.net/index-j.html

コメント(24)

Overlay Weaver はオーバレイ構築ツールキットです。アプリケーション開発
に加えて、オーバレイのアルゴリズム設計もサポートします。

アプリケーション開発者に対しては、分散ハッシュ表 (DHT) やマルチキャス
トといった高レベルサービスに対する共通 API を提供します。この API を用
いることで、特定のトランスポートプロトコル、データベース、ルーティング
アルゴリズムに依存しないアプリケーションを開発できます。

Overlay Weaver は、ルーティングアルゴリズムとして Chord、Kademlia、
Pastry、Tapestry の実装を提供しています。ルーティング層の分割によって、
これらのアルゴリズムをたかだか数百ステップで実装することが可能となりま
した。ルーティング層は高レベルサービスの下位に位置し、ルーティングドラ
イバ、ルーティングアルゴリズム、およびメッセージングサービスから構成さ
れます。この分割によって、新規アルゴリズムの実装も容易になっています。
Overlay Weaver はまた、新たに実装したアルゴリズムを試験、評価、比較す
るためのエミュレータも提供しています。このエミュレータは数千の (仮想)
ノードを扱うことができ、大規模エミュレーションによるアルゴリズム間の公
正な比較を可能にします。

特徴:

- Java 5 で実装されています。
(IPv4 マルチキャストルータの一部は C です。)

- 複数のルーティングアルゴリズムの実装を提供しています:
Chord, Kademlia, Pastry, Tapestry。
iterative / recursive ルーティングを行う

- 2種類のルーティングドライバを提供しており、
任意のルーティングアルゴリズムと組み合わせて使うことができます。
(Kademlia の recursive ルーティング、を除く。)

- 分散環境エミュレータを提供しており、1 GB メモリの 32 ビットマシンで
4000 の (仮想) ノードをエミュレートできています。

- 通信層には 3種類の実装があります:UDP, TCP, エミュレータ実装。
UDP 実装は UDP hole punching を行います。

- 可視化ツール Messaging Visualizer を提供しています。
ノードと通信を動作中に可視化します。
エミュレータと実ネットワークの双方で動作します。

ウェブサイトには、スクリーンショットやデモも用意してあります。
御覧頂けますと幸いです。

本ツールキットを使ったアプリケーション開発、アルゴリズム研究、
テストベッド構築、運用等の活動を、可能な限りサポート致します。
御連絡、もしくは、ML への御参加を検討頂けますと幸いです。
かっこいいっすね。

僕らが作ってるのと共通してるところが幾つかあり
すごく共感できます。(まだリリースまでこぎつけて
ませんが)

やっぱり、しゅどうさんは凄いなー
大変恐縮です。

youkiさんには、ひそかにお世話になってます。
実はMACEDONの存在は、ここ(DHTコミュニティ)へのyoukiさんの書き込みで気づいたのだったりします。
あれともかなりカブるので、一瞬焦りました。

あと、IDEON WGの報告書を大変楽しませて頂きました。
あれだけ網羅的にまとまっている日本語の文章は、他にないのではないかと思います。
WIDE内限定というのがもったいないです。僕は読めたのでいいのだけど :)

RISSONの存在には、IDEON WG報告書で気づきました。
拙稿を読んでいただき恐縮です。

今年度のIDEON報告書の内容は掲載予定の僕の1件と、掲載済みの
斎藤さんの一件をあわせたものなので学会系にアクセスできる人は
わりと簡単に入手できるとおもいます。

さいきん事務仕事ばっかで実装おいつかないっす。

ツールキット系も出揃ってきたことだし、
オーバーレイ実装つかって面白いモノつくるプログラミング
コンテストとか、やったら面白そうですね。

誰か一緒にやりませんかー

5月〜9月あたりでいいから。。。
IDEON報告書の内容、掲載されたらぜひお知らせください。
というか、日本語ネイティブな技術者・研究者のレベルアップのためにも、ぜひどこかで宣伝を。

コンテスト、いいですね!
実装部門に加えて、アイディア部門も設けたりして。
structured (DHT他) に限らずとも、unstructured なライブラリでも何でも、それこそ Skype API を使ったアプリでも OK、とか。

参加の動機付けに、できれば賞品・賞金も欲しいところです。
どこか企業が乗ってくれるといいんですが。。
次回のDHTオフ会かP2P勉強会に優秀なプログラムをデモして欲しいですね!
個人的にはこれを使ったP2P-SNSを作って欲しい!と思いました。
> IDEON報告書の内容、掲載されたらぜひお知らせください。

つい先日、手もとに届きました:

門林雄基: "オーバレイ・ネットワーク", コンピュータソフトウェア, Vol.23, No.1, pp.15-23, 日本ソフトウェア科学会, January 2006
研究室に落ちてた↑を無事ゲットしました。
これから拝読させていただきます。
今日、指導教官から渡されました。
後期受験の問題ってこと?
Overlay Weaver 0.3 をリリースしました。

 Overlay Weaver コミュニティ
 http://mixi.jp/view_community.pl?id=555162

 Overlay Weaver
 http://overlayweaver.sf.net/index-j.html

OpenDHT/Bamboo 互換の XML-RPC なプロトコルで Overlay Weaver (の DHTシェル) に対して put/get/rm できるようになりました。
例えば、OpenDHT の User's Guide にある get.py, put.py, rm.py で操作できます。
DHTシェルを -x オプション付きで起動することで XML-RPC での制御が可能になります。

 OpenDHT: A Publicly Accessible DHT Service
 http://opendht.org/

 The Bamboo DHT
 http://bamboo-dht.org/
まともな (?) 複製 (replication) 機能を実装しました。

 [Overlay Weaver] トピック: 複製 (replication)
 http://mixi.jp/view_bbs.pl?id=10202521&comment_count=0&comm_id=555162
5月に研究発表で使ったスライドを公開しました。

 [Overlay Weaver] トピック: 資料
 http://mixi.jp/view_bbs.pl?id=10442652&comm_id=555162
0.5.6 をリリースしました。

 2007年 1月 6日
  Version 0.5.6 リリース。
   * 処理効率を向上させた。特にスレッドについて。
   * エミュレータのバグを修正。
    高負荷時にメッセージが配送されないことがあった。

 アナウンス:
 http://groups.yahoo.co.jp/group/overlayweaver/message/54
PlanetLab 上で Overlay Weaver を動かしてます。

本文はこちら:
http://looc.jp/?m=pc&a=page_fh_diary&target_c_diary_id=2235

何ヶ所にも同じ内容を貼る、というのもなんなので、
リンクだけにさせて頂きます。
ご不便をおかけします。
0.6 をリリースしました。

 2007年 3月 29日
  Version 0.6 リリース。
   * -x オプション付きの DHT shell (owdhtshell -x) が持っていた
    クロスサイトスクリプティング脆弱性を解消した。
   * DHT シェル, Mcast シェル, メッセージカウンタが
    アクセス制御リスト (ACL) を受け付けるようになった。
    --acl オプションで指定する。
   * 通信のタイムアウトを TCP のように計算するようにした。
   * UDP 通信層が、受信したデータグラムが壊れていたり部分的にしか
    受信できなかった場合を想定するようになった。

アナウンス:
http://groups.yahoo.co.jp/group/overlayweaver/message/72

脆弱性対応の所感とかなんとか:
http://www.shudo.net/diary/2007mar.html#20070329
Overlay Weaverを使わせていただいています。
ひとつ質問があります。

環境の異なる2つのマシン間(win,mac)で、put, getを使って検索を試しているのですが、片方のマシンからは同じキーで値が取れるのですが、同じ状況で逆の場合だと見つからない場合があります。
ちなみにルーティングアルゴリズムはChordで、ルーティングスタイルはIterativeです。
(他のルーティングアルゴリズムを試した場合、確率的にもう少し見つかりにくかった気がします)

よく分からないのは、ログの情報でnullでない値を返しています、と表示があるのにも関わらず、クライアント側で値が取得されていないところです。
そのような現象はいままでに報告されていますでしょうか?僕のコーディングミスだと良いのですが、、、

検索方法は普通にテストコードの中から取ってきたものを応用して使っています。

なにかご存知の方いらっしゃいましたら、コメントいただきたく思います。よろしくお願いします。
すみません。気づくのが遅れました。
ここはリリース情報を書き込むつもりで作ったトピックなので、僕自身はあんまり見てなかったりします。
問い合わせは ML に投げて下さるとありがたいです。

join 後に、経路表が完全に安定するまで、しばらく時間がかかります。それまでの間に put した場合にどうなるかは、アルゴリズムごとに違って、ここでは説明しきれないです。

手がかりの得方としてはこのメソッドが使えるのではないかと思います:
 RoutingResult DHT#getLastRoutingResult()
 IDAddressPair[] RoutingResult#getRoute()

最後に行った get なり put なり何なりで行われたルーティングについての情報を得られます。
getRoute() は経路を返します。
この経路が適切なものとなっているかを確認するといいのではないでしょうか。
0.7 をリリースしました。

 2007年 7月 28日
  Version 0.7 リリース。

   * ノードごとのスレッド数を大幅に減らした。
    例えばエミュレータ上で DHT ノードが占有するのは 2スレッドである。

   * エミュレータが、システムクロックのジャンプ (不連続かつ急激な増加) に
    適応するようになった。発生した場合、連続するスケジュールを一気に
    実行するのではなく、飛んだ時間だけスケジュールを遅らせて対処する。
    その際「[Clock jump ...]」といったメッセージを表示する。

   * OutOfMemoryError が発生した場合、JVM をただちに強制終了するようにした。
    スレッドを作成できなかった場合などに発生する。

   * Koorde (アルゴリズム) 実装のバグを修正。
    存在するノードの ID と同じ ID を目標としてルーティングを行うと、
    経路がループして TTL 切れが起きていた。

   * Jakarta Commons CLI ライブラリを 1.0 から 1.1 に更新した。

   * Jetty を 6.1.4 から 6.1.5 に更新した。

アナウンス:
http://groups.yahoo.co.jp/group/overlayweaver/message/88

コミュニティ Overlay Weaver:
http://mixi.jp/view_community.pl?id=555162
0.7.2 をリリースしました。

 2007年 8月 25日
  Version 0.7.2 リリース。

   * UPnP での NAT 越え (UPnP NAT Traversal) 機能を実装した。
    ノードは、NAT を発見し設定した後、
    自身が NAT 外側の IP アドレスを持つかのように振る舞う。

   * Berkeley DB Java Edition を 3.2.42 から 3.2.43 に更新した。

アナウンス:
http://groups.yahoo.co.jp/group/overlayweaver/message/93
0.7.4 をリリースしました。

 2007年 11月 4日
  Version 0.7.4 リリース。

   * 0.7.3 には、DHT への put、remove 要求に secret を付けると働かない、という問題があった。
    修正した。

   * 特定の場合に、存在するはずの値を DHT#get が返さない、という問題があった。
    修正した。

   * ルーティング結果に、各ノードごとの時刻を含めるようにした。
    DHT シェルのウェブインタフェース (owdhtshell -x) もそれを表示するようにした。

   * ホスト名の逆引きは、別にスレッドを立てて行うようにした。 DNS の返答待ちを避けるため。

   * Overlay Visualizer (owviz) とメッセージカウンタ (owmsgcounter) も、
    DHT シェル (owdhtshell)、Mcast シェル (owmcastshell) と同様に
    --no-upnp オプションを受け付けるようにした。

画像は、ウェブインタフェースの画面 (一部) をキャプチャしたものです。

アナウンス:
http://groups.yahoo.co.jp/group/overlayweaver/message/98
0.7.7 をリリースしました。

 2007年 12月 1日
  Version 0.7.7 リリース。

   * ノードごとのスレッド数を大幅に減らした。各ノードはスレッドを占有しなくなった。
    この変更によって、エミュレータが扱えるノード数が大幅に増えた。

画像は、PC 1台上での 3万ノード実験の様子です。

アナウンス:
http://groups.yahoo.co.jp/group/overlayweaver/message/106
0.7.11 をリリースしました。

 2008年 1月 3日
  Version 0.7.11 リリース。

   * コマンド行ツール owlistnodes を提供。
    オーバレイ上のノードを辿って、見つけたノードを一覧表示する。

   * エミュレータの挙動を変更した。タスクがなくなるか、残りのタスクがすべて
    scheduledaemon コマンドでスケジュールされたものとなった場合に終了する。

画像は、owlistnodes コマンドで PlanetLab 上のノード一覧を表示している際の様子です。

参考:
[mixi] コミュニティ: PlanetLab
http://mixi.jp/view_community.pl?id=1848312

アナウンス:
http://groups.yahoo.co.jp/group/overlayweaver/message/112
Overlay Weaver 0.8.3 をリリース致しました。

 http://overlayweaver.sf.net/index-j.html

0.8.2 で、"collective routing" という新機能を実装しました。
これは、複数のルーティング要求を集合的に扱う機能で、
通信するメッセージ数を減らし、ルーティングにかかる時間を短縮します。
具体的には、複数のルーティングにまたがって、
送信先が同一である要求を 1つのメッセージにまとめます。

 2008年 5月 3日
  Version 0.8.3 リリース。

   * DHT#put() が、事前に DHT#setTTL() と DHT#setHashedSecret() 呼び出しで
    設定された TTL と secret を使うようになった。
    DHTシェルにも "setttl" と "setsecret" コマンドを用意した。

   * DHT#put() と DHT#remove() が、 1つのキーに対して複数の値を
    受け付けるようになった。

   * DHT#put() と DHT#remove() が、複数の put/remove 要求メッセージを、
    宛先が同一ノードの場合に、まとめるようになった。
    これによってメッセージ数が減る。

 2008年 4月 28日
  Version 0.8.2 リリース。

   * collective routing を実装した。

   * DHT シェルの put, get, remove コマンドが、
    一度に複数の key-value ペアを受け付けるようにした。

   * recursive ルーティングのバグをいくつか修正した。

   * Pastry でのルーティングの成功率を向上させた。経路表や leaf set の
    どれかにノードを追加する際、他の表にも追加するようにした。
    ルーティングでのループ発生を抑えた。

   * Berkeley DB Java Edition を 3.2.74 から 3.2.76 に更新した。

 2008年 4月 2日
  Version 0.8.1 リリース。

   * Chord と Koorde でのルーティング (例: DHT への put や get) の
    成功率を向上させた。特に経路表が未成熟な状況で。

   * recursive ルーティングでメッセージが消失した場合、
    ルーティング要求に返答が戻らない、という問題に対処した。

   * Jetty を 6.1.8 から 6.1.9 に更新した。

アナウンス:
http://groups.yahoo.co.jp/group/overlayweaver/message/115

ログインすると、みんなのコメントがもっと見れるよ

mixiユーザー
ログインしてコメントしよう!

分散ハッシュテーブル(DHT) 更新情報

分散ハッシュテーブル(DHT)のメンバーはこんなコミュニティにも参加しています

星印の数は、共通して参加しているメンバーが多いほど増えます。