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

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

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

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

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

% ここに，使用するパッケージを列挙する．
\usepackage[dvipdfm]{graphicx}
\usepackage{mediabb}
% ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
% 再定義は原則として避けること．

\begin{document}

% 論文のタイトル
\title{DataSegment API を用いた分散フレームワークの設計}

% 著者
% 和文論文の場合，姓と名の間には半角スペースを入れ，
% 複数の著者の間は全角スペースで区切る
%
\author{赤嶺 一樹, 河野真治
%
% ここにタイトル英訳 (英文の場合は和訳) を書く．
%
\ejtitle{Design of Distributed Application Framework with DataSegment API}
%
% ここに著者英文表記 (英文の場合は和文表記) および
% 所属 (和文および英文) を書く．
% 複数著者の所属はまとめてよい．
%
\shozoku{Kazuki Akamine, Shinji Kono}{琉球大学理工学研究科情報工学専攻}%
{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{%
本研究室では、分散フレームワークとして、 Linda を拡張した FederatedLinda を開発してきた。しかし、分散用の API として、 in/out/read だけでは足りないことが判明した。また、分散 KVS には、 read/write/update といった API があるが、同期する機構は備わっていないため、ゲームなどのリアルタイムプログラム用途にそのまま利用することはできない。
%
そこで、 Linda の待ち合わせ可能な API と一般的な KVS の持つデータベースの API の中間になるような DataSegment API を設計する。本研究室では、その DataSegment API を用いた分散フレームワークを開発する。}
%
% 英文アブストラクト（大会論文には必要なし)
% \Eabstract{}
%
\maketitle

\section{スケーラブルな分散フレームワークの提案}
ブロードバンド環境やスマートフォンなどをはじめとしたモバイル端末の普及により、ネットワークに接続している端末が増えている。それにしたがって、ネットワーク上におけるサービスの巨大化は必至となっている。そこで、サービスのスタートアップ時期には少量のリソースで運用でき、ユーザー数が増える時期には、リソースを追加するのみでサービスの質を維持できるといった、スケーラビリティーを備えたシステムが求められている。そのようなシステムを開発するためには、様々なプロトコルを提案し、実装し、検証していく必要がある。そのため、提案したプロトコルを玩具的に実験できるフレームワークが求められている。
%
本研究室ではこれまでに、 Linda を拡張した FederatedLinda を開発し、スケーラビリティーのあるシステムについて考えてきた。すると、その開発サイクルの中でいくつかの問題点があることが分かった。また、本研究室が開発している、並列フレームワーク Cerium に新しく実装する予定の DataSegment と CodeSegment を用いた並列計算に関するアイディアが、分散アプリケーションにも応用できるのではないかと考えた。上記の理由から、新しい分散フレームワークを提案する。
%
本論文では、 DataSegment と CodeSegment を用いた分散フレームワークに関して提案する。
%

\section{FederatedLinda}
\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{./fig/fedlinda.pdf}}
\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
を使用して、タプルスペースにアクセスすることが出来る。

\subsection{Federated Linda の問題点}\label{"fedlinda2"}
大きく分けて分散アプリケーションは、次の3つのパートで構成することができる。
\begin{enumerate}
\item {\bf Configuration} 各ノードの接続やルーティングを行う。
\item {\bf ProtocolEngine} Database へアクセスし、他のノードにデータを伝搬する。
\item {\bf Database} 通信した内容や計算結果などの各種データの保存領域。
\end{enumerate}
しかし、 FederatedLinda を利用したプログラマーが記述できる部分は ProtocolEngine だけであるため、 Configuration に関するコードをそこに記述しなくてはならない。そのため、各ノード間の接続やルーティングを利用者が管理する必要が出てくる。
%
また、 FederatedLinda の ProtocolEngine には、次の2つの実行方法がある。
\begin{enumerate}
\item {\bf Polling base} メインループで定期的に ProtocolEngine を実行し、 TupleSpace からデータを取得し、確認する。
\item {\bf Callback function base} とある Tuple が更新される度にその Tuple に設定された Callback function が実行される。
\end{enumerate}
Polling base の場合は、通信が行われる都度、記述した Tuple の内容をチェックするため、負荷が大きくなる。そのため、 Callback function base を用いて記述する方が効率はよくなる。しかし、 Callback function 同士の繋がりがツリー状に構成されるため、利用者がそのツリー同士の接続管理を行わなくてはならない。また、 Callback function 間のデータの共有も難しい。 Callback function で記述されたコード群をシーケンシャルに読むことも難しくなる。

