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

本章では Jungle に行った分散実装について述べる.
まず, Aliceによるトポロジー形成の仕方を述べ, Aliceを利用したプログラミングの方法に
ついて説明を行う.
Aliceの提供する分散プログラミングにおけるデータアクセス機構について述べ, それらを使用する
上での注意点を述べる.
次に, それらをふまえてJungleの分散実装を行っていく.
データ分散に必要なクラスを用意することで他サーバノードとの通信を行う.
最後に, データ更新時の衝突において具体的なMergeの例として掲示板プログラムにおけるMergeについて述べる.

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

\subsection{トポロジーマネージャーの起動}
Alice を用いてサーバノードでトポロジーの形成を行う方法を述べる.
Alice のトポロジーマネージャーの起動はソースコード\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}). 
\newpage
\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 \verb|->| node1 はサーバノード同士の繋がりを示している.
次に続く label="child1" は, node0 が node1 のデータに"child1"という文字列を使うことでアクセス
できることを示す.

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

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


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

%矢印に書かれている文字列は, 相手のデータにアクセスするキーを示す.
%"child1", "child2", "parent" というキーを使うことで別のサーバノードにあるデータを取得することができる.
%これでトポロジーマネージャーが起動される.

\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の取得は文字列のキーを使うことで行える.
ソースコード\ref{src:cs_sample}にCodeSegmentの例を示す.
\newpage
\begin{lstlisting}[frame=lrbt,label=src:cs_sample,caption=CodeSegmentの実行,numbers=left]
public class TestCodeSegment extends CodeSegment {
  public Receiver arg1 = ids.create(CommandType.TAKE);
 
  public TestCodeSegment() { }

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

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

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

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

DataSegmentへデータの追加とCodeSegmentの実行について表した図\ref{fig:testcodesegment}になる.
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.70]{figures/testcodesegment.pdf}
    \caption{DataSegmentとCodeSegmentによるプログラムの例}
    \label{fig:testcodesegment}
  \end{center}
\end{figure}

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

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

まず, Aliceにより2分木3ノードのトポロジーが形成された場合を想定する.
その時に実際に作られるトポロジーは図\ref{fig:remote_cs}となる.
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.70]{figures/remote_codesegment.pdf}
    \caption{トポロジーの形成}
    \label{fig:remote_cs}
  \end{center}
\end{figure}

ネットワークを介したDataSegmentへのアクセスはそのサーバノードを示す
文字列のキーを追加することで行える.
他サーバノードを示す文字列のキーとは図\ref{fig:remote_cs}に矢印の隣に書かれている文字列
"parent", "child1", "child2" のことを指す.
例えば, server node0 が server node1のDataSegmentに入っている"count"というデータを
を使用したい場合は, 次のようにsetKeyを行えばよい（ソースコード\ref{src:remote_cs1}）.
\begin{lstlisting}[frame=lrbt,label=src:remote_cs1,caption=CodeSegmentで他サーバノードのDataSegmentを使用する,numbers=left]
CodeSegment cs = new RemoteCodeSegment();
cs.arg1.setKey("child1", "count");
\end{lstlisting}
　また, 他サーバノードのDataSegmentにデータを送りたい場合は, putを行うときにサーバノードへのキーを
追加すればよい.
例として, server node1やserver node2がserver node0のDataSegmentに"message"というキーでデータを追加したい場合は, 次のようになる（ソースコード\ref{src:remote_cs2}）.
\begin{lstlisting}[frame=lrbt,label=src:remote_cs2,caption=他サーバーノードのDatasSegmentにデータを追加する,numbers=left]
ods.put("parent", "message", "Hello parent");
\end{lstlisting}

\subsection{独自クラスのインスタンスの送受信}
最後に, 独自クラスのインスタンスのDataSegmentでの扱い方について述べる.
AliceではMessagePackを用いてシリアライズを行い他サーバノードへと送信している.
MessagePackはインスタンス単位でシリアライズを行うことができる.
そのため, Aliceでもプリミティブな型に限らずクラスのインスタンスをDataSegmentとして
扱うことができる.

MessagePackによりシリアライズとなるクラスはいくつか制限がある.
それはそのクラスに@Messageアノテーションを付けることと, そのクラスが保持するフィールドが
MessagePackによりシリアライズ可能であることである.
例えば次のようなクラスである(ソースコード\ref{src:msgpack1}).
\begin{lstlisting}[frame=lrbt,label=src:msgpack1,caption=MessagePackによりシリアライズ可能なクラス1,numbers=left]
import org.msgpack.annotation.Message

