Papers/2017/tatsuki-master: jungle.tex comparison

comparison jungle.tex @ 14:e4da23b04260

commit

author	tatsuki
date	Wed, 08 Feb 2017 17:26:22 +0900
parents	f75a57018792
children	33d8077a5d45

comparison

equal deleted inserted replaced

-:7acd7d5afeb6
+:e4da23b04260
 \chapter{非破壊的木構造データベースJungle}
+本章では、当研究室で開発を行っているデータベース Jungle について記述する。
+\section{概要}
 Jungleは、当研究室で開発を行っているデータベースで、Javaを用いて実装されている。
 Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合で出来ている。
 ノードは自身の子のリストと属性名と属性値の組でデータを持ち、データベースのレコードに相当する。
 通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。
 Jungleでは、親から子への片方向の参照しか持たない。
 Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。
 持続性のある分散ノードを用いることでJungleの持続性を保証することができる。本論文では基本的に分散実装部分ではなく on memory DBの
 部分について考察する。
 本章ではまず破壊的木構造と、非破壊的木構造の説明をし、その後Jungleの提供しているAPIについて述べる。
-\section{破壊的木構造}
+\newpage
+\section{非破壊的木構造}
+Jungle は、非破壊的木構造という特殊な木構造を持つ。
+本節では、初めに破壊的木構造と非破壊的木構造の編集・メリットデメリットについて記述する。
+\vspace{0.3in}
+{\Large 破壊的木構造の編集}
+\vspace{0.1in}
 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う。
 図\ref{fig:destractive}は破壊的木構造におけるデータ編集を表している。
 \begin{figure}[htpb]
 \begin{center}
 破壊的木構造は、編集を行う際に木のロックを掛ける必要がある。
 この時、データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり、
 閲覧者がいる場合は木の走査が終わるまで書き換えを待たなければならない。
-\section{非破壊的木構造}
+\vspace{0.3in}
+{\Large 非破壊的木構造の編集}
+\vspace{0.1in}
 データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{fig:nondestractive})。
 その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{fig:nondestractive}の例ではノード1・3・4は編集に関係ないため新しいルートノードから参照を行い、過去の木と共有を行っている)。
 \begin{figure}[htpb]
 \begin{center}
 \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}に記す。
 \label{Attribute}
 \end{center}
 \end{table}
 \newpage
-以下にルートノードの2番目の子供から、属性名 {\tt name}とペアになっている属性値を取得するサンプルコードを記述する。
+以下にルートノードの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);
 TreeNode child = either.b();
 Attribute attribute = child.getAttribute();
 String value = attribute.getString("name");
 \end{lstlisting}
-\begin{enumerate}
+ソースコード\ref{getAttributeCode}の説明を行う。
-\item Jungleから名前が{\tt "TreeName"}の木を取得する。
+1行目から2行目で
-\item 取得した木のルートノードを取得する。
-\item 木のルートノードから{\tt Children}を取得する。
-\item 3で取得した{\tt Children}から2番目の子供を取得する。
-\item 関数{\tt Either.isA()}を用いて、2番目の子供が取得できたかを調べる。
-\item 取得できていなかった場合{\tt Either.a()}でErrorを返す。
-\item 取得に成功していた場合、{\tt Either.b()}で子ノードを取得する。
-\item 取得した子ノードから{\tt Attribute}クラスを取得する。
-\item 取得した{\tt attribute}から属性名 {\tt name}とペアの属性値を取得する。
-\end{enumerate}
 \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}{|p{15em}|p{24em}|}        \hline
