\chapter{Christie}

Christie\cite{christie}とはJavaで記述された並列分散通信フレームワークである。Alice\cite{alice}という前身のプロジェクトが開発されていたが、以下のような問題があった。
データを送受信するAPIはインスタンスを生成して関数を呼び出す様に設計されているが、外部Classからも関数が実行できてしまうため、
受信する際どのkeyに紐づいたデータを受け取るのか、直感的にわからない。
データを管理しているlocalDataSegmentがシングルトンで設計されており、Localで接続を行う際に複数のアプリケーションで立ち上げる必要がある。
データを受け取る際にObject型で受け取っているため、送信元を辿らない限り何の型が送信されているか不明瞭である。


それらの問題点を解消するためにAliceを再設計し、作成されたものがChristieである。
ChristieではAliceの機能や概念を維持しつつ、Aliceで発生していた問題点やプログラムの煩雑さなどを解消している。


\section{Christieの基礎概念}
Christieはタスクとデータを細かい単位に分割してそれぞれの依存関係を記述し、
タスク実行に必要な入力が揃った順から並列実行するというプログラミング手法を用いている。

将来的に当研究室で開発しているGearsOS\cite{gears}のファイルシステムに組み込まれる予定があるため、GearsOSを構成する言語 Continuation based C\cite{cbc}と
似た概念を持っている。Christieに存在する概念として以下の様なものがある。

\begin{itemize}
  \item CodeGear
  \item DataGear
  \item CodeGearManager (以下CGM)
  \item DataGearManager (以下DGM)
\end{itemize}

\begin{figure}[htb]
  \begin{center}
    \includegraphics[width=150mm]{images/GearsRelationships.pdf}
  \end{center}
  \caption{各Gearの関係性}
  \label{fig:GearRelationships}
\end{figure}

図\ref{fig:GearRelationships}はそれぞれのGearの関係性を図示したものである。
CodeGearはクラスやスレッドに相当する。
DataGearは変数データに相当し、CodeGear内でJavaのannotationの機能を用いてkeyに紐づいた変数データを取得できる。
CodeGear内に記述した全てのDataGearにデータが格納された際に、初めてそのCodeGearが実行されるという仕組みになっている。

CGMはノードに相当し、CodeGear、DataGear、DGMを管理している。
DGMはDataGearを管理しており、putという操作によって変数データ、つまりDataGearをDGMに格納できる。
DGMのput操作を行う際にはLocalとRemoteのどちらかを選び、変数のkeyとデータを引数として渡す。
LocalであればLocalのCGMが管理しているDGMに対してDataGearを格納していく。
Remoteであれば、接続したRemote先のCGMが管理しているDGMにDataGearを格納する。

\begin{figure}[htb]
  \begin{center}
      \includegraphics[width=150mm]{images/ChristieClass.pdf}
  \end{center}
  \caption{同一プロセスでのChristieの複数インスタンス立ち上げ}
  \label{fig:MultiInstance}
\end{figure}

図\ref{fig:MultiInstance}は、Christieを同一プロセスで複数のインスタンスを生成した際のDGMやCGMの接続構造を示している。
全てのCGMはThreadPoolと他のCGMをListとして共有している。
ThreadPoolとはCPUに合わせた並列度でqueueに入ったThreadを順次実行していく実行機構である。
ThreadPoolが増えると、CPUコア数に合わない量のThreadを管理することになり並列度が下がるため、1つのThreadPoolで全てのCGMを管理している。
またCGMのListを共有することでメタレベルで全てのCodeGear/DataGearにアクセス可能となっている。
CGを記述する際はCodeGear.classを継承する。
CodeGearはRunnableインターフェースを持っており、runメソッド内に処理を記述することでマルチスレッドで処理が行われる。
CGに記述したkeyと一致するDGが全て揃った時、runに記述された処理が実行される。
runメソッドの引数にCGMを指定しており、そのCGMを経由してChristieのAPIにアクセスする。 
GearsOSではCG間でContextを受け渡すことによってCGはDGにアクセスを行なっているため、Christieでもそのアクセス方法が採用されている。

通常のRunnableクラスでは引数を受け取ることができないが、
CodeGearExecutorというRunnableのMeta Computationを挟んだことでCGMを受け渡しながらの記述を可能にしている。

