% Sample file for the use of compsoft style file.
%
\documentclass[T]{compsoft}

% Preamble
%
% 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
% 巻数，号数，開始ページ，終了ページを指定する．
%\volNoPp{16}{5}{78}{83}

% ワークショップによる推薦論文の場合，ワークショップ名を指定する．
% \suisen{ワークショップ名}

% 特集の場合，特集のタイトルを与える．
% \tokushu{特集のタイトル}

% 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
% 大会の回数は計算される．
\taikai{2010}

% ここに，使用するパッケージを列挙する．
\usepackage[dvips]{graphics}

% ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
% 再定義は原則として避けること．

\begin{document}

% 論文のタイトル
\title{Meta Engine を用いた Federated Linda の実験}

% 著者
% 和文論文の場合，姓と名の間には半角スペースを入れ，
% 複数の著者の間は全角スペースで区切る
%
\author{赤嶺 一樹　河野 真治
%
% ここにタイトル英訳 (英文の場合は和訳) を書く．
%
\ejtitle{Experiment of Federated Linda with Meta Engine}
%
% ここに著者英文表記 (英文の場合は和文表記) および
% 所属 (和文および英文) を書く．
% 複数著者の所属はまとめてよい．
%
\shozoku{Kazuki Akamine}{琉球大学理工学研究科情報工学専攻}%
{Information Engineering Course, Faculty of Engineering Graduate School
of Engineering and Science, University of the Ryukyus}
%
% 出典情報は \shutten とすれば出力される．
%\shutten
%
% 受付年月日，記事カテゴリなどは自動的に生成される．
%\uketsuke{1999}{8}{3}
%
% その他，脚注に入れるものがあれば，\note に記述する．
%\note{脚注に入れる内容}
}

%
% 和文アブストラクト
\Jabstract{%
本研究室では、分散型タプルスペースの実験用に Federated Linda を
提案し、実装してきた。従来の Federated Linda は各ノードの間に配置された
Protocol Engine によって互いに連携するが、プロセスが異なるため無駄な通信
が存在した。そこで Federated Linda と同一プロセス上で動作する Meta Engine
を提案し、実装してきた。本研究では、クラスター上で Meta Engine を用いた実
験用トポロジーを構築し、MetaEngine の使用例を示す。
}
%
% 英文アブストラクト（大会論文には必要なし)
% \Eabstract{}
%
\maketitle

\section{はじめに}

twitter をはじめとする大人数参加型 Web サービスや MMORPG などの大人数参
加型リアルタイムネットワークゲームが、これまで以上に大規模なものとなって
いくためには、分散ネットワークプログラムの発展が不可欠である。

しかし、分散ネットワークプログラムにおけるスケーラビリティーの確保は
難しい。ここで言うスケーラビリティーとは、サービスの大きさが増えたときに
サーバーなどのリソースを追加することのみでサービスの質をリニアに維持でき
ることを指す。

すなわち理想的なモデルは、複数のサーバーを接続することで負荷を分散し、ク
ライアントの数に従ってサービスが自然にスケールするものでなくてはならない。

例えば、現在の分散技術を助けている Key-Value Store などでは、すべてのデー
タのレプリケーションを複数台用意するという手法がとられている。
しかしながら、大人数が参加するサービスにおいて、全員が個人のとあるデータ
を持っている必要性はない。自分と関連のある人物の情報さえ取得できるように
なっていればよいのである。つまり、全データのレプリケーションを用意する必
要はなく、サーバーがクライアントの必要な情報とは何かを把握し、情報を取捨
しながら伝搬していく必要がある。

本研究室では、分散プログラムモデルとして、タプルスペースを制御する Linda
を採用してきた。さらに、複数台の Linda サーバーを接続したモデルである分
散型タプルスペースFederated Linda を提案し、実装してきた。本研究では、
Linda の API の見直しと、 Federated Linda を用いたアプリケーションの実装
を行い、現在のシステムの問題点を洗い出すことにする。

\section{ゲームの例題}

\subsection{水族館ゲーム}\label{subsection:aquarium}
本研究では、ネットワークゲームを例題として用いることにした。そのゲームは、
複数のクライアントのディスプレイを並べて使用する。各プレイヤーは1匹ずつ
魚のオブジェクトが与えられ、それを自由に操作することが出来る。また、魚は
画面の端まで移動すると、自分の画面上からは消え、隣のプレイヤーの画面の端
から魚が出てくる。(図\ref{fig:aqua})

\begin{figure}[htbp]
\begin{center}
\scalebox{0.50}{\includegraphics{./pic/aqua.eps}} % TODO: 重いから最後
%\scalebox{0.50}{\includegraphics{./pic/fedlinda.eps}}
\end{center}
\caption{A,B,C の順に接続すると左から順に画面が接続される。 B の魚は C
 の画面まで移動している。}
\label{fig:aqua}
\end{figure}

\section{Federated Linda}

\subsection{Linda とは}\label{subsection:linda}
Linda は、タプルスペースという ID で区画されたデータストアに、以下の API
(表\ref{tab:lindaapi})
を用いてデータを出し入れすることによって、外部との通信を行う分散プログラ
ミングモデルである。

