Mercurial > hg > Papers > 2014 > nobuyasu-master
diff paper/chapter2.tex @ 31:9eb676914f1d
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 |
line wrap: on
line diff
--- a/paper/chapter2.tex Mon Jan 27 14:54:34 2014 +0900 +++ b/paper/chapter2.tex Mon Jan 27 19:53:12 2014 +0900 @@ -1,13 +1,10 @@ \chapter{木構造データベースJungleの分散設計} - - - -\section{木構造データベースJungle} Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである. 一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している. +現在 Java と Haskell によりそれぞれ言語で開発されており本研究で扱うのは Java 版である. -まず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ編集の実装について述べる. +本章ではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ分散の設計について述べる. \subsection{破壊的木構造} 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う. 図\ref{fig:destractive}は破壊的木構造の編集を表している. @@ -51,7 +48,7 @@ \begin{figure}[htpb] \begin{center} \includegraphics[scale=0.7]{figures/non_destructive_edit1.pdf} - \caption{非破壊的木構造の編集1} + \caption{非破壊的木構造の編集手順1} \label{fig:nondestractive_edit1} \end{center} \end{figure} @@ -59,7 +56,7 @@ \begin{figure}[htpb] \begin{center} \includegraphics[scale=0.7]{figures/non_destructive_edit2.pdf} - \caption{非破壊的木構造の編集2} + \caption{非破壊的木構造の編集手順2} \label{fig:nondestractive_edit2} \end{center} \end{figure} @@ -67,7 +64,7 @@ \begin{figure}[htpb] \begin{center} \includegraphics[scale=0.7]{figures/non_destructive_edit3.pdf} - \caption{非破壊的木構造の編集3} + \caption{非破壊的木構造の編集手順3} \label{fig:nondestractive_edit3} \end{center} \end{figure} @@ -75,14 +72,18 @@ \begin{figure}[htpb] \begin{center} \includegraphics[scale=0.7]{figures/non_destructive_edit4.pdf} - \caption{非破壊的木構造の編集4} + \caption{非破壊的木構造の編集手順4} \label{fig:nondestractive_edit4} \end{center} \end{figure} \newpage -非破壊的木構造により, データの読み込みと編集を同時に行うことが可能になる. +非破壊的木構造においてデータのロックが必要となる部分は, 木のコピーを作終えた後に +ルートノードを更新するときだけである. +データ編集を行っている間ロックが必要な破壊的木構造に比べ, 編集中においてもデータの読み込みが +可能である(図\ref{fig:nondestractive_merit}). +そのため, 破壊的木構造に比べスケールがしやすくなっている. \begin{figure}[htpb] \begin{center} @@ -93,12 +94,11 @@ \end{figure} - -\section{Jungleにおけるデータ編集} +\section{Jungle におけるデータへのアクセス} Jungle ではデータをそれぞれの Node が attribute として保持する. attribute は String 型の Key と ByteBuffer の value のペアにより表される. -Jungle でデータ編集を行う場合, この Node に対して削除や attribute の追加等を行うことを指す. -どの Node へデータの編集を行うかはパスで示す. +Jungle でデータへのアクセスは, この Node へのアクセスをさす. +Node へのアクセスは, 木の名前と Node を指すパスにより行える. このパスは NodePath と呼ばれる(図\ref{fig:nodepath}). \begin{figure}[htpb] @@ -109,8 +109,14 @@ \end{center} \end{figure} -Node の編集は Node の追加・削除, それと attribute の追加・削除を行うことを指す. -Node の編集のためには次の4つの API が用意されている. + + +\section{Jungle におけるデータ編集} + +\subsection{NodeOperation} +Jungle による最小のデータ編集は Node の編集を指す. +Node 編集のために API が用意されており, この API は NodeOperation と呼ばれる. +NodeOperation には次の4つの API が用意されている. \begin{itemize} \item \verb|addNewChild(NodePath _path, int _pos)| NodePath で指定された Node に子供となる Node を追加する API である. @@ -125,24 +131,25 @@ NodePath は Node を示す. \end{itemize} -この Node 編集の為の API は NodeOperation と呼ばれる. +NodeOperation はあくまで最小のデータ編集の単位である. +アプリケーションレベルの実装にもよるが, Jungle によるデータの編集は NodeOperation が複数集まった単位によって行われる. +この複数の NodeOperation の集まりを TreeOperationLog という. + \subsection{TreeOperationLog} -API を使用すると, Jungle 内部では NodeOperation として順次ログに積まれていき, 最終的に -commit されることで編集が行われる. -この時ログに積まれる複数の NodeOperation を TreeOperationLog という. -Jungle ではこの TreeOperationLog 単位でデータの編集が行われる. +Jungle 内部では NodeOperation は順次ログに積まれていき, 最終的に +commit されることで編集が完了する. +この時, ログに積まれた複数の NodeOperation は TreeOperationLog として扱われる. 以下に TreeOperationLog の具体的な例を示す(\ref{src:treelog}). \begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left] [APPEND_CHILD:<-1>:pos:0] -[PUT_ATTRIBUTE:<-1,1>:key:author,value:oshiro] -[PUT_ATTRIBUTE:<-1,1>:key:mes,value:hello] -[PUT_ATTRIBUTE:<-1,1>:key:key,value:hoge] -[PUT_ATTRIBUTE:<-1,1>:key:timestamp,value:0] +[PUT_ATTRIBUTE:<-1,0>:key:author,value:oshiro] +[PUT_ATTRIBUTE:<-1,0>:key:mes,value:hello] +[PUT_ATTRIBUTE:<-1,0>:key:timestamp,value:0] \end{lstlisting} このログは今回の研究で使用したベンチマーク用掲示板プログラムにおける書き込みにより行われるログである(図\ref{fig:treeoperationlog}). -大文字の英字は実行した NodeOperation を表す. -<> により囲まれている数字は NodePath を示す. +大文字の英字は実行した NodeOperation の種類を表す. +\verb|<>| により囲まれている数字は NodePath を示す. NodePath の表記以降は Node の position や attribute の情報を表している. \begin{figure}[htpb] \begin{center} @@ -152,7 +159,13 @@ \end{center} \end{figure} +図\ref{fig:treeoperationlog}の説明を行う. +まず, \verb|APPEND_CHILD| により Root Node の 0 番目の子供となる Node の追加を行う. +次に, 追加を行った Node に対して \verb|PUT_ATTRIBUTE| により attribute の情報を持たせていく. +attribute の内容に作者の情報を表す auther, メッセージの内容を表す mes, そしてタイムスタンプ +を timestamp とそれぞれキーにすることで追加される. +以上が掲示板プログラムにおける1つの書き込みで発生する TreeOperationLog である. \section{分散バージョン管理システムによるデータの分散} Jungle は Git や Mercurial といった分散バージョン管理システムの機能を参考に作られている. @@ -175,7 +188,6 @@ \end{figure} - \subsection{マージによるデータ変更衝突の解決} 分散管理システムでは, データの更新時において衝突が発生する時がある. それは, 分散管理システムを参考にしている Jungle においても起こる問題である. @@ -219,8 +231,11 @@ \newpage +\section{データ分散の設計} +\subsection{} + \section{データの永続性}