\section{DataSegment を用いた新設計}
\label{"datasegment"}

FederatedLinda の経験を踏まえて、新しい分散フレームワークの設計を行う。主なターゲットとしては、ネットワークゲームを考えている。
ネットワークゲームで通信されるデータは色々な型を持っている。今までの FederatedLinda ではその型をうまく定義することが出来なかった。ここでは、 MessagePack \cite{MessagePack} を型付けに利用する。通信されるデータをここでは DataSegment と呼ぶ。

DataSegment はネットワーク上でやり取りされるので、その場所を表す ID を持っている。 FederatedLinda にはなかった Persistency を導入するために Persistent Storage Class を導入する。 DataSegment の ID に Persistent Storage Class を指定することにより、 Cassandra などのような分散データベースのレコードを直接指し示す。自サーバー上にある DataSegment は Local Storage Class を指定する。他のサーバー上にある DataSegment は Remote Storage Class を指定する。

DataSegment を処理するタスクを CodeSegment と呼ぶ。 CodeSegment はシングルスレッドでトランザクションに相当する。今までの FederatedLinda では、 ProtocolEngine と呼ばれていた部分である。 FederatedLinda の Callback による実行ではなく、 TaskManager により、 InputDataSegment がすべて揃った段階で実行される。

タスクは OutputDataSegment に書き込みを行うが、その ID が Remote の場合は、その DataSegment があるサーバーへ転送を行う。 これが FederatedLinda の out() に相当する。

タスクの実行は、タスクの ID で示される、サーバー上で実行される。任意のサーバー上で実行するという指定も可能である。 CodeSegment をどこで実行するかは、 TaskManager が決定する。タスクの ID は全世界で共通である。その ID は Java のパッケージと同じように階層化されて管理される。

同じ ID を持つ DataSegment に複数のタスクが書き込んだ場合は、同期が行われる。例えば、時間順序ごとにキューに入れる。あるいは、上書きされる。これらは MetaCodeSegment により、制御される。

以下にこれらについて、さらに詳しく説明する。

\subsection{MessagePack によるデータの型付け}
\label{"msgpack"}

FederatedLinda では、 Tuple の中の型は binary のみであったため、マシンごとに浮動小数点のフォーマットが異なっていたり、複数の変数をまとめて構造体として扱うことを、利用者がすべて管理する必要があった。

\subsection{ProtocolEngine の代わりに CodeSegment を利用}
\label{"codesegment"}

\subsection{GeometricRouting}
\label{"routing"}

\subsection{Key Value Store に合わせたAPI}
\label{"kvsapi"}

\subsection{CodeSegment の使い方}
\label{"usecodesegment"}

\subsubsection{InputDataSegment を指定}
\label{"inputdatasegment"}

ID

MessagePackClass
Type
 Persistent
 Local
 Remote

\subsubsection{OutputDataSegment を指定}
Remote は自動的に allocate

\subsubsection{InputDataSegment が揃ったら実行開始}

\subsubsection{実行中の CodeSegment 内で次の CodeSegment を生成する}

\subsection{競合的な DataSegment の書き出し}
MetaCodeSegment が取り扱う

OverWrite

Queue

Priority

\subsection{TaskManager}
\label{"TaskManager"}
CodeSegment List を持っている
実行可能な CodeSegment を各プロセッサーに割り当て
\section{まとめと今後の課題}
Java(Scala)
CbC
C++

{\bf 謝辞}\
%
\begin{adjustvboxheight} % needed only when Appendix follows
\begin{thebibliography}{99}
\bibitem{test} test
\end{thebibliography}
\end{adjustvboxheight} % needed only when Appendix follows

\appendix

\end{document}