% 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{msgpack} を型付けに利用する。通信されるデータをここでは 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 のみであったため、バイトオーダーやマシンごとに浮動小数点のフォーマットが異なっていたり、複数の変数をまとめて構造体として扱うことを、利用者が管理する必要があった。

そこで、 MessagePack を導入することにより、データに型付けを行い。転送する際にもシリアライズされたデータを送信できるようにする。

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

FederatedLinda における ProtocolEngine は、 ProtocolEngine の繋がりは Tuple に依存するため、接続を管理する機構がなかった。また、シングルスレッドで作られているため、並列実行できなかった。

そこで、新設計では、 ProtocolEngine に代わり、 CodeSegment という単位で処理を記述することにした。
CodeSegment は InputDataSegment のリストと OutputDataSegment のリストを持っている。
InputDataSegment は、 CodeSegment が利用するデータのことであり、 OutputDataSegment は、 CodeSegment が書きだすデータのことである。
InputDataSegment が揃い次第、 CodeSegment が Executor 上で走るため、並列で実行することが可能となる。並列度を上げるためには、 CodeSegment の処理内容は細かく分割するほうが望ましい。

\begin{figure}[htbp]
\begin{center}
\scalebox{0.50}{\includegraphics{./fig/dsandcs.pdf}}
\end{center}
\caption{DataSegment を読み込んで CodeSegment を実行し、 DataSegment へ書きだす。}
\label{fig:dsandcs}
\end{figure}

また、Callback function を FederatedLinda の Tuple へ接続(in)すると、そのリクエストは Queue で管理されていたため、ひとつの書き込みで複数の Callback function を実行することはできなかった。

\subsection{DataSegment}
\label{"datasegment"}

DataSegment は、データ型と ID で表現される。

データ型は MessagePack で使われる構造体を用いて表現する。

ID は、 GeoAddress と LocalAddress の2つの部分に分けられる。
GeoAddress は、トポロジー上の場所を表すアドレスであり、 LocalAddress は自サーバー上の場所を表すアドレスである。

また、その GeoAddress は3種類存在する。

\begin{enumerate}
\item {\bf Persistent} KVS 上にある DataSegment
\item {\bf Remote} 他のサーバー上にある DataSegment
\item {\bf Local} 自サーバー上にある DataSegment
\end{enumerate}

\begin{figure}[htbp]
\begin{center}
\scalebox{0.50}{\includegraphics{./fig/datasegment.pdf}}
\end{center}
\caption{DataSegment には3つの種類がある。}
\label{fig:datasegment}
\end{figure}

\subsection{Geometric Routing}
\label{"routing"}

分散アプリケーションを開発する際に直面する問題として、 Connection と Routing が複雑になるということが挙げられる。
新設計ではその接続を固定的なものに限定することで、その管理をシンプルにすることにした。アプリケーションを起動する前に、台数とトポロジー(リング、ツリー、メッシュなど)を指定する。その情報をもとに固定されたトポロジーの設計図を作成する。トポロジーの構成ルーチンは、 Routing に関するルーチンとは独立して記述できるため、管理しやすくなる。

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

DataSegment の create, read, update, delete といった API は KVS の API と一致しているので、自明にアクセスできる。
PersistentDataSegment を Input または Output する CodeSegment を呼び出せばよい。
Database はどこからでもアクセスすることができる。 Database のアクセスの集中は、自分で解決する必要がある。

SQL などの複雑な操作は、複数の CodeSegment にコンパイルすることで実現する。

通常の DataSegment には Persistency はない。 CodeSegment の処理が終了すると自動的に消滅する。

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

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

まず、 CodeSegment を生成したら、その処理の中で必要なデータを InputDataSegment として指定する。
また、返り値として出力するデータを OutputDataSegment として指定する。

OutputDataSegment の ID を指定したときに、その ID が存在しない場合は create し、存在する場合は、 update 処理を行う。
また、OutputDataSegment が Remote に存在する場合、一旦 Local のバッファに書き出し、転送する CodeSegment を呼び出すことで表現できる。
Remote の格納先に DataSegment が存在しない場合は自動的に create し、存在する場合は、 update 処理を行う。

\begin{figure}[htbp]
\begin{center}
\scalebox{0.50}{\includegraphics{./fig/remoteds.pdf}}
\end{center}
\caption{Remote DS への転送も CodeSegment で表現できる。}
\label{fig:remoteds}
\end{figure}

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

InputDataSegment に指定されたデータがすべて揃ったら、 CodeSegment が実行される。

その CodeSegment 内で、次の CodeSegment を生成する。

このようにして分散アプリケーションを記述することができる。

\subsection{競合的な DataSegment の書き出し}

DataSegment の update 方法にはいくつか種類がある。例えば次の様なものが挙げられる。

\begin{enumerate}
\item {\bf FIFO} 単純に早いもの順で update する。
\item {\bf Priority} 優先順位の高いものが update する。
\item {\bf Queueing} 上書きせずに書き込みを Queue に格納して順番に取り出す。
\end{enumerate}

このような差異を吸収して記述できるようにするために、 MetaCodeSegment をつくって、 CodeSegment とは分離して記述できるようにする。

\subsection{TaskManager}
\label{"TaskManager"}

TaskManager は CodeSegment の管理を司る。
TaskManager は、生成されたすべての CodeSegment のリストを持っており、 DataSegment の生成や更新を監視している。イベントの発生した DataSegment に依存する CodeSegment をチェックし、すべての InputDataSegment が揃った CodeSegment 、すなわち実行可能な CodeSegment があれば Executor に投げる。

\section{まとめと今後の課題}

本論文では、 FederatedLinda の開発を通して得られた教訓を生かし、 DataSegment と CodeSegment を用いた分散フレームワークを設計した。

今後の課題として、新設計したシステムの実装が挙げられるが、それ行うにあたる前に、実装に用いる言語ごとの使い勝手をまとめる。

Java や Scala には、 java.util.concurrent などの並列処理用のライブラリが充実しているため、 CodeSegment の並列処理まで比較的容易に実装することができる。
特に Scala には、アクターを使ったメッセージ交換があるため、言語レベルで並列処理を記述することができる。

本研究室では、 CbC という、引数付き goto による継続ベースのC言語を開発している。それを用いることで、 CodeSegment とDataSegment の繋がりを表現することができる。 CodeSegment 単位で細かく処理を分けて記述することができるのだが、並列処理をまだサポートをしていないので、 TaskManager などの実行カーネルを作成する必要がある。
%
\begin{adjustvboxheight} % needed only when Appendix follows
\begin{thebibliography}{99}
\bibitem{msgpack} MessagePack
\end{thebibliography}
\end{adjustvboxheight} % needed only when Appendix follows

\appendix

\end{document}