Papers/2014/nobuyasu-master: paper/chapter2.tex comparison

comparison paper/chapter2.tex @ 61:c5c761588168

Modified chapter3

author	Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date	Sat, 01 Feb 2014 10:23:28 +0900
parents	faa708c2958b
children	4f31182c8244

comparison

equal deleted inserted replaced

-:fd226352f17c
+:c5c761588168
 \chapter{木構造データベースJungle}
-Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである.
+Jungle はスケーラビリティのあるCMSの開発を目指して当研究室で開発されている非破壊的木構造データベースである.
-一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの
+一般的なコンテンツマネジメントシステムではブログツールやWiki・SNSが多く, これらの
 ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している.
-現在 Java と Haskell によりそれぞれ言語で開発されており本研究で扱うのは Java 版である.
+現在JavaとHaskellによりそれぞれ言語で開発されており本研究で扱うのはJava版である.
-本章ではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ分散の設計について述べる.
+本章ではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungleにおけるデータ分散の設計について述べる.
 \subsection{破壊的木構造}
 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う.
-図\ref{fig:destractive}は破壊的木構造の編集を表している.
+図\ref{fig:destractive}は破壊的木構造のにおけるデータ編集を表している.
 \begin{figure}[htpb]
 \begin{center}
 \includegraphics[scale=0.7]{figures/destructive_tree.pdf}
 \caption{破壊的木構造の編集}
 \end{center}
 \end{figure}
 \newpage
-非破壊的木構造においてデータのロックが必要となる部分は, 木のコピーを作終えた後に
+非破壊的木構造においてデータのロックが必要となる部分は, 木のコピーを作終りえた後に
 ルートノードを更新するときだけである.
 データ編集を行っている間ロックが必要な破壊的木構造に比べ, 編集中においてもデータの読み込みが
 可能である(図\ref{fig:nondestractive_merit}).
 そのため, 破壊的木構造に比べスケールがしやすくなっている.
 \caption{非破壊的木構造による利点}
 \label{fig:nondestractive_merit}
 \end{center}
 \end{figure}
+\newpage
 \section{Jungle におけるデータへのアクセス}
-Jungle ではデータをそれぞれの Node が attribute として保持する.
+Jungleにおいてのデータアクセス手段について述べる.
-attribute は String 型の Key と ByteBuffer の value のペアにより表される.
+Jungleではデータをそれぞれの Node が attribute として保持する.
-Jungle でデータへのアクセスは, この Node へのアクセスをさす.
+attributeはKey-Valueによりデータを保持する.
+KeyはString型でValueはByteBufferを使用している.
+Jungleでデータへのアクセスは, このNodeへのアクセスをさす.
 Node へのアクセスは, 木の名前と Node を指すパスにより行える.
 このパスは NodePath と呼ばれる(図\ref{fig:nodepath}).
 \begin{figure}[htpb]
 \begin{center}
 \subsection{NodeOperation}
 Jungle による最小のデータ編集は Node の編集を指す.
 Node 編集のために API が用意されており, この API は NodeOperation と呼ばれる.
 NodeOperation には次の4つの API が用意されている.
 \begin{itemize}
-\item \verb|addNewChild(NodePath _path, int _pos)|
+\item \verb|addNewChild(NodePath _path, int _pos)|\\
 NodePath で指定された Node に子供となる Node を追加する API である.
 pos で指定された番号に子供として追加を行う.
-\item \verb|deleteChildAt(NodePath _path, int _pos)|
+\item \verb|deleteChildAt(NodePath _path, int _pos)|\\
 NodePath と pos により指定される Node を削除する API である.
-\item \verb|putAttribute(NodePath _path, String _key, ByteBuffer _value)|
+\item \verb|putAttribute(NodePath _path, String _key, ByteBuffer _value)|\\
 Node に attribute を追加する API である.
 NodePath は attribute を追加する Node を指す.
