\chapter{木構造データベースJungleの分散設計}
Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである.
一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの
ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している.
現在 Java と Haskell によりそれぞれ言語で開発されており本研究で扱うのは Java 版である.

本章ではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ分散の設計について述べる.
\subsection{破壊的木構造}
破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う.
図\ref{fig:destractive}は破壊的木構造の編集を表している.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/destructive_tree.pdf}
    \caption{破壊的木構造の編集}
    \label{fig:destractive}
  \end{center}
\end{figure}

破壊的木構造は, 編集を行う際に木のロックを掛ける必要がある.
この時, データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり, 閲覧者が
いる場合は木の走査が終わるまで書き換えをまたなければならない.
これではロックによりスケーラビリティが損なわれてしまう.

\subsection{非破壊的木構造}
非破壊的木構造は破壊的木構造とは違い, 一度作成した木を破壊することはない.
非破壊的木構造においてデータの編集は, ルートから編集を行うノードまでコピーを
行い新しく木構造を作成することで行われる.
図\ref{fig:nondestractive}は非破壊的木構造のデータ編集を示している.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_tree.pdf}
    \caption{非破壊的木構造の編集}
    \label{fig:nondestractive}
  \end{center}
\end{figure}

非破壊的木構造におけるデータ編集の手順を以下に示す.

\begin{enumerate}
\item ルートから編集を行うノードまでのパスを調べる(図\ref{fig:nondestractive_edit1}).
\item 編集を行うノードのコピーをとる. コピーをとったノードへデータの編集を行う(図\ref{fig:nondestractive_edit2}).
\item 調べたパスに従いルートからコピーしたノードまでの間のノードのコピーをとり繋げる(図\ref{fig:nondestractive_edit3}).
\item コピーしたルートノードは編集を行っていないノードへの参照を貼り新しい木構造を作る(図\ref{fig:nondestractive_edit4}).
\end{enumerate}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_edit1.pdf}
    \caption{非破壊的木構造の編集手順1}
    \label{fig:nondestractive_edit1}
  \end{center}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_edit2.pdf}
    \caption{非破壊的木構造の編集手順2}
    \label{fig:nondestractive_edit2}
  \end{center}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_edit3.pdf}
    \caption{非破壊的木構造の編集手順3}
    \label{fig:nondestractive_edit3}
  \end{center}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_edit4.pdf}
    \caption{非破壊的木構造の編集手順4}
    \label{fig:nondestractive_edit4}
  \end{center}
\end{figure}

\newpage

非破壊的木構造においてデータのロックが必要となる部分は, 木のコピーを作終えた後に
ルートノードを更新するときだけである.
データ編集を行っている間ロックが必要な破壊的木構造に比べ, 編集中においてもデータの読み込みが
可能である(図\ref{fig:nondestractive_merit}).
そのため, 破壊的木構造に比べスケールがしやすくなっている.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf}
    \caption{非破壊的木構造による利点}
    \label{fig:nondestractive_merit}
  \end{center}
\end{figure}


\section{Jungle におけるデータへのアクセス}
Jungle ではデータをそれぞれの Node が attribute として保持する.
attribute は String 型の Key と ByteBuffer の value のペアにより表される.
Jungle でデータへのアクセスは, この Node へのアクセスをさす.
Node へのアクセスは, 木の名前と Node を指すパスにより行える.
このパスは NodePath と呼ばれる(図\ref{fig:nodepath}).

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/nodepath.pdf}
    \caption{Node の attribute と NodePath}
    \label{fig:nodepath}
  \end{center}
\end{figure}



\section{Jungle におけるデータ編集}