\begin{table}[htbp]
\begin{center}
\caption{Linda API}
\label{tab:lindaapi}
\begin{tabular}[t]{|l|l|}
\hline
in(id)&タプル空間から取り出す。\\&タプル空間にタプルは残らない。\\
\hline
rd(id)&タプル空間から取り出す。\\&タプル空間にタプルが残る。\\
\hline
out(id,data)&タプル空間にタプルを入れる。 \\
\hline
\end{tabular}
\end{center}
\end{table}

\subsection{Federated Linda とは}\label{subsection:fedlinda}
Federated Linda は Linda サーバーを複数台、相互に接続することによって、
分散プログラミングを実現する。各サーバーは、接続した Linda サーバー内の
タプルスペースへデータのin/out を行うことによって、データを伝搬する。

\begin{figure}[htbp]
\begin{center}
\scalebox{0.50}{\includegraphics{./pic/fedlinda.eps}}
\end{center}
\caption{Federate Linda の接続モデル。組み込まれた Meta Engine がタプルスペースを操作し、外部のサーバーへデー
タを伝搬する}
\label{fig:fedlinda}
\end{figure}


\subsection{Meta Engine とは}\label{subsection:metaengine}

Federated Linda は、サーバー間に設置された、 Protocol Engine と呼ばれる
プログラムによって、タプルスペースの操作や、他サーバーへのタプルの伝搬などを行っており、
タプルスペースとは別のプロセスとして、サーバー上に存在していた。しかし、
別のプロセスであるため、タプルスペースへのアクセスには同一サーバー上であっ
ても、ソケット通信を用いていた。

そこで、本研究室では、 Meta Engine と呼ばれるプログラムを提案し実装して
きた。 Meta Engine は、 タプルスペースと同一プロセス上に組み込まれた
Protocol Engine である。(図\ref{fig:fedlinda})すなわち、タプルスペースと
同じメモリ空間にあるため、ソケット通信を用いることなく直接 Linda の API
を使用して、タプルスペースにアクセスすることが出来る。

\section{Linda API の見直し}
\subsection{update() API の追加}\label{subsection:update}
現状の Linda API では、タプル内のデータを更新するためには in() を実行し
てデータを取り出して削除したあとに、out() を実行してデータを書き込む必要
があった。(図\ref{fig:inout})今回考えている水族館の例題でも、操作があったときにはタプルスペー
スの座標情報を最新のデータに更新する必要がある。

\begin{figure}[htbp]
\begin{center}
\scalebox{0.50}{\includegraphics{./pic/inout.eps}}
\end{center}
\caption{in/out を用いたデータの更新}
\label{fig:inout}
\end{figure}


そこで、今回、新しく update() API を追加することにした。update() を実行
すると、現在存在するタプルは削除され、新しいデータで上書きされる。(図\ref{fig:update})

\begin{figure}[htbp]
\begin{center}
\scalebox{0.50}{\includegraphics{./pic/update.eps}}
\end{center}
\caption{update を用いたデータの更新}
\label{fig:update}
\end{figure}

update() の引数は、 out() と同じく update(id,data) のように、 id と data を渡す。

\subsection{wait\_rd() の問題点}\label{subsection:problemofwaitrd}

Linda には、 rd API の他に、 wait\_rd という API が存在する。wait\_rd はた
だちに reply を返す rd とは違って、タプルの情報が更新されるまで、サーバー
側で reply が保留される。この API を用いることで、必要な座標情報が更新さ
れたときのみに通信を行うことができる。
しかし、 wait\_rd を受け付けたときのタプルデータは返されないため、最新の
情報を得ることが出来ないというバグが、ゲームのクライアントを作成するとき
に発生した。

これを回避するために、 wait\_rd の結果が次のループで返されなかったときは、
rd を用いて現在のタプルの情報を取得するようにした。しかしこれは、2重で
rd の API を使っており、場合によっては無駄な通信を伴なう。また、クライア
ントの受信側で、 rd と wait\_rd のどちらが最新のデータか判別する無駄な条
件分岐が発生するため、場当たり的な対応でしかない。

これを解決するためには、タプルのバージョンをサーバー側で記録するようにす
るか、タイムスタンプを用いてタプルを管理するといった方法が挙げられる。

Linda にこのような API を実装する予定はないが、 Linda を踏まえて次に本研
究室で設計する分散データベースでは、参考にして設計しなおす予定である。

\section{Meta Engine を用いたサーバーの設計}
\subsection{ツリー型トポロジーを用いた負荷分散}\label{subsection:treetopology}
今回の例題には、ツリー型トポロジー Federated Linda を用いることにした。
(図\ref{fig:treetopology})

\begin{figure}[htbp]
\begin{center}
\scalebox{0.40}{\includegraphics{./pic/treetopology.eps}}
\end{center}
\caption{ツリー型トポロジーで接続された Federated Linda。ツリーの末端に
 クライアントを接続する。}
\label{fig:treetopology}
\end{figure}

ツリー型トポロジーの各ノードは、親と2つの子への接続を持つ。また、末端の
ノードはクライアントによる接続も受け付ける。

