\chapter{Jungle の分散実装}
本章では Jungle に行った分散実装について述べる.
前章では Jungle のアーキテクチャと分散設計について説明した.
トポロジーの形成と他サーバノードのデータのアクセス方法には Alice を使用する.
また, Jungle ではデータ編集のログとして TreeOperationLog がある.
この TreeOperationLog を Alice により他サーバノードへ送ることでデータの分散を行う.

\section{Alice のトポロジーマネージャーの利用}

\subsection{トポロジーマネージャーの起動}
Alice を用いてサーバノードでトポロジーの形成を行う方法を述べる.
Alice のトポロジーマネージャーの起動は\ref{src:alice_dot}の様に行う.
(\ref{src:alice_ntm_run}).
\begin{lstlisting}[frame=lrbt,label=src:alice_ntm_run,caption=Alice によるネットワークトポロジーマネージャーの起動,numbers=left]
% java -cp Alice.jar alice.topology.manager.TopologyManager -p 10000 -conf ./topology/tree5.dot
\end{lstlisting}
-p オプションはトポロジーマネージャーが開くポートの番号, -conf オプションには dot ファイルのパスを渡す.

ポート番号は Alice により記述された並列分散プログラムの起動時に渡す必要がある.
dot ファイルには, トポロジーをどのように形成するかが書かれている.
以下に, サーバノード数5で, 2分木ツリー構造を形成する dot ファイルの例を示す(\ref{src:alice_dot}). 
\begin{lstlisting}[frame=lrbt,label=src:alice_dot,caption=ネットワークトポロジー設定用 dot ファイル,numbers=left]
% cat tree5.dot 
digraph test {
  node0 -> node1 [label="child1"]
  node0 -> node2 [label="child2"]
  node1 -> node0 [label="parent"]
  node1 -> node3 [label="child1"]
  node1 -> node4 [label="child2"]
  node2 -> node0 [label="parent"]
  node3 -> node1 [label="parent"]
  node4 -> node1 [label="parent"]
}
\end{lstlisting}

node0 や node1 はサーバノードの名前を示す.
サーバノードの間にはラベルがあり, Alice 上ではこのラベル
に指定される文字列(キー)を使うことで他のサーバノードのデータへアクセスすることができる.
node0 -> node1 はサーバノード同士の繋がりを示している.
次に続く label="child1" は, node0 が node1 のデータに"child1"という文字列を使うことでアクセス
できることを示す.

dot ファイルを読み込んだ Alice のトポロジーマネージャーに対して, サーバノードは
誰に接続を行えばよいかを訪ねる.
トポロジーマネージャーは訪ねてきたサーバノードに対してノード番号を割り振り, dot ファイル
に記述している通りにサーバノード同士が接続を行うよう指示をだす.

トポロジーマネージャーは接続要求先を聞いてくるサーバノードに対して名前を割り振り, 接続相手を伝える.
dot ファイル\ref{src:alice_dot}により形成されるトポロジーを図\ref{fig:tree_topology}に示す.


\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.70]{figures/tree_topology.pdf}
    \caption{Alice によるネットワークトポロジー形成}
    \label{fig:tree_topology}
  \end{center}
\end{figure}

矢印に書かれている文字列は, 相手のデータにアクセスするキーを示す.
"child1", "child2", "parent" というキーを使うことで別のサーバノードにあるデータを取得することができる.
%子共となるノードは "parent" キーにより親の DSM (Remote DSM) にアクセスすることができる.
%また, 親も子供となるノードの DSM に対して "child1" や "child2" キーによりアクセスすることが可能となる.
これでトポロジーマネージャーが起動される.

\subsection{アプリケーション側の記述}
次は Jungle 側のプログラムが最初に Alice のトポロジーノードと通信を行うようにする.
そのためには Alice の TopologyNode クラスに必要な情報を渡してインスタンスを生成する(\ref{src:app_start}).
\begin{lstlisting}[frame=lrbt,label=src:app_start,caption=アプリケーションの起動,numbers=left]
public static void main( String[] args ) throws Exception
{
  RemoteConfig conf = new RemoteConfig(args);
  new TopologyNode(conf, new StartJungleCodeSegment(args, conf.bbsPort));
}
\end{lstlisting}
TopologyNode クラスは第2引数として CodeSegment を受け取る.
TopologyNode のインスタンスはまず初めにトポロジーマネージャーへ接続を行う.
次にトポロジーマネージャーから受け取った情報を元に別のサーバノードとトポロジーの形成を行う.
その後, 第2引数で渡された StartJungleCodeSegment の実行を行う.
StartJungleCodeSegment には通常のアプリケーションの処理が書かれる.