\subsection{NodeOperation}
Jungle による最小のデータ編集は Node の編集を指す.
Node 編集のために API が用意されており, この API は NodeOperation と呼ばれる.
NodeOperation には次の4つの API が用意されている.
\begin{itemize}
\item \verb|addNewChild(NodePath _path, int _pos)|
NodePath で指定された Node に子供となる Node を追加する API である.
pos で指定された番号に子供として追加を行う.
\item \verb|deleteChildAt(NodePath _path, int _pos)|
NodePath と pos により指定される Node を削除する API である.
\item \verb|putAttribute(NodePath _path, String _key, ByteBuffer _value)|
Node に attribute を追加する API である. 
NodePath は attribute を追加する Node を指す.
\item \verb|deleteAttribute(NodePath _path, String _key)|
\verb|_key| が示す attribute の削除を行う API である.
NodePath は Node を示す.
\end{itemize}

NodeOperation はあくまで最小のデータ編集の単位である.
アプリケーションレベルの実装にもよるが, Jungle によるデータの編集は NodeOperation が複数集まった単位によって行われる.
この複数の NodeOperation の集まりを TreeOperationLog という.

\subsection{TreeOperationLog}
Jungle 内部では NodeOperation は順次ログに積まれていき, 最終的に
commit されることで編集が完了する.
この時, ログに積まれた複数の NodeOperation は TreeOperationLog として扱われる.
以下に TreeOperationLog の具体的な例を示す(\ref{src:treelog}).
\begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left]
[APPEND_CHILD:<-1>:pos:0]
[PUT_ATTRIBUTE:<-1,0>:key:author,value:oshiro]
[PUT_ATTRIBUTE:<-1,0>:key:mes,value:hello]
[PUT_ATTRIBUTE:<-1,0>:key:timestamp,value:0]
\end{lstlisting}
このログは今回の研究で使用したベンチマーク用掲示板プログラムにおける書き込みにより行われるログである(図\ref{fig:treeoperationlog}).

大文字の英字は実行した NodeOperation の種類を表す.
\verb|<>| により囲まれている数字は NodePath を示す.
NodePath の表記以降は Node の position や attribute の情報を表している.
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/treeoperationlog1.pdf}
    \caption{TreeOperationLog の具体例}
    \label{fig:treeoperationlog}
  \end{center}
\end{figure}

図\ref{fig:treeoperationlog}の説明を行う.
まず, \verb|APPEND_CHILD| により Root Node の 0 番目の子供となる Node の追加を行う.
次に, 追加を行った Node に対して \verb|PUT_ATTRIBUTE| により attribute の情報を持たせていく.
attribute の内容に作者の情報を表す auther, メッセージの内容を表す mes, そしてタイムスタンプ
を timestamp とそれぞれキーにすることで追加される.

以上が掲示板プログラムにおける1つの書き込みで発生する TreeOperationLog である.

\section{分散バージョン管理システムによるデータの分散}
Jungle は Git や Mercurial といった分散バージョン管理システムの機能を参考に作られている.
分散バージョン管理システムとは, 多人数によるソフトウェア開発において変更履歴を管理するシステムである.
% 反対の意味の言葉として集中型バージョン管理システムがある.
分散管理システムでは開発者それぞれがローカルにリポジトリのクローンを持ち, 開発はこのリポジトリを通すことで進められる(図\ref{fig:distributed_repo}).
ローカルのリポジトリは独立に損刺し, サーバ上にあるリポジトリや他人のリポジトリで行われた変更履歴を取り込みアップデートにかけることができる.
また逆に, ローカルのリポジトリに開発者自身がかけたアップデートを他のリポジトリへと反映させることもできる.
分散管理システムでは, どれかリポジトリが壊れたとしても, 別のリポジトリからクローンを行うことができる.
ネットワークに障害が発生しても, ローカルにある編集履歴をネットワーク復旧後に伝えることができる.
そのため, 可用性と分断耐性が高いと言える.
% 分散管理システムは結果整合性をとることを述べる.
% 結果整合性の話を先にどっかでしたほうがいいかも
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/distributed_repository.pdf}
    \caption{分散バージョン管理システム}
    \label{fig:distributed_repo}
  \end{center}
\end{figure}


