\chapter{分散データベースJungleの設計}
前章では木構造データベースJungleの仕様について述べた.
非破壊的木構造によりデータを破壊せずに保持するJungleは, 過去のデータ
もみることができる.
また, データ編集をした際には, TreeOperationLogとして履歴が残る.
これらを踏まえ, 本章ではJungleの分散データベースとしての設計を行う.

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


\subsection{分散管理システムのAPI}
分散管理システムでは主に次の3つのAPIを使用することで, データの
分散を行っている.
\begin{itemize}
\item commit\\
前のバージョンのデータに変更を加えたことをリポジトリに登録する.
\item push\\
ローカルのリポジトリで行った変更履歴を別リポジトリへと伝える.
\item pull\\
他のリポジトリの変更履歴をローカルにリポジトリで受け取る.
\end{itemize}
commitによりローカルのリポジトリに変更履歴が積み重なり, pushをすることで
他のリポジトリにローカルで行ったデータ変更を伝える.
また, pullに好きなタイミングでデータの更新履歴を受け取ることができる.

分散管理システムはデータ変更の履歴は自由に受け取ることが
できるが, その変更履歴をそのまま適応できないときがある.
それはお互いが同じデータに対して編集を行っている場合である.
この状態を衝突という.
この衝突を解決する方法としてMergeがある.
Mergeは衝突を起こしたデータ両方の編集履歴を適応したデータを作ることである.
分散管理システムではこの衝突を解決する方法が必要になる.

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

以下にMergeが必要な場合とそうでない場合のデータ編集についての図を示す(図\ref{fig:tree_conflict1},\ref{fig:tree_conflict2},\ref{fig:tree_conflict3}).

\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_conflict2}
  \end{center}
\end{figure}

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


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


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

\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 で使用するネットワークトポロジーはツリー型を考えているが, リング型やメッシュ型といった
他のネットワークトポロジーによる実装に関しても試す余地はある.
そのため, ツリーだけでなく, 自由にネットワークトポロジーの形成を行えるようにしたい.

\begin{figure}[htpb]
  \begin{minipage}{0.5\hsize}
  \begin{center}
    \includegraphics[scale=0.7]{figures/network_topology_ring.pdf}
    \caption{リング型のトポロジー}
    \label{fig:topology_ring}
  \end{center}
  \end{minipage}
  \begin{minipage}{0.5\hsize}
  \begin{center}
    \includegraphics[scale=0.7]{figures/topology_mesh.pdf}
    \caption{メッシュ型のトポロジー}
    \label{fig:topology_mesh}
  \end{center}
  \end{minipage}
\end{figure}


そこで当研究室で開発を行っている並列分散フレームワークである Alice を使用する.
Alice はユーザが望んだマシンへの接続や必要なデータへのアクセスを行う機構と, 接続トポロジー
形成機能を提供している.

% トポロジー形成の説明をする. 重要さなども。
% トポロジーの形成は容易ではない.
% Alice が必要な機能を提供してくれることを述べる
% Alice はトポロジー形成の機能を提供している
% トポロジー間でのデータの受け渡す機能も提供している


\section{並列分散フレームワークAlice}
Alice は当研究室で開発している並列分散フレームワークである.
Alice はデータを DataSegment, タスクを CodeSegment という単位で扱うプログラミングを提供している.
コードの部分となる CodeSegment は, 計算に必要なデータである DataSegment が揃い次第実行が行われる(図\ref{fig:cs_ds}).
CodeSegment の結果により出力される新たなデータでは, 別の CodeSegment が実行されるための DataSegment となる.
DataSegment と CodeSegment の組み合わせにより並列・分散プログラミングの依存関係が表される.

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

\subsection{MessagePack によるシリアライズ}
Alice では DataSegment のデータ表現に MessagePack(http://msgpack.org) を利用している.
MessagePack はオブジェクトをバイナリへと変換させるシリアライズライブラリである.
Alice によりネットワークを介してデータにアクセスするときは, そのデータが MessagePack でシリアライズが
行えることが条件である.



\section{Jungle のデータ分散}
Alice によりトポロジーの形成とデータアクセスの機構が提供された.
後はデータ分散の為にどのデータをネットワークに流すのか決めなければならない.
そこで選ばれたのが TreeOperationLog である.
TreeOperationLog はデータ編集の履歴になる.
どの Node にどのような操作をしたのかという情報が入っている.
この TreeOperationLog を Alice を使って他サーバノードに送り, データの編集をしてもらうことで
同じデータを持つことが可能となる.
Alice を用いるため, この TreeOperationLog は MessagePack によりシリアライズ可能な形にすることが
必要である.




\section{ログによるデータの永続性}
% TreeOperationLog(ログ)をシリアライズ可能な形にしてデータをおくること
% シリアライズできる形にしたものをそのままHDに書き出すだけでログの永続性は行える
Jungle は非破壊でさらにオンメモリにデータを保持するため, 使用するメモリの容量が大きくなる.
だが, オンメモリのままでは電源が落ちた際にデータが失われてしまう.
ディスクからデータを読み込むことでデータの復旧を行えるようにしたい.
そこで, ログによるデータの永続性の実装を行う.

ログをどのようなデータ表現でハードディスクへと書きだすかという問題が発生するが, これは Alice を使うことで
解決している.
Alice を用いるため MessagePack によりシリアライズ可能な TreeOperationLog ができる.
このシリアライズ可能な TreeOperationLog をそのままハードディスクへ書き込むこととでログの永続性ができる.