\chapter{分散版jungleデータベース}
Jungleは、スケーラビリティのあるデータベースの開発を目指して当研究室で開発されている分散データベースである。
本章では、分散データベースJungleの構造と分散部分について触れる。
\section{Jungleデータベースの構造}
Jungleは、当研究室で開発を行っている木構造の分散データベースで、Javaを用いて実装されている。一般的なウェブサイトの構造は大体が木構造であるため、データ構造として木構造を採用している。

Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合でできている。ノードは自身の子のリストと属性名、属性値を持ち、データベースのレコードに相応する。通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。

通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。

また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。

Jungleはデータの変更を非破壊で行なっており、編集ごとのデータをバージョンとしてTreeOperationLogに残している。Jungleの分散ノード間の通信は木の変更のTreeOperationLogを交換することによって、分散データベースを構成するよう設計されている。

\section{分散機構}
Jungleの分散設計は、Git や Mercurial といった分散バージョン管理システム(以下、分散管理システム)の機能を参考に作られている。分散管理システムとは、多人数によるソフトウェア開発において変更履歴を管理するシステムである。分散管理システムでは開発者それぞれがローカルにリポジトリのクローンを持ち、開発はこのリポジトリを通して行われる。ローカルのリポジトリは独立に存在し、サーバ上にあるリポジトリや他人のリポジトリで行われた変更履歴を取り込みアップデートをかけることができる。また、逆にローカルリポジトリに開発者自身がかけたアップデートを他のリポジトリへと反映させることもできる。分散管理システムではどれかリポジトリが壊れたとしても、別のリポジトリからクローンを行うことができる。ネットワークに障害が発生しても、ローカルにある編集履歴をネットワーク復帰後に伝えることができる。
このように、分散管理システムはデータ変更の履歴を自由に受け取ることが可能である。しかし、お互いが同じデータに対して編集を行なっている場合、変更履歴を自由に受け取ることができないことがある。これを衝突という。衝突は、分散管理システムを参考にしている Jungle においても起こる問題である。
Jungleはリクエストが来た場合、現在持っているデータを返す。その為、データは最新のものであるかは保証されない。この場合、古いデータに編集が加えられ、それを更に最新のデータへ伝搬させる必要がある。このように他のリポジトリにより先にデータ編集が行われているとき、データの伝搬が素直にできない為、衝突が起きてしまう。この衝突に対し、分散管理システムではMergeと呼ばれる作業を行う。Mergeとは、相手のリポジトリのデータ編集履歴を受け取り、ローカルにあるリポジトリの編集と合わせる作業である。Jungleは、アプリケーションレベルでのMergeを実装することで、衝突を解決する。

Jungleの分散機構は、木構造、すなわちツリー型を想定したネットワークトポロジーを形成し、サーバー同士を接続することで通信を行なっている。ツリー型であれば、データの整合性をとる場合、一度トップまでデータを伝搬させることで行える。トップまたはトップまでの間にあるサーバーノードでデータを運搬中に衝突が発生したらMergeを行い、その結果を改めて伝搬すればよいからである(図\ref{fig:tree}）。

\begin{figure}[htbp]
    \centering
    \includegraphics[width=100mm]{pic/tree.pdf}
    \caption{ツリー型のトポロジー}
    \label{fig:tree}
\end{figure}

(図\ref{fig:tree}）の矢印の流れを以下に示す。
\begin{enumerate}
 \item servernode 1, servernode 2からきたデータがservernode 0 で衝突。
 \item 衝突したデータのMergeが行われる。
 \item Mergeされたデータがservernode 1,servernode 2へ伝搬
 \item servernode1からMergeされたデータがservernode 3、servernode 4へ伝搬。全体でデータの整合性が取れる。
\end{enumerate}
リング型(図\ref{fig:ring} ）やメッシュ型(図\ref{fig:mesh} ）のトポロジーでは、データの編集結果を他のサーバーノードに流す際に、流したデータが自分自身に返ってくることでループが発生してしまう可能性がある。
ツリー型であれば、閉路がない状態でサーバーノード同士を繋げることができる為、編集履歴の結果を他のサーバーノードに流すだけですみ、結果ループを防ぐことができる。

\begin{figure}[htbp]
    \centering
    \includegraphics[width=100mm]{pic/ring.pdf}
    \caption{ring型のトポロジー}
    \label{fig:ring}
\end{figure}

\begin{figure}[htbp]
    \centering
    \includegraphics[width=100mm]{pic/mesh.pdf}
    \caption{メッシュ型のトポロジー}
    \label{fig:mesh}
\end{figure}

ネットワークトポロジーは、当研究室で開発している並列分散フレームワークであるAliceが提供する、TopologyManagerという機能を用いて構成されている。

また、データ分散の為には、どのデータをネットワークに流すのか決めなければならない。そこで、TreeOperationLogを使用する。前セクションでも述べたが、TreeOperationLogには、どのNodeにどのような操作をしたのかという、データ編集の履歴情報が入っている。
このTreeOperationLogをAliceを用いて他のサーバーノードに送り、データの編集をしてもらうことで、同じデータをもつことが可能になる。