\chapter{分散木構造データベースJungle}
Jungleとは、当研究室で開発を行っている、スケーラビリティのある、世の中の知識構造を煩雑なデータ設計を行うこと無く格納できることを目標としたデータベースである。
本章では、Jungleの基本的な特徴についての解説を行う。

\label{chap:concept}

\section{Jungleのデータ構造}
研究目的でも述べたが、我々が扱う知識は主に木構造である。
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/non_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}

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

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

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}