# HG changeset patch # User suruga # Date 1492759262 -32400 # Node ID d8dd8d66a9b5f1c97717bac9dccb55cad09b62b6 # Parent 6b61e24c14c299cfdd498cbb46adc475f42c3bd7 fix indent diff -r 6b61e24c14c2 -r d8dd8d66a9b5 paper/.DS_Store Binary file paper/.DS_Store has changed diff -r 6b61e24c14c2 -r d8dd8d66a9b5 paper/sigos.dvi Binary file paper/sigos.dvi has changed diff -r 6b61e24c14c2 -r d8dd8d66a9b5 paper/sigos.log --- a/paper/sigos.log Fri Apr 21 03:56:49 2017 +0900 +++ b/paper/sigos.log Fri Apr 21 16:21:02 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 03:56 +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 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -183,73 +183,73 @@ 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 78. +(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 78. +(Font) Font shape `JY1/gt/m/n' tried instead on input line 79. LaTeX Font Info: External font `cmex10' loaded for size -(Font) <10.95> on input line 78. +(Font) <10.95> on input line 79. LaTeX Font Info: External font `cmex10' loaded for size -(Font) <8> on input line 78. +(Font) <8> on input line 79. 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 78. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 79. 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 78. +(Font) Font shape `JY1/gt/m/n' tried instead on input line 79. -Class ipsjpapers Warning: Missing eabstract env on input line 78. +Class ipsjpapers Warning: Missing eabstract env on input line 79. LaTeX Font Info: External font `cmex10' loaded for size -(Font) <7> on input line 78. +(Font) <7> on input line 79. File: ./pic/non_destructive_tree.pdf Graphic file (type 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 92. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 94. 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 92. +(Font) Font shape `JY1/gt/m/n' tried instead on input line 94. [1 ] -LaTeX Font Info: Try loading font information for OML+cmr on input line 100. +LaTeX Font Info: Try loading font information for OML+cmr on input line 102. (/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 100. +(Font) Font shape `OML/cmm/m/it' tried instead on input line 102. 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 125. +(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 125. +(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 166. +line 167. -Overfull \hbox (0.80186pt too wide) in paragraph at lines 172--172 +Overfull \hbox (0.80186pt too wide) in paragraph at lines 173--173 [][]| [] -Overfull \hbox (18.31381pt too wide) in paragraph at lines 171--176 +Overfull \hbox (18.31381pt too wide) in paragraph at lines 172--177 [][][] [] [3] File: ./pic/EditDifferencialTree.pdf Graphic file (type pdf) <./pic/EditDifferencialTree.pdf> -Overfull \hbox (22.76657pt too wide) in paragraph at lines 186--187 +Overfull \hbox (22.76657pt too wide) in paragraph at lines 187--188 [] [] -Overfull \hbox (14.58702pt too wide) in paragraph at lines 194--195 +Overfull \hbox (14.58702pt too wide) in paragraph at lines 195--196 []\OT1/cmr/m/n/9 Editor \JY1/mc/m/n/9 が保持している木構造に対して \OT1/cmr/m/n /9 addNewChild( [] @@ -258,7 +258,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 232--237 +Overfull \hbox (18.31381pt too wide) in paragraph at lines 233--238 [][][] [] @@ -284,6 +284,6 @@ 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,1721b,329s stack positions out of 5000i,500n,10000p,200000b,80000s + 30i,13n,49p,1602b,329s stack positions out of 5000i,500n,10000p,200000b,80000s -Output written on sigos.dvi (6 pages, 40660 bytes). +Output written on sigos.dvi (6 pages, 40624 bytes). diff -r 6b61e24c14c2 -r d8dd8d66a9b5 paper/sigos.pdf Binary file paper/sigos.pdf has changed diff -r 6b61e24c14c2 -r d8dd8d66a9b5 paper/sigos.tex --- a/paper/sigos.tex Fri Apr 21 03:56:49 2017 +0900 +++ b/paper/sigos.tex Fri Apr 21 16:21:02 2017 +0900 @@ -71,7 +71,8 @@ % 和文概要 \begin{abstract} - コンピュータの性能が向上するにつれ、ソフトウェアやアプリケーションを高速に動作させる需要が求められてきた。しかし、RDBでは、同時書き込みの際に起こる競合を防ぐため、編集中にロックがかけられ、編集に時間がかかってしまう。また、不定形のデータ構造と表構造がミスマッチを起こしてしまう、インピーダンスミスマッチという問題がある。そこで当研究では、非破壊的木構造データベースJungleを開発している。非破壊的木構造により、読み込みと書き込みを同時に実行することができる。また、データベースの再設計を行わずに不定形のデータ構造を扱うことが可能である。本研究ではJungleの木と Index の編集機能の改善を行う。また、分散環境におけるjungleの書き出し速度の測定方法の提案をする。 +コンピュータの性能が向上するにつれ、ソフトウェアやアプリケーションを高速に動作させる需要が求められてきた。しかし、RDB +では、同時書き込みの際に起こる競合を防ぐため、編集中にロックがかけられ、編集に時間がかかってしまう。また、不定形のデータ構造と表構造がミスマッチを起こしてしまう、インピーダンスミスマッチという問題がある。そこで当研究では、非破壊的木構造データベースJungleを開発している。非破壊的木構造により、読み込みと書き込みを同時に実行することができる。また、データベースの再設計を行わずに不定形のデータ構造を扱うことが可能である。本研究ではJungleの木と Index の編集機能の改善を行う。また、分散環境におけるjungleの書き出し速度の測定方法の提案をする。 \end{abstract} % 表題などの出力 @@ -81,7 +82,8 @@ % Introduce \section{研究目的と背景} - CPUのマルチコア化により、コンピュータのCPU性能が格段に上がった。マルチコアCPUの普及により、一般的なコンピュータの性能も向上してきた。コンピュータの性能が向上するにつれ、ソフトウェアやアプリケーションを高速に動作させる需要が求められてきた。しかし、RDBでは、１一人のユーザーがデータを書き込んでいるとき、他のユーザーが書き込みをしてくることで起こるデータの競合を防ぐために、書き込みが終わるまでロックをかける必要がある。これにより、データの編集に時間がかかってしまうという問題がある。また、データのネスト構造を許さない第一正規系を要求するRDBの表構造は、Jsonなどの不定形のデータ構造とミスマッチを起こしてしまうという問題がある。この問題はデータベースのインピーダンスミスマッチと呼ばれている。不定形の構造の変更をトランザクションとしてJsonの一括変更という形で処理する方法が考えられるが、並列処理が中心となってきている今のアプリケーションには向いているとは言えない。これらの問題を解決するため、当研究室では、分散処理環境で動くことができるデータベースを目指して非破壊的木構造データベースJungleを開発している。木構造を扱えることによって、従来のRDBとは異なり、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、その木をそのままデータベースとして使用することも可能である。非破壊的木構造とは、データの元の木を直接書き換えずに保存し、新しく構築した木のデータ構造を編集する方法である。 これにより、データの書き込み中であっても、元のデータは変更されない為、読み込みも同時に行うことができる。Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。また、Index の構築も大幅なネックとなっていた。そこで、本研究ではJungleの木と Index の編集機能の改善を行う。また、分散環境におけるjungleの書き出し速度の測定方法の提案をする。 +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に置き換えることで、木のアップデートを行う。変更前の木が残っているので、そのまま使用できる。変更されないノードは変更前と変更後のルートから共有されることになる。 @@ -118,8 +120,7 @@ \end{itemize} %ここもうちょっとかく。 \section{Indexの差分Updateの実装} -Jungleは木の編集を行う際に、編集を行うノードと、経路にあるノードの複製を行い新しい木構造を構築するため、 Index の中には、編集後の木には存在しない複製前のノードが残ってしまう。なので、 Index の差分 Update を行う際には、それらのノードを Index から削除して、新しく複製されたノードを Index に登録する必要がある。 -　そのためには、編集を行なったノードを覚えておく必要がある。そこで、 Jungle Tree Editor 内に、編集を加えたノードを覚えておくためのリストを定義した。 Editor は木に編集を加えた際、リストに編集前のノードを保存する。そして、Commit 時にリストにあるノードを使って Index の中に残っている、編集後の木に存在しないノードを削除する。その後、新しく作られたノードを Index に登録して Update は終了する。 +Jungleは木の編集を行う際に、編集を行うノードと、経路にあるノードの複製を行い新しい木構造を構築するため、 Index の中には、編集後の木には存在しない複製前のノードが残ってしまう。なので、 Index の差分 Update を行う際には、それらのノードを Index から削除して、新しく複製されたノードを Index に登録する必要がある。そのためには、編集を行なったノードを覚えておく必要がある。そこで、 Jungle Tree Editor 内に、編集を加えたノードを覚えておくためのリストを定義した。 Editor は木に編集を加えた際、リストに編集前のノードを保存する。そして、Commit 時にリストにあるノードを使って Index の中に残っている、編集後の木に存在しないノードを削除する。その後、新しく作られたノードを Index に登録して Update は終了する。 \paragraph* {編集前ののノードの削除} @@ -194,7 +195,7 @@ \item Editorが保持している木構造に対して addNewChild( \textless-1.0\textgreater)を実行し、ノードの追加を行う。 \item Commit を行い、Treeの末尾ノードにEditorが保持している木構造を Append する。 \end{itemize} -　Editor が保持している木構造に最後に追加したノードが、新しい木の末尾ノードとなる。また、Differential Jungle Tree は、木の編集時複製を行わないため、 Index のアップデートは、 Editor が保持している木構造のデータを Index に追加するだけで良い。 +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 に存在しないノード３・４は検索対象から省かれる。 @@ -206,7 +207,7 @@ \caption{複数の版の木の表現} \label{fig:Differential_Interface_Traverser} \end{figure} - 　Index を使用した検索を行う場合、各版の木に対応した Index があるため、Default Tree と検索のアルゴリズムは変わらない。これらの実装により Differential Jungle Tree は木構造の構築・検索を行う。 + 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})を例に解説する。（図\ref{fig:Differential_Interface_Traverser}）の過去の版の木 Tree ver1 に新しいノード５を追加・Commit を行うと、新しい木 Tree ver'2 が構築される。ここで、Tree ver'2 に対して全検索を行う。differential Jungle Tree に対する全検索は、末尾ノードよ上にあるノードを検索対象にする。しかしノード３・４という、本来存在しないはずのノードが検索対象に含まれてしまう。これは、過去の版の木である、 tree ver1 の末尾ノードが２つの子ノードを持っているせいで発生する。この問題を解決するために、Differential Jungle Tree では、過去の木に対する変更を禁止している。具体的には。末尾ノードは子を１つしか持つことができないようにした。そうすることで木の整合性を保証している。 @@ -238,7 +239,8 @@ \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 が木の生成時に宣言した属性名でソートされているからである。 @@ -254,7 +256,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の設計手法を確立させる必要がある。 %参考文献