Mercurial > hg > Papers > 2017 > suruga-sigos

comparison paper/sigos.tex @ 3:07a31c08d082

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add sigos_ver1_pdf
author suruga
date Thu, 20 Apr 2017 21:46:39 +0900
parents 66a48dc3b319
children 0c8bb16afb8d
comparison
equal deleted inserted replaced
2:66a48dc3b319 3:07a31c08d082
87 87
88 % Introduce 88 % Introduce
89 \section{研究目的と背景} 89 \section{研究目的と背景}
90 90
91 \section{非破壊的木構造データベースJungle} 91 \section{非破壊的木構造データベースJungle}
92 Jungleは、当研究室で開発を行っている非破壊的木構造データベースで、Javaを用いて実装されている。非破壊的木構造とは、データの編集を一度生成した木を上書きせず、ルートから編集を行う位置までのノードをコピーする特徴を持つ（図\ref{fig:non_destructive_tree} ）。これにより、読み込み中にデータが変更されないことが保証されているため、書き込みと読み込みを同時に行うことできる。 92 Jungleは、当研究室で開発を行っている非破壊的木構造データベースで、Javaを用いて実装さ
93 れている。非破壊的木構造とは、データの編集を一度生成した木を上書きせず、ルートから編集を行う位置までのノードをコピーする特徴を持つ（図\ref{fig:non_destructive_tree} ）。これにより、読み込み中にデータが変更されないことが保証されているため、書き込みと読み込みを同時に行うことできる。
93 %木のルートをAtomicに置き換えることで、木のアップデートを行う。変更前の木が残っているので、そのまま使用できる。変更されないノードは変更前と変更後のルートから共有されることになる。 94 %木のルートをAtomicに置き換えることで、木のアップデートを行う。変更前の木が残っているので、そのまま使用できる。変更されないノードは変更前と変更後のルートから共有されることになる。
94 \begin{figure}[ht] 95 \begin{figure}[ht]
95 \begin{center} 96 \begin{center}
96 \includegraphics[width=80mm]{./pic/non_destructive_tree.pdf} 97 \includegraphics[width=80mm]{./pic/non_destructive_tree.pdf}
97 \end{center} 98 \end{center}
98 \caption{非破壊的木構造の編集} 99 \caption{非破壊的木構造の編集}
99 \label{fig:persistent_data_tree} 100 \label{fig:persistent_data_tree}
100 \end{figure} 101 \end{figure}
101 Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合でできている。ノードは自身の子のリストと属性名、属性値を持ち、データベースのレコードに相応する。通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。Jungleでは、子供からの親へのポインタは持たないため、親から子への片方向の参照しかできない。 102 　Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合でできている。ノードは自身の子のリストと属性名、属性値を持ち、データベースのレコードに相応する。通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。Jungleでは、子供からの親へのポインタは持たないため、親から子への片方向の参照しかできない。
102 　通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。 103 　通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。
103 　Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。持続性のある分散ノードを用いることでJungleの持続性を保証することができる。 104 　Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。持続性のある分散ノードを用いることでJungleの持続性を保証することができる。
104 105
105 \section{Index} 106 \section{Index}
106 　Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。よって、すべての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。既存の TreeMap では、一度 Index の複製を行い、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。その問題を解決するため、Java 上で関数型プログラミングを行えるライブラリである、 Functional Java の TreeMap を使用し、それを用いて Index 実装を行なった。この TreeMap は、 Jungle と同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行なった際、前の版と最大限データを共有した新しい TreeMap を作成する。Jungle との違いは、木の回転処理が入ることである。これにより複数の版すべてに対応した Index をサポートすることが可能になった。 107 　Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。よって、すべての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。既存の TreeMap では、一度 Index の複製を行い、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。その問題を解決するため、Java 上で関数型プログラミングを行えるライブラリである、 Functional Java の TreeMap を使用し、それを用いて Index 実装を行なった。この TreeMap は、 Jungle と同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行なった際、前の版と最大限データを共有した新しい TreeMap を作成する。Jungle との違いは、木の回転処理が入ることである。これにより複数の版すべてに対応した Index をサポートすることが可能になった。
107 \section{非破壊TreeMap} 108 \section{非破壊TreeMap}
108 　Jungle の Index は、Functional Java の非破壊 TreeMap を用いて実装を行なっている。しかし、Functional Java の TreeMap は、木の変更の手間が大きい、並列実行処理速度が落ちるなど、実用的な性能を持っていなかった。そのため、Jungleの性能も、TreeMap 部分がネックとなっていた。その問題を解決するため、 Jungle で使用する非破壊 TreeMap を作成した。TreeMap は、Red Black Tree のアルゴリズムを用いている。RedBlackTreeとは二分木探索の一つで、以下の条件を満たした木のことである。 109 　Jungle の Index は、Functional Java の非破壊 TreeMap を用いて実装を行なっている。しかし、Functional Java の TreeMap は、木の変更の手間が大きい、並列実行処理速度が落ちるなど、実用的な性能を持っていなかった。そのため、Jungleの性能も、TreeMap 部分がネックとなっていた。その問題を解決するため、 Jungle で使用する非破壊 TreeMap を作成した。TreeMap は、Red Black Tree のアルゴリズムを用いている。RedBlackTreeとは二分木探索の一つで、以下の条件を満たした木のことである。
144 \item 自身の子ノードを取得したノードとして２に戻る。 145 \item 自身の子ノードを取得したノードとして２に戻る。
145 \item 全てのノードを登録したら終了する。 146 \item 全てのノードを登録したら終了する。
146 \end{itemize} 147 \end{itemize}
147 148
148 \section{Differential Jungle Treeの実装} 149 \section{Differential Jungle Treeの実装}
149 Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。そのため、木の編集の手間は、木構造の形によって異なる。特に線形の木は、全てのノードの複製を行うため、変更の手間がO(n)になってしまう。そこで、Jungleは、線形の木をO(1)で変更するPushPop の機能を持つ。PushPop とは、ルートノードの上に新しいルートノードを付け加える API である(図\ref{fig:PushPopDemerit} )。すると、木の複製を行う必要が無いため、木の変更の手間がO(1)でノードの追加を行える。 150 　 Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。そのため、木の編集の手間は、木構造の形によって異なる。特に線形の木は、全てのノードの複製を行うため、変更の手間がO(n)になってしまう。そこで、Jungleは、線形の木をO(1)で変更するPushPop の機能を持つ。PushPop とは、ルートノードの上に新しいルートノードを付け加える API である(図\ref{fig:PushPopDemerit} )。すると、木の複製を行う必要が無いため、木の変更の手間がO(1)でノードの追加を行える。
150 \begin{figure}[ht] 151 \begin{figure}[ht]
151 \begin{center} 152 \begin{center}
152 \includegraphics[width=70mm]{./pic/PushPopDemerit.pdf} 153 \includegraphics[width=70mm]{./pic/PushPopDemerit.pdf}
153 \end{center} 154 \end{center}
154 \caption{PushPop} 155 \caption{PushPop}
155 \label{fig:PushPopDemerit} 156 \label{fig:PushPopDemerit}
156 \end{figure} 157 \end{figure}
157 しかし、PushPopはルートノードを追加していくため、図\ref{fig:PushPopDemerit} のようにノードの並びが逆順になってしまう。Logなどの正順の木でなければデータを表現できない場合、木の編集時PushPop を使用できない。そこで、木の編集の手間を O(1) で、正順の木を構築できるDifferential Jungle Tree の実装を行なった。 Differential Jungle Tree は。木のバージョンごとに、自身の木の最後尾を表す末尾ノードを保持する。木の編集は、別途構築したSub Tree に対して破壊的に更新を行い、Commit 時に末尾のノードに Sub Tree を Append することで行う。この場合は木が破壊的に変更されているように見えるが、前の版の末端部分を超えてアクセスすることがなければ複数の版を同時に使用することができる。 158 　しかし、PushPopはルートノードを追加していくため、図\ref{fig:PushPopDemerit} のようにノードの並びが逆順になってしまう。Logなどの正順の木でなければデータを表現できない場合、木の編集時PushPop を使用できない。そこで、木の編集の手間を O(1) で、正順の木を構築できるDifferential Jungle Tree の実装を行なった。 Differential Jungle Tree は。木のバージョンごとに、自身の木の最後尾を表す末尾ノードを保持する。木の編集は、別途構築したSub Tree に対して破壊的に更新を行い、Commit 時に末尾のノードに Sub Tree を Append することで行う。この場合は木が破壊的に変更されているように見えるが、前の版の末端部分を超えてアクセスすることがなければ複数の版を同時に使用することができる。
158 159
159 \paragraph* {Differential Tree Context} 160 \paragraph* {Differential Tree Context}
160 Jungleの木はTreeContext というオブジェクトに自身の木の情報を保持している。Differential Jungle Tree では、現在の版の木構造の末尾ノードを保持することが可能な Differential Tree Context を作成した。 161 　Jungleの木はTreeContext というオブジェクトに自身の木の情報を保持している。Differential Jungle Tree では、現在の版の木構造の末尾ノードを保持することが可能な Differential Tree Context を作成した。
161 162
162 \paragraph* {Differential Jungle Tree の作成} 163 \paragraph* {Differential Jungle Tree の作成}
163 Differential Jungle Tree を作成するためにJungle に、新しいAPIを実装した。(表\ref{table:Differential API}) 164 Differential Jungle Tree を作成するためにJungle に、新しいAPIを実装した。表(\ref{table:Differential API})
164 165
165 \begin{table}[ht] 166 \begin{table}[ht]
166 \begin{center} 167 \begin{center}
167 \small 168 \small
168 \begin{tabular}[htpb]{|c||c|c|c|} 169 \begin{tabular}[htpb]{|c||c|c|c|}