アプリケーションの起動時にはコンフィグの情報として, トポロジーマネージャーが動いているサーバのドメインとポート番号を
渡す必要がある.
例えば, mass00.cs.ie.u-ryukyu.ac.jp というサーバ上でポート番号10000を指定してトポロジーマネージャーを
起動した場合は次のようになる(\ref{src:run_program}).
\begin{lstlisting}[frame=lrbt,label=src:run_program,caption=トポロジーマネージャーの利用,numbers=left]
% java Program -host mass00.cs.ie.u-ryukyu.ac.jp -port 10000 
\end{lstlisting}

\section{Alice を用いての分散実装}
Aliceのポロジー形成と他のサーバのデータへのアクセスする機構を用いるためには, Aliceが
提供するプログラミングスタイルに沿わなければならない.
それはDataSegment(データ)とCodeSegment(タスク)によるプログラムである.
ここではまずDataSegmentとCodeSegmentによるプログラムの方法について説明し, 他サーバとの
通信部分の実装について述べる.

\subsection{Alice によるプログラミング}
AliceはDataSegment（データ）とCodeSegment（タスク）単位でプログラミングを行うことを述べた.
CodeSegmentには計算に必要なDataSegmentが登録される.
そしてDataSegmentが準備され次第CodeSegmentによる計算が実行される.
DataSegmentの取得は文字列のキーを使うことで行える.
以下のコードにCodeSegmentの例を示す.
\begin{lstlisting}[frame=lrbt,label=src:syslog_nfconntrack,caption=CodeSegmentの実行,numbers=left]
public class TestCodeSegment extends CodeSegment {
  public Receiver arg1 = ids.create(CommandType.TAKE);
  
  public TestCodeSegment() {
  }

  public void run() {
    int count = ds.asInteger();
    count++;
    System.out.println("count = "+count);
    if(c > 10) { exit(0); }
    CodeSegment cs = new TestCodeSegment();
    cs.setKey("count");
    ods.update("local", "count", c);
  }

  public static void main(String[] args) {
    CodeSegment cs = new TestCodeSegment();
    cs.arg1.setKey("local", "count"); // setKey API
    cs.ods.update("local", "count", 0);
  }
}
\end{lstlisting}
これは, 数字を1から10まで出力を行い終了するプログラムである.
コードの説明を行う.
まずTestCodeSegmentというCodeSegmentのインスタンスcsを生成する.
csはarg1というReceiverクラスのフィールドを保持しており, Receiverクラスは
DataSegmentを受けとるためのクラスである.
arg1に対しsetKey APIを使うことで, 使用したいDataSegmentのキー"count"を登録することができる.
これによりキー"count"に対してデータが登録された場合, そのデータを受け取りcsの計算が自動で始まる.
setKey APIの第一引数に渡している"local"はどのマシンのDataSegmentにアクセスするのかを指定している.
この場合は自分自身を表す"local"になる.

データの登録は\verb|ods.update|により行える.
上記のコード20行目ではupdateにより"count"をキーとして数値の0を登録している.
updateがされるとcsの計算が始まり別スレッドにより8行目からの処理が行われる.

updateによりキー"count"に登録された数値0はReceiverであるdsを使って取ることができる.
8行目から14行目では\verb|ds.asInteger()|により, "count"に登録したデータの中身を受け取りインクリメントし出力する.
そして最後には\verb|ods.update|を行っている.
新たなTestCodeSegmentも生成しており, これはインクリメントされた"count"がupdateされることで実行される.
この一連の処理を"count"の数値が10以上になるまで行う.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.70]{figures/testcodesegment.pdf}
    \caption{DataSegmentとCodeSegmentによるプログラムの例}
    \label{fig:testcodesegment}
  \end{center}
\end{figure}


% Alice の他サーバノードへの"log"のputの問題

