\section{許認可管理アプリケーション\\maTrix}
本章では、Jungle上に実際に企業で運用されている許認可管理アプリケーションmaTrixを実装し、Jungleにデータベースとしての表現力、機能の十分性、実用的な性能があるかについて実証実験を行なう。

maTrixは、人物、役職、役割、権限、組織等の木構造のデータとポリシーファイルを持つ。maTrixの組織構造は、それぞれの木構造がidを用いた参照を行うことで表現される。また、maTrixは過去のアクセス要求を全て保存する。アクセス要求は当時の組織構造を参照しているため、過去の組織構造にアクセス可能にするため、組織構造は版管理されている。

ポリシーファイルは、データに対するアクセス要求が許可されるか否認されるかを判断するためのルールを誰が(Target)、何を(Resource)、どうできるか(Action)の3つの要素で記述されている。maTrixはアクセス要求に応じたポリシーファイルを参照することで許認可の判断を行う。
ポリシーファイルは組織構造中の人や役職をidを用いて参照している。つまり、ポリシーファイルを用いて許認可を下すためには、その人がどこの組織に所属して、その役割がどの権限を持っているかを返す検索が必要になる。
本章ではmaTrixをJungle上に実装する際の問題点、解法について記述する。

\subsection{Jungle上でのmaTrixデータ構造の表現}
maTrixの人物、組織、役割、権限等のデータ構造は木構造なので、Jungleの木構造にそのままマッピングできる。
実際のmaTrixのデータ構造の一部である人物のデータを格納したJungleTree(図\ref{fig:PersonTree})を以下に記す。

\begin{figure}[h]
\begin{center}
\includegraphics[height = 7cm , bb=0 0 820 817]{images/TreePersonJungle.pdf}
\caption{Jungle上での人物Treeの表現例}
\label{fig:PersonTree}
\end{center}
\end{figure}

図\ref{fig:PersonTree}の人物Treeには、maTrixで使用される人物のデータが記述されている。
属性名 element 属性値 Personsのデータを持つNode1は、人物Treeのルートノードである。このノードの下に各人物のデータが格納されている(図\ref{fig:PersonTree}ではNode2、Node3が該当する)。
Node2、Node3が持つ、属性名 element、属性値 Personの値は、Node2、Node3が人物のデータを持っていることを表す。
またNode2が持つ、属性名 Person-id、属性値 p:1 はこのノードに記述された人物のmaTrix上でのIDを表す。
他の役職、役割、権限といった木構造は、このIDを用いて参照を行うことで組織構造を構築する。
Node2、Node3は子ノードに人物の名前、参照する他の木構造のId等のデータを持つが、今回は省略している。

また、maTrixは自身のデータをXML形式で書き出すことが可能である。書き出したデータをJungleに格納するために汎用XMLReaderの実装も行った。

\subsection{Indexの実装}
% Jungleに含まれる複数の木のノードを相互参照したい
% 木のノードにIDを割ふってIndexを用いて参照する
Jungle上でのmaTrixの組織構造の表現は、木のノードにIdを割り振ってIndexを用いた参照で表現する。
しかし、Jungleには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> node> index> indexMap
\end{lstlisting}

JungleのIndexはIndexMap内に保持されている。
属性名でIndexMapにgetを行うと、対応したIndexが取得できる。
その取得したIndexに属性値で検索を行うと、対応したノードのリストが返ってくる。


\subsection{検索APIの実装}
Indexを実装したことにより、Idを用いた組織構造の表現は可能になった。
しかし、組織構造に対する問い合わせを行うための検索APIが実装されていなかったため、属性名 key 属性値 valueの組で検索を行うAPIの実装を、木の走査を行うTraverserクラス内に、lambda式を用いて行った。
以下に検索を行う関数findの定義を記述する。
\begin{lstlisting}[frame=lrbt,label=query,numbers=left]
public Iterator<TreeNode> find(Query query, 
               String key, String searchValue);
\end{lstlisting}

find関数は引数に、Query query、String key、String valueの3つの引数を取り、条件に一致したノードのIteratorインタフェースを返す。
第1引数には、探索の条件を記述する関数boolean comdition(TreeNode)を定義したInterface Queryを。
第2、第3引数の、String key、String valueはIndexを用いた絞込みに使用する。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("Personid");
    if (personId == null)
      return false;
    if (personId.equals("p:2"))
      return true;
    return false;
    }, "element", "Person");
\end{lstlisting}

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

\item Indexからfindの第2、第3引数である、属性名 element、属性値 Personの組のデータを持つNodeを取得する。

\item (2)で取得したノードを第1引数のQueryに渡す。

\item 引数のノードから関数getAttributes().getString("Personid")で属性名 Personidとペアになっている属性値を取得する。

\item 属性値がnullだった場合、このNodeには属性名がPersonidの組のデータは存在しないので、falseを返し次のNodeの評価を行う。

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

\end{enumerate}

図\ref{fig:PersonTree}の人物Treeに対して、上記の検索を行うとNode3が取得できる。

\subsection{Nodeの親をたどるIndex}
maTrixがJungleに検索を行う際、親をたどる処理が必要になったが、Jungleは親から子への単一リンクしか持っていなかった。
しかし、Jungleは非破壊という性質上、子に親への参照をもたせることが難しいため、ノードを渡すと親ノードを返すParentIndexを実装した。
ParentIndexを実装したことで、非破壊という性質を保持しつつ親への参照を可能にした。

\subsection{性能測定}
maTrixの実装後、Jungleに実用的な性能があるか確かめるために測定を行った。
比較対象にはMongoDBを選択した。
図\ref{fig:compare}はmongoDBとJungleの速度比較のグラフである。
比較は10000人分のデータに対するアクセスの処理時間で行い、mongoDBへのアクセスはjsを用いて行った。
\begin{figure}[h]
\begin{center}
\includegraphics[height = 5cm , bb=0 0 360 252]{images/mongoJungleperfomance.pdf}
\caption{mongoDBとの比較}
\label{fig:compare}
\end{center}
\end{figure}

Jungleは、mongodbの約500倍の性能が出ている。
その理由として、mongoDBがmmapを用いてディスクのデータにアクセスしているのに対し、Jungleは全てのデータがメモリ上にあること。
また、mongoDBは通信を介してアクセスされるが、Jungleは通信を介さないためだと考えられる。