\chapter{非破壊的木構造データベースJungle}
本章では、当研究室で開発を行っているデータベース Jungle について記述する。

\section{概要}
Jungleは、当研究室で開発を行っているデータベースで、Javaを用いて実装されている。
Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合で出来ている。
ノードは自身の子のリストと属性名と属性値の組でデータを持ち、データベースのレコードに相当する。
通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。
Jungleでは、親から子への片方向の参照しか持たない。

通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。
また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。
%特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、
特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、
十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。

Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。
Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。
持続性のある分散ノードを用いることでJungleの持続性を保証することができる。本論文では基本的に分散実装部分ではなく on memory DBの
部分について考察する。
本章ではまず破壊的木構造と、非破壊的木構造の説明をし、その後Jungleの提供しているAPIについて述べる。

\newpage

\section{非破壊的木構造}
Jungle は、非破壊的木構造という特殊な木構造を持つ。
本節では、初めに破壊的木構造と非破壊的木構造の編集・メリットデメリットについて記述する。

\vspace{0.3in}
{\Large 破壊的木構造の編集}

\vspace{0.1in}
破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う。
図\ref{fig:destractive}は破壊的木構造におけるデータ編集を表している。

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

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


\vspace{0.3in}
{\Large 非破壊的木構造の編集}

\vspace{0.1in}
データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{fig:nondestractive})。
その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{fig:nondestractive}の例ではノード1・3・4は編集に関係ないため新しいルートノードから参照を行い、過去の木と共有を行っている)。

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

\newpage
非破壊的木構造においてデータのロックが必要となる部分は、木のコピーを作り終えた後に
ルートノードを更新するときだけである。
データ編集を行っている間ロックが必要な破壊的木構造に比べ、編集中においてもデータの読み込みが可能であるが、
書き込み時の手間は大きくなる。



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

また、過去の木を保持する場合、非破壊的木構造は、木の複製後編集を行う必要がある。
一方、非破壊的木構造は過去の木を上書きしないため、過去の木のルートノードを保持するだけで良い。