DGMに対してput操作を行うことでDGM内のqueueにDGを保管できる。
DGを取り出す際には、CG内で宣言した変数データにannotationを付ける。

\section{Christieにおける継続}
プログラムにおける継続とは、計算の途中を前後に分割し、分割した後の部分をfirst class objectとして扱うものである。
つまり、計算途中などのどのような状況でもそのobjectを取り出すことが可能であると言うことである。
しかし継続を扱うためにはStackを含めた実行環境全体をheapにコピーする必要がある。

継続の一種に軽量継続がある。
軽量継続は、Stackや環境のコピーを持っていないが、全ての必要な情報を関数の引数として持っている。
必要な情報とは、計算に必要なデータや関数を実行した後にJumpするべき関数である。

Christieでは、CodeGearとDataGearでプログラムを行っているが、
内部ではannotationでkeyを待ち、DataGearManagerにkeyをつけてDataGearを渡している。
keyでつながったCodeGearに計算は接続されている。実行されたCodeGearはdataをputし、次のCodeGearをSetupしてプログラムの処理が行われていく。
これにより簡易的な継続が行われているといえる。

また、keyでデータを渡すデータ構造にTreeMapを使用することがある。
TreeMapはStackのような働きをするが、TreeMap自体を分散環境で通信する場合に巨大なデータ構造を渡してしまうことになる。
この方法では分散通信のパフォーマンスが低下してしまうと考えられるため、TreeMapのkeyを使用してPut/Takeすることで対応可能であると考える。
その際、2nd keyとして接続先のhostname:portを指定する。
こうするとで、データはproxyとしてアクセスすることが可能となる。
これよりChristieは、名前付き継続と呼ぶことが可能な継続の一つを使用していると言える。

\section{annotationを使用したデータの記述}

ChristieではDGの指定にannotationを使用する。 annotationとはクラスやメソッド、パッケージに対して付加情報を記述できる
Java のMeta Computationである。先頭に@を付けることで記述でき、オリジナルのannotationを定義することもできる。
Christieのannotationには以下の4種類がある。

\begin{description}
  \item[Take] 先頭のDGを読み込み、そのDGを削除する。
  \item[Peek] 先頭のDGを読み込むが、DGは削除されない。そのため、特に操作をしない場合には同じDGを参照し続ける。
  \item[TakeFrom(Remote DGM name)] Takeと処理動作は同じであるが、Remote DGM nameを指定することで、その接続先(Remote)のDGMからTake操作を行うことができる。
  \item[PeekFrom(Remote DGM name)] Peekと処理動作は同じであるが、 Remote DGM nameを指定することで、その接続先(Remote)のDGMからPeek操作を行うことができる。 
\end{description}


DGの宣言には型と変数を直接宣言し、変数名としてkeyを記述する。 そして、その宣言の上にannotationでTakeまたはPeekを指定する(ソースコード\ref{src:TakeExample})。


\lstinputlisting[label=src:TakeExample, caption=Takeの例]{src/java/TakeExample.java}

annotationで指定したDGはCGを生成した際にCodeGear.class内で待ち合わせの処理が行われる。
これにはJavaのreflectionAPIを利用しており、annotationと同時に変数名も取得できるため、面数名によるkeyの指定が可能になっている。

Christieのannotationはフィールドに対してのみ記述可能であるため、keyの指定とTake/Peekの指定を必ず一箇所で書くことが明確に決まっている。
これより、Aliceの様に外のCGからkeyやデータへの干渉をされることがない。
さらにkeyを変数名にしたことで、動的なkeyの指定やkeyと変数名の不一致による可読性の低下を防ぐことが可能となった。

リモートノードに対してTake/Peekをする際には、TakeFrom/PeekFrom annotationを用いる(ソースコード\ref{src:TakeFromExample})。

\lstinputlisting[label=src:TakeFromExample, caption=TakeFromの例]{src/java/TakeFromExample.java}


\section{データの型整合性}
Aliceでは送受信するデータはReceive型という専用の型を使用していた。
内部のデータ自体はobject型だったため、元データの型を知るためには送信元を確認する必要があった。
ChristieではannotationでDGの宣言を行っているため、直接変数の型を宣言することが可能となっている。
ソースコード\ref{src:InputDGExample}はDGのデータを扱う例である。

