\chapter{分散ネットフレームワーク Alice}
\label{chap:concept}

\section{Alice}
Alice\cite{kono11g}は、本研究室で開発を行なっている分散タスク管理フレームワークである。
Cell 用のOpen CLに似たTask管理フレームワークCerium\cite{kono09b,cerium-sourceforge}と、Linda\cite{linda}を相互接続した分散フレームワークであるFederated Linda\cite{kono05b}の開発を通して得られた知見を生かされている。

Ceriumでは、Taskを小さく分割して並列実行し、データ転送はパイプライン実行により隠される。Taskには依存関係があり、その記述は煩雑になるが、実際にはデータの依存関係がそのままTaskの依存関係になることが多い。繰り返し使われるデータ構造の管理が重要であり、実行時にわかるデータ構造間の依存関係がTaskを複雑にしている。

Federated Lindaでは、Lindaサーバ内部にMeta Engineと呼ばれるLindaのタプル(データ構造)をやり取りする部分を作成した\cite{kono10d}。Meta Engineでは、タプルのやり取りによって起動するcall backを使うが、call backによる記述が分散してしまい、可読性を落としてしまう。また、複数のタプルの待ち合わせが重要だが、その待ち合わせはsingle threadedなMeta Engine内部の状態に依存する。

これらが示しているのは、並列分散実行はコードの並列実行だけでなく、データの単位が重要だということである。そこで、AliceはData SegmentとCode Segmentという単位でデータと処理を細かく分割し、それぞれの依存関係を記述して分散プログラムを作成する。Code SegmentはContinuation based Cの実行単位\cite{kono00a,cbc-sourceforge} であり、その双対がData Segmentである。

Data SegmentはCode Segmentと分離されたデータ構造であり、オブジェクトではない。オブジェクト指向プログラミングが状態を複雑に持ち、並列実行や分散実行に向かないことは徐々に理解されてきている。一方で、状態自体は有限状態遷移機械(Finite State Machine/FSM)で記述するのが自然である。Code Segmentは状態遷移記述そのものであり、その状態遷移はData Segmentの到着によってトリガーされる。

カプセル化されたデータをプロセスがやり取りするのは、DFD(Data Flow Diagram)の古典的な手法であり、それ自体は新しくはない。むしろ、メインフレーム上でのソフトウェア開発に良く使われてきた手法である。Alice では、それを再実装する。

AliceはCode SegmentとData SegmentをJavaとMessage Packで実装したフレームワークである。トポロジーマネージャーを持ち、Blade上での
分散プログラムの実験を容易に行うことができる。また、SEDA Architecture \cite{SEDA2001}を採用しており、マルチコア上でのスループットの向上を期待している。


\section{Data Segment API}
Data Segmentは、データ細かく分割したものであり、数値や文字列などのデータを構造体的に保持す
るが問題はData Segmentの相互参照問題である。AliceはData Segmentをデータベースとして扱う。
Data Segmentは必ずキーを持つ。つまり、Key Value Storeとして考えることができる。
通常のデータベースでは隠されているが、Key毎にキューがあり、key毎に順次実行される。

Aliceのデータベースは通常のKVSと若干異なっている点がある。通常のKVSはプログラミング言語の連想配列やMapと同様に「Key(キー)」と「Value(値)」がペアとなってる。そのためKeyに対して取得できるValueは当然1つである。しかし、Aliceの場合は「Key」と「Queue」がセットとなっているため、Keyに対して複数回putできる。そのため取得できるValueも複数存在する。
key毎の追加と取得は、Lindaに準じた設計になっている。

Data SegmentはData Segment Manager(以下DSM)によって管理されている。ノード毎にLocal DSMとRDSMが存在する。Local DSMは、各ノード固有のKey Value Storeとなっている。従って、Keyはノード内部でuniqueなものである。Remote DSMは他のノードのLocal DSMのproxyである。(図 \ref{fig:RemoteDSM}) AliceのトポロジーマネージャーがRemote DSMを自動的に構築する。つまりRemote DSMは複数存在し、それぞれに対応するノードが異なる。

\begin{figure}[htbp]
\begin{center}
\includegraphics{fig/remote_datasegment.pdf}
\end{center}
\caption{Remote DSM は他の ノードの Local DSM の proxy }
\label{fig:RemoteDSM}
\end{figure}


KVSへのアクセスはキューによって、ノード内部で逐次化される。それ以外は、すべてJavaのThread Poolによって並列実行される。Code Segmentが実行される際には、Data Segmentが揃っているのでBlockingが起こることはない。逆にBlockingが必要な場合は、Code Segmentを分割する必要がある。

以下が用意されているData Segment APIである。これらを用いてデータの送受信を行う。

