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

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

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

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

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

\section{分散機構}
Jungleの分散機構は、木構造、すなわちツリー型を想定したネットワークトポロジーを形成し、サーバー同士を接続することで通信を行なっている。
リング型(図\ref{fig:ring} ）やメッシュ型(図\ref{fig:mesh} ）のトポロジーでは、データの編集結果を他のサーバーノードに流す際に、流したデータが自分自身に返ってくることでループが発生してしまう可能性がある。
ツリー型であれば、閉路がない状態でサーバーノード同士を繋げることができる為、編集履歴の結果を他のサーバーノードに流すだけですみ、結果ループを防ぐことができる(図\ref{fig:tree}）。

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

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

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

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

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