\documentclass[a4j,12pt]{jreport}
\usepackage[dvipdfmx,hiresbb]{graphicx}
\usepackage{mythesis}
\usepackage{multirow}
\usepackage{listings}
\usepackage{url}
\lstset{%
  language={Java},%使用言語
    basicstyle={\small},%書体
  commentstyle={\small\itshape},%コメントの書体
    keywordstyle={\small\bfseries},%キーワードの書体
  %identifierstyle={\small},%
  %ndkeywordstyle={\small},%
  stringstyle={\small},%文字列の書体
    frame={trlb},%外枠
  breaklines=true,%改行
    columns=[l]{fullflexible},%
  xrightmargin=0zw,%
    xleftmargin=3zw,%
  numbers=left,%行番号の表示
    numberstyle={\scriptsize},%行番号の書体
  numbersep=1zw,%
    stepnumber=1,
  lineskip=-0.5ex,%
    captionpos=b,%キャプションの位置
}
\renewcommand{\lstlistingname}{Code}
\usepackage{here}
\setlength{\itemsep}{-1zh}
\title{分散フレームワークAliceのMeta Data Segment}
\icon{
		\includegraphics[width=50mm,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

\setcounter{page}{0}

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

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

% はじめに
\chapter{序論}
\pagenumbering{arabic}
\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{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=150mm]{images/remote_datasegment.pdf}
    \end{center}
    \caption{Remote DSMは他のノードのLocal DSMのproxy }
    \label{fig:Remote DSM}
\end{figure}

\newpage

\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が削除されないことである。

\newpage

\section{Code Segmentの記述方法}
CSをユーザーが記述する際にはCodeSegmentクラスを継承して記述する(ソースコード \ref{src:StartCodeSegment} , \ref{src:CodeSegment})。

継承することによりCode Segmentで使用するData Segment APIを利用する事ができる。

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

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

\newpage

ソースコード \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}と{\tt flip}を実行することができる。
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/flipメソッドをそのまま呼べばよかったが、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として指定する。
このようにプログラムすることで、通常処理と例外処理を分離することができるため、仕様の変更を抑えたシンプルなプログラムを記述できる。

現在Aliceには、トポロジーの構成・管理機能、ノードの生存確認機能、ノードの切断・再接続時の処理管理機能などのMeta Computationが用意されている。

\newpage

\subsection{Meta Code Segment と Meta Data Segment}
Alice提供するMeta ComputationもCS/DSにより実現される。
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=120mm]{images/MetaCSDS.pdf}
    \end{center}
    \caption{CS/DSの間にMetaCS/MetaDSが接続される}
    \label{fig:metaCS}
\end{figure}

Meta DSは基本的にAliceを構成するCSによってのみ管理され、プログラマは認識できない。
しかし一部のMeta DSはプログラマがアプリケーションに利用することもできる。
例えば、トポロジー管理のMeta Computationなどで使われる"\_CLIST"というMeta DSには、利用可能なRemote DSMの情報が管理されている。
プログラマはこのMeta DSを取得しRemote DSM名を指定することで、動的にDSの伝搬などを行うことができる。


\newpage

\section{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}）。

\newpage

