OW 0.7.7のスレッド

[Miko Yoshida]

首藤さん

技術フェチ日記とOWのアナウンス↓を見て気付いたのですが、
http://groups.yahoo.co.jp/group/overlayweaver/message/106

Overlay Weaver のエミュレーションでノード単位にスレッドを消費すること
がなくなったんですね。
これはニュースじゃないですか。

技術的には、イベント駆動アーキテクチャになったのか、とか気になっており
ますが。。

---
吉田　幹 　y...@bbr.jp

[Kazuyuki Shudo]

吉田さん、首藤です。

> Message-Id: <20071204163635.8308B6A1000E1614@px-2>
> From: Miko Yoshida <mik...@mx5.canvas.ne.jp>
> Date: Tue, 04 Dec 2007 16:37:02 +0900

> 技術フェチ日記とOWのアナウンス↓を見て気付いたのですが、
> http://groups.yahoo.co.jp/group/overlayweaver/message/106
>
> Overlay Weaver のエミュレーションでノード単位にスレッドを消費すること
> がなくなったんですね。
> これはニュースじゃないですか。

そうなんですよ。
自分としては大ニュース :) です。

PC 1台 (Linux / x86) で動作させられるノード数が、ずいぶん増えました。

OW 0.7 より前: 4,000 ノード
OW 0.7 以降: 8,000 ノード
OW 0.7.7 以降: それ以上

> 技術的には、イベント駆動アーキテクチャになったのか、とか気になっており
> ますが。。

変更していくうちに、イベント駆動っぽくなってきました。

当初、Overlay Weaver では、
ノード数に比例するスレッドが動いてしまう (*1) ことの言い訳として、
ルーティングアルゴリズム (Chord とか) のプログラミングを
自然にできる (*2) ようにするためには止むを得ない、
と主張しておりました。

(*1) ということは、1台で動作可能なノード数が、
OS やプロセスがサポートするスレッド数に制限される。
(*2) 含 スレッドを作ることも自由。

このあたりが、シミュレートとエミュレートの違いである、
という説明をしておりました:

Means for Peer-to-Peer Research (スライド)
http://www.shudo.net/publications/DAS-P2P-2007/

・ノード群の『シミュレート』
p2psim とか OverSim とか。

・環境 (ネットワークとか) の『エミュレート』
Overlay Weaver はこちら。

実環境と同じ (ノードの) プログラムを動かせるが、
どうしても OS のリソース (プロセスやスレッド等) を食うため、
ホストできるノード数は制限される。

ところが、Overlay Weaver で、スレッド数を削減していった結果、
ノードが占有するスレッドを 0 にできてしまいました。

では、イベント駆動か? というと、まだ違う気がしてます。
依然、タイマがあって、指定した時刻にイベント (put とか get とか) を起こす
という方式を採ってます。
スレッドは、必要に応じて作られます。

タイマも、ある理由から自作したので、
イベント発生のタイミングを調整すれば、
2倍速エミュレーション、3倍速エミュレーションということも
できそうではあります。

ただ、イベントの連鎖を処理し終えたら、次のイベントを処理...
という逐次的に処理していくことが可能なようにはできてません。
なので、イベント駆動ではないのだろう、と思ってます。
でもこれも、スレッド数を 1 に制限してしまえば、
イベント駆動と同じになるのかもしれません。

スレッド数を減らしていく過程で、ルーティングアルゴリズムの既存実装
(Chord, Koorde, Kademlia, Pastry, Tapestry) には、
若干、自然ではない記述法を入れてしまってます。

最初は、例えば Chord の stabilization のようなデーモン的な処理は、
スレッドを作って、ループを回して、ループの中では毎回 sleep して、
という (自然な) 書き方をしてました。
今は、1回の処理が終わったら、
次回の処理をスケジュールする (起動をタイマに依頼する)
という書き方になってます。

とはいえ、自然な書き方でも (スレッドを食いますが) 動きます。
また、両スタイルはフラグ 1つで切替えられるくらい、
コードにはほとんど違いがないです。

スレッドを使った自然 (?) なプログラミングスタイルと
イベント駆動のスタイルは、案外近かったのだなあ、と感じてます。
このあたり、何か整理できるといいな、と夢想してます。

首藤一幸

[Daishi Kato]

At Tue, 04 Dec 2007 18:56:10 +0900 (JST),

