|
1
|
1 \documentclass[techrep]{ipsjpapers}
|
|
|
2 \usepackage[dvipdfmx]{graphicx}
|
|
|
3 \usepackage{url}
|
|
|
4 \usepackage{listings,jlisting}
|
|
|
5 \usepackage{enumitem}
|
|
|
6
|
|
|
7
|
|
|
8 \lstset{
|
|
|
9 language=C,
|
|
|
10 tabsize=2,
|
|
|
11 frame=single,
|
|
|
12 basicstyle={\ttfamily\footnotesize},%
|
|
|
13 identifierstyle={\footnotesize},%
|
|
|
14 commentstyle={\footnotesize\itshape},%
|
|
|
15 keywordstyle={\footnotesize\bfseries},%
|
|
|
16 ndkeywordstyle={\footnotesize},%
|
|
|
17 stringstyle={\footnotesize\ttfamily},
|
|
|
18 breaklines=true,
|
|
|
19 captionpos=b,
|
|
|
20 columns=[l]{fullflexible},%
|
|
|
21 xrightmargin=0zw,%
|
|
|
22 xleftmargin=1zw,%
|
|
|
23 aboveskip=1zw,
|
|
|
24 numberstyle={\scriptsize},%
|
|
|
25 stepnumber=1,
|
|
|
26 numbersep=0.5zw,%
|
|
|
27 lineskip=-0.5ex,
|
|
|
28 }
|
|
|
29 \renewcommand{\lstlistingname}{Code}
|
|
|
30
|
|
|
31 \input{dummy.tex} %% Font
|
|
|
32
|
|
|
33 % ユーザが定義したマクロなど．
|
|
|
34 \makeatletter
|
|
|
35
|
|
|
36 \begin{document}
|
|
|
37
|
|
|
38 % 和文表題
|
|
10
|
39 \title{非破壊木構造データベース Jungle のサービス利用法にそった改良}
|
|
1
|
40 % 英文表題
|
|
|
41 \etitle{}
|
|
|
42
|
|
|
43 % 所属ラベルの定義
|
|
|
44 \affilabel{1}{琉球大学大学院理工学研究科情報工学専攻 \\Interdisciplinary Information Engineering, Graduate School of Engineering and Science, University of the Ryukyus.}
|
|
|
45 \affilabel{2}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}
|
|
|
46
|
|
|
47 % 和文著者名
|
|
|
48 \author{
|
|
8
|
49 仲松 栞\affiref{2}
|
|
1
|
50 \and
|
|
8
|
51 照屋 のぞみ \affiref{1}
|
|
1
|
52 \and
|
|
8
|
53 河野 真治\affiref{1}
|
|
1
|
54 }
|
|
|
55
|
|
|
56 % 英文著者名
|
|
|
57 \eauthor{
|
|
|
58 Nakamatsu Shiori\affiref{1}
|
|
|
59 \and
|
|
8
|
60 Teruya Nozomi\affiref{2}
|
|
1
|
61 \and
|
|
|
62 Shinji KONO\affiref{2}
|
|
|
63 }
|
|
|
64
|
|
|
65 % 連絡先（投稿時に必要．製版用では無視される．）
|
|
|
66 \contact{仲松 栞\\
|
|
|
67 〒903-0213 沖縄県西原町千原1番地\\
|
|
|
68 琉球大学工学部情報工学科\\
|
|
|
69 TEL: (098)895-2221\qquad FAX: (098)895-8727\\
|
|
|
70 email: innparusu@cr.ie.u-ryukyu.ac.jp}
|
|
|
71
|
|
|
72 % 和文概要
|
|
|
73 \begin{abstract}
|
|
13
|
74 現代のインターネットやアプリケーションで使われるデータは、複雑な構造を持っており、RDBの第一正規系には納まらないようになってきている。
|
|
|
75 また、RDBでは、編集中にロックがかけられ、複雑な構造に対する変更に向いていない。
|
|
|
76 これらの問題は、不定形のデータ構造とRDBの表構造のミスマッチである。
|
|
|
77 これをDBのインピーダンスミスマッチと言うことがある。
|
|
|
78 そこで当研究室では、非破壊的木構造データベースJungleを開発している。
|
|
|
79 Jungleでは、不定形のデータ構造を、直接木構造として格納することができる。
|
|
|
80 木構造の変更は、過去の版を保存する非破壊で行われ、木のルートをAtomicに入れ替える操作がトランザクションになる。
|
|
|
81 これにより、複雑な構造をDBとして素直に取り扱うことができる。
|
|
|
82 木構造の変更は、木の形に依存している。
|
|
|
83 サービスやアプリケーションに適した木の形があり、それに対応した木の変更方法を採用する必要がある。
|
|
|
84 本研究ではJungleの木と Index の編集機能の改善を行う。
|
|
|
85 直線的なリスト構造に適したPush/Popと差分リストを提案し、実装と評価を行なった。
|
|
|
86 巨大な木が必要な場合は、木を特定のKeyを用いてbalanceさせることにより、変更をO(log n)にすることができる。
|
|
|
87 Jungleは分散構造を取ることもできる。
|
|
|
88 複数の木を複数の分散したJungleノード間で通信することにより、Jungleをスケールさせる。
|
|
|
89 Jungleの木の変更Logを当研究室で開発した分散フレームワークAliceを用いて通信する。
|
|
|
90 それぞれの木は、ルートノードに集約され、集約の過程で、競合する変更のMergeを行う。
|
|
|
91 分散Jungleの性能を測定する手法について述べる。
|
|
1
|
92 \end{abstract}
|
|
|
93
|
|
|
94 % 表題などの出力
|
|
|
95 \maketitle
|
|
|
96
|
|
|
97 % 本文はここから始まる
|
|
|
98
|
|
|
99 % Introduce
|
|
10
|
100 \section{サービス利用に適したデータベース}
|
|
13
|
101 データのネスト構造を許さない第一正規系を要求するRDBの表構造は、Jsonなどの不定形のデータ構造とミスマッチを起こしてしまうという問題がある。
|
|
|
102 この問題はデータベースのインピーダンスミスマッチと呼ばれている。
|
|
|
103 不定形の構造の変更をトランザクションとしてJsonの一括変更という形で処理する方法が考えられるが、並列処理が中心となってきている今のアプリケーションには向いているとは言えない。
|
|
|
104 これらの問題を解決するため、当研究室では、分散処理環境で動くことができるデータベースを目指して非破壊的木構造データベースJungleを開発している。
|
|
|
105 木構造を扱えることによって、従来のRDBとは異なり、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。
|
|
|
106 また、その木をそのままデータベースとして使用することも可能である。
|
|
|
107 非破壊的木構造とは、データの元の木を直接書き換えずに保存し、新しく構築した木のデータ構造を編集する方法である。
|
|
|
108 これにより、データの書き込み中であっても、元のデータは変更されない為、読み込みも同時に行うことができる。
|
|
|
109 Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。
|
|
|
110 また、Index の構築も大幅なネックとなっていた。
|
|
|
111 そこで、本研究ではJungleの木と Index の編集機能の改善を行う。
|
|
|
112 また、分散環境におけるJungleの書き出し速度の測定方法の提案をする。
|
|
1
|
113 \section{非破壊的木構造データベースJungle}
|
|
5
|
114 Jungleは、当研究室で開発を行っている非破壊的木構造データベースで、Javaを用いて実装されている。非破壊的木構造とは、データの編集を一度生成した木を上書きせず、ルートから編集を行う位置までのノードをコピーする特徴を持つ（図\ref{fig:non_destructive_tree} ）。これにより、読み込み中にデータが変更されないことが保証されているため、書き込みと読み込みを同時に行うことできる。
|
|
2
|
115 %木のルートをAtomicに置き換えることで、木のアップデートを行う。変更前の木が残っているので、そのまま使用できる。変更されないノードは変更前と変更後のルートから共有されることになる。
|
|
3
|
116 \begin{figure}[ht]
|
|
5
|
117 \begin{center}
|
|
8
|
118 \includegraphics[width=70mm]{./pic/non_destructive_tree.pdf}
|
|
5
|
119 \end{center}
|
|
2
|
120 \caption{非破壊的木構造の編集}
|
|
5
|
121 \label{fig:non_destructive_tree}
|
|
3
|
122 \end{figure}
|
|
12
|
123 Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合でできている。ノードは自身の子のリストと属性名、属性値を持ち、データベースのレコードに相応する。通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。また、親と子相互で参照しあうことができる破壊的木構造データベースとは違い、非破壊的木構造であるJungleは、親から子への片方向の参照しかできない。通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。持続性のある分散ノードを用いることでJungleの持続性を保証することができる。
|
|
10
|
124
|
|
|
125 \section{Jungleの構成要素}
|
|
12
|
126
|
|
10
|
127 \subsection*{[NodePath]}
|
|
5
|
128 Jungle では、木のノードの位置を NodePath クラスを使って表す。 NodePath クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。 NodePath クラスを用いて \textless -1,0,2,3 \textgreater を表している際の例を(図\ref{fig:nodepath})に示す。
|
|
|
129
|
|
|
130 \begin{figure}[htpb]
|
|
|
131 \begin{center}
|
|
|
132 \includegraphics[width=60mm]{./pic/nodepath.pdf}
|
|
|
133 \end{center}
|
|
|
134 \caption{NodePath}
|
|
|
135 \label{fig:nodepath}
|
|
|
136 \end{figure}
|
|
12
|
137
|
|
|
138 \subsection*{[Index]}
|
|
|
139 Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。よって、すべての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。既存の TreeMap では、一度 Index の複製を行い、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。その問題を解決するため、Java 上で関数型プログラミングを行えるライブラリである、 Functional Java の TreeMap を使用し、それを用いてIndexは実装されている。この TreeMap は、 Jungle と同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行なった際、前の版と最大限データを共有した新しい TreeMap を作成する。JungleでIndexを実装した場合と違いは、木の回転処理が入るという点である。これにより複数の版すべてに対応した Index をサポートすることが可能になった。
|
|
10
|
140 \subsection*{[非破壊TreeMap]}
|
|
8
|
141 Jungle の Index は、Functional Java の非破壊 TreeMap を用いて実装を行なっている。しかし、Functional Java の TreeMap は、木の変更の手間が大きい、並列実行処理速度が落ちるなど、実用的な性能を持っていなかった。そのため、Jungleの性能も、TreeMap 部分がネックとなっていた。その問題を解決するため、 Jungle で使用する非破壊 TreeMap を作成した。TreeMap は、Red Black Tree のアルゴリズムを用いている。RedBlackTreeとは二分木探索の一つで、以下の条件を満たした木のことである。
|
|
2
|
142 \begin{itemize}
|
|
|
143 \item 各ノードは赤か黒の色を持つ。
|
|
|
144 \item ルートノードは黒色である。
|
|
|
145 \item 全ての葉は黒色である。
|
|
|
146 \item 赤いノードの子は黒色である。
|
|
|
147 \item 全ての葉からルートノードまでのパスには、同じ個数の黒いノードがある。
|
|
|
148 \end{itemize}
|
|
|
149 %ここもうちょっとかく。
|
|
|
150 \section{Indexの差分Updateの実装}
|
|
9
|
151 Jungleは木の編集を行う際に、編集を行うノードと、経路にあるノードの複製を行い新しい木構造を構築するため、 Index の中には、編集後の木には存在しない複製前のノードが残ってしまう。なので、 Index の差分 Update を行う際には、それらのノードを Index から削除して、新しく複製されたノードを Index に登録する必要がある。そのためには、編集を行なったノードを覚えておく必要がある。そこで、 Jungle Tree Editor 内に、編集を加えたノードを覚えておくためのリストを定義した。 Editor は木に編集を加えた際、リストに編集前のノードを保存する。そして、Commit 時にリストにあるノードを使って Index の中に残っている、編集後の木に存在しないノードを削除する。その後、新しく作られたノードを Index に登録して Update は終了する。
|
|
1
|
152
|
|
|
153
|
|
2
|
154 \paragraph* {編集前ののノードの削除}
|
|
|
155 ndex のUpdate を行う際、初めに、編集後の木に存在しないノードを Index から削除する。削
|
|
|
156 除の対象は、変更を加えたノードと、ルートから変更を加えたノードまでの経路にあるノード
|
|
|
157 である。ノードの削除は、以下の手順で行われる。
|
|
|
158 \begin{itemize}
|
|
|
159 \item 編集を行なったノードのリストからノードを取得する。
|
|
|
160 \item 取得したノードが、保持している値をIndex から削除する。
|
|
|
161 \item 自身と子供のペアを Parent Index から削除する。
|
|
|
162 \item ParentIndex から親を取得する。
|
|
|
163 \item 2 - 4 をルートノードにたどり着くか、 ParentIndex から親を取得できなkなるまで続ける。
|
|
|
164 \item 1 - 5 をリストからノードが無くなるまで続ける。
|
|
|
165 \end{itemize}
|
|
8
|
166 Parent Index に現在のノードが登録されていない場合は、現在のノードからルートまでの経路にあるノードはIndexから削除されているため、削除を終えて、リストに入っている次のノードの削除処理を行なっても構わない。
|
|
1
|
167
|
|
2
|
168 \paragraph* {Indexへのノードの挿入}
|
|
|
169 Index から不要なノードを削除した後は、木の編集時新しく作られたノードを Index に挿入する。ノードの挿入は、以下の手順で行われる。
|
|
|
170 \begin{itemize}
|
|
|
171 \item 木からルートノードを取得する
|
|
|
172 \item 取得したノードがIndex に登録されているかを調べる。
|
|
|
173 \item 登録されている場合、そのノード以下の Sub treeは、全てIndexに登録されているので、次のノードに移動する。
|
|
|
174 \item 登録されていなかった場合、自身が保持している値をIndex に登録する。
|
|
|
175 \item 自身と子ノードを Parent Index に登録する。
|
|
|
176 \item 自身の子ノードを取得したノードとして２に戻る。
|
|
|
177 \item 全てのノードを登録したら終了する。
|
|
|
178 \end{itemize}
|
|
|
179
|
|
|
180 \section{Differential Jungle Treeの実装}
|
|
8
|
181 Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。そのため、木の編集の手間は、木構造の形によって異なる。特に線形の木は、全てのノードの複製を行うため、変更の手間がO(n)になってしまう。そこで、Jungleは、線形の木をO(1)で変更するPushPop の機能を持つ。PushPop とは、ルートノードの上に新しいルートノードを付け加える API である(図\ref{fig:PushPopDemerit} )。すると、木の複製を行う必要が無いため、木の変更の手間がO(1)でノードの追加を行える。
|
|
2
|
182 \begin{figure}[ht]
|
|
|
183 \begin{center}
|
|
|
184 \includegraphics[width=70mm]{./pic/PushPopDemerit.pdf}
|
|
|
185 \end{center}
|
|
|
186 \caption{PushPop}
|
|
|
187 \label{fig:PushPopDemerit}
|
|
|
188 \end{figure}
|
|
8
|
189 しかし、PushPopはルートノードを追加していくため、(図\ref{fig:PushPopDemerit} )のようにノードの並びが逆順になってしまう。Logなどの正順の木でなければデータを表現できない場合、木の編集時PushPop を使用できない。そこで、木の編集の手間を O(1) で、正順の木を構築できるDifferential Jungle Tree の実装を行なった。 Differential Jungle Tree は。木のバージョンごとに、自身の木の最後尾を表す末尾ノードを保持する。木の編集は、別途構築したSub Tree に対して破壊的に更新を行い、Commit 時に末尾のノードに Sub Tree を Append することで行う。この場合は木が破壊的に変更されているように見えるが、前の版の末端部分を超えてアクセスすることがなければ複数の版を同時に使用することができる。
|
|
2
|
190
|
|
|
191 \paragraph* {Differential Tree Context}
|
|
8
|
192 Jungleの木はTreeContext というオブジェクトに自身の木の情報を保持している。Differential Jungle Tree では、現在の版の木構造の末尾ノードを保持することが可能な Differential Tree Context を作成した。
|
|
2
|
193
|
|
|
194 \paragraph* {Differential Jungle Tree の作成}
|
|
8
|
195 Differential Jungle Tree を作成するためにJungle に、新しいAPIを実装した。(表\ref{table:Differential API})
|
|
4
|
196
|
|
|
197 \begin{table}[htb]
|
|
|
198 \begin{center}
|
|
|
199 \caption{Jungleに新しく実装したAPI}
|
|
|
200 \begin{tabular}{|p{3cm}|p{4cm}|} \hline
|
|
|
201 \hline \shortstack{ createNewDifferenceTree\\ (StringtreeName)}& Jungleに新しくDifferential Jungle Treeを生成する。木の名前が重複した場合、生成に失敗し null を返す。\\
|
|
|
202 \hline
|
|
|
203 \end{tabular}
|
|
|
204 \label{table:Diffetential API}
|
|
|
205 \end{center}
|
|
|
206 \end{table}
|
|
|
207
|
|
|
208
|
|
2
|
209 \paragraph* {末尾ノードを使用した木の編集}
|
|
8
|
210 Differential Jungle Tree の木の編集は、Differential Jungle Tree Editor を使用して行う。 Differential Jungle Tree Editor は、Default Jungle Tree Editor と違い、生成時に新しい木構造(Sub Tree)を自身の中に構築する。そして、木の編集は、Editor が保持している木構造に対して行う。編集後、Commit を行う際に構築した木構造を、 Differential Jungle Tree の末尾ノードにAppend する。その際木の複製は行わない。
|
|
|
211 また、Differential Tree は自身が保持している木構造に対する変更しか行えないため、一度Commit した木に対して変更は行えない。(図\ref{fig:EditDifferencialTree})
|
|
2
|
212
|
|
1
|
213 \begin{figure}[ht]
|
|
|
214 \begin{center}
|
|
8
|
215 \includegraphics[width=80mm]{./pic/EditDifferencialTree.pdf}
|
|
1
|
216 \end{center}
|
|
2
|
217 \caption{末尾ノードを使用した木の編集}
|
|
|
218 \label{fig:EditDifferencialTree}
|
|
1
|
219 \end{figure}
|
|
|
220
|
|
2
|
221 \begin{itemize}
|
|
|
222 \item 木からgetJungleTreeEditor で Editor を取得する。（このとき Editor は新しい木構造(Sub Tree)を持つ）。
|
|
4
|
223 \item Editorが保持している木構造に対して addNewChild( \textless-1.0\textgreater)を実行し、ノードの追加を行う。
|
|
2
|
224 \item Commit を行い、Treeの末尾ノードにEditorが保持している木構造を Append する。
|
|
|
225 \end{itemize}
|
|
9
|
226 Editor が保持している木構造に最後に追加したノードが、新しい木の末尾ノードとなる。また、Differential Jungle Tree は、木の編集時複製を行わないため、 Index のアップデートは、 Editor が保持している木構造のデータを Index に追加するだけで良い。
|
|
2
|
227
|
|
|
228 \paragraph* {Differential Jungle Tree の検索}
|
|
8
|
229 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 に存在しないノード３・４は検索対象から省かれる。
|
|
7
|
230
|
|
2
|
231 \begin{figure}[ht]
|
|
|
232 \begin{center}
|
|
7
|
233 \includegraphics[width=60mm]{./pic/Differential_Interface_Traverser.pdf}
|
|
2
|
234 \end{center}
|
|
|
235 \caption{複数の版の木の表現}
|
|
7
|
236 \label{fig:Differential_Interface_Traverser}
|
|
2
|
237 \end{figure}
|
|
9
|
238 Index を使用した検索を行う場合、各版の木に対応した Index があるため、Default Tree と検索のアルゴリズムは変わらない。これらの実装により Differential Jungle Tree は木構造の構築・検索を行う。
|
|
2
|
239
|
|
|
240 \paragraph* {Differential Jungle Tree の検索}
|
|
8
|
241 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 では、過去の木に対する変更を禁止している。具体的には。末尾ノードは子を１つしか持つことができないようにした。そうすることで木の整合性を保証している。
|
|
|
242
|
|
7
|
243
|
|
2
|
244 \begin{figure}[ht]
|
|
|
245 \begin{center}
|
|
7
|
246 \includegraphics[width=50mm]{./pic/Tree_ver2.pdf}
|
|
2
|
247 \end{center}
|
|
|
248 \caption{木の整合性が崩れる例}
|
|
7
|
249 \label{fig:Tree_ver2}
|
|
2
|
250 \end{figure}
|
|
|
251
|
|
|
252 \section{Red Black Jungle Tree の実装}
|
|
8
|
253 Jungle は木に編集を加えた際、ルートから編集を行う位置までのノードをコピーする。その為、木の編集の手間は木の大きさにも依存している。バランスの取れた木構造を構築することで、編集の手間をO(log n)にすることは可能だが、Default Jungle Tree の場合、ユーザーがPath を用いて、バランスを取りながら木を構築する必要がある。しかし、ユーザーが全ての木構造の形を把握し、バランスの取れた木を構築するのは困難である。そこで、自動で木のバランスを取り、最適な形の木構造を構築する機能を持つ Red Black Jungle Tree を実装した。バランスは、木の生成時に特定の Balance Key を決定し、それを使って行う。木のバランスを取るアルゴリズムは、前述した非破壊 TreeMap と同じものを使用する。しかし、木の編集を加えた際、木がどのようにバランスを取るか予想するのは困難であるため、木構造自体がデータを表現していない場合に限る。また、自身の木構造が、Balance Key を使った Index と同じ働きを持つため、木のCommit 時に別途 Index を構築する必要が無い、といったメリットもある。
|
|
1
|
254
|
|
4
|
255 \paragraph* {Red Black Jungle Tree の作成}
|
|
8
|
256 Red Black Jungle Tree を作成するため、Jungle に新しいAPIを実装した。(表\ref{table:Diffetential API})
|
|
1
|
257
|
|
4
|
258 \begin{table}[htb]
|
|
|
259 \begin{center}
|
|
|
260 \caption{Jungleに新しく実装したAPI}
|
|
|
261 \begin{tabular}{|p{3cm}|p{4cm}|} \hline
|
|
|
262 \hline \shortstack{ createNewRedBlackTree\\ (StringtreeName, \\String balanceKey)}& Jungleに新しくRed Black Jungle Treeを生成する。第一引数に木の名前、第２引数に木のバランスを取る時に使用する Balance Key を受け取る。木の名前が重複した場合、生成に失敗し null を返す。\\
|
|
|
263 \hline
|
|
|
264 \end{tabular}
|
|
|
265 \label{table:Diffetential API}
|
|
|
266 \end{center}
|
|
|
267 \end{table}
|
|
1
|
268
|
|
4
|
269 \paragraph* { NodePath の拡張}
|
|
9
|
270 Red Black Jungle Tree は、ノードを追加・削除するたびに木のバランスが行われ、各ノードの Path が変わってしまう。その為、数
|
|
|
271 字を使った NodePath では、編集を加える際、編集対象のノードの Pathを毎回調べる必要がある。その問題を解決するためにNodePath を拡張した Red Black Tree Node Path を作成し、属性名 BalanceKey 属性値 value のペアでノードを指定できるようにした。 Red Black Jungle Node Path は、引数に String 型の BalanceKey と ByteBuffer 型の value を取る。
|
|
4
|
272 %サンプル要りますでしょうか
|
|
|
273 Red Black Tree Node Path で指定できる属性名は、木の生成時に宣言した属性名しか使用できない。これは、Red Black Jungle Tree が木の生成時に宣言した属性名でソートされているからである。
|
|
1
|
274
|
|
4
|
275 %\paragraph* { Red Black Jungle Tree の編集}
|
|
|
276 %Red Black Jungle Tree Editor は、既存の Jungle Tree Editor とくらべてAPIの使い方が異なる。以下にDefault Jungle Tree と Red Black Jungle Tree Editor のAPIの使い方の違いを記述する。
|
|
|
277 %\paragraph* { Jungle Red Black Tree の検索}
|
|
|
278 %編集と検索をいれるか迷います。
|
|
1
|
279
|
|
|
280 %Code \ref{src: "src"フォルダの中のコードのファイル名}で、文章中にコードの指定ができる。
|
|
|
281 %\lstinputlisting[label=src:ファイル名, caption=Enqueue]{./src/ファイル名.拡張子}
|
|
|
282
|
|
|
283
|
|
|
284 \section{分散環境でのJungleDBの書き出し実験方法の提案}
|
|
13
|
285 Jungleは分散環境で動くデータベースを目指して開発している。
|
|
|
286 Jungleには大量の様々な木が存在し、その大きさも様々である。
|
|
|
287 それぞれの木を異なるJungleノードに格納することにより、木が大量になる場合にも一定した性能が出るようにしたい。
|
|
|
288 一つの木が極端に大きくなる場合もあるが、それを分散して格納するのは難しい。
|
|
|
289 ここでは、一つの木は一つのノードに納まる大きさだと仮定する。
|
|
|
290 Jungleの木は信頼性向上とアクセス速度の向上のために、複数のノードに格納される。
|
|
|
291 木の変更は複数のノードを伝搬し、特定のJungleの木のルートノードに到達する。
|
|
|
292 そこで、木の状態が確定する。
|
|
|
293 一つのルートノードではなく、複数のノードに対して、多数決などの方法を用いることも考えられるが、
|
|
|
294 今回は単一のルートノードを用いる。
|
|
|
295 この方法は、読み込みに対して書き込みが少ない場合、あるいは書き込みが単一ノードのみからくる場合に有効であると考えられる。
|
|
|
296
|
|
|
297 従来のJungleDBの分散機能の測定はJetty Webサーバー込みで行なっており、DBに対する負荷は直接的には大きくなかった。
|
|
|
298 JungleDBに対して十分な負荷をかけるhttpリクエストを生成するのは困難であった。
|
|
|
299 そこで、Jungleの分散性能そのものを調べるために、Webサーバー抜きで測定したい。
|
|
|
300
|
|
|
301 JungleDBの通信は、研究室で開発した分散フレームワークAliceによって行われる。
|
|
|
302 Aliceはノードの木構造接続を自動的に行うTopologyManagerを持っている。
|
|
|
303 ここでは、Jungleの木それぞれに対してノードの木構造を別々に構成する必要がある。
|
|
|
304 これは、TopologyManagerを改良することによって行う。
|
|
|
305 Aliceはまた、通信を圧縮して行う機能も持っており、それによる高速化も期待できる。
|
|
|
306 通信されるのは、Jungleの木に対する変更Logであり、これをまとめて転送することにより、圧縮がうまく働くと期待される。
|
|
|
307 複数のノードの変更は、互いに競合することがあり、ノード間をルートに向かって通信していく間に競合を解消する必要がある。
|
|
|
308 これをMergeをいう。
|
|
|
309 従来のDBのような変更では、Mergeが失敗することがある。
|
|
|
310 失敗した場合は、複数の木構造がまとめて失敗してしまう。
|
|
|
311 JungleではMergeが失敗しないような場合、例えば、SNSへのコメントの追加などではうまく働く。
|
|
|
312 従来のDBとしてJungleを使う場合には、単一ノードで使用するか、多数決Commitを使うことになるが、ここではそれは測定しない。
|
|
|
313
|
|
|
314 今回、実験で分散構造としてJungleの動くノード16台を木構造に接続する。
|
|
|
315 この木のルートノードをルートjungleと呼び、末端ノードをリーフjungleと呼ぶ。
|
|
|
316 （図）
|
|
|
317 まず、末端のJungleにUserが書き込みをし、Jungleからuserにレスポンスが返ってくるまでの時間を測定する。
|
|
|
318 次に、Jungleの変更がルートのJungleにコピーされるまでの時間の測定方法を提案するJungle同士の接続には、当研究室で開発している分散フレームワークであるAliceを用いる。
|
|
1
|
319 \section{まとめ}
|
|
12
|
320 本研究では、始めに破壊的木構造データベースである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 の実装を行なった。
|
|
13
|
321 また、Jungleの分散機能に対する測定手法を提案した。
|
|
12
|
322 今後の課題として、Jungleは非破壊でデータを保持し続けるため、非常に多くのメモリを使用してしまう。ある程度の単位で過去のデータの掃除を行いたい。Jungleは、過去の木に対するアクセスをサポートしているため、データの掃除を行うタイミングが明確ではない。なので、メモリから追い出すタイミングを定義する必要がある。
|
|
1
|
323
|
|
|
324
|
|
|
325 %参考文献
|
|
|
326 \nocite{*}
|
|
|
327 \bibliographystyle{ipsjunsrt}
|
|
|
328 \bibliography{sigos}
|
|
|
329
|
|
|
330 \end{document}
|
