-title: 連邦型Lindaによる分散アルゴリズムをデバッグするためのメタプロトコル

--author: 赤嶺悠太, 小野雅俊, 河野真治


--分散アルゴリズムを勉強する

	Socketからプログラムするのは敷居が高すぎる

でも実際に動かしてみないと体験出来ない。

	通信のモデルがある方が良い

	Linda って、モデルはわかりやすいよね〜

しかし、Linda の共有されたタプル空間ではScale しようがない

--Scaleする分散プログラム

Scalabilty とは?

	接続するサーバ、ネットワーク規模が増える

	増えても、サービスの性質を一定に保つ

--分散プログラムの三つの要素

	Local Accesss       末端の通信

	Protocol Engine     通信するサーバ

	Configuration       サーバの接続パターン


--プロトコルエンジンとタプル空間

タプル空間を相互に、プロトコルエンジンが接続すると言うのを考える

	タプル空間一つにアクセスが集中しない

	DHTとかとは正反対

Scale する適切なプロトコルを提供して、それを使用して分散アルゴリズムを作る

--Single Thread Implementation

	一つのLinda Server はSingle Threaded

	二つのLinda Serverを接続するPrototocol Engine はSingle Threaded

	in/out では待ち合わせを行なわない

	polling ( callback ) base でプログラムする

--The Reason why Single Thread Implementation

	実装しやすい

	デバッグしやすい

	APIがゲーム向き (主ターゲットがネットワークゲーム)

--API

public PSXLinda open(String _host,int _port)

public PSXReply in(int id)

    タプルスペース番号より引数で指定したidのタプルの受け取りを要求する。

public PSXReply out(int id, ByteBuffer data)

    引数で指定したidでByteBuffer内のデータを送信する。

public int sync(long mtimeout) 

    接続しているLinda Serverとタプルの送受信のポーリングを行う。

\end{itemize}

--プログラミング例

    FederatedLinda fdl;
    PSXLinda getpsx;
    PSXLinda sendpsx;
    PSXReply in;
    ByteBuffer data = ByteBuffer.allocate(10);

    //通信を初期化する
    fdl = FederatedLinda.init();
    //データを取ってくるホストと受け渡すホストとの接続開始
    getpsx  = fdl.open("cs100",10000);
    sendpsx = fdl.open("cs101",10001);
    //取ってくるホストからinを指定してデータを取得
    in = getpsx.in(10)
    data = in.getData();
    //受け渡すホストに対しデータとidを指定して同期
    sendpsx.out(10,data);
    fdl.sync();

--例えば、

これを使って、Compact Routing を実装してみる

    Compact Routing でも Mesh などでは、収束しない

細かい実装をしないとScaleしない。(Split horizen, Hop count)

プログラムミスなのか、アルゴリズムが悪いのか?

Scale するように調整するには?

--デバッグするには?

	サーバの数だけ画面を開く....

だめです。

デバッグを実装する必要がある。

--デバッガに対する要求

	タプル空間に直接アクセス出来る

	デバッグ自体がScale して欲しい

	デバッグ通信自体が、Federated Linda であるべき

	デバッグ通信のデバッグ対象への影響が少ない

	local なサーバの状態だけでなく大域的な通信状態を取り扱える

--メタエンジン

Linda Server に、タプル空間をいじれるメタエンジンを付加する

メタエンジン上に、Fedrated Linda を使ってデバッグプロトコルを実装する

--メタエンジンの実装

Linda Sever/Protocol Engine はSingle Thread なので、変わりばんこに実行してやれば良い。

最初にFederated Linda 上で通常のプログラムとしてデバッグプロトコルを作成する

それを、メタエンジンでの通信に移す

--Linda ServerとMeta Engine

Linda ServerとProtocol Engineは、1対1が自然なようである

Meta Engine とProtocol Engine の違いは、タプル空間に直接さわれるかどうか