Kazuyuki Shudo <20...@shudo.net> wrote:
> タイマも、ある理由から自作したので、
> イベント発生のタイミングを調整すれば、
> 2倍速エミュレーション、3倍速エミュレーションということも
> できそうではあります。

びみょー。
前に首藤さんとお話したときも、
シミュレーションとエミュレーションの定義が話題になりましたね。
私は明確な定義はないとは思ってますが、
倍速ができるならシミュレーションの方がしっくりきますね。

--daishi

[KOBARA Makoto]

首藤さん、みなさま。
こんばんは。
小原です。

首藤さんの投稿に対して質問があります。

> ところが、Overlay Weaver で、スレッド数を削減していった結果、
> ノードが占有するスレッドを 0 にできてしまいました。
>
> では、イベント駆動か? というと、まだ違う気がしてます。
> 依然、タイマがあって、指定した時刻にイベント (put とか get とか) を起こす
> という方式を採ってます。
> スレッドは、必要に応じて作られます。

これは(「必要に応じて作られる」というのは)、指定した時刻で発行したイベント
を処理するときに、そのイベントの発行対象となるノードごとに処理用スレッドを
起動する(つまり常時起動はしていないけどイベント処理時に作られて、処理
が完了したらスレッドを終了させる)、という意味でしょうか。

それとも、
イベント処理用のスレッドが1本イベント待ちしていて(あるいはスレッドプール
が待機していて)、キューからイベントを取り出して処理する、ということでしょうか。

----------------------------------------
KOBARA Makoto
kobara...@gmail.com

[Kazuyuki Shudo]

小原さん、首藤です。

> Message-ID: <a2334423-6d86-4dc4...@b40g2000prf.googlegroups.com>
> From: KOBARA Makoto <kobara...@gmail.com>
> Date: Tue, 4 Dec 2007 07:59:21 -0800 (PST)

> > ところが、Overlay Weaver で、スレッド数を削減していった結果、
> > ノードが占有するスレッドを 0 にできてしまいました。
> >
> > では、イベント駆動か? というと、まだ違う気がしてます。
> > 依然、タイマがあって、指定した時刻にイベント (put とか get とか) を起こす
> > という方式を採ってます。
> > スレッドは、必要に応じて作られます。
>
> これは(「必要に応じて作られる」というのは)、

タイマという形に抽象化してあります。
最初は java.util.Timer クラスを使っていたのですが、
ある理由から、自分で同等 (+ α) のクラスを作りました。

中身はどうなっているかというと、
java.util.Timer も、Overlay Weaver の ow.util.Timer も、
こうなってます:

・スレッドが 1つ、イベント待ちをしている。
・時刻が来たら、そのスレッド自身がイベントを実行する。

ただし、Overlay Weaver の ow.util.Timer は、設定によっては、
イベントに対して、そのイベント専用のスレッドを割り当てることもできます。
(スレッドプールを使います。)

なので

> 指定した時刻で発行したイベント
> を処理するときに、そのイベントの発行対象となるノードごとに処理用スレッドを
> 起動する(つまり常時起動はしていないけどイベント処理時に作られて、処理
> が完了したらスレッドを終了させる)、という意味でしょうか。
>
> それとも、
> イベント処理用のスレッドが1本イベント待ちしていて(あるいはスレッドプール
> が待機していて)、キューからイベントを取り出して処理する、ということでしょうか。

基本的に後者です。
Overlay Weaver の場合は、設定を変えると前者の挙動もします。

首藤一幸

[KOBARA Makoto]

首藤さん、小原です。

お忙しいところ早速ご回答いただき、
ありがとうございます。

> タイマという形に抽象化してあります。
> 最初は java.util.Timer クラスを使っていたのですが、
> ある理由から、自分で同等 (+ α) のクラスを作りました。

……(中略)……

> 基本的に後者です。
> Overlay Weaver の場合は、設定を変えると前者の挙動もします。

理解いたしました、丁寧に解説どうもありがとうございます。


以下は前の首藤さんの投稿に対するコメントですが、

> スレッドを使った自然 (?) なプログラミングスタイルと
> イベント駆動のスタイルは、案外近かったのだなあ、と感じてます。

同意です。
(stabilization のようなデーモン的な処理の説明のくだりにありました)
ループの開始/終了のところを、ノードごとのリソースの関連付け/切り離し
で表現できるようにしておけば、意外と違和感なく記述できるなと思っています。