また、トポロジーファイルでlavelとして指定した名前はRemote DSMの名前としてTopology Nodeに渡される。
そのため、Topology NodeはTopology ManagerのIPアドレスさえ知っていれば自分の接続すべきノードのデータを受け取り、ノード間での正しい接続を実現できる。
\begin{figure}[h]
\begin{center}
\includegraphics{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では動的なトポロジータイプとして二分木に対応している。

\newpage

\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に登録しておけば良い。
また、再接続してきたノードに対し通常の処理とは別の処理を行わせたい場合がある。
そのため、切断時と同様に再接続してきたノードに任意のCSを実行できるMeta Computationも用意した。


% AliceVNC
\chapter{AliceのTreeVNCへの応用}
AliceのMeta Computationが実用的なアプリケーションの記述において有用であることを確認する。
そのために、TreeVNCをAliceを用いて実装したAliceVNCの作成を行った\cite{sigOS}。

\section{TreeVNC}
TreeVNCとは、当研究室で開発を行っている授業向け画面共有システムである。
オープンソースのVNCであるTightVNC \cite{tightVNC} をもとに作られている。
授業でVNCを使う場合、１つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう(図 \ref{fig:vncstructure})。
この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである(図 \ref{fig:treestructure})。
\begin{figure}[htbp]
\begin{tabular}{cc}
\begin{minipage}{0.5\hsize}
\begin{center}
\includegraphics[width=80mm]{images/vnc.pdf}
\caption{通常のVNCの構造}
\label{fig:vncstructure}
\end{center}
\end{minipage}
\begin{minipage}{0.5\hsize}
\begin{center}
\includegraphics[width=80mm]{images/treestructure.pdf}
\caption{TreeVNCの構造}
\label{fig:treestructure}
\end{center}
\end{minipage}
\end{tabular}
\end{figure}

\newpage

\section{AliceVNC}
図 \ref{fig:TreeVNC}はAliceVNCを実現するための構成である。leftとrightのRemote DSMを用意し子ノードと接続することで木構造を実現する。

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=120mm]{images/TreeVNC.pdf}
    \end{center}
    \caption{AliceVNC の構造}
    \label{fig:TreeVNC}
\end{figure}

TreeVNCは通信処理部分や画面データの処理部分が１つのコード内で記述され、大変複雑になっている。
しかし、Aliceで記述すればMeta Computationにより本質的な処理とそれを支える通信処理部分で分離できる。
TreeVNCでは3章で述べた動的なトポロジーの構成、切断ノードの発見、再接続・トポロジーの再構成といった通信処理のMeta Computationが活用できる。
そのため、TightVNCからの修正の少ない、見通しの良い記述で構成可能と期待される。

\newpage

\chapter{圧縮のMeta Computationの追加}
\section{圧縮のMeta Data Segment}
TreeVNCでは画面配信の際、データを圧縮してノード間通信を行っている。
そのため、AliceVNCにも圧縮されたデータ形式を扱える機能が必要だと考えた。
しかし、ただデータを圧縮する機構を追加すればいいわけではない。

AliceVNCでは、ノードは受け取った画面データを描画すると同時に、子ノードのRemote DSMに送信する。
ノードはDSを受信するとそれを一度解凍して画面を表示し、再圧縮して子ノードに送信する。
しかし、受け取ったデータを自分の子ノードに対して送信する際には、解凍する必要はない。
圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる。

そこで、DSを複数作るのではなく１つのDS内で複数の表現を持たせ、必要に応じた形式でDSを扱うことを可能にした。
Meta DSに相当するReceiveData.classに、次の3種類の表現を同時に持つことができるようにしたことで、データの多態性を実現した。

\begin{enumerate}
  \item 一般的なJavaのクラスオブジェクト
  \item MessagePack for Java\cite{MessagePack}でシリアライズ化されたバイナリオブジェクト
  \item 2を圧縮したバイナリオブジェクト
\end{enumerate}

Local DSMにputされた場合は、(1)の一般的なJavaクラスオブジェクトとして追加される。
Remote DSMにputされた場合は、通信時に(2)のbyteArrayに変換されたバイナリオブジェクトに変換されたDSが追加される。
この2つの形式は従来のAliceが持っていた表現である。
今回、Remote DSMに圧縮形式での通信を行いたいため、(3)の圧縮表現を追加した。

\newpage

ソースコード \ref{src:ReceiveData1} は変更前のReceiveData.classである。
変更前はDSの表現は１つでフラグによって、Local DSM にputする(1)の形式とRemote DSMにputする(2)の形式を判別していた。
しかしこの実装では圧縮形式と非圧縮形式を同時に持つことができないため、AliceVNCでは解凍・再圧縮が必要になってしまう。

