% withpage: ページ番号をつける (著者確認用)
% english: 英語原稿用フォーマット
\documentclass[techrep, ,dvipdfmx]{ipsjprosym}
%\documentclass[withpage,english]{ipsjprosym}

\usepackage[dvipdfmx,hiresbb]{graphicx}
\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}
\input{dummy.tex} %% Font 

\begin{document}

% Title, Author %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{分散フレームワークAliceのPC画面配信システムへの応用}
\affiliate{IE}{琉球大学工学部情報工学科}
\author{照屋 のぞみ}{Nozomi Teruya}{IE}
\author{河野 真治}{Shinji Kono}{IE}[kono@ie.u-ryukyu.ac.jp]

\begin{abstract}
当研究室ではデータを Data Segment、タスクを Code Segment という単位で分割して記述する手法を提唱しており、それに基づく並列分散フレームワークAliceを開発している。
Aliceが実用的な分散アプリケーションの記述能力を有することを確認するために、画面共有システムTreeVNCをAlice上で構築した。
TreeVNCをAliceで実装するにあたり必要となった圧縮機能等をAliceが提供するMeta Computationとして実装した。
そして記述したアプリケーションの性能とコードを比較したことで、Aliceが実用的な分散アプリケーションをシンプルな記述で実現でき、仕様の変更を抑えた信頼性の高いプログラミングが可能だということを確認した。
\end{abstract}

\begin{jkeyword}
並列分散フレームワーク
\end{jkeyword}

\maketitle

% Body %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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に対応するため、Data Segmentを扱うAliceの機能として圧縮やゼロコピー転送の機能が必要なる。
これらの機能はTreeVNCではad-hocに実装されているが、AliceではこれをMeta Computationとして実装する。
そして、TreeVNCとの比較を行うことでAlice の実用性を示すと共にAlice のMeta Computationの役割と有効性を示す。

\section{分散フレームワークAlice}
\subsection{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は通常のデータベースとは異なる。

\subsection{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}


\subsection{Data Segment API}
DSの保存・取得にはAliceが提供するAPIを用いる。
putとupdateは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 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が削除されないことである。


\subsection{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}
となっている。

\section{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として指定する。
このようにプログラムすることで、通常処理と例外処理を分離することができるため、仕様の変更を抑えたシンプルなプログラムを記述できる。

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}

現在Aliceには、動的・静的トポロジーの管理構成機能、ノードとの接続状態確認機能、切断・再接続時の処理を指定できる機能など、分散環境の実現に必要なさまざまなMeta Computationが用意されている。

　

\textbf{Topology Manager}

Aliceでは、ノード間の接続管理やトポロジーの構成管理を、Topology ManagerというMeta Computationが提供している。このTopology ManagerもCS/DSを用いて実装されている。
プログラマはトポロジーファイルを用意し、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では動的なトポロジータイプとして二分木に対応している。


　

\textbf{KeepAlive}

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

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

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

\newpage

\textbf{切断・再接続時の処理}

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も用意した。


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

TreeVNCとは、当研究室で開発を行っている授業向け画面共有システムである。
オープンソースのVNCであるTightVNC \cite{tightVNC} をもとに作られている。
授業でVNCを使う場合、１つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう。
この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである。
図 \ref{fig:TreeVNC}はAliceVNCを実現するための構成である。leftとrightのRemote DSMを用意し子ノードと接続することで木構造を実現する。

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

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


\section{Aliceの新機能}
実用的なアプリケーションであるTreeVNCをAlice上で実装することで、Aliceに必要なMeta Computationを洗い出した。
\subsection{転送機能}
Input DSをRecieverに取得したあと、プログラマはRecieverから値を任意の型で取り出し、値を操作した後putメソッドで再度別クラスに変換されOutput DSとして出力する。
しかし、Input DSとして取得したデータ形式のまま子ノードにOutput DSとして出力する場合、一度Recieverから取り出し再変換する操作は無駄である。

そこで、Input DSとして受け取ったDSをそのままOutput DSとして転送する機能をput/updateとは別にflipメソッドをData Segment APIに実装した。
Input DSであるReceiverを展開せずにflipメソッドに引数として渡すことで、展開のオーバーヘッドをなくしている。
TreeVNCでは親ノードから受け取った画面データをそのまま子ノードに配信するため、Meta Computationとして転送機能が有用である。

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

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

そこで、１つのData Segmentに対し複数の表現を持たせ、必要に応じた形式で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)の圧縮表現を追加した。