-\item \verb|deleteAttribute(NodePath _path, String _key)|
+\item \verb|deleteAttribute(NodePath _path, String _key)|\\
 \verb|_key| が示す attribute の削除を行う API である.
 NodePath は Node を示す.
 \end{itemize}
 NodeOperationはNodePathとセットで扱わなければならず, このセットを
 public TreeOperationLog append(TreeOperationLog _log);
 public int length();
 }
 \end{lstlisting}
 \verb|Iterable<TreeOperation>|を継承しているためIteratorによりTreeOperationを取り出せるようになっている.
-addやappendメソッドを使ってTreeOperationを積み上げていくことができる
+addやappendメソッドを使ってTreeOperationを積み上げていくことができる.
 次にデータ編集により発生するTreeOperationLogの具体的な例を示す(\ref{src:treelog}).
 \begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left]
 [APPEND_CHILD:<-1>:pos:0]
 [PUT_ATTRIBUTE:<-1,0>:key:author,value:oshiro]
 \label{fig:treeoperationlog}
 \end{center}
 \end{figure}
 図\ref{fig:treeoperationlog}の説明を行う.
-まず, \verb|APPEND_CHILD| により Root Node の 0 番目の子供となる Node の追加を行う.
+まず, \verb|APPEND_CHILD:<-1>:pos:0|によりRoot Nodeの0番目の子供となるNodeの追加を行う.
-次に, 追加を行った Node に対して \verb|PUT_ATTRIBUTE| により attribute の情報を持たせていく.
+次に, 追加を行ったNodeに対して\verb|PUT_ATTRIBUTE<-1,0>| により attribute の情報を持たせていく.
-attribute の内容に作者の情報を表す auther, メッセージの内容を表す mes, そしてタイムスタンプ
+attributeの内容に作者の情報を表すauther, メッセージの内容を表すmes, そしてタイムスタンプ
-を timestamp とそれぞれキーにすることで追加される.
+をtimestampとそれぞれキーにすることで追加される.
 以上が掲示板プログラムにおける1つの書き込みで発生する TreeOperationLog である.
