\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{分散プログラミングの信頼性向上}


\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=105mm]{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メソッドを呼ぶことで実行を開始させることができる。

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

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

1.で用いられているasInteger()はasClassメソッドの一部であり、asClassはtake/peekで取得したDSをObject型から任意の型で取得するためのAPIである。

\begin{itemize}
    \item {\ttfamily <T> T asClass(Class<T> clazz)}
\end{itemize}

CS内でDSのデータを扱うには、正しい型を意識しながらこのasClassメソッドを使わなければならない。





\section{AliceのMeta Computation}
Aliceでは、処理をComputationとMeta Computationに階層化し、コアな仕様と複雑な例外処理に分離する。
AliceのComputationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理と捉えられる。
それに対して、AliceのMeta Computation は、Remoteノードとの通信トポロジーの構成や扱うデータ形式の変換と言える。

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

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

\subsection{Aliceの圧縮機能}
%API

\subsection{TopologyManager}
Aliceでは、ノード間の接続管理やトポロジーの構成管理を、Topology ManagerとTopology NodeというMeta Computationが提供している。
プログラマはトポロジーファイルを用意し、Topology Managerに読み込ませるだけでトポロジーを構成することができる。
トポロジーファイルはDOT Language\cite{dot}という言語で記述される。
DOT Languageとは、プレーンテキストを用いてデータ構造としてのグラフを表現するためのデータ記述言語の一
つである。
ソースコード\ref{src:topologyfile}は3台のノードでリングトポロジーを組むときのトポロジーファイルの例である。

    \lstinputlisting[label=src:topologyfile, caption=トポロジーファイルの例]{source/TopologyFile.dot}
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{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では動的なトポロジータイプとして二分木に対応している。
%TopologyNodeとnodenameの説明もう少し

\chapter{Aliceの問題点}
\section{直感的でないAPI}
2.4で示したように、CSで使うDSをtake/peekのメソッドを直接は呼び出せない。
一度フィールドでReceiverをcreateして、その後Reveiverに対してsetKeyで待ち合わせるkeyを指定しなければならない。
これでは手間がかかる上、コードを読んだ際にどのKeyに対して待ち合わせを行っているのか直感的に分からない。
さらに、setKeyはそのDSを待ち合わせているCS以外からも呼び出せてしまう\ref{src:StartSetKey}。

    \lstinputlisting[label=src:StartSetKey, caption=setKeyを外部から呼び出す例]{source/StartSetKey.java}
    \lstinputlisting[label=src:SetKey]{source/SetKey.java}

    このような書き方をされると、CSだけを見てどのkeyに対して待ち合わせを行っているのかわからないため、setKeyを呼び出しているコードを辿る必要がある。
可読性の低いコードはプログラマの負担となるため、CSが何を待ち合わせているのかそのCSを見ただけで理解できるようにAPIを改善すべきである。

\section{動的なsetKey}
setKeyはCSのコンストラクタで指定することが多い。
このとき、指定するkeyは引数などから動的に受け取り、セットすることができる。
しかし、その使い方では、putする部分など、該当するkeyを扱う全てコードを変更しなければならない。
現在のAliceではsetKeyが柔軟に使えるがために、慎重に書かなければプログラムの信頼性が保てない。
そのため、動的なsetKeyはできないように制限したほうが良いと考える。

\section{型が推測できない}
inputDSを受け取るReceiverはデータをObject型で持っており、そのデータをCS内で扱うには正しい型にキャストする必要がある。
しかし、inputDSで指定するのはkeyのみであり、そのデータの型までは分からない。
そのため、DSの型を知るにはputしている部分まで辿る必要がある。
辿ってもflipされている可能性もあるため、最初にそのDSをputしている部分を見つけるのは困難である。
従って、待ち合わせているkeyにどのような型のデータが対応しているのかをそのCSを見ただけで分かるようにするべきと考える。

% ここでMessagePackの話入れる？

\section{key名と変数名の不一致}
2.4のCodeSegmentの例題である通り、key名とそのkeyで待ち合わせたDSを受け取るReceiver名は異なることがある。
もしプログラマが適当に命名してしまえば後々混乱を招くため、待ち合わせるkey名とinput DS の変数名一致を強制させたい。

\section{LocalDataSegmentManagerを複数持てない}
Aliceでは1つのノードにつき１つしかLocalDSMを立ち上げられない作りになっている。
そのために以下のような問題が発生した。

\subsection{１つのノードで複数台DSM同士のテストが行えない}
%ローカルで複数できないからテストが気軽にできない


\subsection{TopologyManagerの拡張が困難}
Aliceではより自由度の高い通信を行うために、TopologyManagerに幾つかの機能を追加すること考えていた。

例えば、NAT越えの機能である。NAT越えは分散アプリケーション構築における課題の1つでもあるが、プログラマにとってその実装は容易ではない。Topology ManagerにNATを越えたノード間通信機能をつけることにより、NATを気にせずに通信が行えるようにしたい。
また、別トポロジーで立ち上げたアプリケーション同士を接続する機能も追加したいと考えていた。
TreeTopologyのVNCアプリとStarTopologyのチャットアプリの連携したいといった要望が生まれたためである。

TopologyManagerはネットワークごと、トポロジーごとに存在するため、いずれの機能も複数のTopologyManager同士を連携させることで可能となる。
１つのノードに複数のTopologyManagerを対応させるには、TopologyNodeが複数のnodeNameを持つ必要がある。

%図

そこで、通常のLocal DSMとは別にTopology ManagerごとのMeta LocalDSMを立ち上げる方法を考えた。

それぞれのTopology Managerに対応するLocalDSMを作り、それぞれに対応したnodeNameを格納することで、DSMを切り替えるだけでTopologyNodeの仕様は変えずに複数のTopology Managerに対応できるという設計である。

しかし、現在のAliceのコードではDSMを管理するclassがstatic classであったため、複数のLocal DSMを持つことができない。
staticを取り除こうとしたところ、Aliceの大部分のコードを修正する必要があることがわかった。
よって、再設計の際にはstatic classのない実装を行い、DSM切り替えによる方式を実現したい。






\chapter{分散フレームワークChristieの設計}
3章でのAliceの問題点を踏まえ、新たにフレームワークを作り直すべきだと考えた。
本章では、新たに作った分散フレームワークChristieの設計を説明する。

\section{Christieの基本設計}
ChristieはJavaで書かれている。
将来的に当研究室が開発するGearsOSに取り入れたいため、GearsOSを構成する言語であるContinuation based C(CbC)に互換可能な設計を目指す。


GearsOSではCodeSegment/DataSegmentと同様の概念としてCodeGear/DataGearという名称を用いているため、Christieでもそれに倣いCodeGear/DataGear(以下、CG/DG)と呼ぶこととする。

%DataGearManager
%CodeGearManagerがそれを持ち歩く。CGMはGearsでいうContextで、全てにアクセスできる。
%run(cgm)でCGMを持ち歩く。Gearsもそうだから。
%CodeGearをextends
%StartCodeGearでCGMをつくる。CGを作るときはsetup。


\section{APIの改善}
%take/peekはAnnotationを使う。待ち合わせはJavaのreflectionAPIを用いたメタがよろしくやってくれる。
%keyと変数名の食い違いも防止する。ここはJavassistでやろうとしたけどむりだった。
%DataGearを宣言するとき型も書くのでどんなデータがくるのかわかりやすい。違う型のデータがきたらエラーを吐く
%LocalかRemoteかはAnnotationが違うのでわかりやすい
%odsはない。dsmを指定して直接putする。
%getDataで正しい型でとれる。

\section{CodeGearの記述方法}

    \lstinputlisting[label=src:StartCodeGear, caption=StartCodeGearの例]{source/christie/StartTest.java}
    \lstinputlisting[label=src:TestCodeGear, caption=CodeGearの例]{source/christie/TestCodeGear.java}


\section{DataGearManagerの複数立ち上げ}
%Remoteへの接続


\section{DataGearの拡張}


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