\subsection{マージによるデータ変更衝突の解決}
分散管理システムでは, データの更新時において衝突が発生する時がある.
それは, 分散管理システムを参考にしている Jungle においても起こる問題である.
データの変更を行うときには, 元のデータに編集が加えられている状態かもしれない.
Jungle はリクエストがきた場合, 現在もっているデータを返す.
そのためデータは最新のものであるかは保証されない.
この場合, 古いデータに編集が加えられ, それを更に最新のデータへ伝搬させなければならない.
このように他のリポジトリにより先にデータ編集が行われており, データの伝搬が素直にできない状態を
衝突という.
この衝突を解決する手段が必要である.
分散管理システムでは衝突に対してマージと呼ばれる作業で解決をはかる.
マージは, 相手のリポジトリのデータ編集履歴を受け取り, ローカルにあるリポジトリの編集と合わせる作業である.
データ衝突に対して Jungle はアプリケーションレベルでのマージを実装して貰うことで解決をはかる.


\newpage

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.48]{figures/tree_conflict.pdf}
    \caption{衝突の発生しないデータ編集}
    \label{fig:tree_conflict1}
  \end{center}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.48]{figures/tree_conflict3.pdf}
    \caption{自然に衝突を解決できるデータ編集}
    \label{fig:tree_conflict1}
  \end{center}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.48]{figures/tree_conflict2.pdf}
    \caption{衝突が発生するデータ編集}
    \label{fig:tree_conflict2}
  \end{center}
\end{figure}

\newpage

\section{ネットワークトポロジーの形成}
分散管理システムを参考に Jungle でもそれぞれのデータベースが独立に
動くようにしたい.
そのために必要なことはトポロジーの形成と, サーバノード間でのデータアクセス機構である.
また, データ分散のために形成したトポロジー上で扱うデータを決めなければならない.


\subsection{ツリートポロジーの形成}
分散データーベス Jungle で形成されるネットワークトポロジーはツリー構造を想定している.
ツリー構造ならば, データの整合性をとる場合, 一度トップまでデータを伝搬させることで行える.
トップもしくはトップまでの間にあるサーバノードでデータ伝搬中に衝突が発生したらマージを行い, マージの結果を改めて伝搬すれば
よいからである.
また, リング型, スター型, メッシュ側ではデータ編集の結果を他サーバノードに流すとき
流したデータが自分自身にくることにより発生するループに気をつける必要がある.
ツリー構造の場合は, サーバノード同士の繋がりで閉路が無い.
そのため, 自分自身が行ったデータ編集の履歴を繋がっているノードに送信するだけですむ.
このルーティングの方式はスプリットホライズンと呼ばれるものである.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.70]{figures/network_topology_tree.pdf}
    \caption{ツリー型のNetwork Topology}
    \label{fig:topology_tree}
  \end{center}
\end{figure}


\subsection{トポロジーの形成手段}
% なぜツリー型なのか説明をしたほうがいい？
% マージの利用のためツリー型？
Jungle で使用するネットワークトポロジーはツリー型を考えているが, リング型やメッシュ型といった
他のネットワークトポロジーによる実装に関しても試す余地はある.
そのため, ツリーだけでなく, 自由にネットワークトポロジーの形成を行えるようにしたい.

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

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



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

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


\section{データの永続性}
% TreeOperationLog(ログ)をシリアライズ可能な形にしてデータをおくること
% シリアライズできる形にしたものをそのままHDに書き出すだけでログの永続性は行える


\section{CAP 定理と Jungle}
ここまでの Jungle の設計を踏まえて, CAP 定理における Jungle の立ち位置を考える.
分散管理バージョンのように独立したリポジトリもち, それぞれが独自の変更を加えることが
行えることで一貫性はゆるい.
だが, ネットワークから切断されてもローカルで行ったデータの変更をネットワーク復旧後で伝搬できる
ことと, リクエストに対し持っているデータをすぐに返すことができる.
つまり Jungle は可用性と分断耐性に優れたデータベースを目指している.
第2章で紹介した既存のデータベースと Jungle との CAP 定理の関係を図\ref{fig:cap_theorem}に示す.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/cap_theorem.pdf}
    \caption{CAP 定理における各データベースの立ち位置}
    \label{fig:cap_theorem}
  \end{center}
\end{figure}