Mercurial > hg > Papers > 2014 > nobuyasu-master

comparison paper/chapter2.tex @ 31:9eb676914f1d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Writed description of jungle edit
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Mon, 27 Jan 2014 19:53:12 +0900
parents 92bc4faa9a37
children 04af243ddd7c
comparison
equal deleted inserted replaced
30:92bc4faa9a37 31:9eb676914f1d
1 \chapter{木構造データベースJungleの分散設計} 1 \chapter{木構造データベースJungleの分散設計}
2
3
4
5 \section{木構造データベースJungle}
6 Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである. 2 Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである.
7 一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの 3 一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの
8 ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している. 4 ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している.
9 5 現在 Java と Haskell によりそれぞれ言語で開発されており本研究で扱うのは Java 版である.
10 まず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ編集の実装について述べる. 6
7 本章ではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ分散の設計について述べる.
11 \subsection{破壊的木構造} 8 \subsection{破壊的木構造}
12 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う. 9 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う.
13 図\ref{fig:destractive}は破壊的木構造の編集を表している. 10 図\ref{fig:destractive}は破壊的木構造の編集を表している.
14 11
15 \begin{figure}[htpb] 12 \begin{figure}[htpb]
49 \end{enumerate} 46 \end{enumerate}
50 47
51 \begin{figure}[htpb] 48 \begin{figure}[htpb]
52 \begin{center} 49 \begin{center}
53 \includegraphics[scale=0.7]{figures/non_destructive_edit1.pdf} 50 \includegraphics[scale=0.7]{figures/non_destructive_edit1.pdf}
54 \caption{非破壊的木構造の編集1} 51 \caption{非破壊的木構造の編集手順1}
55 \label{fig:nondestractive_edit1} 52 \label{fig:nondestractive_edit1}
56 \end{center} 53 \end{center}
57 \end{figure} 54 \end{figure}
58 55
59 \begin{figure}[htpb] 56 \begin{figure}[htpb]
60 \begin{center} 57 \begin{center}
61 \includegraphics[scale=0.7]{figures/non_destructive_edit2.pdf} 58 \includegraphics[scale=0.7]{figures/non_destructive_edit2.pdf}
62 \caption{非破壊的木構造の編集2} 59 \caption{非破壊的木構造の編集手順2}
63 \label{fig:nondestractive_edit2} 60 \label{fig:nondestractive_edit2}
64 \end{center} 61 \end{center}
65 \end{figure} 62 \end{figure}
66 63
67 \begin{figure}[htpb] 64 \begin{figure}[htpb]
68 \begin{center} 65 \begin{center}
69 \includegraphics[scale=0.7]{figures/non_destructive_edit3.pdf} 66 \includegraphics[scale=0.7]{figures/non_destructive_edit3.pdf}
70 \caption{非破壊的木構造の編集3} 67 \caption{非破壊的木構造の編集手順3}
71 \label{fig:nondestractive_edit3} 68 \label{fig:nondestractive_edit3}
72 \end{center} 69 \end{center}
73 \end{figure} 70 \end{figure}
74 71
75 \begin{figure}[htpb] 72 \begin{figure}[htpb]
76 \begin{center} 73 \begin{center}
77 \includegraphics[scale=0.7]{figures/non_destructive_edit4.pdf} 74 \includegraphics[scale=0.7]{figures/non_destructive_edit4.pdf}
78 \caption{非破壊的木構造の編集4} 75 \caption{非破壊的木構造の編集手順4}
79 \label{fig:nondestractive_edit4} 76 \label{fig:nondestractive_edit4}
80 \end{center} 77 \end{center}
81 \end{figure} 78 \end{figure}
82 79
83 \newpage 80 \newpage
84 81
85 非破壊的木構造により, データの読み込みと編集を同時に行うことが可能になる. 82 非破壊的木構造においてデータのロックが必要となる部分は, 木のコピーを作終えた後に
83 ルートノードを更新するときだけである.
84 データ編集を行っている間ロックが必要な破壊的木構造に比べ, 編集中においてもデータの読み込みが
85 可能である(図\ref{fig:nondestractive_merit}).
86 そのため, 破壊的木構造に比べスケールがしやすくなっている.
86 87
87 \begin{figure}[htpb] 88 \begin{figure}[htpb]
88 \begin{center} 89 \begin{center}
89 \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf} 90 \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf}
90 \caption{非破壊的木構造による利点} 91 \caption{非破壊的木構造による利点}
91 \label{fig:nondestractive_merit} 92 \label{fig:nondestractive_merit}
92 \end{center} 93 \end{center}
93 \end{figure} 94 \end{figure}
94 95
95 96
96 97 \section{Jungle におけるデータへのアクセス}
97 \section{Jungleにおけるデータ編集}
98 Jungle ではデータをそれぞれの Node が attribute として保持する. 98 Jungle ではデータをそれぞれの Node が attribute として保持する.
99 attribute は String 型の Key と ByteBuffer の value のペアにより表される. 99 attribute は String 型の Key と ByteBuffer の value のペアにより表される.
100 Jungle でデータ編集を行う場合, この Node に対して削除や attribute の追加等を行うことを指す. 100 Jungle でデータへのアクセスは, この Node へのアクセスをさす.
101 どの Node へデータの編集を行うかはパスで示す. 101 Node へのアクセスは, 木の名前と Node を指すパスにより行える.
102 このパスは NodePath と呼ばれる(図\ref{fig:nodepath}). 102 このパスは NodePath と呼ばれる(図\ref{fig:nodepath}).
103 103
104 \begin{figure}[htpb] 104 \begin{figure}[htpb]
105 \begin{center} 105 \begin{center}
106 \includegraphics[scale=0.7]{figures/nodepath.pdf} 106 \includegraphics[scale=0.7]{figures/nodepath.pdf}
107 \caption{Node の attribute と NodePath} 107 \caption{Node の attribute と NodePath}
108 \label{fig:nodepath} 108 \label{fig:nodepath}
109 \end{center} 109 \end{center}
110 \end{figure} 110 \end{figure}
111 111
112 Node の編集は Node の追加・削除, それと attribute の追加・削除を行うことを指す. 112
113 Node の編集のためには次の4つの API が用意されている. 113
114 \section{Jungle におけるデータ編集}
115
116 \subsection{NodeOperation}
117 Jungle による最小のデータ編集は Node の編集を指す.
118 Node 編集のために API が用意されており, この API は NodeOperation と呼ばれる.
119 NodeOperation には次の4つの API が用意されている.
114 \begin{itemize} 120 \begin{itemize}
115 \item \verb|addNewChild(NodePath _path, int _pos)| 121 \item \verb|addNewChild(NodePath _path, int _pos)|
116 NodePath で指定された Node に子供となる Node を追加する API である. 122 NodePath で指定された Node に子供となる Node を追加する API である.
117 pos で指定された番号に子供として追加を行う. 123 pos で指定された番号に子供として追加を行う.
118 \item \verb|deleteChildAt(NodePath _path, int _pos)| 124 \item \verb|deleteChildAt(NodePath _path, int _pos)|
123 \item \verb|deleteAttribute(NodePath _path, String _key)| 129 \item \verb|deleteAttribute(NodePath _path, String _key)|
124 \verb|_key| が示す attribute の削除を行う API である. 130 \verb|_key| が示す attribute の削除を行う API である.
125 NodePath は Node を示す. 131 NodePath は Node を示す.
126 \end{itemize} 132 \end{itemize}
127 133
128 この Node 編集の為の API は NodeOperation と呼ばれる. 134 NodeOperation はあくまで最小のデータ編集の単位である.
135 アプリケーションレベルの実装にもよるが, Jungle によるデータの編集は NodeOperation が複数集まった単位によって行われる.
136 この複数の NodeOperation の集まりを TreeOperationLog という.
137
129 \subsection{TreeOperationLog} 138 \subsection{TreeOperationLog}
130 API を使用すると, Jungle 内部では NodeOperation として順次ログに積まれていき, 最終的に 139 Jungle 内部では NodeOperation は順次ログに積まれていき, 最終的に
131 commit されることで編集が行われる. 140 commit されることで編集が完了する.
132 この時ログに積まれる複数の NodeOperation を TreeOperationLog という. 141 この時, ログに積まれた複数の NodeOperation は TreeOperationLog として扱われる.
133 Jungle ではこの TreeOperationLog 単位でデータの編集が行われる.
134 以下に TreeOperationLog の具体的な例を示す(\ref{src:treelog}). 142 以下に TreeOperationLog の具体的な例を示す(\ref{src:treelog}).
135 \begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left] 143 \begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left]
136 [APPEND_CHILD:<-1>:pos:0] 144 [APPEND_CHILD:<-1>:pos:0]
137 [PUT_ATTRIBUTE:<-1,1>:key:author,value:oshiro] 145 [PUT_ATTRIBUTE:<-1,0>:key:author,value:oshiro]
138 [PUT_ATTRIBUTE:<-1,1>:key:mes,value:hello] 146 [PUT_ATTRIBUTE:<-1,0>:key:mes,value:hello]
139 [PUT_ATTRIBUTE:<-1,1>:key:key,value:hoge] 147 [PUT_ATTRIBUTE:<-1,0>:key:timestamp,value:0]
140 [PUT_ATTRIBUTE:<-1,1>:key:timestamp,value:0]
141 \end{lstlisting} 148 \end{lstlisting}
142 このログは今回の研究で使用したベンチマーク用掲示板プログラムにおける書き込みにより行われるログである(図\ref{fig:treeoperationlog}). 149 このログは今回の研究で使用したベンチマーク用掲示板プログラムにおける書き込みにより行われるログである(図\ref{fig:treeoperationlog}).
143 150
144 大文字の英字は実行した NodeOperation を表す. 151 大文字の英字は実行した NodeOperation の種類を表す.
145 <> により囲まれている数字は NodePath を示す. 152 \verb|<>| により囲まれている数字は NodePath を示す.
146 NodePath の表記以降は Node の position や attribute の情報を表している. 153 NodePath の表記以降は Node の position や attribute の情報を表している.
147 \begin{figure}[htpb] 154 \begin{figure}[htpb]
148 \begin{center} 155 \begin{center}
149 \includegraphics[scale=0.7]{figures/treeoperationlog1.pdf} 156 \includegraphics[scale=0.7]{figures/treeoperationlog1.pdf}
150 \caption{TreeOperationLog の具体例} 157 \caption{TreeOperationLog の具体例}
151 \label{fig:treeoperationlog} 158 \label{fig:treeoperationlog}
152 \end{center} 159 \end{center}
153 \end{figure} 160 \end{figure}
154 161
155 162 図\ref{fig:treeoperationlog}の説明を行う.
163 まず, \verb|APPEND_CHILD| により Root Node の 0 番目の子供となる Node の追加を行う.
164 次に, 追加を行った Node に対して \verb|PUT_ATTRIBUTE| により attribute の情報を持たせていく.
165 attribute の内容に作者の情報を表す auther, メッセージの内容を表す mes, そしてタイムスタンプ
166 を timestamp とそれぞれキーにすることで追加される.
167
168 以上が掲示板プログラムにおける1つの書き込みで発生する TreeOperationLog である.
156 169
157 \section{分散バージョン管理システムによるデータの分散} 170 \section{分散バージョン管理システムによるデータの分散}
158 Jungle は Git や Mercurial といった分散バージョン管理システムの機能を参考に作られている. 171 Jungle は Git や Mercurial といった分散バージョン管理システムの機能を参考に作られている.
159 分散バージョン管理システムとは, 多人数によるソフトウェア開発において変更履歴を管理するシステムである. 172 分散バージョン管理システムとは, 多人数によるソフトウェア開発において変更履歴を管理するシステムである.
160 % 反対の意味の言葉として集中型バージョン管理システムがある. 173 % 反対の意味の言葉として集中型バージョン管理システムがある.
171 \includegraphics[scale=0.7]{figures/distributed_repository.pdf} 184 \includegraphics[scale=0.7]{figures/distributed_repository.pdf}
172 \caption{分散バージョン管理システム} 185 \caption{分散バージョン管理システム}
173 \label{fig:distributed_repo} 186 \label{fig:distributed_repo}
174 \end{center} 187 \end{center}
175 \end{figure} 188 \end{figure}
176
177 189
178 190
179 \subsection{マージによるデータ変更衝突の解決} 191 \subsection{マージによるデータ変更衝突の解決}
180 分散管理システムでは, データの更新時において衝突が発生する時がある. 192 分散管理システムでは, データの更新時において衝突が発生する時がある.
181 それは, 分散管理システムを参考にしている Jungle においても起こる問題である. 193 それは, 分散管理システムを参考にしている Jungle においても起こる問題である.
217 \end{center} 229 \end{center}
218 \end{figure} 230 \end{figure}
219 231
220 \newpage 232 \newpage
221 233
222 234 \section{データ分散の設計}
235
236
237 \subsection{}
223 238
224 239
225 \section{データの永続性} 240 \section{データの永続性}
226 241
227 242