変更後の実装ではソースコード \ref{src:ReceiveData1} のようになっている。
{\tt val}に(1) 一般的なJavaのクラスオブジェクト の表現でデータ本体が保存される。
{\tt messagePack}には(2) シリアライズ化されたバイナリオブジェクトが保存される。
そして、{\tt zMessagePack}には(3) 圧縮されたバイナリオブジェクトが保存される。
このようにDSが複数の表現を同時に保持することで、DSが圧縮表現を持っている場合に再圧縮する必要がなくなる。
プログラマ側がから見れば1つのDSであり直接これら３つの表現を操作することはないため、これらはAliceのMeta Data Segmentと言える。

\begin{table}[html]
\lstinputlisting[label=src:ReceiveData1, caption=変更前のデータ表現]{source/beforeReceiveData.java}
\end{table}

\begin{table}[html]
\lstinputlisting[label=src:ReceiveData2, caption=変更後のデータ表現]{source/ReceiveData.java}
\end{table}


\newpage

\section{圧縮のMeta Code Segment}
圧縮表現を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerを追加した。
Compressed DSMの内部では、put/updateが呼ばれた際にReceiveData.classが圧縮表現を持っていればそれを使用し、持っていなければその時点で圧縮表現を作ってput/updateを行う。
Local Compressed DSM は表現の判別や変換を行うだけで、操作する対象は Local DSM と同じDSを指すため、DSの管理が別々になるわけではない。


ソースコード \ref{src:before} はRemote DSMに対しInt型のデータをputする記述である。
この通信を圧縮形式のDSで行いたい場合、ソースコード \ref{src:after} のように指定するDSM名の先頭に"compressed"をつければCompressed DSM内部の圧縮Meta Computationが走り圧縮形式に変換さ
れたDSとなって通信が行われる。

\begin{table}[html]
\lstinputlisting[label=src:before, caption=通常のDSを扱うCSの例]{source/beforeCompress.java}
\end{table}

\begin{table}[html]
\lstinputlisting[label=src:after,caption=圧縮したDSを扱うCSの例]{source/afterCompress.java}
\end{table}

この機能は先述のMeta Data Segmentを扱うMeta Code Segmentと言える。
これによりユーザは指定するDSMを変えるだけで、他の計算部分を変えずに圧縮表現をDS内で持つことができる。
ノードは圧縮されたDSを受け取った後、そのまま子ノードにflipメソッドで転送すれば圧縮状態のまま送信されるので、送信の際の再圧縮がなくなる。


画面表示の際はReceiveData.class内のasClassメソッドを使うことで適切な形式でデータを取得できる。
asClassメソッドはDSを目的の型にcastするためのメソッドである。
AliceVNCで圧縮形式を指定してDSを送信すると、それを受け取るDSMは圧縮形式のみを持ったDSとして保存する。
そしてasClassメソッドが呼ばれて初めて、メソッド内で解凍してcastが行われDSが複数の表現を同時に持つようになる。
これによりDSの表現を必要になったときに作成できるため、プログラマはどんな形式でDSを受け取ってもDSを編集可能な形式として扱うことができる。
また、複数表現は必要なときにしか作成されないため、メモリ使用量も必要最低限に抑えることができる。

\newpage

\section{Aliceの通信プロトコルの変更}
4.2で述べたように、Remoteからputされたデータは必ずシリアライズ化されておりbyteArrayで表現される。
しかし、データの表現に圧縮したbyteArrayを追加したため、RemoteからputされたbyteArrayが圧縮されているのかそうでないのかを判別がつかなくなった。

そこで、Aliceの通信におけるヘッダにあたるCommandMessage.class(ソースコード\ref {src:CommandMessage} 表 \ref{tb:variable})に圧縮状態を表すフラグを追加した。
これによってputされたDSMはフラグに応じた適切な形式でReceiveData.class内にDSを格納できる。
また、CommandMessage.classに圧縮前のデータサイズも追加したことで、適切な解凍が可能になった。