\begin{itemize}
\item {\ttfamily void put(String key, Value val)}
\item {\ttfamily void update(String key, Value val)}
\item {\ttfamily void peek(Receiver receiver, String key)}
\item {\ttfamily void take(Receiver receiver, String key)}
\end{itemize}

\subsection{put}
putはデータを追加するためのAPIである。putは受けとったvalをキーに毎重複しない連番のIDを受け取った順に振る。Lindaのout()に相当する。(図 \ref{fig:put})

\begin{figure}[htbp]
\begin{center}
\includegraphics{fig/put.pdf}
\end{center}
\caption{putはデータを追加する}
\label{fig:put}
\end{figure}

\subsection{update}
updateはデータを置き換える特急メッセージのように動作する。 putと同様に受けとったvalをキーに毎重複しない連番のIDを受け取った順に振る。Lindaのupdate()に相当する。(図 \ref{fig:update})

\begin{figure}[htbp]
\begin{center}
\includegraphics{fig/update.pdf}
\end{center}
\caption{updateはキューの先頭を書き換える}
\label{fig:update}
\end{figure}

\subsection{peek}
peekはデータを調べるAPIである。(図 \ref{fig:peek})

要求したData Segmentが存在しなければ、Code Segmentの待ち合わせ(Blocking)が起こる。(図 \ref{fig:no_peek})

\begin{figure}[htbp]
\begin{center}
\includegraphics{fig/peek.pdf}
\end{center}
\caption{peekはデータを調べる}
\label{fig:peek}
\end{figure}

putやupdateによりData Segmentに更新があった場合、peekが直ちに実行される。目的のData Segmentを取得できた場合、Data Segmentを作成したCode Segmentがactive queueに移される。Lindaのrd()に相当する。

\begin{figure}[htbp]
\begin{center}
\includegraphics{fig/peek1.pdf}
\end{center}
\caption{希望のデータが無いときは保留する}
\label{fig:no_peek}
\end{figure}

\subsection{take}
takeもデータを読み込むためのAPIである。読み込まれたデータをKVSから取り除かれる。Lindaのin() に相当する。(図 \ref{fig:take})

\begin{figure}[htbp]
\begin{center}
\includegraphics{fig/take.pdf}
\end{center}
\caption{take はデータを読み込む}
\label{fig:take}
\end{figure}

\section{Data Segmentの実装}
Data Segmentのデータの表現にはMessagePackを利用している。
MessagePackに関してJavaにおけるデータ表現は以下の3段階あり、これらのデータ表現は制限を伴うが互いに変換可能である。

\begin{itemize}
\item {\ttfamily 一般的なJavaのクラスオブジェクト}
\item {\ttfamily MessagePack for JavaのValueオブジェクト}
\item {\ttfamily byte[]で表現されたバイナリ}
\end{itemize}

Data Segment APIでは、このMessagePack for JavaのValueオブジェクトを用いてデータが表現されている。
MessagePackはJavaのように静的に型付けされたオブジェクトではなく、自己記述なデータ形式である。MessagePack for JavaのValueオブジェクトはMessagePackのバイナリに
シリアライズできる型のみで構成されたJavaのオブジェクトである。そのため、Valueも自己記述式のデータ形式になっている。

Valueオブジェクトは通信に関わるときには、シリアライズ・デシリアライズを高速に行うことができる。
また、ユーザーはメソッドを用いてオブジェクト内部のデータを閲覧、編集することができる。

ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを表現することができる。
この場合、クラス宣言時に@Messageというアノテーションをつける必要がある。もちろん、MessagePackで扱うことのできるデータのみをフィールドに入れなければならない。

\section{Code Segment}
Code Segmentはタスクのことである。Code Segmentをユーザーが記述するときに、Code Segmentの作成を記述する。Code Segment内で使用するData Segmentの作成を記述する。Code Segmentには、Input Data SegmentとOutput Data Segmentを作るAPIが存在する。

\begin{figure}[htbp]
\begin{center}
\includegraphics{fig/dsandcs.pdf}
\end{center}
\caption{Code SegmentはInput Data Segment とOut put Data Segmenが存在する}
\label{fig:dsandcs}
\end{figure}

Input Data Segmentで作成されたData Segmentは、remoteかlocalか、またkeyを指定する必要がある。Input Data Segmentがすべて揃うまでCode Segmentはactiveにならない。

Out Data Segmentで作成されたData Segmentに対してもremoteかlocalか、keyを指定する必要がある。

Input Data Segment とOut put Data SegmentがCode Segment間の依存関係を自動的に記述することになる。(図\ref{fig:dsandcs2})
\begin{figure}[htbp]
\begin{center}
\includegraphics{fig/dsandcs2.pdf}
\end{center}
\caption{Input Data Segment とOut put Data SegmentがCode Segment間の依存関係を自動的に記述する}
\label{fig:dsandcs2}
\end{figure}


