\chapter{分散データベースJungle}
Jungleはスケーラビリティのある、世の中の知識構造を煩雑なデータ設計を行うこと無く格納できることを目指して、当研究室が開発しているデータベースである。
我々が扱う知識は、それぞれが連なり大きな知識を表現しているため主に木構造である。そのためJungleのデータ構造は、非破壊的木構造を採用している。

本章では、まずJungleの核部分であるJungle-Coreの説明を行った後、分散実装を行ったJungle-Networkについて述べる。
\label{chap:concept}

\section{JungleCore}
はじめにJungle最大の特徴である非破壊的木構造と通常の破壊的木構造の違いについて説明を行う。

通常の破壊的木構造は、データの編集を行う際に、データを上書き更新する(図\ref{fig:Des})ため、編集を行っている間ずっと木にロックをかける必要があり、また、閲覧者がいる場合、検索途中にデータが変わることを避けるために、データの検索が終わるまで書き換えを待つ必要がある。
しかし、これではロックによりスケーラビリティが損なわれてしまう。

\begin{figure}[h]
\begin{center}
\includegraphics[height = 5cm ,bb=0 0 404 207]{fig/destructive_tree.pdf}
\caption{破壊的木構造の編集}
\label{fig:Des}
\end{center}
\end{figure}

\clearpage

それに比べ非破壊的木構造は、一度生成した木を上書きすることはない。
データの編集は、ルートから編集を行うノードまでコピーを行い新しく木構造を構築することで行う(図\ref{fig:nonDes})。

\begin{figure}[h]
\begin{center}
\includegraphics[height = 5cm , bb=0 0 459 207]{fig/destructive_tree.pdf}
\caption{非破壊的木構造の編集}
\label{fig:nonDes}
\end{center}
\end{figure}

非破壊的木構造においてデータのロックが必要になる部分は、木のコピーを作った後に、ルートノードを更新するときだけである。
また、データ編集を行っている間ロックが必要な破壊的木構造に比べ、非破壊的木構造は検索中の木が変更されないことが保証されいているため、編集中においてもデータの読み込みが可能である。(図\ref{fig:desMerit})
そのため、非破壊的木構造に比べてスケールアウトがしやすくなっている。
\begin{figure}[h]
\begin{center}
\includegraphics[height = 7cm ,bb=0 0 350 301]{fig/non_destructive_merit.pdf}
\caption{非破壊的木構造の編集}
\label{fig:desMerit}
\end{center}
\end{figure}

また、過去のTreeは全て保持しているため、いつでもアクセスすることが可能である。

\section{JungleNetwork}
Jungle-Networkとは、通信機能を実装し、データを分散させて、スケールアウトを可能にしたJungleのことある。木構造を想定したネットワークトポロジーを形成し、サーバー同士を接続することで通信を行っている。
木構造なら、一度RootNodeまでデータを伝搬させることで整合性を取ることが出来る(図\ref{fig:topologu})。
データの伝搬中に衝突が発生した場合、Mergeを行い結果を改めて伝搬すれば良い。

\begin{figure}[h]
\begin{center}
\includegraphics[bb=0 0 329 263]{fig/network_topology_tree.pdf}
\caption{Jungle-networkのトポロジの形成例とデータの伝搬}
\label{fig:topologu}
\end{center}
\end{figure}


また、データの伝搬には当研究室で開発を行っている並列分散フレームワークであるAliceを使用している、
Aliceはユーザーが望んだマシンへの接続や、必要なデータへのアクセスを行う機構等、ネットワークトポロジー形成機能を提供している。