\begin{table}[html]
\lstinputlisting[label=src:CommandMessage, caption=CommandMessage]{source/CommandMessage.java}
\end{table}


\begin{table}[htbp]
\caption{CommandMessageの変数名の説明}
\label{tb:variable}
\begin{center}
\begin{tabular} {|l|l|}
  \hline
  変数名&説明\\
  \hline
  type&CommandType {\tt PEEK, PUT}などを表す\\
  \hline
  seq&\shortstack{Data Segmentの待ち合わせを行っている\\Code Segmentを表すunique number }\\
  \hline
  key&どのKeyに対して操作を行うか指定する\\
  \hline

  quickFlag&SEDAを挟まずCommandを処理を行うかを示す\\
  \hline

  compressed&データ本体の圧縮状態を示す\\
  \hline

  dataSize&圧縮前のデータサイズを表す\\
  \hline

\end{tabular}
\end{center}
\end{table}

\newpage


% 実験
\chapter{評価と考察}
\section{圧縮のMeta Computationの評価}
圧縮のMeta Computationが正しく機能しているかを確認するために通信時間の計測を行った。
2台のPC間でお互いにデータを100回転送し合う。圧縮を指定したコードとしていないコードで5回計測した。

結果が表\ref{tb:compressmesure}である。
データサイズから見ても圧縮に成功していることがわかる。
通信においても、所要時間が1/3以下に抑えられていることから圧縮が効果的に作用している。
TreeVNCと同等の性能をだすために有用なMeta Computationが実装できたと言える。

\begin{table}[htbp]
\caption{圧縮機能の測定結果}
\label{tb:compressmesure}
\begin{center}
\begin{tabular} {|l|l|l|}
  \hline
  　 &圧縮なし&圧縮あり\\
  \hline
  データサイズ&300KB&91KB\\
  \hline
  平均通信時間&6014ms&1764ms\\
  \hline
\end{tabular}
\end{center}
\end{table}



\section{TreeVNCとAliceVNCの比較}
TreeVNCをAlice上で構築するために必要な機能をAliceのMeta Computationとして実装した。
これにより、AliceVNCが簡潔な記述でTreeVNCと同等の性能を出せれば、実用的な分散アプリケーションの実装においてAliceのMeta Computationは有用であるといえる。
そこで、TreeVNCとAliceVNCの性能評価としてメッセージ伝達速度の比較を、コードの評価としてコード量とその複雑度の比較を行った\cite{prosym}。

\subsection{メッセージ伝達速度の比較}
TreeVNC/AliceVNCにおいて、配信する画像データは構成した木を伝ってノードに伝搬され、接続する人数が増える毎に木の段数は増えていく。
そこで、木の段数ごとにメッセージの到達にどれぐらい時間がかかっているかを計測した。

講義内で学生に協力してもらい、最大17名の接続がある中でTreeVNC、AliceVNCの木の段数1〜3の測定を行った。

　

\textbf{実験内容}

ルートノードから画面データを子ノードに伝搬する際に、計測用のヘッダをつけたパケットを子ノードに送信する。
各子ノードはパケットを受け取り自身のViewerに画面データを表示すると同時に、計測用ヘッダ部分のみのDSを作成し、親ノードに送り返す。
計測用DSは木を伝ってルートノードまで送り返され、ルートノードは受け取った計測用DSから到達時間を計算する。

計測用のヘッダは以下の要素で構成されている。
\begin{table}[htbp]
\caption{計測用ヘッダの変数名の説明}
\label{tb:mesure}
\begin{center}
\begin{tabular} {|l|l|}
  \hline
  変数名&説明\\
  \hline
  time&ルートノードがパケットを送信した時刻\\
  \hline
  depth&木の段数。初期値=1。\\
  \hline
  dataSize&送信時の形式に変換済みの画面データのサイズ\\
  \hline