\lstinputlisting[label=src:InputDGExample, caption=DGのデータを扱う例]{src/java/InputDG.java}

DGとして宣言した変数の型は、JavaのreflectionAPIを用いてCGMで保存され、LocalやRemoteノードと通信する際に適切な変換が行われれる。
この様にプログラマが指定せずとも正しい型でデータを取得できるため、プログラマの負担を減らし信頼性を保証することができる。


\section{CodeGearの記述方法}
以下のソースコード\ref{src:StartCGExample}、\ref{src:CGExample}、\ref{src:CounteObj}はLocalDGMにputしたDGを取り出して表示し、
インクリメントして10回繰り返す例題である。

\lstinputlisting[label=src:StartCGExample, caption=StartCodeGearの記述例]{src/java/StartCountUp.java}
\lstinputlisting[label=src:CGExample, caption=CodeGearの記述例]{src/java/CountUpper.java}
\lstinputlisting[label=src:CounteObj, caption=DGとして送信されるオブジェクトのクラス]{src/java/CountObject.java}

Christieでは、StartCodeGear(以下StartCG)から処理を開始する。
StartCGはStartCodeGear.javaを継承することで記述可能である。

StartCGを記述する際には、createCGMメソッドによりCGMを生成する必要がある(ソースコード\ref{src:StartCGExample} 5行目)。
createCGMの引数にはremoteノードとソケット通信をする際に使用するポート番号を指定する。
CGMを生成した際にLocalDGMやremoteと通信を行うためのDaemonも生成される。


CGに対してannotationから待ち合わせを実行する処理はsetupメソッドが行う。
そのためソースコード\ref{src:StartCGExample}の10行目、ソースコード\ref{src:CGExample}の10行目のように、
CGのインスタンスをCGMのsetupメソッドに渡す必要がある。
そのためどこでもCGの待ち合わせを行うことができず、必ずCGMの生成を行う必要がある。
その制約により、複雑になりがちな分散プログラミングのコードの可読性を高めている。
実行されたCGを再度実行する場合にも、CGのインスタンスを生成してsetupメソッドに渡す。



\section{DataGearManagerの複数立ち上げ}
AliceではLocalDGMと同じ機能のLocalDataSegmentManagaer(以下LocalDSM)がstaticで実装されていたため、複数のLocalDSMを立ち上げることができなかった。
しかしChristieではCGMの生成に伴いLocalDGMも生成されるため、複数作成が可能である。
複数のLocalDGM同士のやり取りも、Remoteへの接続と同じ様に相手をRemoteDGMとしてproxyとして立ち上げることでアクセス可能である(図\ref{fig:LocalRemoteCommunication})。

\begin{figure}[tb]
  \begin{center}
      \includegraphics[width=120mm]{images/LocalRemoteCommunication.pdf}
  \end{center}
  \caption{RemoteDGMを介したCGM間の通信}
  \label{fig:LocalRemoteCommunication}
\end{figure}


ソースコード\ref{src:2LocalDGM}はLocalDGMを2つ立ち上げ、お互いをremoteに見立てて通信する例である。
6行目にあるように、RemoteDGMを立ち上げるにはCGMが持つcreateRemoteDGMメソッドを用いる。
引数にはRemoteDGM名と接続するremoteノードhost名、ポート番号を指定している。

\newpage

\lstinputlisting[label=src:2LocalDGM, caption=LocalDGMを2つ作る例]{src/java/RemoteDGMCommunication.java}

remoteへの接続と同じ様にアクセスが可能になっており、コードを変更せずに同一マシン上の1つのアプリケーション内で分散アプリケーションのテストが可能となっている。


また、CGMは内部に同一プロセス全てのCGMリストをstaticで持っており、複数生成したCGMを全て管理している。
つまり、メタレベルではRemoteDGMを介さずに各LocalDGMに相互アクセス可能である。

\newpage

\section{通信フロー}
本章で説明したChristieの設計をいくつか例を挙げてChristieの通信のフローをシーケンス図を用いて解説する。
図\ref{fig:LocalTakeSequence}はLocalDGMにTakeを行い、LocalDGM内にDGがあったときの処理の流れである。