@Message
public class Student {
  String name;
  int age;
}
\end{lstlisting}
　上記のStudentクラスはプリミティブ型しか保持していない.
そのためシリアライズが可能である.
また, 次のようなクラスもシリアライズ可能な型となる(ソースコード\ref{src:msgpack2}).
\begin{lstlisting}[frame=lrbt,label=src:msgpack2,caption=MessagePackによりシリアライズ可能なクラス2,numbers=left]
import org.msgpack.annotation.Message

@Message
public class Class {
  List<Student> studentList;
}
\end{lstlisting}
　この場合, フィールドはプリミティブな型でないStudentクラスのフィールドを保持している.
しかし, Studentクラスはシリアライズ可能な形で作成しているため, クラスのフィールドとして
保持しても問題ない.

これらの制約にそった形で作成しDataSegmentにネットワークを介してクラスのインスタンス
をputすることができる.
DataSegmentから受け取ったデータはそのままではシリアライズされたものなため, 一度手元で
元のクラスにコンバートすることで扱う.
例として, AliceにおけるStudenクラスのコンバートを次に示す(ソースコード\ref{src:msgpack1}).
\begin{lstlisting}[frame=lrbt,label=src:msgpack3,caption=DataSegment,numbers=left]
// public Receiver arg1 = ids.create(CommandType.PEEK);
Student s = arg1.asClass(Student.class);
\end{lstlisting}
　MessagePackでシリアライズ可能な形としているためDataSegmentはネットワークを介して
送受信が可能である.


\section{ログのシリアライズ}
Jungleの具体的な分散実装について述べる.
実装にあたり, 解決しなければならない問題はまず, ログをDataSegmentで扱える形にすることである.
そのためには, @Messageアノテーションを付けたログのクラスの作成を行わなければならない.


\subsection{TreeOperationLogのシリアライズ}
ログの実体であるTreeOperationLogをシリアライズ可能な形にするにあたって気をつけなければならないのが, フィールドを
シリアライズ可能にする部分である.
TreeOperationLogはTreeOperationをいくつも保持し, TreeOperationはNodePathとNodeOperationを保持するものであった.
そのため, これら全てをシリアライズ可能な形にしなければならない.

基本的にこれらの実装は, フィールドを全てプリミティブなものだけにすればよい.
MessagePackはListを扱うこともできるため, TreeOperationLogで継承されていたIterableの挙動もListを使うことで
実装を行うことができた.

\section{ログに対する情報の追加}
TreeOperationLogをシリアライズ可能な形にした後, 問題が発生した.
それは, TreeOperationLog自体は木の名前を保持していないというものである.
そのため, TreeOperationLogだけを受け取っても, そのログがどの木に対して行われるのか
わからなかった.
そこで, TreeOperationLogの情報だけでなく, 木の名前とUUID, それとtimestampの情報も付与
してシリアライズが可能なNetworkTreeOperationLogの実装を行った.

% TreeOperationLog に木の名前の情報がない
% そのため木の名前を追加して持たせた
% 木がなければそのばでつくるようにした

