\documentclass[a4j,12pt]{jreport}
\usepackage{master_paper}
\usepackage{ascmac}
\usepackage{bussproofs}
\usepackage[dvipdfmx]{graphicx}
\usepackage{here}
\usepackage{listings}
\usepackage{comment}
\usepackage[deluxe, multi]{otf}
\usepackage{url}
\usepackage{cite}
\usepackage{listings}
\usepackage{colonequals}
\usepackage[utf8]{inputenc}

%\input{dummy.tex} %% font

\jtitle{分散フレームワークChristieの設計}
\etitle{Design of Distributed framework Christie}
\year{2018年 3月}
\eyear{March 2018}
\author{照屋 のぞみ}
\eauthor{NOZOMI TERUYA}
\chife{指導教員：教授　和田 知久}
\echife{Supervisor: Prof. Tomohisa WADA}

\marklefthead{% 左上に挿入
  \begin{minipage}[b]{.4\textwidth}
    琉球大学大学院学位論文(修士)
\end{minipage}}

\markleftfoot{% 左下に挿入
  \begin{minipage}{.8\textwidth}
    並列分散フレームワークChristieの設計
\end{minipage}}

\newcommand\figref[1]{図 \ref{fig:#1}}
\newcommand\tabref[1]{表 \ref{tab:#1}}
\newcommand{\tblcaption}[1]{\def\@captype{table}\caption{#1}}

\lstset{
  frame=single,
  keepspaces=true,
  stringstyle={\ttfamily},
  commentstyle={\ttfamily},
  identifierstyle={\ttfamily},
  keywordstyle={\ttfamily},
  basicstyle={\ttfamily},
  breaklines=true,
  xleftmargin=0zw,
  xrightmargin=0zw,
  framerule=.2pt,
  columns=[l]{fullflexible},
  numbers=left,
  stepnumber=1,
  numberstyle={\scriptsize},
  numbersep=1em,
  language={},
  tabsize=4,
  lineskip=-0.5zw,
  escapechar={@},
}
\def\lstlistingname{リスト}
\def\lstlistlistingname{リスト目次}


%%% 索引のために以下の2行を追加
\usepackage{makeidx,multicol}
\makeindex
\begin{document}

%rome
\frontmatter

\maketitle
\newpage

\makecommission

%要旨
\input{abstract.tex}

%目次
\tableofcontents

%図目次
\listoffigures

%表目次
\listoftables

%リスト目次
\lstlistoflistings


%arabic
\mainmatter

%chapters
\chapter{分散プログラミングの信頼性向上}
スマートフォンやタブレット端末の普及率が増加している。
それに伴いインターネット利用者数も増加しており、ネットワーク上のサービスには
、信頼性とスケーラビリティーが要求される。
ここでいう信頼性とは、定められた環境下で安定して仕様に従った動作を行うことを
指す。
またスケーラビリティーとは、スケーラビリティとは、分散ソフトウェアに対して単純にノードを追加するだけで性能を線形的に上昇させることができる性質である。
しかし、これらをもつ分散プログラムをユーザーが一から記述することは容易ではない。

これらの問題の解決のために、当研究室ではデータをData Segment、タスクをCode Segmentという単位で記述するプログラミング手法を導入した分散フレームワークAlice の開発を実現した。
Data Segmentは整数や文字列や構造体などの基本的なデータの集まりである。
Code Segmentは入力となるData Segmentが全て揃ったら処理を開始し計算結果のData Segmentを出力するタスクである。

Aliceが実用的な分散アプリケーションを記述でき、仕様の変更を抑えた信頼性の高い拡
張を可能にするということは、水族館の例題やTreeVNCの例題から確認された。
しかし、AliceではAPI設計が直感的でなく、型の整合性がとれない問題があった。また、AliceにNAT越えの機能を実装しようとした際、Data Segment Managerが1つしか持てない
たために拡張が困難であることが分かった。

本研究では、Aliceから得られた知見をもとに、分散フレームワークChristieの設計を行
う。


\chapter{分散フレームワークAliceの概要}
\section{CodeSegmentとDataSegment}
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{DataSegmentManager}
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}


\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 flip(String managerKey, String key,  Receiver val)}
\end{itemize}
flipはDSの転送用のAPIである。取得したDSに対して何もせずに別のKeyに対し保存を行いたい場合、一旦値を取
り出すのは無駄である。flipはDSを受け取った形式のまま転送するため無駄なコピーなく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{CodeSegmentの記述方法}
CSをユーザーが記述する際にはCodeSegmentクラスを継承して記述する(ソースコード \ref{src:StartCodeSegmen
t} , \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}
となっている。


\section{TopologyManager}
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コマンドを用いてグラフの画像ファイルを生成することができる。そのため、記述したトポロジーが正しいか可視化することが可能である。

\newpage

Topology Managerはトポロジーファイルを読み込み、参加を表明したクライアント（以下、Topology Node）に接続するべきクライアントのIPアドレスやポート番号、接続名を送る（図\ref{fig:topologymanager}）。
また、トポロジーファイルで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では動的なトポロジータイプとして二分木に対応している。


\chapter{Aliceの問題点}
\section{直感的でないAPI}
\section{型がわからない}
\section{DataSegmentManagerを複数持てない}
\subsection{TopologyManagerのNAT超え機能}
\subsection{Jungleのテスト}

\chapter{分散フレームワークChristieの設計}
\section{Christieの基本設計}
\section{APIの改善}
\section{DataGearManagerの複数立ち上げ}

\chapter{Christieの評価}
\section{Akka}
\section{Corba}
\section{Erlang}
\section{Hazelcast}

\chapter{まとめ}

\chapter{今後の課題}


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

そして、数々の貴重な御助言と技術的指導を戴いた伊波立樹さん、並びに並列信頼研究室
の皆様、本研究を遂行するにあたり参考にさせていただいた先行研究のAlice, Federated
 Linda, Jungle, TreeVNC の設計・実装に関わった全ての方々に感謝いたします。
 
 また、本フレームワークの名前の由来となったクリスティー式戦車の生みの親、ジョン・
 W・クリスティーに敬意を評します。
 
 最後に、日々の研究生活を支えてくださった米須智子さん、情報工学科の方々、そし
 て家族に心より感謝いたします。
 
 
%参考文献
\nocite{*}
\bibliographystyle{junsrt}
\bibliography{reference}

%発表履歴
\addcontentsline{toc}{chapter}{発表履歴}
%\input{history.tex}

%付録
\addcontentsline{toc}{chapter}{付録}
\appendix
%\input{sources.tex}
\end{document}