\chapter{木構造データベースJungle}
Jungle はスケーラビリティのあるCMSの開発を目指して当研究室で開発されている非破壊的木構造データベースである.
一般的なコンテンツマネジメントシステムではブログツールやWiki・SNSが多く, これらの
ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している.
現在JavaとHaskellによりそれぞれ言語で開発されており本研究で扱うのはJava版である.

本章ではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungleにおけるデータ分散の設計について述べる.
\subsection{破壊的木構造}
破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う.
図\ref{fig:destractive}は破壊的木構造のにおけるデータ編集を表している.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/destructive_tree.pdf}
    \caption{破壊的木構造の編集}
    \label{fig:destractive}
  \end{center}
\end{figure}

破壊的木構造は, 編集を行う際に木のロックを掛ける必要がある.
この時, データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり, 閲覧者が
いる場合は木の走査が終わるまで書き換えをまたなければならない.
これではロックによりスケーラビリティが損なわれてしまう.

\subsection{非破壊的木構造}
非破壊的木構造は破壊的木構造とは違い, 一度作成した木を破壊することはない.
非破壊的木構造においてデータの編集は, ルートから編集を行うノードまでコピーを
行い新しく木構造を作成することで行われる.
図\ref{fig:nondestractive}は非破壊的木構造のデータ編集を示している.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_tree.pdf}
    \caption{非破壊的木構造の編集}
    \label{fig:nondestractive}
  \end{center}
\end{figure}

非破壊的木構造におけるデータ編集の手順を以下に示す.

\begin{enumerate}
\item ルートから編集を行うノードまでのパスを調べる(図\ref{fig:nondestractive_edit1}).
\item 編集を行うノードのコピーをとる. コピーをとったノードへデータの編集を行う(図\ref{fig:nondestractive_edit2}).
\item 調べたパスに従いルートからコピーしたノードまでの間のノードのコピーをとり繋げる(図\ref{fig:nondestractive_edit3}).
\item コピーしたルートノードは編集を行っていないノードへの参照を貼り新しい木構造を作る(図\ref{fig:nondestractive_edit4}).
\end{enumerate}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_edit1.pdf}
    \caption{非破壊的木構造の編集手順1}
    \label{fig:nondestractive_edit1}
  \end{center}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_edit2.pdf}
    \caption{非破壊的木構造の編集手順2}
    \label{fig:nondestractive_edit2}
  \end{center}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_edit3.pdf}
    \caption{非破壊的木構造の編集手順3}
    \label{fig:nondestractive_edit3}
  \end{center}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_edit4.pdf}
    \caption{非破壊的木構造の編集手順4}
    \label{fig:nondestractive_edit4}
  \end{center}
\end{figure}

\newpage

非破壊的木構造においてデータのロックが必要となる部分は, 木のコピーを作終りえた後に
ルートノードを更新するときだけである.
データ編集を行っている間ロックが必要な破壊的木構造に比べ, 編集中においてもデータの読み込みが
可能である(図\ref{fig:nondestractive_merit}).
そのため, 破壊的木構造に比べスケールがしやすくなっている.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf}
    \caption{非破壊的木構造による利点}
    \label{fig:nondestractive_merit}
  \end{center}
\end{figure}

\newpage

\section{Jungle におけるデータへのアクセス}
Jungleにおいてのデータアクセス手段について述べる.
Jungleではデータをそれぞれの Node が attribute として保持する.
attributeはKey-Valueによりデータを保持する.
KeyはString型でValueはByteBufferを使用している.
Jungleでデータへのアクセスは, このNodeへのアクセスをさす.
Node へのアクセスは, 木の名前と Node を指すパスにより行える.
このパスは NodePath と呼ばれる(図\ref{fig:nodepath}).

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/nodepath.pdf}
    \caption{Node の attribute と NodePath}
    \label{fig:nodepath}
  \end{center}
\end{figure}



\section{Jungle におけるデータ編集}

\subsection{NodeOperation}
Jungle による最小のデータ編集は Node の編集を指す.
Node 編集のために API が用意されており, この API は NodeOperation と呼ばれる.
NodeOperation には次の4つの API が用意されている.
\begin{itemize}
\item \verb|addNewChild(NodePath _path, int _pos)|\\
NodePath で指定された Node に子供となる Node を追加する API である.
pos で指定された番号に子供として追加を行う.
\item \verb|deleteChildAt(NodePath _path, int _pos)|\\
NodePath と pos により指定される Node を削除する API である.
\item \verb|putAttribute(NodePath _path, String _key, ByteBuffer _value)|\\
Node に attribute を追加する API である. 
NodePath は attribute を追加する Node を指す.
\item \verb|deleteAttribute(NodePath _path, String _key)|\\
\verb|_key| が示す attribute の削除を行う API である.
NodePath は Node を示す.
\end{itemize}

NodeOperationはNodePathとセットで扱わなければならず, このセットを
TreeOperationという.
TreeOperationが1つのデータ編集の単位になるが, これはあくまで最小のデータ編集の単位である.
Jungle によるデータの編集はTreeOperationが複数集まった単位でcommitされていく.
このTreeOperationの集まりをTreeOperationLogという.

\subsection{TreeOperationLog}
Jungle 内部ではTreeOperationは順次ログに積まれていき, 最終的に
commitされることで編集が完了する.
この時, ログに積まれた複数のTreeOperationはTreeOperationLogとして扱われる.
TreeOperationLogの仕様を\ref{src:treeoperationlog}に示す.
\begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left]
public interface TreeOperationLog extends Iterable<TreeOperation>
{
  public TreeOperationLog add(NodePath _p,NodeOperation _op);
  public TreeOperationLog append(TreeOperationLog _log);
  public int length();
}
\end{lstlisting}
\verb|Iterable<TreeOperation>|を継承しているためIteratorによりTreeOperationを取り出せるようになっている.
addやappendメソッドを使ってTreeOperationを積み上げていくことができる.

次にデータ編集により発生するTreeOperationLogの具体的な例を示す(\ref{src:treelog}).
\begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left]
[APPEND_CHILD:<-1>:pos:0]
[PUT_ATTRIBUTE:<-1,0>:key:author,value:oshiro]
[PUT_ATTRIBUTE:<-1,0>:key:mes,value:hello]
[PUT_ATTRIBUTE:<-1,0>:key:timestamp,value:0]
\end{lstlisting}
このログは今回の研究で使用したベンチマーク用掲示板プログラムにおける書き込みにより行われるログである(図\ref{fig:treeoperationlog}).

大文字の英字は実行した NodeOperation の種類を表す.
\verb|<>| により囲まれている数字は NodePath を示す.
NodePath の表記以降は Node の position や attribute の情報を表している.
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.7]{figures/treeoperationlog1.pdf}
    \caption{TreeOperationLog の具体例}
    \label{fig:treeoperationlog}
  \end{center}
\end{figure}

図\ref{fig:treeoperationlog}の説明を行う.
まず, \verb|APPEND_CHILD:<-1>:pos:0|によりRoot Nodeの0番目の子供となるNodeの追加を行う.
次に, 追加を行ったNodeに対して\verb|PUT_ATTRIBUTE<-1,0>| により attribute の情報を持たせていく.
attributeの内容に作者の情報を表すauther, メッセージの内容を表すmes, そしてタイムスタンプ
をtimestampとそれぞれキーにすることで追加される.

以上が掲示板プログラムにおける1つの書き込みで発生する TreeOperationLog である.

\newpage