\subsection{NetworkTreeOperationLogの実装}
NetworkTreeOperationLogの実装の一部を以下（ソースコード\ref{src:netlog}）に示す.
\begin{lstlisting}[frame=lrbt,label=src:netlog,caption=NetworkTreeOperationが持つフィールド,numbers=left]
@Message
public class NetworkTreeOperationLog implements TreeOperationLog
{
  public LinkedList<NetworkTreeOperation> list;
  String treeName;
  long timestamp;
\end{lstlisting}
　Listにより保持しているNetworkTreeOperationはTreeOperationをシリアライズ可能な形にしたものである.
TreeOperationLogをimplementsし, 木の名前とtimestampをを保持する.
他サーバノードへ伝える必要のある情報が増えた場合, このようにNetworkTreeOperationLogに情報を付与することで
対応することができる.

\subsection{ログの送信部分}
%ログの送信をいつ行うか.
%それは, 木の編集が成功した時である.
ログの送信は木の編集が成功したときに行われる.
木の編集が成功した結果得られるTreeOperationLogをNetworkTreeOperationLogに変換し, \verb|ods.put|を使って
CodeSegment側から利用できるようにする.

しかし, この時気をつけなければならないことがある.
それは, \verb|ods.put|の処理をレスポンスを返すスレッドの中で行うと, レスポンスが悪くなる可能性が
あることだ.
そのため, \verb|ods.put|を行うのは別のThreadにしたほうがよい.
以下のコードはcommitに成功した後に, NetworkTreeOperationへと変換したログを別スレッドに渡し
て処理させるコードである(ソースコード\ref{src:logconvert_and_execute}).
\begin{lstlisting}[frame=lrbt,label=src:logconvert_and_execute,caption=NetworkTreeOperationをputするために別スレッドを立ち上げる,numbers=left]
NetworkTreeOperationLog netLog = new NetworkTreeOperationLog(_uuid, _treeName,newLog);
CodeSegment cs = new LogPutCodeSegment(netLog);
cs.execute();
\end{lstlisting}

LogPutCodeSegmentの実装は次のようになっている(ソースコード\ref{src:logputcs}).
\begin{lstlisting}[frame=lrbt,label=src:logputcs,caption=putを行うためのCodeSegmentの用意,numbers=left]
public class LogPutCodeSegment extends CodeSegment{
  NetworkTreeOperationLog log;
  public LogPutCodeSegment(NetworkTreeOperationLog _log) {
    log = _log;
  }
  @Override
  public void run() {
    ods.put("log", log);
  }
}
\end{lstlisting}
　上で述べた問題は, ベンチマークテストなど, 大量の負荷をかけた際に発生する.
負荷とはJungleのデータに変更が加わることである.
多数のデータの変更により大量のログが生成される.
そのため, \verb|ods.put|によりDataSegmentの"log"にアクセスが集中してしまい, レスポンスが
悪くなっていた.
\verb|ods.put|を行うタイミングには気をつけなければず, 上記のコードにしても改良の余地はある.

\subsection{他サーバノードへのログの送信}
上記の実装によりDataSegmentの"log"キーにアクセスすることでTreeOperationLogを取得できるようになった.
次はこのデータを他サーバノードへ送る部分の実装を行う.

他サーバノードに対してデータを送るときに必要なことは, そのサーバノードのDataSegmentにアクセスする
キーである.
Aliceでは接続を行っている相手のDataSegmentのキーのリストは"\_CLIST"キーを使うことで取得することができる.
"\_CLIST"キーで得られるリストを使って他サーバノードへとデータをputするコードを次に示す(ソースコード\ref{src:log_put}).

\newpage
\begin{lstlisting}[frame=lrbt,label=src:log_put,caption=他サーバノードへのログの送信部分,numbers=left]
public class LogUpdateCodeSegment extends CodeSegment {
  Receiver log = ids.create(CommandType.TAKE);
  Receiver clist = ids.create(CommandType.PEEK);
  
  public LogUpdateCodeSegment() {
    log.setKey("log"); 
    clist.setKey("_CLIST");; 
  }
  