クライアントから座標情報を受け取った末端のノードは、その座標情報を他のク
ライアントが必要としているかを判断する。もしも必要ならば、その Linda サー
バーのみで通信は完結しているため、 Federated Linda 上でデータの伝搬は行
われない。

もし必要としない場合は、親のノードにタプルデータの伝搬を行う。そのとき
親のノードは、その子から送られてきた座標情報を元に、対になっている子がデー
タを必要としているかを判断する。もし必要ならば、対になっている子に対し
てタプルデータを伝搬する。そうでなければ、さらにその親に対してタプルデー
タの伝搬を行う。

このように、座標データを必要としているマシンのみに座標データをコピーする
ことで、負荷分散を実現するモデルである。 このモデルを用いない場合、つま
り Linda サーバーを単体で用いる場合は、各クライアントは、すべての接続し
ているクライアントの所持しているオブジェクトの座標情報を常に監視する必要
があり、画面に表示されない(すなわち、必要のない)データも操作がされるたび
に通信する必要があった。

\subsection{Meta Engine の問題点}\label{subsection:problemofmetaengine}
具体的に Meta Engine とは、サーバーが他サーバーとどのような接続を行い、
どのタプルを監視し、どこに伝搬するかというのを記述するものである。

Federated Linda は Java を用いて実装しており、その上に実装されている
Meta Engine ももちろん Java で記述している。処理は関数でシンプルに記述で
きるとよいが、 Java では関数のみを記述することはできないので、 interface
を実装したクラスを作成することで処理を記述する必要がある。

また、タプルの伝搬を行うために Federated Linda サーバーの接続一つごとに
専用のタプルを決め、そこを in によって監視するのだが、その記述を
Callback 関数のように記述すると、コードの難読化が進んでしまう。

さらに、他サーバーと接続する処理を記述し、そのサーバーからのデータを受信
するタプルと、相手への伝搬先のタプルを対応付けする処理を毎回記述する必要
があるため、新しいトポロジーを構築しようとしたときにコードの記述量が増え
てしまう。これを解決するためには、 Meta Engine とタプルスペースの間にそ
れらの伝搬のシステムを管理する機構を準備する必要がある。

\section{評価}
\subsection{update API の検証}\label{subsection:updateverification}
update() API を \ref{subsection:update} で設計した通りに実装した。

また、 in/out を用いた場合と、 update を用いた場合で時間を比較することに
した。

それぞれの API で N 回の更新を行う処理時間を2台のクラスタを用いて計測し
た。(図\ref{fig:updateinout})

\begin{figure}[htbp]
\begin{center}
\scalebox{0.50}{\includegraphics{./pic/updateinout.eps}}
\end{center}
\caption{in/out による更新と update による更新時間の比較}
\label{fig:updateinout}
\end{figure}

この結果より、 update を用いてタプルを更新した場合と、 in/out を用いてタ
プルを更新した場合とで、特に差を見ることはできなかった。

しかし、クライアントのコードを書くときに、 in/out を2つ書くよりも
update を1つだけ書く方が、書きやすく、読みやすいという点は利点として挙げ
られる。

\subsection{TCP No Delay の検証}\label{subsection:tcpnodelay}
TCP No Delay (短いパケットの送信を遅らせる動作の制御フラグ)
の影響が大きいとの指摘があったので、 Federated Linda でリング型トポロジーを構築し、
タプルの転送速度の差を検証した。今回、使用したクラスタの台数は46台である。

リングに流したデータには、 4096 Bytes のデータを用い、 100 周したうちの
平均時間より、 1 周にかかる時間を算出した。(図\ref{fig:tcpnodelay})

\begin{figure}[htbp]
\begin{center}
\scalebox{0.50}{\includegraphics{./pic/tcpnodelay.eps}}
\end{center}
\caption{TCP No Delay の検証}
\label{fig:tcpnodelay}
\end{figure}

この事より、TCP No Delay によって、パフォーマンスに大きな差を得られ
ることはないことがわかった。

\section{まとめと今後の課題}
今回の研究では、 Federated Linda を用いたゲームの設計を行った。この設計や
Linda をもちいたクライアントを実装している段階で、 \ref{subsection:problemofwaitrd} や
\ref{subsection:problemofmetaengine} のように改善できそうな点を複数見つけることができた。

まだ、ツリー型トポロジーの Federated Linda を用いたバージョンをきちんと
実装できていないのでこれらの実装を通して、さらに Federated Linda の問題
点を見つけていくことができる。

また、複数の Federated Linda サーバーをデバッグするのは難しいため、それ
らに加えて、スケーラブルなデバッグ方法なども考えていかなくてはならない。
%
\begin{adjustvboxheight} % needed only when Appendix follows
\begin{thebibliography}{99}
\bibitem{fuchita} 渕田良彦: 分散プログラミングモデル Federated Linda と分散
	デバッグ開発
\bibitem{kono} 赤嶺悠太, 小野雅俊, 河野真治: 連邦型Lindaによる分散アルゴ
	リズムをデバッグするためのメタプロトコル
\end{thebibliography}
\end{adjustvboxheight} % needed only when Appendix follows

\end{document}