ただ、このイベント処理に加えて、さらに非同期IO(ディスク,ソケット,
etc.)の完了通知の合流処理が加わったりすると、ちょっと複雑になり、
苦労したりもします。
(一般論として)

------------------------------------------
KOBARA Makoto

[Kazuyuki Shudo]

首藤です。

まだしつこく、Overlay Weaver の分散環境エミュレータ、
というか、タイマによるイベント (*) の処理を改良し続けてます。

さきほど、とうとうイベント駆動エミュレーションまで可能になったので、
メモの意味も兼ねて、経緯を書きます。

(*) エミュレータにおいては、シナリオ中に書かれた指示。
こんなやつ：

...
schedule 0 invoke
schedule 5000,5,999 invoke
...
schedule 14 control 1171 put k14 v14
schedule 15 control 7370 put k15 v15
schedule 16 control 6710 put k16 v16
...

> Message-Id: <20071206.003252...@utagoe.com>
> From: Kazuyuki Shudo <20...@shudo.net>
> Date: Thu, 06 Dec 2007 00:32:52 +0900 (JST)

> 小原さん、首藤です。
>
>> Message-ID: <a2334423-6d86-4dc4...@b40g2000prf.googlegroups.com>
>> From: KOBARA Makoto <kobara...@gmail.com>
>> Date: Tue, 4 Dec 2007 07:59:21 -0800 (PST)
>
>> > ところが、Overlay Weaver で、スレッド数を削減していった結果、
>> > ノードが占有するスレッドを 0 にできてしまいました。
>> >
>> > では、イベント駆動か? というと、まだ違う気がしてます。
>> > 依然、タイマがあって、指定した時刻にイベント (put とか get とか) を起こす
>> > という方式を採ってます。
>> > スレッドは、必要に応じて作られます。

> タイマという形に抽象化してあります。

> 最初は java.util.Timer クラスを使っていたのですが、
> ある理由から、自分で同等 (+ α) のクラスを作りました。
>
> 中身はどうなっているかというと、
> java.util.Timer も、Overlay Weaver の ow.util.Timer も、
> こうなってます:
>
> ・スレッドが 1つ、イベント待ちをしている。
> ・時刻が来たら、そのスレッド自身がイベントを実行する。
>
> ただし、Overlay Weaver の ow.util.Timer は、設定によっては、
> イベントに対して、そのイベント専用のスレッドを割り当てることもできます。
> (スレッドプールを使います。)

PC 1台上で効率よく多ノードの実験 (エミュレーション) を行うために
マルチプロセッサを活用したく、
いろいろ模索しました。

・タイマスレッド自身がイベントを実行するのか、
それとも別スレッドに実行させる (→ スレッドプール) のか？

・タイマスレッドは１つなのか複数なのか？
(タイマスレッドを複数用意することでもマルチプロセッサ活用は可能。)

結局、タイマスレッドは 1つにして、
各イベントはスレッドプールに実行を依頼するという形にしました。

タイマスレッドを 1つにしたのは、
複数にすると、次の機能との両立が難しかったからです：
Overlay Weaver (OW) のタイマ (ow.util.Timer) には、
PC がアップアップになったり時計が急に飛んだ場合でも
それに適応して将来のイベント起動タイミングを調整する機能があります。

ここで、目的に合うスレッドプールを作るまで、いろいろ苦労しました。
マルチプロセッサを活用し、なおかつ、スレッド生成数を制限したかったのですが、
java.util.concurrent パッケージに用意されているクラス群を使うだけでは済まず、
自作しました。詳細はここでは割愛します。

ここまでの成果が ver. 0.9.2 です：

2009年 5月 1日
Version 0.9.2 リリース。
* エミュレータがスレッドプールを使うようになった。
これによって "control" コマンド間の並列性を活かせる。
* 何種類かの有用なスレッドプール実装 (ow.util.concurrent.*) を用意した。
* 過負荷 / 時計のジャンプについての検出・適応機構を改善した。

先日、2009年 9月 16日に 0.9.5 をリリースしてから、
ここまでタイマを整理できたのだから、
イベント駆動エミュレーションまでいけるんじゃね？と考えて、
やってみたらできました。

作業内容は次の通りです：

・タイマ (ow.util.Timer) のインスタンスを
OW の各所で個別に持っていたところ、これをシングルトンにした。
つまり、タイマのインスタンスを OW 全体でひとつだけにした。

