Mercurial > hg > Papers > 2014 > nobuyasu-master
diff paper/chapter2.tex @ 10:02c7fc1cda10
Writed description of TreeOperationLog
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 16 Jan 2014 07:07:38 +0900 |
parents | c09b83fe37ef |
children | e16dad3b80fc |
line wrap: on
line diff
--- a/paper/chapter2.tex Thu Jan 16 00:20:41 2014 +0900 +++ b/paper/chapter2.tex Thu Jan 16 07:07:38 2014 +0900 @@ -1,17 +1,18 @@ \chapter{木構造データベースJungleの実装と分散設計} + \section{木構造データベースJungle} Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである. 一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している. -ここではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ編集の実装について述べる. +まず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ編集の実装について述べる. \subsection{破壊的木構造} 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う. 図\ref{fig:destractive}は破壊的木構造の編集を表している. \begin{figure}[htpb] \begin{center} - \includegraphics[scale=0.8]{figures/destructive_tree.pdf} + \includegraphics[scale=0.7]{figures/destructive_tree.pdf} \caption{破壊的木構造の編集} \label{fig:destractive} \end{center} @@ -77,21 +78,84 @@ \end{center} \end{figure} -非破壊的木構造により, 木構造を編集しながら走査することが可能となる. +\newpage + +非破壊的木構造により, データの読み込みと編集を同時に行うことが可能になる. -\section{Jungleにおけるデータ編集} -Jungleではデータの編集のため次のAPIが用意されている. -\begin{itemize} -\item \verb|addNewChild(NodePath _path, int _pos)| -\item \verb|deleteChildAt(NodePath _path, int _pos)| -\item \verb|putAttribute(NodePath _path, String _key, ByteBuffer _value)| -\item \verb|deleteAttribute(NodePath _path, String _key)| -\end{itemize} - -\section{Jungleの分散データベース設計} - - -\subsection{マージ} +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf} + \caption{非破壊的木構造による利点} + \label{fig:nondestractive_merit} + \end{center} +\end{figure} +\section{Jungleにおけるデータ編集} +Jungle ではデータをそれぞれの Node が attribute として保持する. +attribute は String 型の Key と ByteBuffer の value のペアにより表される. +Jungle でデータ編集を行う場合, この Node に対して削除や attribute の追加等を行うことを指す. +どの Node へデータの編集を行うかはパスで示す. +このパスは NodePath と呼ばれる(図\ref{fig:nodepath}). + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.7]{figures/nodepath.pdf} + \caption{Node の attribute と NodePath} + \label{fig:nodepath} + \end{center} +\end{figure} + +Node の編集は Node の追加・削除, それと attribute の追加・削除を行うことを指す. +Node の編集のためには次の4つの API が用意されている. +\begin{itemize} +\item \verb|addNewChild(NodePath _path, int _pos)| +NodePath で指定された Node に子供となる Node を追加する API である. +pos で指定された番号に子供として追加を行う. +\item \verb|deleteChildAt(NodePath _path, int _pos)| +NodePath と pos により指定される Node を削除する API である. +\item \verb|putAttribute(NodePath _path, String _key, ByteBuffer _value)| +Node に attribute を追加する API である. +NodePath は attribute を追加する Node を指す. +\item \verb|deleteAttribute(NodePath _path, String _key)| +\verb|_key| が示す attribute の削除を行う API である. +NodePath は Node を示す. +\end{itemize} + +この Node 編集の為の API は NodeOperation と呼ばれる. +\subsection{TreeOperationLog} +API を使用すると, Jungle 内部では NodeOperation として順次ログに積まれていき, 最終的に +commit されることで編集が行われる. +この時ログに積まれる複数の NodeOperation を TreeOperationLog という. +Jungle ではこの TreeOperationLog 単位でデータの編集が行われる. +以下に TreeOperationLog の具体的な例を示す. +\begin{verbatim} +[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] +\end{verbatim} +このログは今回の研究で使用したベンチマーク用掲示板プログラムにおける書き込みにより行われるログである(図\ref{fig:treeoperationlog}). + +大文字の英字は実行した NodeOperation を表す. +<> により囲まれている数字は NodePath を示す. +NodePath の表記以降は Node の position や attribute の情報を表している. +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.7]{figures/treeoperationlog1.pdf} + \caption{TreeOperationLog の具体例} + \label{fig:treeoperationlog} + \end{center} +\end{figure} + +\section{TreeOperationLogを用いての分散データベースの実装} +Jungle でデータ扱うと TreeOperationLog として残る. +つまり, この TreeOperationLog を他のサーバへと送ることでデータの分散を +行うことができる. + + + + +