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

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で使用される人物のデータが記述されている。
人物Treeは、 ルートノードが、属性名 {\tt element} 属性値 {\tt Persons}の組のデータを持つ。図\ref{fig:PersonTree}では、{\tt Node1}がルートノードとなる。
ルートノードの下には、各人物のデータが格納されている(図\ref{fig:PersonTree}では{\tt Node2}、{\tt Node3}が該当する)。
属性名 {\tt element}、属性値 {\tt Person}の値は、この値を持つノードが人物のデータを持っていることを表す。
属性名 {\tt Person-id}、属性値 {\tt p:1} はこのノードに記述された人物のmaTrix上でのIDを表す。
他の役職、役割、権限といった木構造は、このIDを用いて参照を行うことで組織構造を構築する。
{\tt Node2}、{\tt 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は{\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をJungleが持っているか)を調べる。

\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}を持つノードをJungleが持っているか)を調べる。

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

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

\end{enumerate}


\subsection{検索APIの実装}
Indexを実装したことにより、Idを用いた組織構造の表現は可能になった。
しかし、組織構造に問い合わせを行う検索APIが実装されていなかったため、属性名 {\tt key} 属性値 {\tt value}の組で検索を行う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 Query query}、{\tt String key}、{\tt String value}の3つの引数を取り、条件に一致したノードの{\tt Iterator}インタフェースを返す。
第1引数には、探索の条件を記述する関数{\tt boolean comdition(TreeNode)}を定義した{\tt Interface Query}を。
第2、第3引数の、{\tt String key、String value}はIndexを用いた絞込みに使用する。{\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("Personid");
  if (personId == null) return false;
  return personId.equals("p:2");
}, "element", "Person");
\end{lstlisting}

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

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

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

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

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

\end{enumerate}

図\ref{fig:PersonTree}の人物Treeに対して、上記の検索を行うとNode3が取得できる。
(付録AにJDBCとの検索方法の比較を記述する。)
\subsection{ノードの親をたどるIndex}
maTrixがJungleに検索を行う際、親をたどる処理が必要になったが、Jungleは親から子への単一リンクしか持っていなかった。
しかし、Jungleは非破壊という性質上、子に親への参照をもたせることが難しいため、ノードを渡すと親ノードを返すParentIndexを実装した。
ParentIndexを実装したことで、非破壊という性質を保持しつつ親への参照を可能にした。

\subsection{性能測定}
maTrixの実装後、Jungleに実用的な性能があるか確かめるために測定を行った。
比較対象にはMongoDB\cite{mongodb2013}を選択した。
図\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は通信を介さないためだと考えられる。