\chapter{分散フレームワーク Alice の概要} \label{chapter:chapter1}
Aliceは、本研究室で開発を行っている分散タスク管理フレームワークである。Cell用のOpen CLに似たTask管理フレームワークCeriumとLindaを相互に接続した分散フレームワークであるFederated Lindaの開発を通して得られた知見が生かされている。

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

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

これらが示しているのは、並列分散実行はコードの並列実行だけでなく、データの単位が重要だということである。そこで、AliceはData SegmentとCode Segmentという単位でデータと処理を細かく分割し、それぞれの依存関係を記述して分散プログラムを作成する。Code SegmentはContinuation based Cの実行単位であり、その双対が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で実装したフレームワークである。Topology Managerを持ち、Blade上での
分散プログラムの実験を容易に行うことができる。また、SEDA Architectureを採用しており、マルチコア上でのスループットの向上を期待している。

\section{Data Segment}
Data Segmentはデータを細かく分割したものであり、数値や文字列などのデータを構造的に保持する。AliceはData Segmentをデータベースとして扱っている。Data Segmentには必ず対になるKeyが存在する。つまりKey Value Storeとして考える事ができる。

Aliceのデータベースは通常のKVSとは異なっている点がある。通常のKVSはプログラミング言語の連想配列やMapと同様に 「Key（キー）」と「Value（値）」がペアとなっている。そのため1つのKeyに対して値は1つである。しかし、Aliceの場合は「Key」と「Queue」がペアとなっているため、Keyに対して複数回putできる。従って取得できるValueも複数存在できる。便宜上これをKey Value Queueと呼ぶものとする。Key毎の追加と取得はLindaに準じた設計になっている。

Data SegmentはData Segment Manager（以下DSM）によって管理されている。ノード毎にLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のKVSとなっている。従ってRemote DSMを指定するKeyはノード内部でuniqueなものである。Remote DSMは他のノードのLocal DSMのproxyと考えられる。つまりRemote DSMは複数存在し、それぞれに対応するノードは異なる。

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

KVQへのアクセスはqueueによって、ノード内部で逐次化される。それ以外は、すべてJavaのThread Poolにより並列実行される。
\subsection{Data Segment API}
以下が用意されているData Segment APIである。これらを用いてデータの送受信を行う。
\begin{itemize}
\item {\ttfamily void put(String key, Object val)}
\item {\ttfamily void update(String key, Object val)}
\item {\ttfamily void peek(Receiver receiver, String key)}
\item {\ttfamily void take(Receiver receiver, String key)}
\end{itemize}
\subsubsection{put}
putはデータをQueueに追加するためのAPIである。Lindaのout()に相当する。(図 \ref{fig:put})
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=100mm]{images/put.pdf}
\end{center}
\caption{queueにデータを追加する}
\label{fig:put}
\end{figure}

\subsubsection{update}
updateはデータを置き換える特急メッセージのように動作する。Lindaのupdate()に相当する。(図 \ref{fig:update})
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=100mm]{./images/update.pdf}
\end{center}
\caption{update"は先頭データを取り除き、queueにデータを追加する}
\label{fig:update}
\end{figure}

\subsubsection{peek}
peekはデータを読み込むAPIである。読み込まれたデータはQueueに残る。要求したデータが存在しなければ、Code Segmentの待ち合わせ （Blocking）が起こる。putやupdateによりデータに更新があった場合、peekが直ちに実行される。Lindaのread()に相当する。
\subsubsection{take}
takeもデータを読み込むためのAPIである。読み込まれたデータはQueueから削除される。Lindaのin()に相当する。
\subsection{Data Segment の表現}
Data Segmentの表現にはMessage Packを利用している。Message Packに関してJavaにおけるデータ表現は以下の3種類があり、制限を伴うが互いに変換可能である。
\begin{itemize}
\item {\ttfamily 一般的なJavaのクラスオブジェクト}
\item {\ttfamily MessagePack for JavaのValueオブジェクト}
\item {\ttfamily byte[]で表現されたbinary}
\end{itemize}

Data Segment APIの内部においてデータは、一般的なJavaのクラスオブジェクトまたはbyteArrayで表現されたbinaryで表現されている。
Localからデータがputされた場合は一般的なJavaのクラスオブジェクトの状態でenqueueされる。RemoteからデータがputされるとbyteArrayで表現されたbinaryの（シリアライズされた）状態でenqueueされる。

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

Remoteに対してputできるデータは、@MessageをもつクラスオブジェクトかMessage Packで扱える型に限られる。

\section{Code Segment}
Code SegmentとはAlice上で実行されるタスクの単位である。ユーザーはCode Segmentを組み合わせることでプログラミングを行う。Code Segmentをユーザーが記述する際に、内部で使用するData Segmentの作成を記述する。入力時のData SegmentをInput Data Segment、出力時をOutput Data Segmentと呼ぶ。Input Data SegmentとOutput Data SegmentによってCode Segmentの間の依存関係が自動的に記述される。

Input Data Segment と Output Data SegmentはCode Segmentに用意されているAPIを用いて作成する。
Input Data Segmentは、LocalかRemoteか、またkeyを指定する必要がある。Code Segmentは、記述したInput Data Segmentが全て揃うとThread poolに送られ、実行される。

Out Data SegmentもLocalかRemoteか、またkeyを指定する必要がある。

現在、Inputの場合はsetKeyを呼ぶ際、Outputはput(またはupdate)の際にノードとkeyの指定を行っている。
しかし、どの時点でノードとkeyの指定を行えばよいか、どのようなAPIを用意するべきかは、議論の余地がある。
\section{Meta Data Segment}
\section{Meta Code Segment}

\section{Topology Manager}
Aliceは複数のノードで構成され、相互に接続される。通信するノードはURLにより直接指定するのではなくTopology Managerで管理する。
Topology Managerはトポロジーダイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきTopology NodeのIPアドレス、ポート番号、接続名を送りトポロジーファイルに記述されたとおりにトポロジーを作成する。(図\ref{fig:topologymanager})

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

Code Segment内部でRemote DSMにアクセスする場合はToplogyManagerによって指定されたノード内部だけで有効なlabel(文字列)を使う。これにより特定のURLがCode Segment内部に記述されることを防いでいる。
\subsection{トポロジーファイルの記述方法}

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

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

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

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

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

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

\section{Aliceによるプログラミング手法}