\chapter{Jungleの分散実装}
\section{TreeOperationLogを用いての分散データベースの実装}
Jungle でデータ扱うと TreeOperationLog として残ることは述べた.
この TreeOperationLog を他のサーバへと送り, Jungle の編集を行って
貰うことでデータの分散を行うことができる.
ここで問題になることはネットワークトポロジーの形成方法であった.

Jungle で使用するネットワークトポロジーはツリー型を考えている.
しかし, リング型といった他のネットワークトポロジーによる実装に関しても試す余地はある.
自由にネットワークトポロジーの形成を行うことができる必要があった.

そこで当研究室で開発を行っている並列分散フレームワークである Alice を使用することにした.
Alice により提供されるネットワークトポロジー形成を用いて TreeOperationLog を各サーバノードへ
配ることで並列分散フレームワークの実装を行う.

% トポロジー形成の説明をする. 重要さなども。
% トポロジーの形成は容易ではない.
% Alice が必要な機能を提供してくれることを述べる
% Alice はトポロジー形成の機能を提供している
% トポロジー間でのデータの受け渡す機能も提供している
\begin{figure}[htpb]
  \begin{minipage}{0.5\hsize}
  \begin{center}
    \includegraphics[scale=0.7]{figures/network_topology_ring.pdf}
    \caption{リング型のNetwork Topology}
    \label{fig:topology_ring}
  \end{center}
  \end{minipage}
  \begin{minipage}{0.5\hsize}
  \begin{center}
    \includegraphics[scale=0.7]{figures/network_topology_tree.pdf}
    \caption{ツリー型のNetwork Topology}
    \label{fig:topology_tree}
  \end{center}
  \end{minipage}
\end{figure}

\section{並列分散フレームワークAlice}
Alice は当研究室で開発している並列分散フレームワークである.
Alice はデータを DataSegment, コードを CodeSegment という単位で扱うプログラミングを提供している.
DataSegment として扱われるデータは



% DataSegment, CodeSegment はなしにしたほうがいいかもしれない. Alice が論文の主題じゃないから
% それとこの2つの説明をするとしたら結構な量になる

\section{Alice のトポロジーマネージャーの利用}
Alice はサーバノード同士によるネットワークトポロジー形成の機能を持つ.
トポロジーマネージャーの起動は\ref{src:alice_dot}の様にポート番号の指定と 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}


ポート番号は 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}に示す.

\newpage

\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" キーによりアクセスすることが可能となる.

トポロジーマネージャーに最初に接続要求を行う並列分散プログラム側は, 次のように記述する(\ref{src:alice_start})
\begin{lstlisting}[frame=lrbt,label=src:alice_start,caption=Alice を使用してのトポロジー形成,numbers=left]
public static void main( String[] args ) throws Exception
{
  RemoteConfig conf = new RemoteConfig(args);
  new TopologyNode(conf, new StartBBSCodeSegment(args, conf.bbsPort));
}
\end{lstlisting}


そして, プログラムの起動時にはトポロジーマネージャーが動いているサーバのドメインとポート番号を
渡すことでトポロジーの形成が行われれプログラムの処理がはしる.
例えば, 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}

% MessagePackの説明もここに簡単に入れたほうがいいかも.

\section{Aliceを用いての分散実装}
形成されたトポロジー上でのデータの送受信を行う部分について述べる.


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

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


\section{Jungleの永続性の実装}


\section{マージの実装}
Jungle への分散実装を行うことである問題が発生する.
それは更新されたデータ同士が衝突を起こした時の処理である.
Jungle はリクエストがきた場合, 現在もっているデータを返す.
しかしそのデータは最新のものであるかは保証されない.
よって, 別のサーバノードで動いている Jungle からの更新データと衝突する可能性がある.

この問題に対して Jungle はアプリケーションレベルでのマージを実装して貰うことで解決をはかる.
今回 Jungle に分散を行うにあたり掲示板プログラムを実装した.
掲示板プログラムに実装を行ったマージの例について述べる.

Jungle を用いた掲示板プログラムのデータ保持方法を示したのが図\ref{fig:merge1}になる.
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.70]{figures/merge1.pdf}
    \caption{Jungle による掲示板プログラムのデータ保持方法}
    \label{fig:merge1}
  \end{center}
\end{figure}

掲示板プログラムでは各掲示板毎に1つの木構造が作成される.
また, この時作成された木構造データのルートノードを保持する木構造が別にある.