\subsection{他サーバノードのDataSegmentへアクセス}
Aliceにおける基本的なプログラミングは述べた.
次はネットワークを介して他サーバノードのDataSegmentにアクセスするプログラムについて述べる.

まず, Aliceにより2分木3ノードのトポロジーが形成された場合を想定する.
その時に実際に作られるトポロジーを図\ref{fig:remote_cs}に示す.
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.70]{figures/testcodesegment.pdf}
    \caption{トポロジーの形成}
    \label{fig:remote_cs}
  \end{center}
\end{figure}
このトポロジー上で, 標準入力より入力されたメッセージを他サーバノードに送信
するプログラムを考える.

server node0, server node1, server node2 がそれぞれ接続しあっている.
矢印に付いている

\begin{lstlisting}[frame=lrbt,label=src:,caption=メッセージを受け取り他のサーバに流すCodeSegment,numbers=left]
public class SendMessageCodeSegment extends CodeSegment {

  Receiver sendNodeList = ids.create(CommandType.PEEK);
  public SendMessageCodeSegment() {
    sendNodeList.setKey("_CLIST");
  }
  @Override
  public void run() {
    @SuppressWarnings("unchecked")
    List<String> list = sendNodeList.asClass(List.class);
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String message = null;
    try {
      System.out.println("Please enter your message");
      while((message = reader.readLine()) != null ) {
        for(String node : list) {
          ods.put(node, "message", message);
          System.out.println("send message to "+node);
      }
    } catch (IOException e) {
     e.printStackTrace();
  }
}
\end{lstlisting}

\begin{lstlisting}[frame=lrbt,label=src:,caption=,numbers=left]

\end{lstlisting}

\begin{lstlisting}[frame=lrbt,label=src:,caption=,numbers=left]

\end{lstlisting}



\section{ログのシリアライズ}
ここでログのシリアライズについて述べる.

シリアライズとは, データをネットワーク上に流しても良い形式に変換することである.




\section{掲示板プログラムにおけるマージの実装}
Jungle に分散実装を行った後の問題としてデータ衝突がある.
他のサーバノードから送られてくるデータが既に手元で変更を加えた木構造を対象とした
場合に発生する問題である.
Jungle ではこれをアプリケーション毎にマージを実装することで解決させる.

今回分散実装を行い, 例題として掲示板プログラムを用意した.
掲示板プログラムに実装を行ったマージについて述べる.
まず Jungle を用いた掲示板プログラムのデータ保持方法を図\ref{fig:merge2}に示す.
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.70]{figures/merge2.pdf}
    \caption{Jungle による掲示板プログラムのデータ保持方法}
    \label{fig:merge2}
  \end{center}
\end{figure}

掲示板プログラムでは各掲示板毎に1つの木構造が作成される.
掲示板への1つの書き込みは子ノードを1つ追加することに相当する.
また, 各子ノードは attributes として書き込みの内容である message と書き込まれた時間を表す timestamp を保持している.
先に追加された順で子ノードには若い番号が割り振られる.

他サーバノードからの書き込みをそのまま子ノードの後ろに追加してしまうと, データの整合性が崩れてしまう.
この時の状態を表しているのが図\ref{fig:merge_imp1}と\ref{fig:merge_imp2}になる.
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.70]{figures/merge_imp1.pdf}
    \caption{他サーバノードの編集データ反映による整合性の崩れ1}
    \label{fig:merge_imp1}
  \end{center}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.70]{figures/merge_imp2.pdf}
    \caption{他サーバノードの編集データ反映による整合性の崩れ2}
    \label{fig:merge_imp2}
  \end{center}
\end{figure}

\newpage

図\ref{fig:merge_imp2}の server node0 の木の状態にするのが理想である.
掲示板のへの書き込みの表示は, 書き込みされた時間が早い順に表示されるようにしたい.
これを timestamp を利用することで行う.
他サーバノードから来たデータに関しては, timestamp を参照し, 次に自分の保持している
木の子ノードの timestamp と比べていくことでデータの追加する場所を決める.
これが今回実装を行った掲示板システムにおけるマージになる.

%単一サーバで動いている時の Jungle はただ子ノードとして後ろに追加するだけだが, 分散
%環境下においては timestamp に従い子ノードを追加する位置を決めるようにする.