# HG changeset patch # User suruga # Date 1492714609 -32400 # Node ID 6b61e24c14c299cfdd498cbb46adc475f42c3bd7 # Parent ad41c4a444284f7aa5850b8d0b2a98750024d57b sigos_ver6 : add abstract diff -r ad41c4a44428 -r 6b61e24c14c2 paper/sigos.aux --- a/paper/sigos.aux Fri Apr 21 02:27:16 2017 +0900 +++ b/paper/sigos.aux Fri Apr 21 03:56:49 2017 +0900 @@ -1,11 +1,12 @@ \relax -\newlabel{fig:non_destructive_tree}{{1}{1}} +\newlabel{fig:non_destructive_tree}{{1}{2}} \newlabel{fig:nodepath}{{2}{2}} \newlabel{fig:PushPopDemerit}{{3}{3}} -\newlabel{table:Diffetential API}{{1}{3}} -\newlabel{fig:EditDifferencialTree}{{4}{3}} +\newlabel{table:Diffetential API}{{1}{4}} +\newlabel{fig:EditDifferencialTree}{{4}{4}} \newlabel{fig:Differential_Interface_Traverser}{{5}{4}} -\newlabel{fig:Tree_ver2}{{6}{4}} +\newlabel{fig:Tree_ver2}{{6}{5}} +\newlabel{table:Diffetential API}{{2}{5}} \citation{*} \bibstyle{ipsjunsrt} \bibdata{sigos} @@ -15,5 +16,4 @@ \bibcite{opencl}{4} \bibcite{cuda}{5} \bibcite{gears}{6} -\newlabel{table:Diffetential API}{{2}{5}} -\gdef\ipsj@lastpage{5} +\gdef\ipsj@lastpage{6} diff -r ad41c4a44428 -r 6b61e24c14c2 paper/sigos.dvi Binary file paper/sigos.dvi has changed diff -r ad41c4a44428 -r 6b61e24c14c2 paper/sigos.log --- a/paper/sigos.log Fri Apr 21 02:27:16 2017 +0900 +++ b/paper/sigos.log Fri Apr 21 03:56:49 2017 +0900 @@ -1,4 +1,4 @@ -This is e-pTeX, Version 3.14159265-p3.7-160201-2.6 (utf8.euc) (TeX Live 2016) (preloaded format=platex 2017.4.10) 21 APR 2017 02:26 +This is e-pTeX, Version 3.14159265-p3.7-160201-2.6 (utf8.euc) (TeX Live 2016) (preloaded format=platex 2017.4.10) 21 APR 2017 03:56 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -183,82 +183,93 @@ LaTeX Font Info: ... okay on input line 36. \c@lstlisting=\count113 LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <14.4> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 82. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 78. LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <14.4> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 82. +(Font) Font shape `JY1/gt/m/n' tried instead on input line 78. LaTeX Font Info: External font `cmex10' loaded for size -(Font) <10.95> on input line 82. +(Font) <10.95> on input line 78. LaTeX Font Info: External font `cmex10' loaded for size -(Font) <8> on input line 82. +(Font) <8> on input line 78. LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <12> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 82. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 78. LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <12> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 82. +(Font) Font shape `JY1/gt/m/n' tried instead on input line 78. + + +Class ipsjpapers Warning: Missing eabstract env on input line 78. + LaTeX Font Info: External font `cmex10' loaded for size -(Font) <7> on input line 82. +(Font) <7> on input line 78. File: ./pic/non_destructive_tree.pdf Graphic file (type pdf) - <./pic/non_destructive_tree.pdf> +<./pic/non_destructive_tree.pdf> LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <7> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 96. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 92. LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <7> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 96. -LaTeX Font Info: Try loading font information for OML+cmr on input line 106. +(Font) Font shape `JY1/gt/m/n' tried instead on input line 92. + [1 + + +] +LaTeX Font Info: Try loading font information for OML+cmr on input line 100. (/usr/local/texlive/2016/texmf-dist/tex/latex/base/omlcmr.fd File: omlcmr.fd 2014/09/29 v2.5h Standard LaTeX font definitions ) LaTeX Font Info: Font shape `OML/cmr/m/n' in size <9> not available -(Font) Font shape `OML/cmm/m/it' tried instead on input line 106. - [1 - - -] +(Font) Font shape `OML/cmm/m/it' tried instead on input line 100. File: ./pic/nodepath.pdf Graphic file (type pdf) -<./pic/nodepath.pdf> +<./pic/nodepath.pdf> [2] LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <9> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 131. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 125. LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <9> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 131. +(Font) Font shape `JY1/gt/m/n' tried instead on input line 125. File: ./pic/PushPopDemerit.pdf Graphic file (type pdf) - <./pic/PushPopDemerit.pdf> [2] + <./pic/PushPopDemerit.pdf> LaTeX Warning: Reference `table:Differential API' on page 3 undefined on input -line 172. +line 166. -Overfull \hbox (0.80186pt too wide) in paragraph at lines 178--178 +Overfull \hbox (0.80186pt too wide) in paragraph at lines 172--172 [][]| [] -Overfull \hbox (18.31381pt too wide) in paragraph at lines 177--182 +Overfull \hbox (18.31381pt too wide) in paragraph at lines 171--176 [][][] [] +[3] File: ./pic/EditDifferencialTree.pdf Graphic file (type pdf) -<./pic/EditDifferencialTree.pdf> -Overfull \hbox (14.58702pt too wide) in paragraph at lines 200--201 + <./pic/EditDifferencialTree.pdf> +Overfull \hbox (22.76657pt too wide) in paragraph at lines 186--187 + [] + [] + + +Overfull \hbox (14.58702pt too wide) in paragraph at lines 194--195 []\OT1/cmr/m/n/9 Editor \JY1/mc/m/n/9 が保持している木構造に対して \OT1/cmr/m/n /9 addNewChild( [] -[3] File: ./pic/Differential_Interface_Traverser.pdf Graphic file (type pdf) - <./pic/Differential_Interface_Traverser.pdf> +<./pic/Differential_Interface_Traverser.pdf> [4] File: ./pic/Tree_ver2.pdf Graphic file (type pdf) - <./pic/Tree_ver2.pdf> [4] -Overfull \hbox (18.31381pt too wide) in paragraph at lines 241--246 + <./pic/Tree_ver2.pdf> +Overfull \hbox (18.31381pt too wide) in paragraph at lines 232--237 [][][] [] -(./sigos.bbl +[5] (./sigos.bbl Overfull \hbox (58.50209pt too wide) in paragraph at lines 20--21 []\OT1/cmr/m/n/9 : CUDA, https://developer.nvidia.com/category/zone/cuda- [] -) [5] (./sigos.aux) +) [6 + +] (./sigos.aux) LaTeX Warning: There were undefined references. @@ -269,10 +280,10 @@ Here is how much of TeX's memory you used: 3090 strings out of 493693 43373 string characters out of 6149787 - 145093 words of memory out of 5000000 + 147093 words of memory out of 5000000 6635 multiletter control sequences out of 15000+600000 17185 words of font info for 66 fonts, out of 8000000 for 9000 929 hyphenation exceptions out of 8191 - 30i,13n,49p,943b,329s stack positions out of 5000i,500n,10000p,200000b,80000s + 30i,13n,49p,1721b,329s stack positions out of 5000i,500n,10000p,200000b,80000s -Output written on sigos.dvi (5 pages, 35256 bytes). +Output written on sigos.dvi (6 pages, 40660 bytes). diff -r ad41c4a44428 -r 6b61e24c14c2 paper/sigos.pdf Binary file paper/sigos.pdf has changed diff -r ad41c4a44428 -r 6b61e24c14c2 paper/sigos.tex --- a/paper/sigos.tex Fri Apr 21 02:27:16 2017 +0900 +++ b/paper/sigos.tex Fri Apr 21 03:56:49 2017 +0900 @@ -46,18 +46,18 @@ % 和文著者名 \author{ - 仲松　栞\affiref{1} + 仲松　栞\affiref{2} \and - 照屋 のぞみ \affiref{2} + 照屋 のぞみ \affiref{1} \and - 河野 真治\affiref{2} + 河野 真治\affiref{1} } % 英文著者名 \eauthor{ Nakamatsu Shiori\affiref{1} \and - eruya Nozomi\affiref{2} + Teruya Nozomi\affiref{2} \and Shinji KONO\affiref{2} } @@ -71,13 +71,9 @@ % 和文概要 \begin{abstract} - + コンピュータの性能が向上するにつれ、ソフトウェアやアプリケーションを高速に動作させる需要が求められてきた。しかし、RDBでは、同時書き込みの際に起こる競合を防ぐため、編集中にロックがかけられ、編集に時間がかかってしまう。また、不定形のデータ構造と表構造がミスマッチを起こしてしまう、インピーダンスミスマッチという問題がある。そこで当研究では、非破壊的木構造データベースJungleを開発している。非破壊的木構造により、読み込みと書き込みを同時に実行することができる。また、データベースの再設計を行わずに不定形のデータ構造を扱うことが可能である。本研究ではJungleの木と Index の編集機能の改善を行う。また、分散環境におけるjungleの書き出し速度の測定方法の提案をする。 \end{abstract} -% 英文概要 -\begin{eabstract} -\end{eabstract} - % 表題などの出力 \maketitle @@ -85,20 +81,18 @@ % Introduce \section{研究目的と背景} - + CPUのマルチコア化により、コンピュータのCPU性能が格段に上がった。マルチコアCPUの普及により、一般的なコンピュータの性能も向上してきた。コンピュータの性能が向上するにつれ、ソフトウェアやアプリケーションを高速に動作させる需要が求められてきた。しかし、RDBでは、１一人のユーザーがデータを書き込んでいるとき、他のユーザーが書き込みをしてくることで起こるデータの競合を防ぐために、書き込みが終わるまでロックをかける必要がある。これにより、データの編集に時間がかかってしまうという問題がある。また、データのネスト構造を許さない第一正規系を要求するRDBの表構造は、Jsonなどの不定形のデータ構造とミスマッチを起こしてしまうという問題がある。この問題はデータベースのインピーダンスミスマッチと呼ばれている。不定形の構造の変更をトランザクションとしてJsonの一括変更という形で処理する方法が考えられるが、並列処理が中心となってきている今のアプリケーションには向いているとは言えない。これらの問題を解決するため、当研究室では、分散処理環境で動くことができるデータベースを目指して非破壊的木構造データベースJungleを開発している。木構造を扱えることによって、従来のRDBとは異なり、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、その木をそのままデータベースとして使用することも可能である。非破壊的木構造とは、データの元の木を直接書き換えずに保存し、新しく構築した木のデータ構造を編集する方法である。 これにより、データの書き込み中であっても、元のデータは変更されない為、読み込みも同時に行うことができる。Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。また、Index の構築も大幅なネックとなっていた。そこで、本研究ではJungleの木と Index の編集機能の改善を行う。また、分散環境におけるjungleの書き出し速度の測定方法の提案をする。 \section{非破壊的木構造データベースJungle} Jungleは、当研究室で開発を行っている非破壊的木構造データベースで、Javaを用いて実装されている。非破壊的木構造とは、データの編集を一度生成した木を上書きせず、ルートから編集を行う位置までのノードをコピーする特徴を持つ（図\ref{fig:non_destructive_tree} ）。これにより、読み込み中にデータが変更されないことが保証されているため、書き込みと読み込みを同時に行うことできる。 %木のルートをAtomicに置き換えることで、木のアップデートを行う。変更前の木が残っているので、そのまま使用できる。変更されないノードは変更前と変更後のルートから共有されることになる。 \begin{figure}[ht] \begin{center} - \includegraphics[width=60mm]{./pic/non_destructive_tree.pdf} + \includegraphics[width=70mm]{./pic/non_destructive_tree.pdf} \end{center} \caption{非破壊的木構造の編集} \label{fig:non_destructive_tree} \end{figure} -　Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合でできている。ノードは自身の子のリストと属性名、属性値を持ち、データベースのレコードに相応する。通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。Jungleでは、子供からの親へのポインタは持たないため、親から子への片方向の参照しかできない。 -　通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。 -　Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。持続性のある分散ノードを用いることでJungleの持続性を保証することができる。 +Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合でできている。ノードは自身の子のリストと属性名、属性値を持ち、データベースのレコードに相応する。通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。Jungleでは、子供からの親へのポインタは持たないため、親から子への片方向の参照しかできない。通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。持続性のある分散ノードを用いることでJungleの持続性を保証することができる。 \section{Index} Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。よって、すべての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。既存の TreeMap では、一度 Index の複製を行い、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。その問題を解決するため、Java 上で関数型プログラミングを行えるライブラリである、 Functional Java の TreeMap を使用し、それを用いて Index 実装を行なった。この TreeMap は、 Jungle と同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行なった際、前の版と最大限データを共有した新しい TreeMap を作成する。Jungle との違いは、木の回転処理が入ることである。これにより複数の版すべてに対応した Index をサポートすることが可能になった。 @@ -114,7 +108,7 @@ \end{figure} \section{非破壊TreeMap} -　Jungle の Index は、Functional Java の非破壊 TreeMap を用いて実装を行なっている。しかし、Functional Java の TreeMap は、木の変更の手間が大きい、並列実行処理速度が落ちるなど、実用的な性能を持っていなかった。そのため、Jungleの性能も、TreeMap 部分がネックとなっていた。その問題を解決するため、 Jungle で使用する非破壊 TreeMap を作成した。TreeMap は、Red Black Tree のアルゴリズムを用いている。RedBlackTreeとは二分木探索の一つで、以下の条件を満たした木のことである。 +Jungle の Index は、Functional Java の非破壊 TreeMap を用いて実装を行なっている。しかし、Functional Java の TreeMap は、木の変更の手間が大きい、並列実行処理速度が落ちるなど、実用的な性能を持っていなかった。そのため、Jungleの性能も、TreeMap 部分がネックとなっていた。その問題を解決するため、 Jungle で使用する非破壊 TreeMap を作成した。TreeMap は、Red Black Tree のアルゴリズムを用いている。RedBlackTreeとは二分木探索の一つで、以下の条件を満たした木のことである。 \begin{itemize} \item 各ノードは赤か黒の色を持つ。 \item ルートノードは黒色である。 @@ -124,7 +118,7 @@ \end{itemize} %ここもうちょっとかく。 \section{Indexの差分Updateの実装} -　Jungleは木の編集を行う際に、編集を行うノードと、経路にあるノードの複製を行い新しい木構造を構築するため、 Index の中には、編集後の木には存在しない複製前のノードが残ってしまう。なので、 Index の差分 Update を行う際には、それらのノードを Index から削除して、新しく複製されたノードを Index に登録する必要がある。 +Jungleは木の編集を行う際に、編集を行うノードと、経路にあるノードの複製を行い新しい木構造を構築するため、 Index の中には、編集後の木には存在しない複製前のノードが残ってしまう。なので、 Index の差分 Update を行う際には、それらのノードを Index から削除して、新しく複製されたノードを Index に登録する必要がある。 　そのためには、編集を行なったノードを覚えておく必要がある。そこで、 Jungle Tree Editor 内に、編集を加えたノードを覚えておくためのリストを定義した。 Editor は木に編集を加えた際、リストに編集前のノードを保存する。そして、Commit 時にリストにあるノードを使って Index の中に残っている、編集後の木に存在しないノードを削除する。その後、新しく作られたノードを Index に登録して Update は終了する。 @@ -140,7 +134,7 @@ \item 2 - 4 をルートノードにたどり着くか、 ParentIndex から親を取得できなkなるまで続ける。 \item 1 - 5 をリストからノードが無くなるまで続ける。 \end{itemize} -　Parent Index に現在のノードが登録されていない場合は、現在のノードからルートまでの経路にあるノードはIndexから削除されているため、削除を終えて、リストに入っている次のノードの削除処理を行なっても構わない。 +Parent Index に現在のノードが登録されていない場合は、現在のノードからルートまでの経路にあるノードはIndexから削除されているため、削除を終えて、リストに入っている次のノードの削除処理を行なっても構わない。 \paragraph* {Indexへのノードの挿入} Index から不要なノードを削除した後は、木の編集時新しく作られたノードを Index に挿入する。ノードの挿入は、以下の手順で行われる。 @@ -155,7 +149,7 @@ \end{itemize} \section{Differential Jungle Treeの実装} -　 Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。そのため、木の編集の手間は、木構造の形によって異なる。特に線形の木は、全てのノードの複製を行うため、変更の手間がO(n)になってしまう。そこで、Jungleは、線形の木をO(1)で変更するPushPop の機能を持つ。PushPop とは、ルートノードの上に新しいルートノードを付け加える API である(図\ref{fig:PushPopDemerit} )。すると、木の複製を行う必要が無いため、木の変更の手間がO(1)でノードの追加を行える。 +Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。そのため、木の編集の手間は、木構造の形によって異なる。特に線形の木は、全てのノードの複製を行うため、変更の手間がO(n)になってしまう。そこで、Jungleは、線形の木をO(1)で変更するPushPop の機能を持つ。PushPop とは、ルートノードの上に新しいルートノードを付け加える API である(図\ref{fig:PushPopDemerit} )。すると、木の複製を行う必要が無いため、木の変更の手間がO(1)でノードの追加を行える。 \begin{figure}[ht] \begin{center} \includegraphics[width=70mm]{./pic/PushPopDemerit.pdf} @@ -163,13 +157,13 @@ \caption{PushPop} \label{fig:PushPopDemerit} \end{figure} -　しかし、PushPopはルートノードを追加していくため、図\ref{fig:PushPopDemerit} のようにノードの並びが逆順になってしまう。Logなどの正順の木でなければデータを表現できない場合、木の編集時PushPop を使用できない。そこで、木の編集の手間を O(1) で、正順の木を構築できるDifferential Jungle Tree の実装を行なった。 Differential Jungle Tree は。木のバージョンごとに、自身の木の最後尾を表す末尾ノードを保持する。木の編集は、別途構築したSub Tree に対して破壊的に更新を行い、Commit 時に末尾のノードに Sub Tree を Append することで行う。この場合は木が破壊的に変更されているように見えるが、前の版の末端部分を超えてアクセスすることがなければ複数の版を同時に使用することができる。 +しかし、PushPopはルートノードを追加していくため、(図\ref{fig:PushPopDemerit} )のようにノードの並びが逆順になってしまう。Logなどの正順の木でなければデータを表現できない場合、木の編集時PushPop を使用できない。そこで、木の編集の手間を O(1) で、正順の木を構築できるDifferential Jungle Tree の実装を行なった。 Differential Jungle Tree は。木のバージョンごとに、自身の木の最後尾を表す末尾ノードを保持する。木の編集は、別途構築したSub Tree に対して破壊的に更新を行い、Commit 時に末尾のノードに Sub Tree を Append することで行う。この場合は木が破壊的に変更されているように見えるが、前の版の末端部分を超えてアクセスすることがなければ複数の版を同時に使用することができる。 \paragraph* {Differential Tree Context} -　Jungleの木はTreeContext というオブジェクトに自身の木の情報を保持している。Differential Jungle Tree では、現在の版の木構造の末尾ノードを保持することが可能な Differential Tree Context を作成した。 +Jungleの木はTreeContext というオブジェクトに自身の木の情報を保持している。Differential Jungle Tree では、現在の版の木構造の末尾ノードを保持することが可能な Differential Tree Context を作成した。 \paragraph* {Differential Jungle Tree の作成} - Differential Jungle Tree を作成するためにJungle に、新しいAPIを実装した。表(\ref{table:Differential API}) + Differential Jungle Tree を作成するためにJungle に、新しいAPIを実装した。(表\ref{table:Differential API}) \begin{table}[htb] \begin{center} @@ -184,12 +178,12 @@ \paragraph* {末尾ノードを使用した木の編集} -　Differential Jungle Tree の木の編集は、Differential Jungle Tree Editor を使用して行う。 Differential Jungle Tree Editor は、Default Jungle Tree Editor と違い、生成時に新しい木構造(Sub Tree)を自身の中に構築する。そして、木の編集は、Editor が保持している木構造に対して行う。編集後、Commit を行う際に構築した木構造を、 Differential Jungle Tree の末尾ノードにAppend する。その際木の複製は行わない。 -　また、Differential Tree は自身が保持している木構造に対する変更しか行えないため、一度Commit した木に対して変更は行えない。図\ref{fig:EditDifferencialTree} +Differential Jungle Tree の木の編集は、Differential Jungle Tree Editor を使用して行う。 Differential Jungle Tree Editor は、Default Jungle Tree Editor と違い、生成時に新しい木構造(Sub Tree)を自身の中に構築する。そして、木の編集は、Editor が保持している木構造に対して行う。編集後、Commit を行う際に構築した木構造を、 Differential Jungle Tree の末尾ノードにAppend する。その際木の複製は行わない。 +　また、Differential Tree は自身が保持している木構造に対する変更しか行えないため、一度Commit した木に対して変更は行えない。(図\ref{fig:EditDifferencialTree}) \begin{figure}[ht] \begin{center} - \includegraphics[width=70mm]{./pic/EditDifferencialTree.pdf} + \includegraphics[width=80mm]{./pic/EditDifferencialTree.pdf} \end{center} \caption{末尾ノードを使用した木の編集} \label{fig:EditDifferencialTree} @@ -203,7 +197,7 @@ 　Editor が保持している木構造に最後に追加したノードが、新しい木の末尾ノードとなる。また、Differential Jungle Tree は、木の編集時複製を行わないため、 Index のアップデートは、 Editor が保持している木構造のデータを Index に追加するだけで良い。 \paragraph* {Differential Jungle Tree の検索} - 　Differential Jungle Tree は、末尾ノードを使って、現在の木構造を表現している。なので、過去の木に対して全探索を行なった場合、その版には無いはずのノードが取得できてしまう。例として、編集前の木である Tree ver1 と編集後の木である Tree ver2 があるとする(図\ref{fig:Differential_Interface_Traverser})。ここで、Tree ver1 に対して、全探索を行なった場合、本来Tree ver1 に存在しないノード3・４も検索対象に含まれてしまう。そこで、その版の木が持つ末尾ノード以下のSub Tree を検索対象から除外する、Differential Interface Traverser を実装した。Differential Interface Traverserを用いて木の全探索を行なった場合、Tree ver1 に存在しないノード３・４は検索対象から省かれる。 + Differential Jungle Tree は、末尾ノードを使って、現在の木構造を表現している。なので、過去の木に対して全探索を行なった場合、その版には無いはずのノードが取得できてしまう。例として、編集前の木である Tree ver1 と編集後の木である Tree ver2 があるとする(図\ref{fig:Differential_Interface_Traverser})。ここで、Tree ver1 に対して、全探索を行なった場合、本来Tree ver1 に存在しないノード3・４も検索対象に含まれてしまう。そこで、その版の木が持つ末尾ノード以下のSub Tree を検索対象から除外する、Differential Interface Traverser を実装した。Differential Interface Traverserを用いて木の全探索を行なった場合、Tree ver1 に存在しないノード３・４は検索対象から省かれる。 \begin{figure}[ht] \begin{center} @@ -215,11 +209,8 @@ 　Index を使用した検索を行う場合、各版の木に対応した Index があるため、Default Tree と検索のアルゴリズムは変わらない。これらの実装により Differential Jungle Tree は木構造の構築・検索を行う。 \paragraph* {Differential Jungle Tree の検索} - 　Differential Jungle Tree への Commit は、編集後の木のデータを持つ TreeContext を作り、編集前の木が持つ TreeContext と Atomic に入れ替えることで行われる。しかし、Differential Jungle Tree のCommit は、Default Jungle Tree の Commit と異なり、TreeContext の入れ替えと、 Editor が保持している木構造の末尾ノードへの Append の２つのプロセスからなる。 TreeContext の入れ替えに関しては、 Default Jungle Tree と同じように行い、末尾ノードへの Editor が持っている木構造の Append は、TreeContect の入れ替えが成功した後に行う。そうすることで、別Thread で行われている Commit と競合した際に、 TreeContext を入れ替えた Thread と別 Thread がAppend を行い、木の整合性が崩れることを回避している。 - 　また、過去の版の木に対して、編集を加えCommit を行なった場合、木の整合性が崩れてしまう問題もある。図(\ref{fig:Differential_Interface_Traverser})(\ref{fig:Tree_ver2})を例に解説する。図（）の過去の版の木 Tree ver1 に新しいノード５を追加・Commit を行うと、新しい木 Tree ver'2 が構築される。ここで、Tree ver'2 に対して全検索を行う。differential Jungle Tree に対する全検索は、末尾ノードよ上にあるノードを検索対象にする。しかしノード３・４という、本来存在しないはずのノードが検索対象に含まれてしまう。これは、過去の版の木である、 tree ver1 の末尾ノードが２つの子ノードを持っているせいで発生する。 - 　この問題を解決するために、Differential Jungle Tree では、過去の木に対する変更を禁止している。具体的には。末尾ノードは子を１つしか持つことができないようにした。そうすることで木の整合性を保証している。 - - + Differential Jungle Tree への Commit は、編集後の木のデータを持つ TreeContext を作り、編集前の木が持つ TreeContext と Atomic に入れ替えることで行われる。しかし、Differential Jungle Tree のCommit は、Default Jungle Tree の Commit と異なり、TreeContext の入れ替えと、 Editor が保持している木構造の末尾ノードへの Append の２つのプロセスからなる。 TreeContext の入れ替えに関しては、 Default Jungle Tree と同じように行い、末尾ノードへの Editor が持っている木構造の Append は、TreeContect の入れ替えが成功した後に行う。そうすることで、別Thread で行われている Commit と競合した際に、 TreeContext を入れ替えた Thread と別 Thread がAppend を行い、木の整合性が崩れることを回避している。また、過去の版の木に対して、編集を加えCommit を行なった場合、木の整合性が崩れてしまう問題もある。(図\ref{fig:Differential_Interface_Traverser})(\ref{fig:Tree_ver2})を例に解説する。（図\ref{fig:Differential_Interface_Traverser}）の過去の版の木 Tree ver1 に新しいノード５を追加・Commit を行うと、新しい木 Tree ver'2 が構築される。ここで、Tree ver'2 に対して全検索を行う。differential Jungle Tree に対する全検索は、末尾ノードよ上にあるノードを検索対象にする。しかしノード３・４という、本来存在しないはずのノードが検索対象に含まれてしまう。これは、過去の版の木である、 tree ver1 の末尾ノードが２つの子ノードを持っているせいで発生する。この問題を解決するために、Differential Jungle Tree では、過去の木に対する変更を禁止している。具体的には。末尾ノードは子を１つしか持つことができないようにした。そうすることで木の整合性を保証している。 + \begin{figure}[ht] \begin{center} @@ -230,10 +221,10 @@ \end{figure} \section{Red Black Jungle Tree の実装} -　Jungle は木に編集を加えた際、ルートから編集を行う位置までのノードをコピーする。その為、木の編集の手間は木の大きさにも依存している。バランスの取れた木構造を構築することで、編集の手間をO(log n)にすることは可能だが、Default Jungle Tree の場合、ユーザーがPath を用いて、バランスを取りながら木を構築する必要がある。しかし、ユーザーが全ての木構造の形を把握し、バランスの取れた木を構築するのは困難である。そこで、自動で木のバランスを取り、最適な形の木構造を構築する機能を持つ Red Black Jungle Tree を実装した。バランスは、木の生成時に特定の Balance Key を決定し、それを使って行う。木のバランスを取るアルゴリズムは、前述した非破壊 TreeMap と同じものを使用する。しかし、木の編集を加えた際、木がどのようにバランスを取るか予想するのは困難であるため、木構造自体がデータを表現していない場合に限る。また、自身の木構造が、Balance Key を使った Index と同じ働きを持つため、木のCommit 時に別途 Index を構築する必要が無い、といったメリットもある。 +Jungle は木に編集を加えた際、ルートから編集を行う位置までのノードをコピーする。その為、木の編集の手間は木の大きさにも依存している。バランスの取れた木構造を構築することで、編集の手間をO(log n)にすることは可能だが、Default Jungle Tree の場合、ユーザーがPath を用いて、バランスを取りながら木を構築する必要がある。しかし、ユーザーが全ての木構造の形を把握し、バランスの取れた木を構築するのは困難である。そこで、自動で木のバランスを取り、最適な形の木構造を構築する機能を持つ Red Black Jungle Tree を実装した。バランスは、木の生成時に特定の Balance Key を決定し、それを使って行う。木のバランスを取るアルゴリズムは、前述した非破壊 TreeMap と同じものを使用する。しかし、木の編集を加えた際、木がどのようにバランスを取るか予想するのは困難であるため、木構造自体がデータを表現していない場合に限る。また、自身の木構造が、Balance Key を使った Index と同じ働きを持つため、木のCommit 時に別途 Index を構築する必要が無い、といったメリットもある。 \paragraph* {Red Black Jungle Tree の作成} - Red Black Jungle Tree を作成するため、Jungle に新しいAPIを実装した。(表) + Red Black Jungle Tree を作成するため、Jungle に新しいAPIを実装した。(表\ref{table:Diffetential API}) \begin{table}[htb] \begin{center} @@ -247,8 +238,7 @@ \end{table} \paragraph* { NodePath の拡張} - Red Black Jungle Tree は、ノードを追加・削除するたびに木のバランスが行われ、各ノードの Path が変わってしまう。その為、数字を使った NodePath では、編集を加える際、編集対象のノードの Path -を毎回調べる必要がある。その問題を解決するために、NodePath を拡張した Red Black Tree Node Path を作成し、属性名 BalanceKey 属性値 value のペアでノードを指定できるようにした。 Red Black Jungle Node Path は、引数に String 型の BalanceKey と ByteBuffer 型の value を取る。 + Red Black Jungle Tree は、ノードを追加・削除するたびに木のバランスが行われ、各ノードの Path が変わってしまう。その為、数字を使った NodePath では、編集を加える際、編集対象のノードの Pathを毎回調べる必要がある。その問題を解決するために、NodePath を拡張した Red Black Tree Node Path を作成し、属性名 BalanceKey 属性値 value のペアでノードを指定できるようにした。 Red Black Jungle Node Path は、引数に String 型の BalanceKey と ByteBuffer 型の value を取る。 %サンプル要りますでしょうか Red Black Tree Node Path で指定できる属性名は、木の生成時に宣言した属性名しか使用できない。これは、Red Black Jungle Tree が木の生成時に宣言した属性名でソートされているからである。 @@ -264,9 +254,7 @@ \section{分散環境でのJungleDBの書き出し実験方法の提案} \section{まとめ} -　本研究では、始めに破壊的木構造データベースであるJungleについて説明を行い、次にJungleの性能を上げるために実装した点を挙げ、最後に分散環境での Jungle の書き出し実験の手法について述べた。 -　実装した点は、まず Jungle の Index の Update を高速化させるために、前の版の Index と値を共有しながら Update を行う、差分 Update の実装を行なった。次に、線形の木を正順で構築する際、木の変更の手間が O(n) になる問題を解決するために、 Differential Jungle Tree の実装をした。 Differential Jungle Tree は、自身の末尾のノードの情報を保持している。この末尾ノードを使用して、木の編集や検索を行う。次に、自動的に木のバランスを行い、最適な形の木構造を構築する Red Black Jungle Tree を実装した。 Red Black Jungle Tree は、自身が Index を構築する Default Jungle Tree により、編集できる。また、ノードは、木のバランスによって Path が編集ごとに変わってしまうため、属性名と属性値のペアでノードを指定できる、 Red Black Jungle Tree Editor の実装を行なった。 -　今後の課題として、Jungleは非破壊でデータを保持し続けるため、非常に多くのメモリを使用してしまう。ある程度の単位で過去のデータの掃除を行いたい。Jungleは、過去の木に対するアクセスをサポートしているため、データの掃除を行うタイミングが明確ではない。なので、メモリから追い出すタイミングを定義する必要がある。%また、Jungleのパフォーマンスを出すために、データを最適化する必要がある。最適な木構造はアプリケーションによって違うため、Jungleの設計手法を確立させる必要がある。 +　本研究では、始めに破壊的木構造データベースであるJungleについて説明を行い、次にJungleの性能を上げるために実装した点を挙げ、最後に分散環境での Jungle の書き出し実験の手法について述べた。実装した点は、まず Jungle の Index の Update を高速化させるために、前の版の Index と値を共有しながら Update を行う、差分 Update の実装を行なった。次に、線形の木を正順で構築する際、木の変更の手間が O(n) になる問題を解決するために、 Differential Jungle Tree の実装をした。 Differential Jungle Tree は、自身の末尾のノードの情報を保持している。この末尾ノードを使用して、木の編集や検索を行う。次に、自動的に木のバランスを行い、最適な形の木構造を構築する Red Black Jungle Tree を実装した。 Red Black Jungle Tree は、自身が Index を構築する Default Jungle Tree により、編集できる。また、ノードは、木のバランスによって Path が編集ごとに変わってしまうため、属性名と属性値のペアでノードを指定できる、 Red Black Jungle Tree Editor の実装を行なった。今後の課題として、Jungleは非破壊でデータを保持し続けるため、非常に多くのメモリを使用してしまう。ある程度の単位で過去のデータの掃除を行いたい。Jungleは、過去の木に対するアクセスをサポートしているため、データの掃除を行うタイミングが明確ではない。なので、メモリから追い出すタイミングを定義する必要がある。%また、Jungleのパフォーマンスを出すために、データを最適化する必要がある。最適な木構造はアプリケーションによって違うため、Jungleの設計手法を確立させる必要がある。 %参考文献