\end{tabular}
\end{center}
\end{table}

timeにはパケットの送信時刻を、dataSizeには圧縮された画面データのサイズを付けて送信する。
depthは各ノードに到達するごとにインクリメントされる。

到達時間の計算方法は、計測用DSを受け取った時刻とDSのtime（送信した時刻）の差をとる。
この到達時間は画面データがノードまで到達した時間と計測DSをルートまで送り返す時間を含めているが、送り返す時間は誤差として考える。
また、depthは各ノードに到達するごとにインクリメントされるため、送り返す際もインクリメントされる。そのため、木の段数を計算するにはdepthを1/2した値となる。



\textbf{実験結果}  


3段目の測定結果の散布図を示す（図\ref{fig:TreeVNC_delay} 〜 \ref{fig:AliceVNC_compress_delay}）。
X軸が画面データのサイズ(byte)、Y軸が計算した到達時間(ms)である。
実験時間の都合上、AliceVNCの計測時間が他より短くなってしまったためプロットされた点の数が少なくなっている。
また、それぞれの図で処理に10000ms以上かかっている点の集合が見られるが、これは今回の実験において3段目にPCのスペック上処理が遅いノードが1台あったためである。
そのため比較においてこの点集合は無視する。

どの図も同様の傾向があり、画面データのサイズが小さいうちは処理時間も5ms程度だが、50000byte以上から比例して処理時間も遅くなっている。
このことからAliceVNCはTreeVNCと同等の処理性能があることがわかる。


\begin{figure}[htbp]
    \begin{center}
        \includegraphics[width=100mm]{images/TreeVNC_depth3.pdf}
    \end{center}
    \caption{TreeVNCの測定結果}
    \label{fig:TreeVNC_delay}
    
    \begin{center}
        \includegraphics[width=100mm]{images/AliceVNC_compress_depth3.pdf}
    \end{center}
    \caption{AliceVNC(圧縮・転送機能あり)の測定結果}
    \label{fig:AliceVNC_compress_delay}
\end{figure}

\newpage　

\subsection{コード量比較}

TreeVNCとAliceVNCのコード量を比較した表が表\ref{tb:code}である。
TightVNCを含むコード全体にwcを行い、行数と単語数を比較した。
また、hg diffでTightVNCからの変更行数を調べ変更量を比較した。

表からわかるように、Aliceを用いればコードの行数が25\%削減できる。
また、TreeVNCではTightVNCに大幅に修正を加えながら作成したため仕様の変更が多かった。
しかし、AliceVNCではTightVNCにほとんど修正を加えることなくトポロジー構成等のAliceのMeta Computationを使うために新しいクラスを作成したのみであった。
そのためTreeVNCに比べ75\%も仕様の変更が抑えられている。
\begin{table}[htbp]
\label{tb:code}
\begin{center}
\begin{tabular} {|l|l|l|l|}
  \hline
   &行数&単語数&変更行数\\
  \hline
  TreeVNC&19502&73646&7351\\%11369+8133=19502,47010+26636,2094+5257
  \hline
  AliceVNC&14647&59217&1129\\%689+7094+6864=14647,23035+34610+1572,689+395+45
  \hline
  減少率(\%)&25&20&75\\
  \hline
\end{tabular}
\end{center}
\end{table}


\subsection{コードの複雑度比較}
コード量の比較で述べたように、TreeVNCはTightVNCからの変更が多い。
その理由の一つがトポロジーの構成や通信処理がコアな仕様と分離できておらず、
そのためTreeVNCは大変複雑な記述になってしまっている。

