Mercurial > hg > Papers > 2014 > nobuyasu-master

comparison paper/chapter2.tex @ 100:ae161408bc1c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed chapter2.tex
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Sat, 15 Feb 2014 04:37:14 +0900
parents 4e8bfd65768f
children d116e59fc8a2
comparison
equal deleted inserted replaced
99:be9d52d3c424 100:ae161408bc1c
1 \chapter{木構造データベースJungle} 1 \chapter{木構造データベースJungle}
2 Jungle はスケーラビリティのあるCMSの開発を目指して当研究室で開発されている非破壊的木構造データベースである. 2 　Jungle はスケーラビリティのあるCMSの開発を目指して当研究室で開発されている非破壊的木構造データベースである.
3 一般的なコンテンツマネジメントシステムではブログツールやWiki・SNSが多く, これらの 3 一般的なコンテンツマネジメントシステムではブログツールやWiki・SNSが多く, これらの
4 ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している. 4 ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している.
5 現在JavaとHaskellによりそれぞれ言語で開発されており本研究で扱うのはJava版である. 5 現在JavaとHaskellによりそれぞれ言語で開発されており本研究で扱うのはJava版である.
6 6
7 本章ではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungleにおけるデータ分散の設計について述べる. 7 本章ではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungleにおけるデータ分散の設計について述べる.
21 この時, データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり, 閲覧者が 21 この時, データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり, 閲覧者が
22 いる場合は木の走査が終わるまで書き換えをまたなければならない. 22 いる場合は木の走査が終わるまで書き換えをまたなければならない.
23 これではロックによりスケーラビリティが損なわれてしまう. 23 これではロックによりスケーラビリティが損なわれてしまう.
24 24
25 \subsection{非破壊的木構造} 25 \subsection{非破壊的木構造}
26 非破壊的木構造は破壊的木構造とは違い, 一度作成した木を破壊することはない. 26 非破壊的木構造は破壊的木構造とは異なり, 一度作成した木を破壊することはない.
27 非破壊的木構造においてデータの編集は, ルートから編集を行うノードまでコピーを 27 非破壊的木構造においてデータの編集は, ルートから編集を行うノードまでコピーを
28 行い新しく木構造を作成することで行われる. 28 行い新しく木構造を作成することで行われる.
29 図\ref{fig:nondestractive}は非破壊的木構造のデータ編集を示している. 29 図\ref{fig:nondestractive}は非破壊的木構造のデータ編集を示している.
30 30
31 \begin{figure}[htpb] 31 \begin{figure}[htpb]
39 非破壊的木構造におけるデータ編集の手順を以下に示す. 39 非破壊的木構造におけるデータ編集の手順を以下に示す.
40 40
41 \begin{enumerate} 41 \begin{enumerate}
42 \item ルートから編集を行うノードまでのパスを調べる(図\ref{fig:nondestractive_edit1}). 42 \item ルートから編集を行うノードまでのパスを調べる(図\ref{fig:nondestractive_edit1}).
43 \item 編集を行うノードのコピーをとる. コピーをとったノードへデータの編集を行う(図\ref{fig:nondestractive_edit2}). 43 \item 編集を行うノードのコピーをとる. コピーをとったノードへデータの編集を行う(図\ref{fig:nondestractive_edit2}).
44 \item 調べたパスに従いルートからコピーしたノードまでの間のノードのコピーをとり繋げる(図\ref{fig:nondestractive_edit3}). 44 \item 調べたパスに従いルートからコピーしたノードまでの間のノードのコピーをとり, 繋げる(図\ref{fig:nondestractive_edit3}).
45 \item コピーしたルートノードは編集を行っていないノードへの参照を貼り新しい木構造を作る(図\ref{fig:nondestractive_edit4}). 45 \item コピーしたルートノードは編集を行っていないノードへの参照を貼り, 新しい木構造を作る(図\ref{fig:nondestractive_edit4}).
46 \end{enumerate} 46 \end{enumerate}
47 47
48 \begin{figure}[htpb] 48 \begin{figure}[htpb]
49 \begin{center} 49 \begin{center}
50 \includegraphics[scale=0.7]{figures/non_destructive_edit1.pdf} 50 \includegraphics[scale=0.7]{figures/non_destructive_edit1.pdf}
81 81
82 非破壊的木構造においてデータのロックが必要となる部分は, 木のコピーを作終りえた後に 82 非破壊的木構造においてデータのロックが必要となる部分は, 木のコピーを作終りえた後に
83 ルートノードを更新するときだけである. 83 ルートノードを更新するときだけである.
84 データ編集を行っている間ロックが必要な破壊的木構造に比べ, 編集中においてもデータの読み込みが 84 データ編集を行っている間ロックが必要な破壊的木構造に比べ, 編集中においてもデータの読み込みが
85 可能である(図\ref{fig:nondestractive_merit}). 85 可能である(図\ref{fig:nondestractive_merit}).
86 そのため, 破壊的木構造に比べスケールがしやすくなっている. 86 そのため, 破壊的木構造に比べてスケールアウトがしやすくなっている.
87 87
88 \begin{figure}[htpb] 88 \begin{figure}[htpb]
89 \begin{center} 89 \begin{center}
90 \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf} 90 \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf}
91 \caption{非破壊的木構造による利点} 91 \caption{非破壊的木構造による利点}
139 TreeOperationが1つのデータ編集の単位になるが, これはあくまで最小のデータ編集の単位である. 139 TreeOperationが1つのデータ編集の単位になるが, これはあくまで最小のデータ編集の単位である.
140 Jungle によるデータの編集はTreeOperationが複数集まった単位でcommitされていく. 140 Jungle によるデータの編集はTreeOperationが複数集まった単位でcommitされていく.
141 このTreeOperationの集まりをTreeOperationLogという. 141 このTreeOperationの集まりをTreeOperationLogという.
142 142
143 \subsection{TreeOperationLog} 143 \subsection{TreeOperationLog}
144 Jungle 内部ではTreeOperationは順次ログに積まれていき, 最終的に 144 　Jungle 内部ではTreeOperationは順次ログに積まれていき, 最終的に
145 commitされることで編集が完了する. 145 commitされることで編集が完了する.
146 この時, ログに積まれた複数のTreeOperationはTreeOperationLogとして扱われる. 146 この時, ログに積まれた複数のTreeOperationはTreeOperationLogとして扱われる.
147 TreeOperationLogの仕様を\ref{src:treeoperationlog}に示す. 147 TreeOperationLogの仕様をソースコード\ref{src:treeoperationlog}に示す.
148 \begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left] 148 \begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left]
149 public interface TreeOperationLog extends Iterable<TreeOperation> 149 public interface TreeOperationLog extends Iterable<TreeOperation>
150 { 150 {
151 public TreeOperationLog add(NodePath _p,NodeOperation _op); 151 public TreeOperationLog add(NodePath _p,NodeOperation _op);
152 public TreeOperationLog append(TreeOperationLog _log); 152 public TreeOperationLog append(TreeOperationLog _log);
153 public int length(); 153 public int length();
154 } 154 }
155 \end{lstlisting} 155 \end{lstlisting}
156 \verb|Iterable<TreeOperation>|を継承しているためIteratorによりTreeOperationを取り出せるようになっている. 156 　\verb|Iterable<TreeOperation>|を継承しているためIteratorによりTreeOperationを取り出せるようになっている.
157 addやappendメソッドを使ってTreeOperationを積み上げていくことができる. 157 addやappendメソッドを使ってTreeOperationを積み上げていくことができる.
158 158
159 次にデータ編集により発生するTreeOperationLogの具体的な例を示す(\ref{src:treelog}). 159 次にデータ編集により発生するTreeOperationLogの具体的な例を示す(ソースコード\ref{src:treelog}).
160 \begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left] 160 \begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left]
161 [APPEND_CHILD:<-1>:pos:0] 161 [APPEND_CHILD:<-1>:pos:0]
162 [PUT_ATTRIBUTE:<-1,0>:key:author,value:oshiro] 162 [PUT_ATTRIBUTE:<-1,0>:key:author,value:oshiro]
163 [PUT_ATTRIBUTE:<-1,0>:key:mes,value:hello] 163 [PUT_ATTRIBUTE:<-1,0>:key:mes,value:hello]
164 [PUT_ATTRIBUTE:<-1,0>:key:timestamp,value:0] 164 [PUT_ATTRIBUTE:<-1,0>:key:timestamp,value:0]
165 \end{lstlisting} 165 \end{lstlisting}
166 このログはルートノードに対し子ノードを追加し, 追加した子ノードに attribute を3つ追加する際に図れるログである(図\ref{fig:treeoperationlog}). 166 　このログはルートノードに対し子ノードを追加し, 追加した子ノードに attribute を3つ追加する際に図れるログである(図\ref{fig:treeoperationlog}).
167 167
168 大文字の英字は実行した NodeOperation の種類を表す. 168 大文字の英字は実行した NodeOperation の種類を表す.
169 \verb|<>| により囲まれている数字は NodePath を示す. 169 \verb|<>| により囲まれている数字は NodePath を示す.
170 NodePath の表記以降は Node の position や attribute の情報を表している. 170 NodePath の表記以降は Node の position や attribute の情報を表している.
171 171