\begin{figure}[htb]
  \begin{center}
      \includegraphics[width=160mm]{images/LocalSequence.pdf}
  \end{center}
  \caption{LocalDGMにTakeした際のフロー}
  \label{fig:LocalTakeSequence}
\end{figure}


プログラマはmainでCGMを生成する。CGMと同時にLocalDGMが作成される。
続いてStartCG内でCGのインスタンスを作成し、setupメソッドが呼ばれると、DGに付与されたannotationからTakeコマンドが作られ実行される。
CGは生成したコマンドの総数を初期値としたカウンタを持っており、コマンドが解決される(DGが揃う)度にカウンタは減少する。
カウンタが0になると待ち合わせが完了したとなり、run内の処理がThreadPoolへ送られる。


図\ref{fig:RemotePutSequence}は、LocalDGMにTakeを行うが、LocalDGM内にDGがなかったためにPutの待ち合わせを行うときの処理の流れである。
mainなどの最初の処理は図\ref{fig:LocalTakeSequence}と同様のため省略する。


\begin{figure}[htb]
  \begin{center}
      \includegraphics[width=160mm]{images/RemotePutSequence.pdf}
  \end{center}
  \caption{RemoteDGMからPutされた際のフロー}
  \label{fig:RemotePutSequence}
\end{figure}


LocalまたはRemoteノードからPutコマンドが実行された際にwaitListを確認し、
PutされたDGを待っているコマンドが存在すれば、そのコマンドは実行される。


図\ref{fig:RemoteTakeSequence}はRemoteDGMにTakeを行った際の処理の流れである。


\begin{figure}[htb]
  \begin{center}
      \includegraphics[width=160mm]{images/RemoteTakeSequence.pdf}
  \end{center}
  \caption{RemoteDGMにTakeした際のフロー}
  \label{fig:RemoteTakeSequence}
\end{figure}

プログラマはStartCGで事前にRemoteDGMを生成しておく。
続いて、TakeFrom annotationからRemoteDGMに対するTakeコマンドが生成され実行される。
TakeFromの様にRemoteからの応答を待つコマンドはLocalDGMではなく、RemoteDGMのwaitListに格納される。
RemoteDGMに対するTakeコマンドはMessagePack形式に変換され、RemoteDGMが参照している別ノードのLocalDGMに送信される。

送信されたTakeコマンドを受け取ったLocalDGMは、要求されたDGがあればReplyコマンドを生成して送り返す。
もしDGがなければ、Remoteから来たコマンドもLocalの場合と同様にLocalDGMのwaitListに格納される。

Replyコマンドを受け取るとRemoteDGMはwaitListに入っていたコマンドを解決し、待ち合わせが完了する。


\section{Topology Manager}
Topology Manager\cite{topology}とは、Christie上でのNetwork Topologyを自動的に形成する機能である。
Topologyを形成するために参加を表明したnode、TopologyNodeに名前を与え、必要があればnode同士の接続も自動で行う。
Topology ManagerのTopologyの形成方法として、静的Topologyと動的Topologyの2つがある。

静的Topologyはソースコード \ref{src:ringdot}のようなdot形式のファイルを与えることでnodeの関係を図\ref{fig:ringdot}のように構築できる。
静的Topologyはdotファイルのnode数と同等のTopologyNodeがあって初めて、CGが実行される。


\begin{figure}[htb]
  \begin{center}
      \includegraphics[width=120mm]{images/ring.pdf}
  \end{center}
  \caption{ソースコード \ref{src:ringdot}によるring状の接続}
  \label{fig:ringdot}
\end{figure}

\newpage

\lstinputlisting[label=src:ringdot, caption=dot形式によるnode間接続の記述]{src/java/ring.dot}


動的Topologyは図\ref{fig:dynamicTopology}のような手順で自動的に接続が行われる。
nodeが参加表明を行うと、Topologyを管理しているManagerからHost messageがnodeへ送信され、nodeは接続すべき親に接続を行う。
親はHostから送信されるnode infoより子nodeとの接続を行う。

\begin{figure}[htb]
  \begin{center}
      \includegraphics[width=140mm]{images/DynamicTopology.pdf}
  \end{center}
  \caption{動的Topologyの接続手順}
  \label{fig:dynamicTopology}
\end{figure}


現在はTree型にのみ対応しているが、Star型への対応も可能である。