そこでTreeVNCとAliceVNCにおいてコードの複雑度を比較した。
今回、複雑度の指標としてThomas McCabeが提案した循環的複雑度\cite{complaxy}を用いた。
循環的複雑度とはコード内の線形独立な経路の数であり、if文やfor文が多ければ複雑度も高くなりバグ混入率も高まる。
一般的に、循環的複雑度が10以下であればバグ混入率の少ない非常に良いコードとされる。
計測にはIntelliJのCodeMetrics計測プラグインであるMetricsReloadedを使用した。

\newpage

表\ref{tb:complex}はTightVNC、TreeVNC、AliceVNCにおける循環的複雑度の比較である。

\begin{table}[htbp]
\caption{複雑度の比較}
\label{tb:complex}
\begin{center}
\begin{tabular} {|l|l|l|}
  \hline
   &平均値&最高値\\
  \hline
  TightVNC&13.63&97\\
  \hline
  TreeVNC&15.33&141\\
  \hline
  AliceVNC&10.95&99\\%(4.12+13.64)/2 (4.12+9.16+19.59)/3
  \hline
\end{tabular}
\end{center}
\end{table}

プロジェクト全体でのクラスの複雑度の平均値と最高値をとった。
平均値・最高値ともにAliceVNCのほうが複雑度が低いことから、Aliceではシンプルな記述が可能だということがわかる。

TreeVNCで最高値を出したTreeRFBProto.classは全てプログラマが記述したコードであり、データの待ち合わせのためのタイマー処理や通信処理、画面データの圧縮処理などの複数のスレッド処理が集中した複雑なコードになっている。
これをAliceで記述した場合、データの待ち合わせはCSが行うためプログラマがデータの不整合を気にする必要はなく、また通信処理や圧縮処理もMeta Computationが提供するためコードが複雑になることはない。

AliceVNCで複雑度の最高値を出したSwingViewerWindow.classはTightVNCで最高値を出したクラスと同じであり、コード量の比較でも示したようにAliceVNCで変更を加えた点がほとんどない。つまりこの複雑度は元来TightVNCが持っている複雑度と言える。

AliceVNCとTreeVNCの性能比較・コード比較から、AliceVNCはTreeVNCと同等の性能を持つ分散アプリケーションの記述ができ、かつコードの修正量・複雑度共に低く抑える能力を有することがわかった
。

\newpage

\section{他言語等との比較}
Aliceが採用しているCS/DSのプログラミングモデルやMeta Computationの特性を明確にするため、他言語・フレームワークとの類似点・相違点を比較した。

\subsection{Erlang}

並列指向プログラミング言語Erlang\cite{Erlang}は、プロセスと呼ばれるid付きの独立したタスクに対して、データをメッセージでやりとりする。
タスクをプロセスという細かい単位に分割して並列に動かす点や、メモリロックの仕組みを必要としない点はAliceと同様である。

しかしErlangでは分散環境の構築等はすべてプログラマ自身が記述しなければならない。
Aliceでは分散環境の構築はTopology ManagerなどのMeta Computationが行うためプログラマはトポロジーを指定するだけで良い。
また、Erlangでは複数のデータの待ち合わせのための再帰処理も自分で書かないといけない。
一方、Aliceのプログラミング手法はCSが必要なデータが全て揃うまで待ち合わせを行うためその必要はない。


\subsection{Akka}

Akka\cite{Akka}はScala・Java向けの並列分散処理フレームワークである。
アクターモデルを採用しており、アクターと呼ばれるアドレスを持ったタスクに、データをメッセージでやりとりする点がErlangと似ている。
AkkaもErlangもプロセス/アクターに直接データをやりとりする。データには名前がないため、メッセージを受け取ったあとにその内容を確認した上で次にどう振る舞うかを判断する。
一方Aliceでは、DSをCSに直接やりとりはせず、keyを指定してDSMにputする。
また、DSをtakeするときもkeyを指定して取り出すためどんなデータが入っているかを確認する必要がなく、扱い易い。

