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

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

--はじめに

分散アプリケーションが多数開発されている近年、
ノードやネットワークの動的な変化、故障、性能の多様性を考慮した
フレームワークが必要である。
分散環境ではスケーラビリティを確保すること重要である。ここでの
スケーラビリティとはノードの規模の増大にも関わらず、
アプリケーションの性能を維持できることを指す。
分散アルゴリズムの作成には、論理的なプログラムの正しさだけでなく、
スケーラビリティのデバッグを可能にする必要がある。
つまり、デバッガ自体をスケーラブルに作る必要がある。
そのため、分散
フレームワークとして本研究室が提案しているFederated Lindaに、
スケーラビリティなデバッグを行う為のメタな通信を行うプロトコルエンジン
を設計し実装した。

分散プログラムの
デバッグを行う際には通信は必須であるが、その通信によって
本来の通信に影響を及ぼす恐れがある。
ここでは、スケーラビリティには若干問題があるが、
本来の通信に影響を与えないように、一つのトークンをリング上に
流す方法を提案\cite{kono03f,kono03d}している。本論文ではPCクラスタ上で実際の通信を行ない、100台程度の
分散プログラムでの評価を行なった。

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

Internet 上で動作している分散プログラムは、例えば、DNS、
SMTP、NNTP、あるいは、さまざまなP2PやDHTなどがある。
これらのサービスで重要なのは、Scalability つまり、
サービスの規模が大きくなっても、応答速度などの要求仕様を
満たすことである。このようなプログラムは、一つのコンピュータ
に閉じた逐次型のプログラムや、マルチスレッドのプログラムとは
様相が異なる。

Federated Linda\cite{kono05b,kono05f} は、計算モデルが明解なLinda\cite{linda} を
複数接続することで、分散プログラムの作り方を明確なモデル
上で学ぶことができるようにするように設計されている。

我々は、この上で投票システムやCompact Routing\cite{Abraham04compactname-independent,kono08c} 等を
実装して来たが、分散プログラムは、それ自体が複雑なだけで
なく、デバッグ自体の困難さが問題であることがわかってきた。

最初の目標は、琉大情報工学科にある200台規模のPCクラスタ
上で、Federated Linda を用いた分散プログラムを作成し
デバッグすることである。

分散プログラムは正しい答えを出すだけでなく、Scalability
があるかどうかを調べることが必要である。PCクラスタ上の
デバッグでは、デバッグ自体に通信が必要であり、その通信が
Scalability に影響しないようにする必要がある。


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

Federated Lindaとは、複数のタプル空間を相互に
結ぶプロトコルエンジンによって
接続する分散プログラミングモデルである。
Lindaと同じAPIを持つが、
Lindaが一つのタプル空間を共有するのに対し、
Federated Lindaは複数のタプル空間を個別に持つ。
クライアントのアクセス数に対応して、
タプルスペースの数を増やし処理を分散させる事により、スケーラビリティを保つ。

% タプルスペース内の情報はプロトコルエンジンが切断されても
% そこに残る。プロトコルエンジンは、再接続することにより、自然に
% 計算を再開できる。このように、Federated Linda は実際のインターネット
% 上で起きる通信切断に強いフレームワークとなっている。

% この耐切断性を実現するためには、タプルスペースの持続性(Persistency)
% が重要であるが、一方で、プロトコルエンジンが状態を持たないように
% することが望ましい。
%  ってことは、プロトコルエンジンがトランザクションをサポート
%  した方が良いってことだよな〜


--プログラミング例

Federated Lindaは以下の様にして通信を行う。

\begin{itemize}
\item public PSXLinda open(String \_host,int \_port)

Linda Serverに対し、接続を行う。引数はホスト名とポート番号をとる。返り値はタプルスペースの番号となる。

\item public PSXReply in(int id)

タプルスペース番号より引数で指定したidのタプルの受け取りを要求する。
受け取りは、返値のPSXReplyをチェックすることにより非同期に行なう。
in では待ち合わせは行なわれない。Call back 形式でタプルを受け取る
ことも出来る。

\item public PSXReply out(int id, ByteBuffer data)

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

\item public int sync(long mtimeout) 

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

\end{itemize}

Protocol Engineとはタプルスペースを介してデータをやり取りするEngineである。
二つのサーバー間でやり取りを行う場合、以下のようなプログラムとなる。
\begin{verbatim}
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();
\end{verbatim}

callback のAPIも用意されていて、{\tt fdl.sync() } した時に、
{\tt in, rd} の結果が戻っていれば、そのcallback が実行される
ようになっている。

--デバッグするには?

Federated Linda 上でデバッグする一つの方法は、デバッガ
からタプルスペースへ問い合わせの通信を行なうことである(図\ref{集中型デバッガ})。
<center><img src="fig/comDebug.jpg" alt="集中型デバッガ"></center>

この方法では、Linda Serverのad-hocな改変が必要であり、
デバッガは各Linda Serverへ1対多の集中的な通信を行なう
必要がある。この方法では、デバッガはLinda Server への
直接の通信路を持つ必要があるが、分散環境では、ファイアウォール
などの関係で、それが可能であるとは限らない。

