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

\usepackage[dvipdfmx]{graphicx}
\usepackage[dvipdfmx]{color}
\usepackage{latexsym}
\usepackage{url}
\usepackage{listings}
\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,%キャプションの位置
  moredelim=**[s][\color{red}]{\"compressed}{\"},
}
\renewcommand{\lstlistingname}{Code}
\input{dummy.tex} %% Font 

\begin{document}

% Title, Author %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{分散フレームワークAliceのPC画面配信システムへの応用}

\affiliate{IPSJ}{情報処理学会}
\affiliate{PROSYM}{プログラミング・シンポジウム幹事団}

\author{照屋 のぞみ}{Nozomi Teruya}{琉球大学工学部情報工学科}[dpop@cr.ie.u-ryukyu.ac.jp]
\author{河野 真治}{Shinji Kono}{琉球大学工学部情報工学科}[kono@ie.u-ryukyu.ac.jp]

\begin{abstract}
当研究室ではデータを Data Segment、タスクを Code Segment という単位で分割して記述する手法を提唱しており、
それに基づく並列分散フレームワーク Alice を開発している。
Aliceが分散プログラムを記述する能力を有することは、Aliceを用いた水族館の例題等で確認された。
しかし、実用的な分散アプリケーションを作成するためには、通信時にData Segmentを圧縮形式で扱う機能やData Segmentを他ノードへそのまま転送する機能が必要な場合がある。
本研究では、Alice上に実用的な分散アプリケーションの例題である画面共有システムTreeVNCを構築する。
構築するにあたり必要となった圧縮などの機能を、AliceのMeta Computationとして実装する。
そして Alice を使用していないTreeVNCとの比較を行うことでMeta Computationの役割と有効性を示す。
\end{abstract}

\begin{jkeyword}
プログラミング・シンポジウム，冬，予稿集
\end{jkeyword}

\maketitle

% Body %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{研究背景と目的}
当研究室ではデータをData Segment、タスクをCode Segmentという単位で記述する分散フレームワークAliceの開発を行っている。
Aliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。
ここで言う信頼性とは、定められた環境下で安定して仕様に従った動作を行うことを指す。

Aliceでは、処理をComputationとMeta Computationに階層化し、コアな仕様と複雑な例外処理に分離する。
そして分散環境の構築に必要な処理をMeta Computationとして提供する。
プログラマはコアな仕様の変更を抑えつつプログラムの挙動変更ができるため、信頼性の高い分散アプリケーションの記述が可能となる。

本研究では、 実用的なアプリケーションである画面共有システムTreeVNC \cite{treeVNC} を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ではデータが他から変更され整合性がとれなくなることはない。
実際にはAliceはJavaで実装されており、DSはJavaObjectでCSはRannableThreadである。プログラマーがCSを記述する際は、CodeSegmentクラスを継承し、DSを操作するAPIを使用する。

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

\subsection{DataSegmentManager}
DSはAliceが内部にもつデータベースによって管理されており、このデータベースをAliceではDS Manager（以下DSM）と呼ぶ。
DSには対になるString型のkeyが存在し、このkeyを指定してDSの保存・取得を行う。
一つのkeyに対して複数のDSを登録することもでき、その場合DSはqueueに保存されFIFOで取り出される。

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

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


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

\begin{itemize}
\item {\ttfamily void put(String managerKey, String key, Object val)}
\end{itemize}
DSをDSMに追加するためのAPIである。第一引数はLocalDSMかRemoteDSMかといったDSM名を指定する。そして第二引数で指定された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{Data Segmentの表現}
DSの表現にはMessagePack for Java \cite{MessagePack} を利用している。
\begin{itemize}
\item {\ttfamily DSは一般的なJavaのクラスオブジェクト}
\item {\ttfamily MessagePackを用いて変換したbyte[]で表現されたバイナリオブジェクト}
\end{itemize}
の２種類があり、LocalDSMにputされた場合は一般的なJavaのクラスオブジェクトとして追加される。
RemoteDSMにputされた場合は通信時にbyteArrayに変換されたバイナリオブジェクトが追加される。

