# HG changeset patch # User suruga # Date 1492760962 -32400 # Node ID 321952dbf59ad51a9a6ab801a73830f891401368 # Parent d8dd8d66a9b5f1c97717bac9dccb55cad09b62b6 fix title, column name, etc diff -r d8dd8d66a9b5 -r 321952dbf59a paper/sigos.aux --- a/paper/sigos.aux Fri Apr 21 16:21:02 2017 +0900 +++ b/paper/sigos.aux Fri Apr 21 16:49:22 2017 +0900 @@ -2,7 +2,7 @@ \newlabel{fig:non_destructive_tree}{{1}{2}} \newlabel{fig:nodepath}{{2}{2}} \newlabel{fig:PushPopDemerit}{{3}{3}} -\newlabel{table:Diffetential API}{{1}{4}} +\newlabel{table:Diffetential API}{{1}{3}} \newlabel{fig:EditDifferencialTree}{{4}{4}} \newlabel{fig:Differential_Interface_Traverser}{{5}{4}} \newlabel{fig:Tree_ver2}{{6}{5}} diff -r d8dd8d66a9b5 -r 321952dbf59a paper/sigos.dvi Binary file paper/sigos.dvi has changed diff -r d8dd8d66a9b5 -r 321952dbf59a paper/sigos.log --- a/paper/sigos.log Fri Apr 21 16:21:02 2017 +0900 +++ b/paper/sigos.log Fri Apr 21 16:49:22 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 16:19 +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 16:45 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -186,6 +186,11 @@ (Font) Font shape `JT1/gt/m/n' tried instead on input line 79. 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 79. + + +Class ipsjpapers Warning: \title is too wide. Break line(s) by \\ on input line + 79. + LaTeX Font Info: External font `cmex10' loaded for size (Font) <10.95> on input line 79. LaTeX Font Info: External font `cmex10' loaded for size @@ -195,7 +200,6 @@ 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 79. - Class ipsjpapers Warning: Missing eabstract env on input line 79. LaTeX Font Info: External font `cmex10' loaded for size @@ -210,46 +214,46 @@ ] -LaTeX Font Info: Try loading font information for OML+cmr on input line 102. +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 100. +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 100. +LaTeX Font Info: Try loading font information for OML+cmr on input line 103. (/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 102. +(Font) Font shape `OML/cmm/m/it' tried instead on input line 103. File: ./pic/nodepath.pdf Graphic file (type 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 126. -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 126. File: ./pic/PushPopDemerit.pdf Graphic file (type pdf) <./pic/PushPopDemerit.pdf> LaTeX Warning: Reference `table:Differential API' on page 3 undefined on input -line 167. +line 168. -Overfull \hbox (0.80186pt too wide) in paragraph at lines 173--173 +Overfull \hbox (0.80186pt too wide) in paragraph at lines 174--174 [][]| [] -Overfull \hbox (18.31381pt too wide) in paragraph at lines 172--177 +Overfull \hbox (18.31381pt too wide) in paragraph at lines 173--178 [][][] [] [3] File: ./pic/EditDifferencialTree.pdf Graphic file (type pdf) <./pic/EditDifferencialTree.pdf> -Overfull \hbox (22.76657pt too wide) in paragraph at lines 187--188 +Overfull \hbox (22.76657pt too wide) in paragraph at lines 188--189 [] [] -Overfull \hbox (14.58702pt too wide) in paragraph at lines 195--196 +Overfull \hbox (14.58702pt too wide) in paragraph at lines 196--197 []\OT1/cmr/m/n/9 Editor \JY1/mc/m/n/9 が保持している木構造に対して \OT1/cmr/m/n /9 addNewChild( [] @@ -258,7 +262,7 @@ <./pic/Differential_Interface_Traverser.pdf> [4] File: ./pic/Tree_ver2.pdf Graphic file (type pdf) <./pic/Tree_ver2.pdf> -Overfull \hbox (18.31381pt too wide) in paragraph at lines 233--238 +Overfull \hbox (18.31381pt too wide) in paragraph at lines 234--239 [][][] [] @@ -286,4 +290,4 @@ 929 hyphenation exceptions out of 8191 30i,13n,49p,1602b,329s stack positions out of 5000i,500n,10000p,200000b,80000s -Output written on sigos.dvi (6 pages, 40624 bytes). +Output written on sigos.dvi (6 pages, 40696 bytes). diff -r d8dd8d66a9b5 -r 321952dbf59a paper/sigos.pdf Binary file paper/sigos.pdf has changed diff -r d8dd8d66a9b5 -r 321952dbf59a paper/sigos.tex --- a/paper/sigos.tex Fri Apr 21 16:21:02 2017 +0900 +++ b/paper/sigos.tex Fri Apr 21 16:49:22 2017 +0900 @@ -36,7 +36,7 @@ \begin{document} % 和文表題 -\title{Code Gear、 Data Gear に基づく OS のプロトタイプ} +\title{非破壊木構造データベース Jungle のサービス利用法にそった改良} % 英文表題 \etitle{} @@ -81,7 +81,7 @@ % 本文はここから始まる % Introduce -\section{研究目的と背景} +\section{サービス利用に適したデータベース} CPUのマルチコア化により、コンピュータのCPU性能が格段に上がった。マルチコアCPUの普及により、一般的なコンピュータの性 能も向上してきた。コンピュータの性能が向上するにつれ、ソフトウェアやアプリケーションを高速に動作させる需要が求められてきた。しかし、RDBでは、１一人のユーザーがデータを書き込んでいるとき、他のユーザーが書き込みをしてくることで起こるデータの競合を防ぐために、書き込みが終わるまでロックをかける必要がある。これにより、データの編集に時間がかかってしまうという問題がある。また、データのネスト構造を許さない第一正規系を要求するRDBの表構造は、Jsonなどの不定形のデータ構造とミスマッチを起こしてしまうという問題がある。この問題はデータベースのインピーダンスミスマッチと呼ばれている。不定形の構造の変更をトランザクションとしてJsonの一括変更という形で処理する方法が考えられるが、並列処理が中心となってきている今のアプリケーションには向いているとは言えない。これらの問題を解決するため、当研究室では、分散処理環境で動くことができるデータベースを目指して非破壊的木構造データベースJungleを開発している。木構造を扱えることによって、従来のRDBとは異なり、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、その木をそのままデータベースとして使用することも可能である。非破壊的木構造とは、データの元の木を直接書き換えずに保存し、新しく構築した木のデータ構造を編集する方法である。 これにより、データの書き込み中であっても、元のデータは変更されない為、読み込みも同時に行うことができる。Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。また、Index の構築も大幅なネックとなっていた。そこで、本研究ではJungleの木と Index の編集機能の改善を行う。また、分散環境におけるjungleの書き出し速度の測定方法の提案をする。 \section{非破壊的木構造データベースJungle} @@ -95,10 +95,11 @@ \label{fig:non_destructive_tree} \end{figure} Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合でできている。ノードは自身の子のリストと属性名、属性値を持ち、データベースのレコードに相応する。通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。Jungleでは、子供からの親へのポインタは持たないため、親から子への片方向の参照しかできない。通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。持続性のある分散ノードを用いることでJungleの持続性を保証することができる。 - -\section{Index} + +\section{Jungleの構成要素} +\subsection*{[Index]} Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。よって、すべての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。既存の TreeMap では、一度 Index の複製を行い、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。その問題を解決するため、Java 上で関数型プログラミングを行えるライブラリである、 Functional Java の TreeMap を使用し、それを用いて Index 実装を行なった。この TreeMap は、 Jungle と同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行なった際、前の版と最大限データを共有した新しい TreeMap を作成する。Jungle との違いは、木の回転処理が入ることである。これにより複数の版すべてに対応した Index をサポートすることが可能になった。 -\section{NodePath} +\subsection*{[NodePath]} Jungle では、木のノードの位置を NodePath クラスを使って表す。 NodePath クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。 NodePath クラスを用いて \textless -1,0,2,3 \textgreater を表している際の例を(図\ref{fig:nodepath})に示す。 \begin{figure}[htpb] @@ -109,7 +110,7 @@ \label{fig:nodepath} \end{figure} -\section{非破壊TreeMap} +\subsection*{[非破壊TreeMap]} Jungle の Index は、Functional Java の非破壊 TreeMap を用いて実装を行なっている。しかし、Functional Java の TreeMap は、木の変更の手間が大きい、並列実行処理速度が落ちるなど、実用的な性能を持っていなかった。そのため、Jungleの性能も、TreeMap 部分がネックとなっていた。その問題を解決するため、 Jungle で使用する非破壊 TreeMap を作成した。TreeMap は、Red Black Tree のアルゴリズムを用いている。RedBlackTreeとは二分木探索の一つで、以下の条件を満たした木のことである。 \begin{itemize} \item 各ノードは赤か黒の色を持つ。