なので、今後は、1対1を仮定して良いと思われる

--分散プログラムのデバッグ手法

対象とするバグ

	Protocol Engine の実装ミス

	    入出力が正しくない

	大域的な分散アルゴリズム自体のミス

	    Dead Lock/Live Lock

	Scale しないバグ

	    輻輳、飢餓


--デバッグプロトコル

	大域状態を調べる

	計算を止める

	計算を再開する

	デッドロック/ライブロックを検出する

	条件に従って入出力するタプルの通信パターンを記憶する

--デバッグ用の通信パターン

もっとも干渉が少ない場合として、単一のデバッグコマンドを全サーバに周回させるプロトコルを考える。


--Simulation

分散通信に影響を最低限にするために、Ringで性能を評価する。
3台のLinda Server間でMeta Engineがデータをやり取りする場合
のUMLシーケンス図は
図\ref{ringthree}のようになる。
\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.2]{fig/meta_ring_three.eps}
\caption{3台間の通信}
\label{ringthree}
\end{center}
\end{figure}

Ring では通信パケットは一つのみであり、デバッグ対象への
影響が小さい。
しかし、スナップショットや一時停止などの
デバッグ操作をするためには、全ノードを周回する必要がある。
%これはo(n)であり、十分にスケーラビリティがあるとは言えない。
%しかし、もっとも影響が少ない方法なので、どの程度まで使える
%かを測定することには意味がある。

ここでは、通信パケットの大きさを変えて、
3〜100までの台数でデータが1周(図\ref{metaring})する時間、
および1000周(図\ref{metaring1000})した時に掛かった時間を測定する。
前者では接続の手間を含む通信時間、後者では通信のみの時間を
計ることが出来る。

実験は、
琉球大学
情報工学科のクラスタ上(Core Duo 2GHz,メモリ1GB)で、
クラスタジョブ管理システム
Torqueを用いて行なった。
ネットワークはAlaxalA Gigabit Ethernet Switchで構成されている。
クラスタ自体は180台あるが、
安定して動作する100台までを使用して測定を行なった。

\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.3]{fig/metaring1.eps}
\caption{接続を含む一周の時間}
\label{metaring}
\end{center}
\end{figure}

X軸が台数、Y軸がミリ秒、ラインの色が通信するデータサイズを表す。
両図から見てわかる通り、データの量にはあまり依存する事はなくほぼ同じラインを形作っている。
データを1周のみした場合は1サイクルあたり約14000ms、一台あたり約140ms掛かっている計算になる。
これは、TCPの接続時間がかなり大ききことを示している。1MB程度の通信を
隠すほど接続時間のオーバヘッドは大きい。
14秒はインタラクティブな
デバッガとしては容認できないと思われる。
従って、毎回、新しく接続するようなHTMLのような
通信を採用することはできないことがわかる。


\begin{figure}[htbp]
\begin{center}
\includegraphics[scale=0.3]{fig/metaring1000.eps}
\caption{千周の平均周回時間}
\label{metaring1000}
\end{center}
\end{figure}

それに対し1000周した際に掛かった時間は、1サイクルおよそ60ms、一台につき約0.6msとなっている。
これより、一度、接続してしまえば、
Meta Engine での通信は実際に100台程度のデバッグに使用するのに十分な性能を
持っていることが確認出来た。

パケット1KBから100KBまでの差は2倍程度であり、それ以上はパケットサイズに
リニアに時間がかかる。従って、数十KB程度以下にデータを抑えることは、
応答時間的には意味がない。


--比較


本稿ではデバッグを行う為に通常通信とは他に、Metaで通信するMeta Protocol Engineを実装し評価した。
今回は、スナップショットなどの実際のデバッグ機能を実装することは出来なかった。
通信の実験においても、
同クラスタ上で別のRing通信や他のMetaLinda通信等があった場合の干渉の程度
などを測定する必要があると考えられる。