\subsection{Code Segmentの記述方法}
CSをユーザーが記述する際にはCSを継承して記述する(ソースコード \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は実行される。


\ref{src:CodeSegment}は、0から9までインクリメントする例題である。
2行目で取得されたDSが格納される受け皿を作る。Input DS APIがもつcreateメソッド使うことで作成できる。
\begin{itemize}
\item {\ttfamily Receiver create(CommandType type)}
\end{itemize}

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

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

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

5行目はInput DS APIがもつ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として指定する。
このようにプログラムすることで、通常処理と例外処理を分離することができるため、仕様の変更を抑えたシンプルなプログラムを記述できる。
現在Aliceには、動的・静的トポロジーの管理構成機能、ノードとの接続状態確認機能、切断・再接続時の処理を指定できる機能などのMeta Computationが用意されている。

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

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

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[width=60mm]{images/vnc.pdf}
    \end{center}
    \caption{VNCの構造 }
    \label{fig:vnc}
\end{figure}


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

TreeVNCは通信処理部分の記述が大変複雑になっている。しかし、Aliceで記述すれば本質的な処理とそれを支える通信処理部分で分離できる。
そのため、TightVNCからの修正も少なく、見通しの良い記述で構成可能と期待される。

\section{Aliceの新機能}
実用的なアプリケーションであるTreeVNCをAlice上で実装することで、Aliceに必要な機能を洗い出した。
\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を扱うことを可能にした。
DSを扱うReceiveData.classに、次の3種類の表現を同時に持つことができる。

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

ソースコード \ref{src:ReceiveData} はReceiveData.classが持つ表現であり、{\tt val}に(1) 一般的なJavaのクラスオブジェクト の表現でデータ本体が保存される。
{\tt messagePack}には(2) シリアライズ化されたバイナリオブジェクトが保存され、通常のRemoteDSMへの通信にこの表現が扱われる。
そして、{\tt zMessagePack}には(3) 圧縮されたバイナリオブジェクトが保存される。

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

また、圧縮状態を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerの追加した。
Compressed DSMの内部では、put/updateが呼ばれた際にReceiveData.classが圧縮表現を持っていればそれを使用し、持っていなければその時点で圧縮表現を作ってput/updateを行う。
ソースコード \ref{src:before} はRemoteからDSをtakeしインクリメントしてLocalにputすることを10回繰り返す例題である。
これを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内の{\tt asClass()}(ソースコード\ref {src:asClass} )を使うことで適切な形式でデータを取得できる。
{\tt asClass()}はDSを目的の型にcastするメソッドであり、ReceiveData.classが圧縮表現だけを持っている場合はこのメソッド内で解凍してcastを行っている。
これによりDSの表現を必要になったときに作成できる。

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

\subsection{Aliceの通信プロトコルの変更}
2.4 Data Segmentの表現 で述べたように、Remoteからputされたデータは必ずシリアライズ化されておりbyteArrayで表現される。
しかし、TreeVNCのようにもとからbyteArrayの画像データをputする場合、MessagePackでシリアライズされたものかの判別が付かない。
また、データの表現に圧縮したbyteArrayを追加したため、RemoteからputされたbyteArrayが圧縮されているのかそうでないのかを判断する必要がある。

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

\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
  serialized&データ本体のシリアライズ状態を示す\\
  \hline

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

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

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



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

\section{まとめ}
並列分散フレームワークAliceの計算モデルと実装について説明を行い、Aliceにおけるプログラミング手法を述べた。

Aliceが実用的なアプリケーションを記述するために必要なMeta Computationとして、データの多態性を実現し、指定するDSMの切り替えで扱うデータ表現を変えるようにした。
これにより、必要に応じた形式を扱うことができ、ユーザが記述するComputation部分を大きく変えずに自由度の高い通信を行うことが可能になった。
同様の手法を用いれば、圧縮形式以外にも暗号形式・JSON形式などの複数のデータ表現をユーザに扱いやすい形で拡張することができる。
Aliceに圧縮等のMeta Computationを追加したことで、AliceVNCではシンプルな記述でTreeVNCと同等の性能を提供できると期待される。

今後の課題としては、圧縮機能をAliceVNCで用いることでMeta Computationの有効性を測る必要がある。
また、AliceのMeta ComputationにProxy機能を実装することで、TreeVNCでは実装が困難であったNAT越えの機能を提供できると期待される。



% BibTeX を使用する場合 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{ipsjsort}
% \bibliography{ref}

% BibTeX を使用しない場合
\begin{thebibliography}{9}

\bibitem{treeVNC}
{MIWA OSHIRO, and Shinji KONO}:授業やゼミ向け画面配信システムTreeVNCの拡張機能，琉球大学工学部情報工学科平成26年度学位論文(学士) (2014).

\bibitem{MessagePack}
MessagePack, http://msgpack.org/

\bibtem{tightVNC}
TightVNC, http://www.tightvnc.com/

\bibitem{senkokenkyu}
{Yu SUGIMOTO and Shinji KONO}: 分散フレームワークAlice上のMeta Computationと応用，琉球大学工学部情報工学科平成26年度学位論文(修士) (2014).

\bibitem{Erlang}
{柏原正三}:プログラミング言語Erlang入門,アスキー (2007).
 
\bibitem{hadoop}


\end{thebibliography}

\end{document}