\documentclass[a4j,12pt]{jreport}
\usepackage[dvips]{graphicx}
\usepackage{mythesis}
\usepackage{multirow}
\usepackage{here}
\setlength{\itemsep}{-1zh}
\title{分散フレームワークAliceのMeta Data Segment}
\icon{
		\includegraphics[width=80mm,bb=0 0 595 842]{fig/ryukyu.pdf}
	}
\year{平成27年度 卒業論文}
\belongto{琉球大学工学部情報工学科}
\author{e125769 照屋 のぞみ  \\ 指導教員 {河野 真治} }
%%
%% プリアンブルに記述
%% Figure 環境中で Table 環境の見出しを表示・カウンタの操作に必要
%%
\makeatletter
\newcommand{\figcaption}[1]{\def\@captype{figure}\caption{#1}}
\newcommand{\tblcaption}[1]{\def\@captype{table}\caption{#1}}
\makeatother
\setlength\abovecaptionskip{0pt}

\begin{document}

% タイトル
\maketitle
\baselineskip 17pt plus 1pt minus 1pt

\pagenumbering{roman}
\setcounter{page}{0}

\tableofcontents	% 目次
\listoffigures		% 図目次
\listoftables		% 表目次

%以下のように、章ごとに個別の tex ファイルを作成して、
% main.tex をコンパイルして確認する。
%章分けは個人で違うので下のフォーマットを参考にして下さい。

% はじめに
\chapter{序論}
\section{研究背景と目的}
近年、スマートフォンやタブレット端末の普及率が増加している。
それに伴いインターネット利用者数も増加しており、ネットワーク上のサービスの利用者の増加は必至である。
従って、サービスには、信頼性とスケーラビリティーが要求される。
ここでいう信頼性とは、定められた環境下で安定して仕様に従った動作を行うことをさす。
またスケーラビリティーとは、サービスの利用者が増大した場合、メモリ等のリソースを追加するだけでサービスを維持できる性能をさす。
しかし、これらをもつ分散プログラムをユーザーが一から記述することは容易ではない。

当研究室ではデータをData Segment、タスクをCode Segmentという単位で記述する分散フレームワークAlice\cite{senkokenkyu}\cite{senkokenkyu2} の開発を行っている。
Aliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。

Aliceでは、処理をComputationとMeta Computationに階層化し、コアな仕様と複雑な例外処理に分離する。
そして分散環境の構築に必要な処理をMeta Computationとして提供する。
プログラマは仕様を大きく変更することなくプログラムの挙動が変えられるため、変更前の信頼性を保ったまま拡張ができる。

本研究では、Alice上に実用的な分散アプリケーションの例題である画面共有システムTreeVNC \cite{treeVNC} を構築する。
TreeVNCは画面変更の差分を木構造にそって配布する分散システムで、差分は数MByteに達するので圧縮を行う必要がある。そして表示時には伸長したデータを取り扱わなければならない。
差分データはAliceのData Segementに対応するため、AliceのMeta Data Segmentとして圧縮機能が必要なる。
これらの機能はTreeVNCではad-hocに実装されているが、AliceではこれをMeta Computationとして実装する。
そして、TreeVNCとの比較を行うことでAlice の実用性を示すと共にAlice のMeta Computationの役割と有効性を示す。


% 基礎概念
\chapter{分散フレームワークAliceの概要}
\section{Code Segment と Data Segment}
AliceではCode Segment（以下CS）とData Segment（以下DS）の依存関係を記述することでプログラミングを行う。
CSは実行に必要なDSが全て揃うと実行される。CSを実行するために必要な入力されるDSのことをInputDS、CSが計算を行った後に出力されるDSのことをOutput DSと呼ぶ。
データの依存関係にないCSは並列実行が可能である（図 \ref{fig:CS} ）。
CSの実行においてDSが他のCSから変更を受けることはない。そのためAliceではデータが他から変更され整合性がとれなくなることはない。

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[width=70mm]{images/dsandcs2.pdf}
    \end{center}
    \caption{CodeSegmentの依存関係 }
    \label{fig:CS}
\end{figure}

AliceはJavaで実装されており、DSはJava Objectに相当する。CSはRunnableなObject(void run()を持つObject)に相当する。
プログラマがCSを記述する際は、CodeSegmentクラスを継承する。

DSは数値や文字列などの基本的なデータの集まりを指し、Aliceが内部にもつデータベースによって管理されている。このデータベースをAliceではDS Managerと呼ぶ。

CSは複数のDS Managerを持っている。DSには対になるString型のkeyが存在し、それぞれのManagerにkeyを指定してDSにアクセスする。
一つのkeyに対して複数のDSをputするとFIFO的に処理される。なのでData Segment Managerは通常のデータベースとは異なる。


\section{Data Segment Manager}
DS Manager（以下DSM）にはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。
Remote DSMは他ノードのLocal DSMに対応するproxyであり、接続しているノードの数だけ存在する（図 \ref{fig:Remote DSM} ）。
他ノードのLocal DSMに書き込みたい場合はRemote DSMに対して書き込めば良い。

Remote DSMを立ち上げるには、DataSegmentクラスが提供するconnectメソッドを用いる。
接続したいノードのipアドレスとport番号、そして任意のManager名を指定することで立ちあげられる。その後はManager名を指定してData Segment APIを用いてDSのやり取りを行うため、プログラマはManager名さえ意識すればLocalへの操作もRemoteへの操作も同じ様に扱える。

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


\section{Data Segment API}
DSの保存・取得にはAliceが提供するAPIを用いる。
putとupdate、flipはOutput DS APIと呼ばれ、DSをDSMに保存する際に用いる。
peekとtakeはInput DS APIと呼ばれ、DSをDSMから取得する際に使用する。

\begin{itemize}
\item {\ttfamily void put(String managerKey, String key, Object val)}
\end{itemize}
DSをDSMに追加するためのAPIである。第一引数はLocal DSMかRemote DSMかといったManager名を指定する。そして第二引数で指定されたkeyに対応するDSとして第三引数の値を追加する。

\begin{itemize}
\item {\ttfamily void update(String managerKey, String key,  Object val)}
\end{itemize}
updateもDSをDSMに追加するためのAPIである。putとの違いは、queueの先頭のDSを削除してからDSを追加することである。そのためAPI実行前後でqueueの中にあるDSの個数は変わらない。

\begin{itemize}
\item{\ttfamily void update(String managerKey, String key,  Receiver val)}
\end{itemize}
flipはDSの転送用のAPIである。取得したDSに対して何もせずに別のKeyに対し保存を行いたい場合、flipを使うことで無駄なコピーなくDSの保存ができる。

\begin{itemize}
\item {\ttfamily void take(String managerKey, String key)}
\end{itemize}
takeはDSを読み込むためのAPIである。読み込まれたDSは削除される。要求したDSが存在しなければ、CSの待ち合わせ （Blocking）が起こる。putやupdateによりDSに更新があった場合、takeが直ちに実行される。

\begin{itemize}
\item {\ttfamily void peek(String managerKey, String key)}
\end{itemize}
peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。



\section{Code Segmentの記述方法}
CSをユーザーが記述する際にはCodeSegmentクラスを継承して記述する(ソースコード \ref{src:StartCodeSegment} , \ref{src:CodeSegment})。
継承することによりCode Segmentで使用するData Segment APIを利用する事ができる。

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

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

ソースコード \ref{src:StartCodeSegment} は、5行目で次に実行させたいCS（ソースコード \ref{src:CodeSegment} ）を作成している。8行目でOutput DS APIを通してLocal DSMに対してDSをputして
いる。
Output DS APIはCSの{\tt ods}というフィールドを用いてアクセスする。
{\tt ods}は{\tt put}と{\tt update}を実行することができる。
TestCodeSegmentはこの"cnt"というkeyに対して依存関係があり、8行目でputが行われるとTestCodeSegmentは実行される。


CSのInput DSは、CSの作成時に指定する必要がある。指定はCommandType(PEEKかTAKE)、DSM名、そしてkey よって行われる。
Input DS API はCSの{\tt ids}というフィールドを用いてアクセスする。
Output DSは、{\tt ods}が提供するput/updateメソッドをそのまま呼べばよかったが、Input DSの場合{\tt ids}にpeek/takeメソッドはなく、create/setKeyメソッド内でCommandTypeを指定して実行す
る。

ソースコード\ref{src:CodeSegment}は、0から9までインクリメントする例題である。
2行目では、Input DS APIがもつcreateメソッドでInput DSを格納する受け皿(Receiver)を作っている。
引数には{\tt PEEK}または{\tt TAKE}を指定する。
\begin{itemize}
\item {\ttfamily Receiver create(CommandType type)}
\end{itemize}

4行目から6行目はコンストラクタである。コンストラクタはオブジェクト指向のプログラミング言語で新たなオブジェクトを生成する際に呼び出されて内容の初期化を行う関数である。

% TestCodeSegmentのコンストラクタが呼ばれた際には、
% \begin{enumerate}
% \item CSが持つフィールド変数 {\tt Receiver input}に{\tt ids.create(CommandType.TAKE)}が行われ、{\tt input}が初期化される。
% \item 5行目にあるTestCodeSegmentのコンストラクタのTAKEが実行される。
% \end{enumerate}

5行目は、2行目のcreateで作られたReceiverが提供するsetKeyメソッドを用いてLocal DSMからDSを取得している。
\begin{itemize}
\item \verb+void setKey(String managerKey, String key)+
\end{itemize}
setKeyメソッドはpeek/takeの実行を行う。どのDSMのどのkeyに対してpeekまたはtakeコマンドを実行させるかを指定できる。コマンドの結果がレスポンスとして届き次第CSは実行される。

実行されるrunメソッドの内容は
\begin{enumerate}
\item 10行目で取得されたDSをInteger型に変換してcountに代入する。
\item 12行目でcountをインクリメントする。
\item 16行目で次に実行されるCSが作られる。（この時点で次のCSはInput DSの待ち状態に入る）
\item 17行目でcountをLocal DSMにputする。Input DSが揃い待ち状態が解決されたため、次のCSが実行される。
\item 13行目が終了条件であり、countの値が10になれば終了する。
 \end{enumerate}
となっている。


\chapter{AliceのMeta Computation}
\section{Computetion と Meta Computation}
Aliceでは、計算の本質的な処理をComputation、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。
AliceのComputationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理と捉えられる。
それに対して、AliceのMeta Computation は、Remoteノードとの通信時のトポロジーの構成や切断・再接続の処理と言える。
つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。

Aliceの機能を追加するということはプログラマ側が使うMeta Computationを追加すると言い換えられる。
AliceではMeta Computationとして分散環境の構築等の機能を提供するため、プログラマはCSを記述する際にトポロジー構成や切断、再接続という状況を予め想定した処理にする必要はない。
プログラマは目的の処理だけ記述し、切断や再接続が起こった場合の処理をMeta Computationとして指定する。
このようにプログラムすることで、通常処理と例外処理を分離することができるため、仕様の変更を抑えたシンプルなプログラムを記述できる。

\subsection{Meta Code Segment と Meta Data Segment}
AliceのMeta ComputationもCS/DSにより実現される。
Meta Computationは、CSの処理を支えるMeta CSと、Meta CSに管理されるMeta DSに分けられる。
図\ref{fig:metaCS}は、AliceのMeta CS/Meta DSの接続関係の例である。
プログラマ側はCSとDSの依存関係を記述するが、その裏ではMeta CSやMeta DSが間に接続されて処理を行っている。

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=70mm]{images/metaCS.pdf}
    \end{center}
    \caption{CS/DSの間にMetaCS/MetaDSが接続される}
    \label{fig:metaCS}
\end{figure}


\section{Aliceが持つMeta Computation}
Aliceでは分散環境構築のためにさまざまなMeta Computationが用意されている。

\subsection{Topology Manager}
Aliceでは、ノード間の接続管理やトポロジーの構成管理を、Topology ManagerというMeta Computationが提供している。
プログラマはトポロジーファイルを用意し、Topology Managerに読み込ませるだけでトポロジーを構成することができる。
トポロジーファイルはDOT Language\cite{dot}という言語で記述される。
DOT Languageとは、プレーンテキストを用いてデータ構造としてのグラフを表現するためのデータ記述言語の一つである。
ソースコード\ref{src:topologyfile}は3台のノードでリングトポロジーを組むときのトポロジーファイルの例である。
\begin{table}[html]
    \lstinputlisting[label=src:topologyfile, caption=トポロジーファイルの例]{source/TopologyFile.dot}
\end{table}
また、DOT Languageファイルはdotコマンドを用いてグラフの画像ファイルを生成することができる。そのため、記述したトポロジーが正しいか可視化することが可能である。

Topology Managerはトポロジーファイルを読み込み、参加を表明したクライアント（以下、Topology Node）に接続するべきクライアントのIPアドレスやポート番号、接続名を送る（図\ref{fig:topologymanager}）。
また、トポロジーファイルでlavelとして指定した名前はRemote DSMの名前としてTopology Nodeに渡される。
そのため、Topology NodeはTopology ManagerのIPアドレスさえ知っていれば自分の接続すべきノードのデータを受け取り、ノード間での正しい接続を実現できる。
\begin{figure}[h]
\begin{center}
\includegraphics[width=60mm]{images/topologymanager.pdf}
\end{center}
\caption{Topology Managerが記述に従いトポロジーを構成}
\label{fig:topologymanager}
\end{figure}

また、実際の分散アプリケーションでは参加するノードの数が予め決まっているとは限らない。
そのためTopology Managerは動的トポロジーにも対応している。
トポロジーの種類を選択してTopology Managerを立ち上げれば、あとは新しいTopology Nodeが参加表明するたびに、Topology ManagerからTopology Nodeに対して接続すべきTopology Nodeの情報がput
され接続処理が順次行われる。
そしてTopology Managerが持つトポロジー情報が更新される。
現在Topology Managerでは動的なトポロジータイプとして二分木に対応している。


\subsection{Keep Alice}
ノード間通信はRemote DSMに対してputやtakeを行うことでのみ発生する。
アプリケーション次第では長時間通信が行われない可能性があり、その間にノード間接続が切れた場合、次の通信が行われるまで切断を発見することができない。
また、接続状態ではあるが応答に時間がかかる場合もある。

これらの問題を検知するために、KeepAliveという定期的にheart beatを送信し生存確認を行うMeta Computationがある。この機能もCS/DSを用いて実装されている。
一定時間内にノードからの応答がない場合、KeepAliveにより、そのノードのRemote DSMが切断される。

また、トポロジーからノードが切断された際にトポロジーを再構成する機能もTopology Managerに用意した。
例えばツリートポロジーでノードが切断された場合、そのノードの子ノードは全体のトポロジーから分断されてしまう。
ノードは切断を検知するとただちにTopology Managerに再接続すべきノード情報を要求し、木を構成し直す。


\subsection{切断・再接続時の処理}
MMORPGでは、試合の最中にサーバーからユーザーが切断された場合、自動的にユーザーが操作するキャラクターをゲームの開始時の位置に戻すという処理が実行される。
同様に、Aliceを用いたアプリケーションでもノードの切断時に対する処理を用意したい場合がある。
そこで、Aliceが切断を検知した際に任意のCSを実行できる機能(ClosedEventManager)を追加した。
プログラマは切断の際に実行したいCSを書き、ClosedEventManagerに登録しておけば良い(ソースコード\ref{src:closedEvent})。
\begin{table}[html]
    \lstinputlisting[label=src:closedEvent, caption=切断時に実行されるCSの登録方法]{source/RegisterEvent.java}
\end{table}

また、再接続してきたノードに対し通常の処理とは別の処理を行わせたい場合がある。
そのため、切断時と同様に再接続してきたノードに任意のCSを実行できるMeta Computationも用意した。



% AliceVNC
\chapter{AliceのTreeVNCへの応用}
\section{TreeVNC}
\section{AliceVNCで用いるMeta Computation}
\section{圧縮のMeta Computationの追加}
\section{Topology Managerの複数対応}

% 実験
\chapter{評価と考察}
\section{性能比較}
\section{コード量比較}
\section{コードの複雑度比較}
\section{他言語等との比較}
\subsection{Erlang}
\subsection{Akka}

% 今後の課題
\chapter{結論}
\section{まとめ}
\section{今後の課題}

% 参考文献
\chapter{参考文献}
\input{bibliography.tex}

% 謝辞
\chapter{謝辞}
\input{thanks.tex}

% 付録
%\input{appendix.tex}

\end{document}