ソースコード \ref{src:ReceiveData} はReceiveData.classが持つ表現である。
{\tt val}に(1) 一般的なJavaのクラスオブジェクト の表現でデータ本体が保存される。
{\tt messagePack}には(2) シリアライズ化されたバイナリオブジェクトが保存される。
そして、{\tt zMessagePack}には(3) 圧縮されたバイナリオブジェクトが保存される。
このようにDSが複数の表現を同時に保持することで、DSが圧縮表現を持っている場合に再圧縮する必要はない。

\begin{table}[html]
\lstinputlisting[label=src:ReceiveData, caption=データを表現するクラス]{source/ReceiveData.java}
\end{table}

また、圧縮表現を持つDSを扱うDSMとしてRemote DSMにCompressed Data Segment Managerを追加した。
Compressed DSMの内部では、put/updateが呼ばれた際にReceiveData.classが圧縮表現を持っていればそれを使用し、持っていなければその時点で圧縮表現を作ってput/updateを行う。

ソースコード \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}

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


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

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

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

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

また、AliceのMeta Computationの価値を明確にするため、他言語・フレームワークとの比較を行った。

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

　

\textbf{実験環境}

講義内で学生に協力してもらい、最大17名の接続がある中でTreeVNC、AliceVNC(圧縮・転送機能あり)、AliceVNC(圧縮・転送機能なし)の木の段数1〜3の測定を行った。

　

\textbf{実験内容}

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

計測用のヘッダは以下の要素で構成されている。
\newpage
\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には画面データのサイズを付けて送信する。
今回、TreeVNCとAliceVNC(圧縮・転送機能あり)では圧縮形式の画面データのサイズを、AliceVNC(圧縮・転送機能なし)ではMessegePack形式でのサイズを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と同等の処理性能があることがわかる。

\newpage
\begin{figure}[h]
    \begin{center}
        \includegraphics[width=70mm]{images/TreeVNC_depth3.pdf}
    \end{center}
    \caption{TreeVNCの測定結果}
    \label{fig:TreeVNC_delay}
\end{figure}

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=70mm]{images/AliceVNC_notcompress_depth3.pdf}
    \end{center}
    \caption{AliceVNC(圧縮・転送機能なし)の測定結果}
    \label{fig:AliceVNC_notcompress_delay}
\end{figure}

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


また、AliceVNCを圧縮機能の有無でデータサイズ比較すると、圧縮機能のないAliceVNCはデータサイズがほとんど1000byte以上なのに対し、圧縮機能のあるAliceVNCではTreeVNC同様10byte程度のサイズに抑えるので圧縮も成功している。

さらに転送機能の有無で比較した場合、転送機能がないAliceVNCでは木の段数に関係なく1000ms近く到達に時間がかかってしまっているが、転送機能のあるAliceVNCではデータサイズが大きくなっても100ms程度に抑えられている。これは転送機能が余計なコピーを防いでいるためだと考えられる。
このことから、圧縮・転送のMeta Computationは分散通信において有用であると言える。
\subsection{コードの比較}
\textbf{コード量}

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

表からわかるように、Aliceを用いればコードの行数が25\%削減できる。
また、TreeVNCではTightVNCに大幅に修正を加えながら作成したため仕様の変更が多かった。
しかし、AliceVNCではTightVNCにほとんど修正を加えることなくトポロジー構成等のAliceのMeta Computationを使うために新しいクラスを作成したのみであった。
そのためTreeVNCに比べ75\%も仕様の変更が抑えられている。
\begin{table}[htbp]
\caption{コード量の比較}
\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}

　
\textbf{コードの複雑度}

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

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

表\ref{tb:complex}はTightVNC、TreeVNC、AliceVNCにおける循環的複雑度の比較である。
プロジェクト全体でのクラスの複雑度の平均値と最高値をとった。
平均値・最高値ともにAliceVNCのほうが複雑度が低いことから、Aliceではシンプルな記述が可能だということがわかる。

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

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

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

\subsection{他言語・フレームワークとの比較}

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

\textbf{Erlang}

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

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


\textbf{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にはない。


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

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

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=75mm]{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が拡張性の高い環境を提供できると言える。

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





\nocite{*}
\bibliographystyle{ipsjunsrt}
\bibliography{prosym}


\end{document}