Mercurial > hg > Papers > 2016 > tatsuki-prosym
view jungle.tex @ 34:34ee004791a3
Modify
author | tatsuki |
---|---|
date | Wed, 30 Nov 2016 16:24:29 +0900 |
parents | 388da5c83f48 |
children | eea008c85b3b |
line wrap: on
line source
\section{非破壊的木構造データベースJungle} Jungleは、当研究室が開発を行っているデータベースで、Javaを用いて実装されている。 Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合で出来ている。 ノードは自身の子のリストと属性名と属性値の組でデータを持ち、データベースのレコードに相当する。 通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。 Jungleでは、親から子への片方向の参照しか持たない。 Jungleは、データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{nonDestractTreeEdit})。 その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{nonDestractTreeEdit}の例ではノードB D Eは編集に関係ないためノードAから参照を行い、過去の木と共有を行っている)。 これを非破壊的木構造と呼ぶ。非破壊木構造は新しい木を構築している時にも、現在の木を安全に読み出せるという特徴がある。 しかし、書き込み時の手間は大きくなる。 \begin{figure}[h] \begin{center} \includegraphics[height = 2.5cm , bb=0 0 511 188]{images/nonDestractTreeEdit.pdf} \caption{非破壊的木構造の木の編集} \label{nonDestractTreeEdit} \end{center} \end{figure} \newpage 通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。 この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。 %特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、 特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、 十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。 Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。 Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。 持続性のある分散ノードを用いることでJungleの持続性を保証することができる。本論文では分散実装部分ではなく on memory DBの 部分について考察する。 \subsection{木の生成} 初めにJungleにおける木の生成について述べる。 Jungleは複数の木を、名前を利用して管理しており、名前を利用することで作成・編集・削除を行う。 以下にJungleクラスが提供している木の生成・管理を行うAPI(表\ref{jungleAPI})を記す。 \begin{table}[htb] \begin{center} \caption{Jungleに実装されているAPI} \begin{tabular}{|p{12em}|p{12em}|} \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} \newpage \subsection{TreeNode} Jungleが保持している木は、複数のノードの集合で出来ている。 ノードは、自身の子のListと属性名と属性値の組でデータを持つ。 ノードに対するアクセスは、表\ref{TreeNodeAPI}に記述されているAPIを用いて行われる。 \begin{table}[htb] \begin{center} \caption{TreeNodeに実装されているAPI} \begin{tabular}{|p{8em}|p{14em}|} \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{8em}|p{14em}|} \hline {\tt int size()} & 子供の数を返す。\\ \hline {\tt <Either Error,TreeNode> at(int num)} &ノードが持つ子供の中から、 変数{\tt num}で指定された位置にある子ノードを返す。 \\ \hline \end{tabular} \label{Children} \end{center} \end{table} 関数{\tt children.at(int num)}が返す{\tt Either\textless Error,TreeNode\textgreater} オブジェクトは、{\tt isA() }で{\tt Error}かどうかをチェックすることができる。 {\tt Error}でない場合は{\tt b()}で{\tt TreeNode}オブジェクトを取り出すことができる。 \begin{table}[htbH] \begin{center} \caption{Attributeに実装されているAPI} \begin{tabular}{|p{10em}|p{12em}|} \hline {\tt ByteBuffer get(String key)} &ノードが持つ値から、属性名 {\tt key}とペアの属性値を{\tt ByteBuffer}型で返す。 \\ \hline {\tt String getString(String key)} &ノードが持つ値から、属性名 {\tt key} とペアの属性値を{\tt String}型で返す。 \\ \hline \end{tabular} \label{Attribute} \end{center} \end{table} \newpage 以下にルートノードの2番目の子供から、属性名 {\tt name}とペアになっている属性値を取得するサンプルコードを記述する。 \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(2); if (either.isA()) throw new IOException(); TreeNode child = either.b(); Attribute attribute = child.getAttribute(); String value = attribute.getString("name"); \end{lstlisting} \begin{enumerate} \item Jungleから名前を指定して木を取得する。 \item 取得した木のルートノードを取得する。 \item 木のルートノードから{\tt Children}型の子ノードを取得する。 \item 変数{\tt children}から2番目の子供を取得する。 \item 2番目の子供が取得できたかを調べる。 \item 取得できていなかった場合{\tt Exception}を投げる。 \item 取得に成功していた場合、{\tt either}から子ノードを受け取る。 \item 取得した子ノードから{\tt Attribute}クラスを取得する。 \item 取得した{\tt attribute}から属性名 {\tt name}がペアの値を取得する。 \end{enumerate} \subsection{NodePath} Jungleでは、木のノードの位置を{\tt NodePath}クラスを使って表す。 {\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。また、ルートノードは例外として-1と表記される。 {\tt NodePath}クラスが{\tt < -1,1,2,3>} を表している際の例を図\ref{NodePath}に記す。 \begin{figure}[h] \begin{center} \includegraphics[height = 6cm , bb=0 0 568 455]{images/nodePath.pdf} \caption{NodePath} \label{NodePath} \end{center} \end{figure} \newpage \subsection{木の編集API} Jungleの木の編集は{\tt JungleTreeEditor}クラスを用いて行われる。 {\tt JungleTreeEditor}クラスには編集を行うために、表\ref{editor}で定義されているAPIが実装されている。 \begin{table}[htb] \begin{center} \caption{Editorに実装されているAPI} \begin{tabular}{|p{8em}|p{14em}|} \hline {\tt Either<Error, JungleTreeEditor> addNewChildAt( NodePath path, int pos)} & 変数{\tt path}で指定した場所にある、ノードの子供の変数{\tt pos}で指定した位置子ノードを追加する\\ \hline {\tt Either<Error, JungleTreeEditor> deleteChildAt( NodePath path,int pos)} & 変数{\tt path}で指定した場所にある、ノードの子供の変数{\tt pos}で指定した位置の子ノードを削除する。 \\ \hline {\tt Either<Error, JungleTreeEditor> putAttribute( NodePath path,String key,ByteBuffer value)} & 変数{\tt path}で指定した場所にあるノードに、属性名 変数{\tt key} 属性値 変数{\tt value} のペアで値を挿入する。 \\ \hline {\tt Either< Error, JungleTreeEditor> deleteAttribute( NodePath path,String key)}& 変数{\tt path}で指定した場所にあるノードが持つ、属性名 変数{\tt key}とペアで保存されているデータを削除する。\\ \hline {\tt Either<Error, JungleTreeEditor> moveChild( NodePath path,int num,String move)} & 変数{\tt path}で指定した場所にある、ノードの変数{\tt num}で指定された位置の子供を変数{\tt move}の方向に移動させる。 \\ \hline {\tt Either<Error, JungleTreeEditor> pushPop()} & ルートノードの上に新しいルートノードを追加する。線形の木を作る際に使用することで計算量をO(n)からO(1)にできる。\\ \hline {\tt Either<Error, JungleTreeEditor> 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}クラスを用いて、木の編集を行うサンプルコードを記述する。 \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()) throw new IllegalStateException(); 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 Exception}を投げる。 \item 編集に成功していた場合、編集後木を持った、{\tt JungleTreeEditor}クラスを取得する。 \item 取得した{\tt JungleTreeEditor}クラスを用いて木の変更をコミットする。 \end{enumerate} これらのAPIにより、Jungleは木構造を格納、編集する機能を持っている。