+\begin{tabular*}{\textwidth}{|p{15em}|p{22em}|}         \hline
-{\tt Either<Error, JungleTreeEditor> addNewChildAt( NodePath path,  int pos)} &
+{\small\tt addNewChildAt( NodePath path,  int pos)} &
-変数{\tt path}で指定した場所にあるノードの、変数{\tt pos}で指定した位置に子ノードを追加する。\\ \hline
+{\tt path}で指定したノードの{\tt pos}番目の子の後にノードを追加する。\\ \hline
-{\tt Either<Error, JungleTreeEditor> deleteChildAt( NodePath path,int pos)}      &
+{\small\tt deleteChildAt( NodePath path,int pos)}      &
-変数{\tt path}で指定した場所にあるノードの、変数{\tt pos}で指定した位置の子ノードを削除する。 \\ \hline
+{\tt path}で指定したノードの{\tt pos}番目の子ノードを削除する。 \\ \hline
-{\tt Either<Error, JungleTreeEditor> putAttribute( NodePath path,String key,ByteBuffer value)} &
+{\small\tt putAttribute( NodePath path,String key,ByteBuffer value)} &
-変数{\tt path}で指定した場所にあるノードに、属性名 変数{\tt key} 属性値 変数{\tt value} のペアで値を挿入する。 \\ \hline
+{\tt path}で指定したノードに属性名 {\tt key} 属性値 {\tt value} のペアで値を挿入する。 \\ \hline
-{\tt Either< Error, JungleTreeEditor> deleteAttribute( NodePath path,String key)}&
+{\small\tt deleteAttribute( NodePath path,String key)}&
-変数{\tt path}で指定した場所にあるノードが持つ、属性名 変数{\tt key}とペアで保存されている属性値を削除する。\\ \hline
+{\tt path}で指定したノードが持つ、属性名 {\tt key}とペアで保存されている属性値を削除する。\\ \hline
-{\tt Either<Error, JungleTreeEditor> moveChild( NodePath path,int num,String move)} &
+{\small\tt moveChild( NodePath path,int num,String move)} &
-変数{\tt path}で指定した場所にあるノードの、変数{\tt num}で指定された位置の子供を変数{\tt move}の方向に移動させる。 \\ \hline
+{\tt path}で指定したノードの{\tt num}番目の子供を{\tt move}の方向に移動させる。 \\ \hline %あとで直す
-{\tt Either<Error, JungleTreeEditor> pushPop()} &
+{\small\tt pushPop()} &
 ルートノードの上に新しいルートノードを追加する。線形の木を作る際に使用することで木の変更の手間をO(n)からO(1)にできる。\\ \hline
-{\tt Either<Error, JungleTreeEditor> success()}  &
+{\small\tt success()}  &
 木へ行った変更をコミットする。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗する。 \\ \hline
-\end{tabular}
+\end{tabular*}
 \label{editor}
 \end{center}
 \end{table}
 分散版Jungleでは、Logを他ノードに送ることで、データの分散を行う。
-\section{検索APIの実装}
+\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);
 結果として、{\tt ryukyu}に所属する、名前が{\tt kanagawa}のデータを持つノードが取得できる。
 検索の際に使用する Index の実装については次節に記述する。
-\section{Indexの実装}
+\section{Index}
 Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。
 よって、全ての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。
 既存のTreeMapでは、一度Indexの複製を行ない、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。
 その問題を解決するため、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。
 このTreeMapは、Jungleと同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行った際、前の版と最大限データを共有した新しいTreeMapを作成する。
 return nodeListOp.get().iterator();
 \end{lstlisting}
 \begin{enumerate}
-\item {\tt indexMap}に、今回検索で使用する属性名 {\tt name}を使用して{\tt get("name")}を行う。すると属性名 {\tt name}に対応したIndexが、{\tt Optional}クラスで包まれて返ってくる。
+\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 取得したIndexに、検索で使用する属性値{\tt "kanagawa"}で{\tt get()}を行う。すると、属性名 {\tt "name"} 属性値{\tt  "kanagawa"}の値を持つノードのリストが、{\tt Optional}クラスに包まれて返ってくる。
-\item {\tt Optional}オブジェクトに対して中身を保持しているか(属性名 {\tt name} 属性値 {\tt kanagawa}を持つノードを木が持っているか)を調べる。
+\item {\tt Optional}オブジェクトに対して中身を保持しているか(属性名 {\tt "name"} 属性値 {\tt "kanagawa"}を持つノードを木が持っているか)を調べる。
 \item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。
 \item 持っていた場合{\tt Optional}オブジェクトからノードリストの{\tt Iterator}を返す。

Mercurial > hg > Papers > 2017 > tatsuki-master

comparison jungle.tex @ 14:e4da23b04260