デバッグ自体は、
タプル空間に直接アクセス出来るプロトコルエンジンと
考えることができ、Federated Lindaのメタエンジン
ととらえることができる。メタエンジンのAPIを
Linda にそろえることにより、Linda Serverへの
ad-hoc な改変を、決まったAPI上のデバッグプロトコル
の設計にすることができる(図\ref{Debugger})。
<center><img src="fig/debugger.jpg" alt="Debugger"></center>

デバッグ自体をScalableにして、分散計算への影響を少なく
するためには、デバッグ用の通信自体がScalable である必要が
ある。

それには、デバッグプロトコル自体が、Federated Linda に
よってScalable だと示されたプロトコルであることが望ましい。
つまり、最初に情報収集などに適したプロトコルをFederated
Linda で作成し、それをそのままデバッガのプロトコルに
採用できることが望ましい。
<center><img src="fig/obj2meta.jpg" alt="メタへの移行"></center>




--メタエンジン

デバッグ用の通信はLinda Server内部に直接アクセス出来なければ
ならない。これをLinda Server内のMeta Protocol Engine に
よって実現する(図\ref{メタエンジン})。

Meta Engine は、
通常のFederatedLindaと同様のin/out APIを持つ。
Meta Engine では、\verb+sync()+が、属するLinda Server
自体のポーリングを行なう。\verb+sync()+の間は、
通信は行なわれず タプル空間は変化しない。
Meta Engine は安全にタプル空間にアクセス出来る。
Meta Engine のプログラムは、
Linda Serverのメインループで指定することが出来、
Server 毎に独自の動作をさせることが可能である。
<center><img src="fig/meta.jpg" alt="メタエンジン"></center>

--メタエンジンの実装

ここでの Linda Server は、Single Thread に実装されており、
Java nio のselect で待ち、通信パケットを受け取って処理する
というメインループを持っている。
メタエンジンは、このメインループを置き換える形で
実装した。つまり、メタエンジン自体が{\tt sync()}
しながらループするという構造を持っている(図\ref{メタエンジン})。

メタエンジンは、Linda serverの立ち上げ時、または、
メタエンジンそのものから、特殊なものに置き換えるAPI
を用意する。

APIは、通常のLindaのAPIだが、メタエンジンでは、
タプルスペースに対して直接アクセスする。

Single Thread Server上のメインループの一部として
実現されているので、タプルスペースをlockすることなく
自由にアクセスすることができる。ここでのLinda API
は{\tt in,rd}で待ち合わせしない仕様になっていて、
待ち合わせは、{\tt sync()}とポーリング、または、
call back によって実現されている。従って、
メインループの一部としても、{\tt in,rd}の待ち合わせ
によってデッドロックするようなことはない。


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

Federated Linda では、プロトコルエンジンは、
タプルスペース(Linda Server)から、
タプルを受け取って、それに計算を施して、
他のタプルスペースへ引き渡す。従って、
バグは、あるタプルを受け取って、どのような
タプルを出力するかというのを見ることになる。

個々のプロトコルエンジンの計算が正しくても、
大域的なエラーが起きる場合も存在するので、
個々の処理だけでなく、全体的な状態の情報も
必要となる場合がある。

通信状態を含めた大域的な状態は分散スナップショット
と呼ばれる。分散スナップショットを取ること自体に
通信が必要である。また、分散スナップショットは、
未来からの通信が含まれている場合は、
再実行可能でないことがある。再実行可能なスナップ
ショットを取るためには、通常の通信に制限をかける
ことが必要である。

デバッグプロトコルには、個々のTuple Space の情報収集
とともに、スナップショットを取る機能が必要である。
スナップショットが取れれば、そのイメージを
調べることによりデッドロック検出も可能となる。

Scalability の検証では、通信の集中を見つける必要がある。
そのためには、タプルスペース側での通信のlogの監視を
行なう必要がある。すべてのlog情報を一ヶ所に集める
ことなく、通信の集中を調べる機能が必要である。

--デバッグプロトコル

分散環境で情報を集めるには、デバッグのための通信そのものが
分散プログラムになる。ここでは、PCクラスタ上でのシミュレーション
を想定して、ターゲットの通信を妨げないデバッグ通信を考える。
200台規模では、単一のリング上の通信が良いと考えている。

メタエンジン上にリングを構成し、デバッガフロントエンドは、
そのリングを通して、コマンドを送ったり情報を収集したりする
構成である(図\ref{Debugger})。

--Simulation

デバッグプロトコルを実装するために、PCクラスタによるシミュレーション
を行なった。メタエンジン上にリングを構成し、その周回時間をパケットの
大きさを変えて調べる。これにより、リングを使うことによるデバッグの
ユーザへの応答性能と、デバッグを行なう情報を交換する時のパケットの
適切な大きさを調べることができる。これらの数値は、その時その時の
技術に依存している。

本稿では
分散通信に影響を最低限にするために、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通信等があった場合の干渉の程度
などを測定する必要があると考えられる。