changeset 9:d8dd8d66a9b5

fix indent
author suruga
date Fri, 21 Apr 2017 16:21:02 +0900
parents 6b61e24c14c2
children 321952dbf59a
files paper/.DS_Store paper/sigos.dvi paper/sigos.log paper/sigos.pdf paper/sigos.tex
diffstat 5 files changed, 33 insertions(+), 31 deletions(-) [+]
line wrap: on
line diff
Binary file paper/.DS_Store has changed
Binary file paper/sigos.dvi has changed
--- 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).
Binary file paper/sigos.pdf has changed
--- 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では、1一人のユーザーがデータを書き込んでいるとき、他のユーザーが書き込みをしてくることで起こるデータの競合を防ぐために、書き込みが終わるまでロックをかける必要がある。これにより、データの編集に時間がかかってしまうという問題がある。また、データのネスト構造を許さない第一正規系を要求するRDBの表構造は、Jsonなどの不定形のデータ構造とミスマッチを起こしてしまうという問題がある。この問題はデータベースのインピーダンスミスマッチと呼ばれている。不定形の構造の変更をトランザクションとしてJsonの一括変更という形で処理する方法が考えられるが、並列処理が中心となってきている今のアプリケーションには向いているとは言えない。これらの問題を解決するため、当研究室では、分散処理環境で動くことができるデータベースを目指して非破壊的木構造データベースJungleを開発している。木構造を扱えることによって、従来のRDBとは異なり、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、その木をそのままデータベースとして使用することも可能である。非破壊的木構造とは、データの元の木を直接書き換えずに保存し、新しく構築した木のデータ構造を編集する方法である。 これにより、データの書き込み中であっても、元のデータは変更されない為、読み込みも同時に行うことができる。Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。また、Index の構築も大幅なネックとなっていた。そこで、本研究ではJungleの木と Index の編集機能の改善を行う。また、分散環境におけるjungleの書き出し速度の測定方法の提案をする。
+CPUのマルチコア化により、コンピュータのCPU性能が格段に上がった。マルチコアCPUの普及により、一般的なコンピュータの性
+能も向上してきた。コンピュータの性能が向上するにつれ、ソフトウェアやアプリケーションを高速に動作させる需要が求められてきた。しかし、RDBでは、1一人のユーザーがデータを書き込んでいるとき、他のユーザーが書き込みをしてくることで起こるデータの競合を防ぐために、書き込みが終わるまでロックをかける必要がある。これにより、データの編集に時間がかかってしまうという問題がある。また、データのネスト構造を許さない第一正規系を要求する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・4も検索対象に含まれてしまう。そこで、その版の木が持つ末尾ノード以下のSub Tree を検索対象から除外する、Differential Interface Traverser を実装した。Differential Interface Traverserを用いて木の全探索を行なった場合、Tree ver1 に存在しないノード3・4は検索対象から省かれる。
@@ -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 の2つのプロセスからなる。 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 に新しいノード5を追加・Commit を行うと、新しい木 Tree ver'2 が構築される。ここで、Tree ver'2 に対して全検索を行う。differential Jungle Tree に対する全検索は、末尾ノードよ上にあるノードを検索対象にする。しかしノード3・4という、本来存在しないはずのノードが検索対象に含まれてしまう。これは、過去の版の木である、 tree ver1 の末尾ノードが2つの子ノードを持っているせいで発生する。この問題を解決するために、Differential Jungle Tree では、過去の木に対する変更を禁止している。具体的には。末尾ノードは子を1つしか持つことができないようにした。そうすることで木の整合性を保証している。
@@ -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の設計手法を確立させる必要がある。
 
 
 %参考文献