\section{NodePath}
Jungleでは、木のノードの位置を{\tt NodePath}クラスを使って表す。
{\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。
{\tt NodePath}クラスを用いて{\tt< -1,1,2,3>}を表している際の例を図\ref{NodePath}に記す。

\begin{figure}[htpb]
\begin{center}
\includegraphics[scale=0.7]{figures/nodePath.pdf}
\caption{NodePath}
\label{NodePath}
\end{center}
\end{figure}

\newpage 
\section{Either}
Jungleは、失敗する可能性のある関数では返り値を{ \tt Either<A、B>}に包んで返す。
AにはError、Bには処理に成功した際の返り値の型が入る。
Eitherは、AかBどちらかの値しか持たない。
以下にEitherクラスが提供しているAPI(表\ref{EitherAPI})を記す。
\begin{table}[htb]
\begin{center}
\caption{Eitherに実装されているAPI}
\begin{tabular}{|p{15em}|p{24em}|}        \hline
{\tt boolean isA()} & EitherがAを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline
{\tt boolean isB()} & EitherがBを持っているかどうかを調べる。持っている場合trueを返す。\\ \hline
{\tt A a()} & Aの値を取得する。\\ \hline
{\tt B b()} & Bの値を取得する。\\ \hline
\end{tabular}
\label{EitherAPI}
\end{center}
\end{table}

{\tt Either<A、B>} の使い方は、{\tt isA()}を用いて関数が{\tt Error}を返していないかを調べる。
{\tt Error}でない場合は{\tt b()}で関数の返り値を取得する。


\section{木の生成}
Jungleにおける木の生成について述べる。
Jungleは複数の木構造を、名前を利用して作成・編集・削除を行い管理している。
Jungleクラスが提供している木の生成・管理を行うAPIを表\ref{jungleAPI}に記す。

\begin{table}[htb]
  \begin{center}
  \caption{Jungleに実装されているAPI}
    \begin{tabular}{|p{15em}|p{24em}|}        \hline
      {\tt JungleTree createNewTree(String treeName) } & Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す。     \\ \hline
      {\tt JungleTree getTreeByName(String treeName)}  & JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す       \\ \hline
    \end{tabular}
    \label{jungleAPI}
  \end{center}
\end{table}


\section{JungleTree}
Jungleは複数の木の集合で出来ている。
Jungleの木は、変更を加えるためのEditor・検索を行うTraversreなどを保持しており、ユーザーはそれらを用いてデータにアクセスする。
過去のバージョンの木に対するアクセスや、特定のノードのPathを検索する機能も持っている。
以下にJungleTreeクラスが提供しているAPI(表\ref{JungleTreeAPI})を記す
\begin{table}[htb]
\begin{center}
\caption{JungleTreeに実装されているAPI}
\begin{tabular}{|p{15em}|p{24em}|}        \hline
{\tt TreeNode getRootNode()} &木のルートノードを取得する。   \\ \hline
{\tt long revision()} & 木のバーションを取得する。初めは0から始まり、木への変更がCommitされる度に1上昇する。 \\ \hline
{\tt JungleTreeEditor getJungleTreeEditor()} & 木へ変更を加えるEditorを取得する。\\ \hline
{\tt Either<Error, JungleTree> getOldTree(long revision)} & 引数で指定したint revisionに等しいバージョンの木を取得する。 \\ \hline
{\tt InterfaceTraverser getTraverser()} & 木の検索を行うTraverserを取得する。 \\ \hline
{\tt Either<Error, TreeNode> getNodeOfPath(NodePath path)} & {\tt NodePathで指定した位置と値なるノードを取得する。}  \\ \hline
{\tt NodePath getNodePath(TreeNode node)} & 引数で渡したノードの位置を表す{\tt NodePath}を返す。\\ \hline
\end{tabular}
\label{JungleTreeAPI}
\end{center}
\end{table}


\section{TreeNode}
Jungleの木構造は、複数のノードの集合で出来ている。
ノードは、自身の子のListと属性名と属性値の組でデータを持つ。
ノードに対するアクセスは、表\ref{TreeNodeAPI}に記述されているAPIを用いて行われる。

\begin{table}[htb]
  \begin{center}
    \caption{TreeNodeに実装されているAPI}
    \begin{tabular}{|p{15em}|p{24em}|}                                  \hline
      {\tt Children getChildren()} & ノードの子供を扱うChildrenオブジェクトを返す。\\ \hline
      {\tt Attribute getAttribute()} &ノードが保持しているデータを扱うAttribteオブジェクトを返す。    \\ \hline
    \end{tabular}
    \label{TreeNodeAPI}
  \end{center}
\end{table}

Childrenクラスは表\ref{Children}に記述されたAPIを、Attributeクラスは表\ref{Attribute}に記述されたAPIを提供する。
これらを利用しノードが保持している値や、子供にアクセスする。
\begin{table}[htbH]
  \begin{center}
    \caption{Childrenに実装されているAPI}
    \begin{tabular}{|p{15em}|p{24em}|}                                  \hline
      {\tt int size()}  &  子供の数を返す。\\ \hline
      {\tt <Either Error,TreeNode> at(int num)} &ノードが持つ子供の中から、 変数{\tt num}で指定された位置にある子ノードを返す。存在しない位置を指定した場合、{\tt Error} を返す。   \\ \hline
    \end{tabular}
  \label{Children}
  \end{center}
\end{table}



\begin{table}[htbH]
  \begin{center}
    \caption{Attributeに実装されているAPI}
    \begin{tabular}{|p{15em}|p{24em}|} \hline
      {\tt ByteBuffer get(String key)}   &ノードが持つ値から、属性名 {\tt key}とペアの属性値を{\tt ByteBuffer}型で返す。ノードが保持していない{\tt key}を渡した場合エラーを返す。 \\ \hline
      {\tt String getString(String key)} &ノードが持つ値から、属性名 {\tt key} とペアの属性値を{\tt String}型で返す。ノードが保持していない{\tt key}を渡した場合エラーを返す。 \\ \hline
    \end{tabular}
  \label{Attribute}
  \end{center}
\end{table}

\newpage
以下にルートノードの2番目の子供から、属性名 {\tt name}とペアになっている属性値を取得するサンプルコード\ref{getAttributeCode}を記述する。
\begin{lstlisting}[frame=lrbt,numbers=left,label=getAttributeCode]
JungleTree tree = jungle.getTreeByName("TreeName");
TreeNode root = tree.getRootNode();
Children children = root.getChildren();
Either<Error,TreeNode> either = children.at(1);
if (either.isA()) 
  return either.a();
TreeNode child = either.b();
Attribute attribute = child.getAttribute();
String value = attribute.getString("name");
\end{lstlisting}

ソースコード\ref{getAttributeCode}の説明を行う。
1行目から2行目で

\section{木の編集API}
Jungleの木の編集は{\tt Default Jungle Tree Editor}クラスを用いて行われる。
{\tt Default Jungle Tree Editor}クラスは、木に対する編集を行うAPIが定義されているJungle Tree Editorインターフェースを実装している。
Default Jungle Tree Editorは、Jungle Tree から、{\tt getTreeEditor()}を用いて取得する。
表\ref{editor}にJungle Tree Editorインターフェースに定義されているAPIを記述する。
また、表\ref{editor}に記述しているAPIは全て、{\tt Either<Error,JungleTreeEditor>} を返す。
\newpage

\begin{table}[htb]
  \begin{center}
    \caption{Editorに実装されているAPI}
    \begin{tabular*}{\textwidth}{|p{15em}|p{22em}|}         \hline
      {\small\tt addNewChildAt( NodePath path,  int pos)} &
      {\tt path}で指定したノードの{\tt pos}番目の子の後にノードを追加する。\\ \hline
      {\small\tt deleteChildAt( NodePath path,int pos)}      &
      {\tt path}で指定したノードの{\tt pos}番目の子ノードを削除する。 \\ \hline
      {\small\tt putAttribute( NodePath path,String key,ByteBuffer value)} &
      {\tt path}で指定したノードに属性名 {\tt key} 属性値 {\tt value} のペアで値を挿入する。 \\ \hline
      {\small\tt deleteAttribute( NodePath path,String key)}&
      {\tt path}で指定したノードが持つ、属性名 {\tt key}とペアで保存されている属性値を削除する。\\ \hline
      {\small\tt moveChild( NodePath path,int num,String move)} &
      {\tt path}で指定したノードの{\tt num}番目の子供を{\tt move}の方向に移動させる。 \\ \hline %あとで直す
      {\small\tt pushPop()} &
      ルートノードの上に新しいルートノードを追加する。線形の木を作る際に使用することで木の変更の手間をO(n)からO(1)にできる。\\ \hline
      {\small\tt success()}  &
      木へ行った変更をコミットする。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗する。 \\ \hline
    \end{tabular*}
  \label{editor}
  \end{center}
\end{table}



編集後に返される{\tt JungleTreeEditor}クラスは、編集後の木構造を保持しているため、編集前の木構造を保持している{\tt JungleTreeEditor}クラスとは別のオブジェクトである。
編集を行った後は、関数{\tt editor.success()}で今までの編集をコミットすることができる。他の{\tt JungleTreeEditor}クラスによって木が更新されていた場合はコミットは失敗し、{\tt success()}は{\tt Error}を返す。
その場合は、木の編集を最初からやり直す必要がある。

以下に{\tt JungleTreeEditor}クラスを用いて、木の編集を行うサンプルコードを記述する。

\newpage 

\begin{lstlisting}[frame=lrbt,numbers=left,label=editorCode]
JungleTreeEditor editor = tree.getTreeEditor();
DefaultNodePath editNodePath = new DefaultNodePath();
Either<Error, JungleTreeEditor> either = editor.addNewChildAt(editNodePath, 0);
if (either.isA()) 
  return either.a();
editor = either.b();
editor.success();
\end{lstlisting}

\begin{enumerate}
  \item 関数{\tt tree.getEditor()}で編集を行う木から、{\tt JungleTreeEditor}クラスを取得する。 
  \item 次に変更するノードの場所を示す、{\tt NodePath}クラスを作成する。
  \item 関数{\tt editor.addNewChildAt()}を用いて、変数{\tt path}で指定したノードの子供の0番目に子ノードを追加する。
  \item 返り値の変数{\tt either}が{\tt Error}クラスを保持していないか(編集に失敗していないか)を確認する。
  \item {\tt Error}クラスを保持していた場合{\tt Either.a()}でErrorを返す。
  \item 編集に成功していた場合、編集後木を持った、{\tt JungleTreeEditor}クラスを取得する。
  \item 取得した{\tt JungleTreeEditor}クラスを用いて木の変更をコミットする。
\end{enumerate}

また、木に対して行われた変更は、Logとして書き出される。
これらのAPIにより、Jungleは木構造を格納、編集する機能を持っている。

\section{Log}
Jungle は、 Editor を用いて木に編集を加える際、使用した API に応じて対応する NodeOperation を作成する。
NodeOperation は NodePath とペアで扱わなければならず、このペアを TreeOperation という。
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を積み上げていくことができる。
積み上げたLogをディスクに書き出すことで、Jungleは永続性を持つ。
分散版Jungleでは、Logを他ノードに送ることで、データの分散を行う。




\section{検索API}
これまでに紹介したAPIにより、Jungleは木構造を構築できるようになった。
しかし、木に問い合わせを行う検索APIが実装されていなかったため、木の走査を行う{\tt Traverser}クラス内に、lambda式を用いて実装した。
以下に検索を行う関数{\tt find}の定義を記述する。
\begin{lstlisting}[frame=lrbt,label=query,numbers=left]
public Iterator<TreeNode> find(Query query, String key, String searchValue);
\end{lstlisting}

関数{\tt find}は、第一引数には、探索の条件を記述する関数{\tt boolean comdition(TreeNode)}を定義した{\tt Query}を。
第二、第三引数には、Indexを用いた絞込に使用する{\tt String key、String value}を取り、条件に一致したノードの{\tt Iterator}を返す。
{\tt 関数find}の使用例を以下に記す。

\begin{lstlisting}[frame=lrbt,label=find,numbers=left]
InterfaceTraverser traverser = tree.getTraverser(true);
Iterator<TreeNode> resultNodeIterator = traverser.find((TreeNode node) -> {
    String personId = node.getAttributes().getString("name");
      if (personId == null) return false;
        return personId.equals("kanagawa");
}, "belong", "ryukyu");
\end{lstlisting}


上記コードについて解説する。
\begin{enumerate}
  \item 木の走査を行う{\tt Traverser}クラスを取得する。

  \item Indexから{\tt find}の第2、第3引数である、属性名 {\tt belong}、属性値 {\tt ryukyu}の組のデータを持つノードを取得し、Queryに渡す(ノードの絞込を行う)。

  \item 引数のノードから関数{\tt getAttributes().getString("name")}で属性名 {\tt name}とペアになっている属性値を取得する。
  
  \item 属性値が{\tt null}だった場合、このノードには属性名が{\tt name}の組のデータは存在しないので、{\tt false}を返し次のノードの評価を行う。

  \item 属性値が{\tt null}でなかった場合、{\tt kanagawa}と一致するかどうかを調べ結果を返す。

\end{enumerate}

結果として、{\tt ryukyu}に所属する、名前が{\tt kanagawa}のデータを持つノードが取得できる。

検索の際に使用する Index の実装については次節に記述する。

\section{Index}
Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。
よって、全ての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。
既存のTreeMapでは、一度Indexの複製を行ない、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。
その問題を解決するため、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。
このTreeMapは、Jungleと同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行った際、前の版と最大限データを共有した新しいTreeMapを作成する。
Jungleとの違いは、木の回転処理が入ることである。
これにより複数の版全てに対応したIndexをサポートすることが可能になった。
以下にJungleにおけるIndexの型を記述する

\begin{lstlisting}[frame=lrbt,label=index,numbers=left]
TreeMap<String key,TreeMap<String attribute,List<TreeNode> nodeList> index> indexMap
\end{lstlisting}

JungleのIndexは{\tt IndexMap}内に保持されている。
属性名で{\tt IndexMap}に{\tt get}を行うと、対応したIndexが取得できる。
取得したIndexに属性値で{\tt get}を行うと、ノードのリストが返ってくる。
以下にIndexから属性名 name 属性値 kanagawaのデータを持つ、ノードのIteratorを取得するサンプルコードを記述する。

\begin{lstlisting}[frame=lrbt,label=find,numbers=left]
Optional<TreeMap<String, List<TreeNode>>> indexOp = indexMap.get("name");
if (!indexOp.isPresent())
  return new NulIterator<TreeNode>();
TreeMap<String, List<TreeNode>> index = indexOp.get();
Optional<List<TreeNode>> nodeListOp = index.get("kanagawa");
if (!nodeListOp.isPresent())
  return new NulIterator<TreeNode>();
return nodeListOp.get().iterator();
\end{lstlisting}


\begin{enumerate}
\item {\tt indexMap}に、今回検索で使用する属性名 {\tt name}を使用して{\tt get("name")}を行う。すると属性名 {\tt "name"}に対応したIndexが、{\tt Optional}クラスで包まれて返ってくる。

\item {\tt Optional}オブジェクトに対して、中身を保持しているか(属性名 {\tt name}に対応したIndexを木が持っているか)を調べる。

\item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。

\item 持っていた場合、{\tt Optional}オブジェクトからIndexを取得する。

\item 取得したIndexに、検索で使用する属性値{\tt "kanagawa"}で{\tt get()}を行う。すると、属性名 {\tt "name"} 属性値{\tt  "kanagawa"}の値を持つノードのリストが、{\tt Optional}クラスに包まれて返ってくる。

\item {\tt Optional}オブジェクトに対して中身を保持しているか(属性名 {\tt "name"} 属性値 {\tt "kanagawa"}を持つノードを木が持っているか)を調べる。

\item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。

\item 持っていた場合{\tt Optional}オブジェクトからノードリストの{\tt Iterator}を返す。

\end{enumerate}

JungleはこれらのAPIにより、木構造を格納、編集、検索する機能を持っている。

\newpage