Akkaの特徴として、メッセージを送りたいプロセスのアドレスを知っていればアクターがどのマシン上にあるかを意識せずにプログラミングできるという点がある。
逆にAliceはどのRemote DSMに対してやり取りをするかを考慮するが、CSがOutputしたDSを次にどのCSに渡すかを意識する必要がない。この点はアクターモデルとCS/DSモデルのパラダイムの違いと言え
る。

一方AliceとAkkaは提供されるAPIという点で類似している。AkkaのメッセージAPIでは、メッセージを送るtellメソッドと、メッセージを送って返信を待つaskメソッドが用意されている。これはAliceのDataSegment APIのput/takeメソッドに対応している。

また、Akkaのもう一つの特徴として、アクターで親子関係を構成できる点がある。
分散通信部分を子アクターに分離し、親アクターは子アクターのExceptionが発生した時に再起動や終了といった処理を指定できる。
さらにRouterという子アクターへのメッセージの流れを制御するアクターや、Dispatcherというアクターへのスレッドの割当を管理する機能をAkkaが提供している。
このように処理を階層化し複雑な処理をフレームワーク側が提供する仕組みはAliceのMeta Computationと共通している。
相違点としては、AliceのMeta DSのようにデータの多態性を実現する機能はAkkaにはない。

\subsection{MPICH?}


% 今後の課題
\chapter{結論}
\section{まとめ}
並列分散フレームワークAliceでは、スケーラブルかつ信頼性の高いプログラムを記述する環境を実現するため、CS/DSの計算モデルとMeta Computationによる実装の階層化を採用している。
Aliceが実用的な分散アプリケーションを記述するために必要なMeta Computationとして、多態性を持つデータを扱う機能や無駄なコピーなくデータを転送する機能を実装した。
そしてMeta Computationを用いて分散アプリケーションTreeVNCをAlice上で実装し性能評価を行った。
その結果、TreeVNCで使用される基本機能はAliceでも実現でき、同等の性能を出すことができるということが分かった。
またコードの観点からTreeVNCとAliceVNCを比較した結果、Aliceが仕様の変更を抑えたシンプルな記述を実現し、信頼性の高い実用的な分散アプリケーションを構築するに有用であることが確認された
。

\section{今後の課題}
\subsection{AliceVNCのNAT超え通信の実装}
今後の課題としては、TreeVNCで実装が困難であったNATを超えたノード間通信をAliceVNCで実現し、その性能とコード修正量を比較することが挙げられる。
図\ref{fig:overNAT}は２つの違うプライベートネットワークを超えた接続の設計例である。

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=120mm]{images/overNAT.pdf}
    \end{center}
    \caption{複数のTopology ManagerでNAT超えを実現}
    \label{fig:overNAT}
\end{figure}

各ネットワークごとにTopoogy Managerを立ち上げることでネットワークを超えたノード間接続を実現する。
プライベートネットワークのTopoogy Managerは今までどおりネットワーク内に木を構築・管理する。
他のネットワークにあるノードBがノードAに接続したい場合は、グローバルアドレスを持ったTopology Managerに参加表明をすればノードAの情報が提供され、ノードAの子ノードとして接続される。
つまり、Topology Managerを複数用意するだけで、Topology Manager自体の「参加表明のあったノードで木を構成する」という仕様は全く変更しないで良い。
TreeVNCでは500行以上の変更が必要とされたが、Aliceでは複数のTopology Managerに接続するためのconfigファイルを変更するだけなので、AliceVNCの仕様の変更を抑えられると期待される。
この機能も実現できれば、AliceのMeta Computationが拡張性の高い環境を提供できると言える。

\subsection{セキュリティのサポート}
現在のAliceはネットワーク通信においてセキュリティをサポートしていない。
しかし、圧縮機能と同様に、暗号化形式を扱うMeta Computationを追加すれば、プログラマが記述するComputation部分を大きく変えずに自由度の高い通信を行うことができると期待できる。

