Mercurial > hg > Papers > 2014 > nobuyasu-master

comparison paper/chapter2.tex @ 22:56753cfbeeab

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added merge_imp.pdf
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Thu, 23 Jan 2014 19:05:44 +0900
parents a7fbd5db80fb
children 67880a2ca650
comparison
equal deleted inserted replaced
21:a4dfb70496ee 22:56753cfbeeab
1 \chapter{木構造データベースJungleの実装と分散設計} 1 \chapter{木構造データベースJungleの実装と分散設計}
2 \section{CAP 定理} 2
3 3
4 4
5 \section{木構造データベースJungle} 5 \section{木構造データベースJungle}
6 Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである. 6 Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである.
7 一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの 7 一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの
129 \subsection{TreeOperationLog} 129 \subsection{TreeOperationLog}
130 API を使用すると, Jungle 内部では NodeOperation として順次ログに積まれていき, 最終的に 130 API を使用すると, Jungle 内部では NodeOperation として順次ログに積まれていき, 最終的に
131 commit されることで編集が行われる. 131 commit されることで編集が行われる.
132 この時ログに積まれる複数の NodeOperation を TreeOperationLog という. 132 この時ログに積まれる複数の NodeOperation を TreeOperationLog という.
133 Jungle ではこの TreeOperationLog 単位でデータの編集が行われる. 133 Jungle ではこの TreeOperationLog 単位でデータの編集が行われる.
134 以下に TreeOperationLog の具体的な例を示す. 134 以下に TreeOperationLog の具体的な例を示す(\ref{src:treelog}).
135 \begin{verbatim} 135 \begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left]
136 [APPEND_CHILD:<-1>:pos:0] 136 [APPEND_CHILD:<-1>:pos:0]
137 [PUT_ATTRIBUTE:<-1,1>:key:author,value:oshiro] 137 [PUT_ATTRIBUTE:<-1,1>:key:author,value:oshiro]
138 [PUT_ATTRIBUTE:<-1,1>:key:mes,value:hello] 138 [PUT_ATTRIBUTE:<-1,1>:key:mes,value:hello]
139 [PUT_ATTRIBUTE:<-1,1>:key:key,value:hoge] 139 [PUT_ATTRIBUTE:<-1,1>:key:key,value:hoge]
140 [PUT_ATTRIBUTE:<-1,1>:key:timestamp,value:0] 140 [PUT_ATTRIBUTE:<-1,1>:key:timestamp,value:0]
141 \end{verbatim} 141 \end{lstlisting}
142 このログは今回の研究で使用したベンチマーク用掲示板プログラムにおける書き込みにより行われるログである(図\ref{fig:treeoperationlog}). 142 このログは今回の研究で使用したベンチマーク用掲示板プログラムにおける書き込みにより行われるログである(図\ref{fig:treeoperationlog}).
143 143
144 大文字の英字は実行した NodeOperation を表す. 144 大文字の英字は実行した NodeOperation を表す.
145 <> により囲まれている数字は NodePath を示す. 145 <> により囲まれている数字は NodePath を示す.
146 NodePath の表記以降は Node の position や attribute の情報を表している. 146 NodePath の表記以降は Node の position や attribute の情報を表している.
152 \end{center} 152 \end{center}
153 \end{figure} 153 \end{figure}
154 154
155 155
156 156
157 \section{データ衝突時におけるマージによる解決}
158 Jungle への分散実装を行うことである問題が発生する.
159 それは更新されたデータ同士が衝突を起こした時の処理である.
160 Jungle はリクエストがきた場合, 現在もっているデータを返す.
161 しかしそのデータは最新のものであるかは保証されない.
162 よって, 別のサーバノードで動いている Jungle からの更新データと衝突する可能性がある.
163
164 この問題に対して Jungle はアプリケーションレベルでのマージを実装して貰うことで解決をはかる.
157 165
158 166
159 167
168
169
170
171
172
173
174
175