idsとods によりInput/Outputを選択してData Segmentを作成する。Outputにはput時(update時)にremoteかlocalか、keyを指定する。Inputの場合にはsetKeyする際にremoteかlocal、keyを指定する。

今現在はInputはsetKeyをする際に、Outputはputの際にノードとkeyを指定しているが、どの時点でノードとkeyを指定するのか、どのようなAPIを用意するべきかは、まだ議論の余地がある。

\section{Code Segmentの実行方法}
Aliceには、Start Code SegmentというCのmainに相当するような最初に実行されるCode Segmentがある。Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。(ソースコード \ref{fig:StartCodeSegment})

\section{Code Segmentの記述方法}
Code Segmentをユーザーが記述する際にはCode Segmentを継承して記述する。(ソースコード \ref{fig:CodeSegment})そのCode SegmentはInput DSMとOutput DSMを利用することができる。

\begin{table}[htbp]
\lstinputlisting[label=fig:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java}
\end{table}

\begin{table}[htbp]
\lstinputlisting[label=fig:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java}
\end{table}

Input DSMはCode Segmentのidsというフィールドを用いてアクセスする。

\begin{itemize}
\item {\ttfamily Receiver create(CommndType type)}
\end{itemize}

createでコマンドが実行された際に取得されるData Segmentが格納される受け皿を作成する。引数にはCommandType取る。ここで指定できるCommandTypeはPEEKまたはTAKEである。

\begin{itemize}
\item {\ttfamily void setKey(String managerKey, String key)}
\end{itemize}

setKeyメソッドにより、どこのData Segmentのあるkeyに対してpeekまたはtakeコマンドを実行するかを指定することができる。
コマンドの結果がレスポンスとして届き次第Code Segmentは実行される。



Output DSMはCode Segmentのodsというフィールドを用いてアクセスする。Output DSMはputまたは updateを実行することができる。

\begin{itemize}
\item {\ttfamily void put(String managerKey, String key, Value val)}
\item {\ttfamily void update(String managerKey, String key, Value val)}
\end{itemize}

\section{Topology Manager}
Aliceは複数のノードで構成され、相互に接続される。通信するノードは、URLにより直接指定するのではなく、TopologyManagerで管理する。

TopologyManagerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきTopology NodeのIPアドレス、ポート番号、接続名を送りトポロジーファイルに記述されたとおりにトポロジーを作成する。(図\ref{fig:topologymanager})

Code Segment内部でRemote DSMにアクセスする場合はToplogyManagerによって指定されたノード内部だけで有効なlabel(文字列)を使う。これにより特定のURLがCode Segment内部に記述されることを防いでいる。

\begin{figure}[htbp]
\begin{center}
\includegraphics{fig/topologymanager.pdf}
\end{center}
\caption{Topology Manager はトポロジーファイルの記述に従ってトポロジーを生成する}
\label{fig:topologymanager}
\end{figure}

\subsection{Topology Manager の設定ファイルの記述方法}
Topology Managerが読み込むトポロジーファイルは Language\cite{graphviz}と呼ばれる言語で記述する。
DOT Languageはプレーンテキストを用いてデータ構造としてのグラフ構造を表現するデータ記述する言語の一種である。
このDOT Languageを用いてクライアント間の接続を表現する。

テキストのみではユーザーが望む形のトポロジーかどうかを判断しにくい。ノードの数が少なければ、可能であるがノードの数が増加するに連れて困難になるが、dotコマンドを用いることでその問題を解決することができる。
dotコマンドでトポロジーファイルを画像として出力することができるので、記述したトポロジーが正しいことを可視化して判断することができる。

クライアント間の接続にはlabelを用いて名前が割り振られている。この接続名を指定することでユーザーは他のノードのDSMにアクセスすることができる。ReceiverにsetKeyを行う際、odsでput、updateする際のmanagerKeyがlabelである。(図\ref{fig:ring})


AliceのNodeを起動する際にコマンドライン引数としてTopology ManagerのIPアドレスとポート番号を指定する。main関数内でTopologyNodeのnewを行い、その際に引数として渡すだけでよい。TopologyNodeの第一引数はAliceのdeamonの設定オブジェクト、第二引数はStart Code Segmentである。このStart Code Segmentがトポロジーが完成した後に実行される。

\begin{table}[htbp]
\lstinputlisting[label=ring, caption=3台でリングを組んだ時の例]{source/ring.dot}
\end{table}

\begin{figure}[htbp]
\begin{itemize}
\item {\ttfamily dot -T png ring.dot -o ring.png}
\end{itemize}

\begin{center}
\includegraphics{fig/ring.pdf}
\end{center}
\caption{dotコマンドで作成された3台で構成されたリングのグラフ}
\label{fig:ring}
\end{figure}