\subsection{APIの再設計}
2.4で示したように、DSを取得するときのAPIはpeek/takeが直接扱えず、create/setKeyを組み合わせてプログラミングしなければならない。
この設計だとプログラマにとってわかりづらく、コンストラクタ内でtakeを行いたい場合はsetKeyを必ず最後に呼ばなければならない等の注意点がある。
put/update/flipと同様に、peek/takeをそのまま呼べるように再設計する必要がある。

\subsection{DSの型情報のマネジメント}
Aliceでは型情報がないので、peek/takeする際にどんな型のデータが入っているのかがわからない。
takeしたDSの型を確認したい場合には、そのDSをputしている部分を確認しなくてはならない。
そのため、型情報をサポートする機能が必要である。

\subsection{DSとMeta DSの領域分け}
現在、DSとMeta DSは同じData Segment Managerで管理されており、同じAPIを利用してアクセスされる。
そのため誰でもMeta DSの変更が可能になってしまっている。
プログラマが定義しようとしたKeyが偶然Aliceがもともと持っているMeta DSのKeyと一致してしまった場合、ユーザーが意図した動作にならずエラーとなる状況は充分にありえる。
しかもMeta DSはプログラマ側からは認識できないためエラーの解決がしづらい。
このような事態を避けるためにも、DSの領域分けが必要である。

また、現在はMeta DSに対してtakeすることもできるため、アクセスしようとしたKeyに対してDSが存在せず、Aliceが機能しなくなる場合も想定される。
そのため、プログラマ側のCSとMeta CSを区別し、CSからはpeekのみ許可するMeta Computationも必要になってくると考えられる。

\subsection{データの永続性の確保}
現在のAliceは、On memoryであるためプロセスの終了とともにData Segmentは全て失われてしまう。

この問題を解決するためには、Data Segmentを他のKey Value Store等のシステムに保存し、永続性を確保する昼用がある。
また、当研究室で開発しているJungle Database\cite{Jungle}のようにLogファイルとして出力することでも解決ができる。

\subsection{Java以外での実装}
Alice に Garbage Collection は必要ない。Alice では、すべての Data Segment は Key Value に格納され、実行時の Data Segment は Code Segment が active な時のみにメモリ上にある。
この最大値を見積ることは、Active Task の量を見積もれば良い。したがって、Alice にはGarbage Collection は必要ない。
一方で、Key Value Store 上のデータは決して Garbage Collection の対象にならない。
しかし、それは Garbage Collector には負荷をかけてしまう。
つまり、Alice 自体は Java で実装するのには向いていない。

当研究室ではCode Segment/Data Segmentのプログラミング形式で記述する言語CbC

(Continuation based C)\cite{CbC}と、CbCを用いて記述されるGears OS\cite{Gears}の開発を行っている。
そのため、CbCを用いてGears OSの分散機構の一部としてAliceを再設計することが望ましい。

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

% 謝辞
\chapter{謝辞}
\hspace{1zw}本研究の遂行，また本論文の作成にあたり、ご多忙にも関わらず終始懇切なる御指導と御教授を賜わりました河野真治助教授に深く感謝したします。

そして、数々の貴重な御助言と技術的指導を戴いた杉本優さん、比嘉健太さん、伊波立樹さん、並びに並列信頼研究室の皆様に感謝いたします。

また、横山大作教授をはじめ、OS研究会、プログラミング・シンポジウムにおいて多くのフィードバックを頂いた先生方に感謝いたします。

本研究を遂行するにあたり参考にさせていただいた先行研究のFederated Linda, Cerium, TreeVNC の設計・実装に関わった全ての先輩方に感謝いたします。

最後に、日々の研究生活を支えてくださった米須智子さん、情報工学科の方々、そして家族に心より感謝いたします。


\begin{flushright}
 2016年 2月 \\ hoge
\end{flushright}


% 付録
%\input{appendix.tex}

\end{document}