・時刻の取得を、System#currentTimeMillis() ではなく、
タイマが提供する ow.util.Timer#currentTimeMillis() で取得するようにした。

これで、OW というか分散環境エミュレータ上の時間の進み具合いを
タイマから自由にできるようになりました。
イベントがスケジュールされた時刻まで待つのではなくて、
その時刻まで進んだことにしてしまえばいい (→ イベント駆動)、と。

ただ、マルチプロセッサの活用との両立はまだできていません。
今のところ、イベント駆動のモードでは、
スレッドプールは使わず、タイマ自身がイベントを実行するようにしてます。

スレッドプールでの並列処理を行った場合に、
時刻をどう決めて / 進めていけばいいか、考えてます。

CVS head、または次のバージョン (0.9.6) 以降で、
次のパラメータを true にすると、
分散環境エミュレータがイベント駆動になる予定です：

src/ow/util/Timer.java:
public final static boolean SERIAL_BEST_EFFORT_MODE = false;

首藤一幸

[Kazuyuki Shudo]

首藤です。

考察を進めていたら、おもしろいことに気がついたので、
さらにひとりよがりのメールを続けさせて頂きます _o_

要約: sleep(...) のイベント駆動対応には
継続 (continuation) の機能があればいい。

> Message-Id: <20090920.013523...@shudo.net>
> From: Kazuyuki Shudo <20...@shudo.net>
> Date: Sun, 20 Sep 2009 01:35:23 +0900 (JST)

> まだしつこく、Overlay Weaver の分散環境エミュレータ、
> というか、タイマによるイベント (*) の処理を改良し続けてます。
>
> さきほど、とうとうイベント駆動エミュレーションまで可能になったので、
> メモの意味も兼ねて、経緯を書きます。

> 先日、2009年 9月 16日に 0.9.5 をリリースしてから、

> ここまでタイマを整理できたのだから、
> イベント駆動エミュレーションまでいけるんじゃね？と考えて、
> やってみたらできました。
>
> 作業内容は次の通りです：
>
> ・タイマ (ow.util.Timer) のインスタンスを
> OW の各所で個別に持っていたところ、これをシングルトンにした。
> つまり、タイマのインスタンスを OW 全体でひとつだけにした。
>
> ・時刻の取得を、System#currentTimeMillis() ではなく、
> タイマが提供する ow.util.Timer#currentTimeMillis() で取得するようにした。
>
> これで、OW というか分散環境エミュレータ上の時間の進み具合いを
> タイマから自由にできるようになりました。
> イベントがスケジュールされた時刻まで待つのではなくて、
> その時刻まで進んだことにしてしまえばいい (→ イベント駆動)、と。

これで時刻 & 時間の扱いを完全に一元化してイベント駆動にできたかというと、
まだ完全ではありません。
例えば Thread#sleep(long ...) が取り残されています。

これまでも、sleep() がスレッドを占有しないように、
つまり普段は sleep() してるのだけどたまに起きて何かを行うような場合に、
sleep() ではなくて、次に起動してもらう時刻を指定してスケジュールする、
というようなことをやってました：

src/ow/routing/chord/Chord.java (Chord 実装) の末尾、
FingerTableFixer (finger table メンテ処理) クラスの sleep 部分:

if (config.getUseTimerInsteadOfThread()) {
timer.schedule(this, Timer.currentTimeMillis() + sleepPeriod, ...
return true;
}
else {
Thread.sleep(sleepPeriod);
return false;
}

↑ 設定によっては、Thread#sleep(...) の代わりに timer.schedule(...) を呼ぶ

この方法では、次に起動してもらう際に
メソッド (具体的には run()) の先頭から実行が始まります。
タイマからの起動ではメソッド呼び出ししかできないので、そりゃそうです。
この場合は、それで OK です。

ここで、任意の (メソッド途中の) sleep(...) もイベント駆動に対応させるには、
換言すると、任意の sleep(...) をタイマへのスケジュール要求で
置き換えるためにはどうすればいいか。
メソッド先頭だけでなく、
プログラム中の sleep(...) 完了後の地点を、タイマから呼び出せればいい、と。

継続 (continuation) を使えればいけるのではないか、と。

このために OW から Javaflow (継続ライブラリ) を使ってみようか、
などと妄想してます。

首藤一幸