--- a/paper/chapter3.tex	Fri Jan 31 11:19:32 2014 +0900
+++ b/paper/chapter3.tex	Fri Jan 31 17:13:59 2014 +0900
@@ -1,335 +1,3 @@
-\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まで出力を行い終了するプログラムである.
-コードの説明を行う.
-17行目から19行目の処理が最初に行われる.
-まずTestCodeSegmentというCodeSegmentのインスタンスcsを生成する.
-csはarg1というReceiverクラスのフィールドを保持しており, Receiverクラスは
-DataSegmentを受けとるためのクラスである.
-arg1に対しsetKey APIを使うことで, 使用したいDataSegmentのキー"count"を登録することができる.
-これによりキー"count"に対してデータが登録された場合, そのデータを受け取りcsの計算が自動で始まる.
-setKey APIの第一引数に渡している"local"はどのマシンのDataSegmentにアクセスするのかを指定している.
-この場合は自分自身を表す"local"になる.
-
-データの登録は\verb|ods.update|により行える.
-上記のコード19行目ではupdateにより"count"をキーとして数値の0を登録している.
-updateがされるとcsの計算が始まり別スレッドにより8行目からの処理が行われる.
-
-updateによりキー"count"に登録された数値0はReceiverであるdsを使って取ることができる.
-7行目から13行目では\verb|ds.asInteger()|により, "count"に登録したデータの中身を受け取りインクリメントし出力する.
-そして最後には\verb|ods.update|を行っている.
-新たなTestCodeSegmentも生成しており, これはインクリメントされた"count"がupdateされることで実行される.
-この一連の処理を"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}
+\chapter{分散データベースJungleの設計}
 
 
-% 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によりシリアライズ可能であることである.
-例えば次のようなクラスである.
-\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}
-上記のStudenクラスはプリミティブ型しか保持していない.
-そのためシリアライズが可能である
-また, 次のようなクラスもシリアライズ可能な型となる.
-\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にネットワークを介してクラスのインスタンス
-をupdateすることができる.
-DataSegmentから受け取ったデータはそのままではシリアライズされたものため, 一度手元で
-元のクラスにコンバートすることで扱う.
-例として, AliceにおけるStudenクラス(Listing\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を使うことで
-実装を行うことができた.
-
-\subsection{ログに対する情報の追加}
-TreeOperationLogをシリアライズ可能な形にした後, 問題が発生した.
-それは, TreeOperationLog事態は木の名前を保持していないというものである.
-そのため, TreeOperationLogだけを受け取っても, そのログがどの木に対して行われるのか
-わからなかった.
-そこで, TreeOperationLogの情報だけでなく, 木の名前とUUID, それとtimestampの情報も付与
-してシリアライズが可能なNetworkTreeOperationLogの実装を行った.
-
-\subsection{NetworkTreeOperationLogの実装}
-NetworkTreeOperationLogの実装の一部を以下に示す.
-
-
-
-
-
-% TreeOperationLog に木の名前の情報がない
-% そのため木の名前を追加して持たせた
-% 木がなければそのばでつくるようにした
-
-\subsection{local専用の編集の用意}
-
-
-\subsection{}
-
-
-
-\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 に従い子ノードを追加する位置を決めるようにする.
-
-
-
-