-\section{分散バージョン管理システムによるデータの分散}
+\newpage
-Jungle は Git や Mercurial といった分散バージョン管理システムの機能を参考に作られている.
-分散バージョン管理システムとは, 多人数によるソフトウェア開発において変更履歴を管理するシステムである.
-% 反対の意味の言葉として集中型バージョン管理システムがある.
-分散管理システムでは開発者それぞれがローカルにリポジトリのクローンを持ち, 開発はこのリポジトリを通すことで進められる(図\ref{fig:distributed_repo}).
-ローカルのリポジトリは独立に損刺し, サーバ上にあるリポジトリや他人のリポジトリで行われた変更履歴を取り込みアップデートにかけることができる.
-また逆に, ローカルのリポジトリに開発者自身がかけたアップデートを他のリポジトリへと反映させることもできる.
-分散管理システムでは, どれかリポジトリが壊れたとしても, 別のリポジトリからクローンを行うことができる.
-ネットワークに障害が発生しても, ローカルにある編集履歴をネットワーク復旧後に伝えることができる.
-そのため, 可用性と分断耐性が高いと言える.
-% 分散管理システムは結果整合性をとることを述べる.
-% 結果整合性の話を先にどっかでしたほうがいいかも
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.7]{figures/distributed_repository.pdf}
-\caption{分散バージョン管理システム}
-\label{fig:distributed_repo}
-\end{center}
-\end{figure}
-\subsection{マージによるデータ変更衝突の解決}
-分散管理システムでは, データの更新時において衝突が発生する時がある.
-それは, 分散管理システムを参考にしている Jungle においても起こる問題である.
-データの変更を行うときには, 元のデータに編集が加えられている状態かもしれない.
-Jungle はリクエストがきた場合, 現在もっているデータを返す.
-そのためデータは最新のものであるかは保証されない.
-この場合, 古いデータに編集が加えられ, それを更に最新のデータへ伝搬させなければならない.
-このように他のリポジトリにより先にデータ編集が行われており, データの伝搬が素直にできない状態を
-衝突という.
-この衝突を解決する手段が必要である.
-分散管理システムでは衝突に対してマージと呼ばれる作業で解決をはかる.
-マージは, 相手のリポジトリのデータ編集履歴を受け取り, ローカルにあるリポジトリの編集と合わせる作業である.
-データ衝突に対して Jungle はアプリケーションレベルでのマージを実装して貰うことで解決をはかる.
-以下にマージが必要な場合とそうでない場合のデータ編集についての図を示す(図\ref{fig:tree_conflict1},\ref{fig:tree_conflict2},\ref{fig:tree_conflict3}).
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.48]{figures/tree_conflict.pdf}
-\caption{衝突の発生しないデータ編集}
-\label{fig:tree_conflict1}
-\end{center}
-\end{figure}
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.48]{figures/tree_conflict3.pdf}
-\caption{自然に衝突を解決できるデータ編集}
-\label{fig:tree_conflict2}
-\end{center}
-\end{figure}
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.48]{figures/tree_conflict2.pdf}
-\caption{衝突が発生するデータ編集}
-\label{fig:tree_conflict3}
-\end{center}
-\end{figure}
-\section{ネットワークトポロジーの形成}
-分散管理システムを参考に Jungle でもそれぞれのデータベースが独立に
-動くようにしたい.
-そのために必要なことはトポロジーの形成と, サーバノード間でのデータアクセス機構である.
-また, データ分散のために形成したトポロジー上で扱うデータを決めなければならない.
-\subsection{ツリートポロジーの形成}
-分散データーベス Jungle で形成されるネットワークトポロジーはツリー構造を想定している.
-ツリー構造ならば, データの整合性をとる場合, 一度トップまでデータを伝搬させることで行える.
-トップもしくはトップまでの間にあるサーバノードでデータ伝搬中に衝突が発生したらマージを行い, マージの結果を改めて伝搬すれば
-よいからである.
-また, リング型, スター型, メッシュ側ではデータ編集の結果を他サーバノードに流すとき
-流したデータが自分自身にくることにより発生するループに気をつける必要がある.
-ツリー構造の場合は, サーバノード同士の繋がりで閉路が無い.
-そのため, 自分自身が行ったデータ編集の履歴を繋がっているノードに送信するだけですむ.
-このルーティングの方式はスプリットホライズンと呼ばれるものである.
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.70]{figures/network_topology_tree.pdf}
-\caption{ツリー型のNetwork Topology}
-\label{fig:topology_tree}
-\end{center}
-\end{figure}
-\subsection{トポロジーの形成手段}
-Jungle で使用するネットワークトポロジーはツリー型を考えているが, リング型やメッシュ型といった
-他のネットワークトポロジーによる実装に関しても試す余地はある.
-そのため, ツリーだけでなく, 自由にネットワークトポロジーの形成を行えるようにしたい.
-\begin{figure}[htpb]
-\begin{minipage}{0.5\hsize}
-\begin{center}
-\includegraphics[scale=0.7]{figures/network_topology_ring.pdf}
-\caption{リング型のトポロジー}
-\label{fig:topology_ring}
-\end{center}
-\end{minipage}
-\begin{minipage}{0.5\hsize}
-\begin{center}
-\includegraphics[scale=0.7]{figures/topology_mesh.pdf}
-\caption{メッシュ型のトポロジー}
-\label{fig:topology_mesh}
-\end{center}
-\end{minipage}
-\end{figure}
-そこで当研究室で開発を行っている並列分散フレームワークである Alice を使用する.
-Alice はユーザが望んだマシンへの接続や必要なデータへのアクセスを行う機構と, 接続トポロジー
-形成機能を提供している.
-% トポロジー形成の説明をする. 重要さなども。
-% トポロジーの形成は容易ではない.
-% Alice が必要な機能を提供してくれることを述べる
-% Alice はトポロジー形成の機能を提供している
-% トポロジー間でのデータの受け渡す機能も提供している
-\section{並列分散フレームワークAlice}
-Alice は当研究室で開発している並列分散フレームワークである.
-Alice はデータを DataSegment, タスクを CodeSegment という単位で扱うプログラミングを提供している.
-コードの部分となる CodeSegment は, 計算に必要なデータである DataSegment が揃い次第実行が行われる(図\ref{fig:cs_ds}).
-CodeSegment の結果により出力される新たなデータでは, 別の CodeSegment が実行されるための DataSegment となる.
-DataSegment と CodeSegment の組み合わせにより並列・分散プログラミングの依存関係が表される.
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.70]{figures/cs_ds.pdf}
-\caption{DataSegment と CodeSegment によるプログラムの流れ}
-\label{fig:cs_ds}
-\end{center}
-\end{figure}
-\subsection{MessagePack によるシリアライズ}
-Alice では DataSegment のデータ表現に MessagePack(http://msgpack.org) を利用している.
-MessagePack はオブジェクトをバイナリへと変換させるシリアライズライブラリである.
-Alice によりネットワークを介してデータにアクセスするときは, そのデータが MessagePack でシリアライズが
-行えることが条件である.
-\section{Jungle のデータ分散}
-Alice によりトポロジーの形成とデータアクセスの機構が提供された.
-後はデータ分散の為にどのデータをネットワークに流すのか決めなければならない.
-そこで選ばれたのが TreeOperationLog である.
-TreeOperationLog はデータ編集の履歴になる.
-どの Node にどのような操作をしたのかという情報が入っている.
-この TreeOperationLog を Alice を使って他サーバノードに送り, データの編集をしてもらうことで
-同じデータを持つことが可能となる.
-Alice を用いるため, この TreeOperationLog は MessagePack によりシリアライズ可能な形にすることが
-必要である.
-\subsection{CAP 定理と Jungle}
-ここまでの Jungle の設計を踏まえて, CAP 定理における Jungle の立ち位置を考える.
-分散管理バージョンのように独立したリポジトリもち, それぞれが独自の変更を加えることが
-行えることで一貫性はゆるい.
-だが, ネットワークから切断されてもローカルで行ったデータの変更をネットワーク復旧後で伝搬できる
-ことと, リクエストに対し持っているデータをすぐに返すことができる.
-つまり Jungle は可用性と分断耐性に優れたデータベースを目指している.
-第2章で紹介した既存のデータベースと Jungle との CAP 定理の関係を図\ref{fig:cap_theorem}に示す.
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.7]{figures/cap_theorem.pdf}
-\caption{CAP 定理における各データベースの立ち位置}
-\label{fig:cap_theorem}
-\end{center}
-\end{figure}
-\section{ログによるデータの永続性}
-% TreeOperationLog(ログ)をシリアライズ可能な形にしてデータをおくること
-% シリアライズできる形にしたものをそのままHDに書き出すだけでログの永続性は行える
-Jungle は非破壊でさらにオンメモリにデータを保持するため, 使用するメモリの容量が大きくなる.
-そのため, ハードディスクに書き出し, 一定の区切りで保持している過去のデータをメモリ上から掃除しなければならない.
-そこで, ログによるデータの永続性の実装を行う.
-ここでログをどのようなデータ表現でハードディスクへと書きだすかという問題が発生するが, これは Alice を使うことで
-解決している.
-Alice を用いるため MessagePack によりシリアライズ可能な TreeOperationLog ができる.
-このシリアライズ可能な TreeOperationLog をそのままハードディスクへ書き込むこととでログの永続性ができる.

Mercurial > hg > Papers > 2014 > nobuyasu-master

comparison paper/chapter2.tex @ 61:c5c761588168