  List<String> list = clist.asClass(List.class);
  for (String node : list) {
    ods.put(node, log.key, log.getVal()); // Send datasegment to other node
  }
  :
\end{lstlisting}
　12行目の\verb|ods.put(node, log.key, log.getVal())|が他サーバノードへデータを送る部分になる.
変数logにはNetworTreeOperationLogが入っている.
変数listには"\_CLIST"により得られたデータが入っている.
それは文字列のListとなっている.
listの中身を1つずつ受け取り, \verb|ods.put|する際に引数として渡してやることで, 他サーバノードの
DataSegmentにアクセスが行える.

listの具体的な内容は, 図\ref{fig:tree_topology}で組まれたトポロジーでいうところの, "parent", "child1", "child2"
の文字列のListとなっている.
もし子どもとなるサーバノードがないときは"parent"だけがListには入れられる.

\subsection{ログの受信とデータ反映}
次は受け取ったログからデータの編集を行う部分の実装を行う.
Jungleはデータを変更する手段として木構造データ毎にTreeEditorクラスを提供している.
このTreeEditorを使用し, ログに入っているTreeOperationを1つ1つ取り出し同じ編集を行わせる.
例えば次のようになる(ソースコード\ref{src:data_edit}).
\begin{lstlisting}[frame=lrbt,label=src:data_edit,caption=ログを受け取ってのデータの反映,numbers=left]
// Receiver log <- "log"キーから取得できるデータが入っている
// Jungle jugnle
// Either<Error,JungleTreeEditor> either
NetworkTreeOperationLog netLog = log.asClass(NetworkTreeOperationLog.class);
String treeName = netLog.getTreeName();
JungleTree tree = jungle.getTreeByName(treeName);
TreeEditor editor = tree.getLocalTreeEditor();  // Editor の取得
for (TreeOperation op : netlog) { 
  NodePath path = op.getNodePath();
  NodeOperation nodeOp = op.getNodeOperation();
  either = edit(editor, path, nodeOp, nodeOp.getPosition()); // データの編集を行う.
  if(either.isA()) {
    // エラー処理.編集失敗
  }
  editor = either.b();
}
\end{lstlisting}
　8行目で取り出されたTreeOperationからさらにNodePathとNodeOperationを取り出しているのが9行目と10行目になる.
最後にedit関数にTreeEditorとNodePath, それとNodeOpeartionを引き渡している.
edit関数は次のようになる(ソースコード\ref{src:data_edit2}).
\begin{lstlisting}[frame=lrbt,label=src:data_edit2,caption=edit関数の実装,numbers=left]
Either<Error, JungleTreeEditor> edit(JungleTreeEditor editor, NodePath path, 
  NodeOperation nodeOp, int pos) {
    String key = "";
    Command c = nodeOp.getCommand();
    switch (c) {
     case PUT_ATTRIBUTE:
       key = nodeOp.getKey();
       ByteBuffer value = nodeOp.getValue();
       return editor.putAttribute(path, key, value);
     case DELETE_ATTRIBUTE:
       key = nodeOp.getKey();
       return editor.deleteAttribute(path, key);
     case APPEND_CHILD:
       return editor.addNewChildAt(path, pos);
     case DELETE_CHILD:
       return editor.deleteChildAt(path, 0);
}
\end{lstlisting}
　NodeOperationのAPIの種類（Command）毎に使用するTreeEditorのAPIを変えている.
もしNodeOperationのAPIの種類を増えるようなことが合っても, 上記のコードのように
対応するTreeEditorのAPIを書くことで対応できる.

%\subsection{ローカルのデータ編集専用のTreeEditorの用意}
%データ編集が行われ, 

\newpage
\section{永続性の実装}
次は, ログの書き出しによる永続性の実装について述べる.
第3章でJungleはWriterという永続性実装のための機能が元々用意されていることを述べた.
永続性で考えなければならないことは, どのようなデータをどんなデータ表現で書き込むかということである.
今回の実装ではログであるTreeOperationLogを書き出す.
また, TreeOperationLogの情報を保持しつつ, MessagePackでシリアライズできるクラスとして
NetworkTreeOperationLogの実装を行った.

つまり, WriterでNetworkTreeOperationLogを書き出すようにすればよい.
以下にログをディスクへ書き出すためのクラスPersistentChangeListWriterの実装を示す(ソースコード\ref{src:writer}).
\begin{lstlisting}[frame=lrbt,label=src:writer,caption=NetworkTreeOperationをディスクへ書き出す,numbers=left]
public class PersistentChangeListWriter implements ChangeListWriter {
  
  MessagePack msgpack;
  OutputStream out;

  public PersistentChangeListWriter(OutputStream _out, MessagePack _msgpack) {
    out = _out;
    msgpack = _msgpack;
  }
  @Override
  public Result write(ChangeList cs)
  {
    NetworkTreeOperationLog log 
      = new NetworkTreeOperationLog(cs.uuid(), cs.getTreeName(), cs);
    try {
      msgpack.write(out, log);
      out.flush();
      return Result.SUCCESS;
    } catch (IOException e) {
      // エラー処理
    }
  return Result.FAILED;
}
\end{lstlisting}
　write関数はJungleのデータ編集が完了すると呼び出される関数である.
引数として渡されているChangeListはTreeOperationLogと同じく\verb|Iterable<TreeOperation>|を継承している.
またUUIDや木の名前も取得することができる.
そのため, NetworkTreeOperationLogへと変換が行える.

ログの書き出しを行いたいときはこのPersistentChangeListWriterを設定することで行えるようになった.
これにより木の編集が行われるたびにNetworkTreeOperationLogが書き込まれていく.
読み込みたいときはMessagePackを使ってディスクから読み込み, データ分散実装と同じ方法で木の編集を行っていく
ことができる.


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

\section{掲示板プログラムにおけるデータ衝突}

今回分散実装を行い, 例題として掲示板プログラムを用意した.
掲示板プログラムに実装を行ったMergeについて述べる.
まず 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

\subsection{掲示板プログラムにおけるMerge}

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

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