# HG changeset patch # User Nobuyasu Oshiro # Date 1391171860 -32400 # Node ID 1d07365c60ffd4232a287340899acefdb4f1cce5 # Parent cff4aee4fcf6285e4bfecc349e2f1131b96e0dfa Writed conclstion diff -r cff4aee4fcf6 -r 1d07365c60ff paper/chapter3.tex --- a/paper/chapter3.tex Fri Jan 31 20:36:54 2014 +0900 +++ b/paper/chapter3.tex Fri Jan 31 21:37:40 2014 +0900 @@ -1,3 +1,195 @@ \chapter{分散データベースJungleの設計} +\section{分散バージョン管理システムによるデータの分散} +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 をそのままハードディスクへ書き込むこととでログの永続性ができる. + + + + + diff -r cff4aee4fcf6 -r 1d07365c60ff paper/conclusion.tex --- a/paper/conclusion.tex Fri Jan 31 20:36:54 2014 +0900 +++ b/paper/conclusion.tex Fri Jan 31 21:37:40 2014 +0900 @@ -1,12 +1,46 @@ \chapter{結論} \label{chapter:conclusion} \section{まとめ} +本研究では, まず初めにRDBとNoSQLの説明を行い, 既存のNoSQLであるCassandra, MongoDB, Neo4jが +スケーラビリティをどのように確保しているかを述べた. +次に木構造データベースJungleで使われている非破壊的木構造について述べ, 破壊的 +木構造に比べロックが少ないというメリットがあることを論じた. +Jungleは非破壊的木構造により過去のデータを保持することでMergeを行うことができる. +そのため, 分散バージョン管理システムを参考に分散設計を行った. +Jungleの分散設計では当研究室で開発している並列分散フレームワークAliceを用いた. +Aliceにより自由にトポロジーを組め, 他サーバノードへのデータアクセス機構を手に入れることができた. +Jungleの分散実装ではデータの編集履歴であるTreeOperationLogをAliceが使用できるようにし, 木の名前と +いった必要な情報を追加することでデータの分散を行った. +最後に簡易掲示板を作成, Cassandraとの性能比較を行った. +読み込み, 書き込みの負荷をかける実験を2つ行った. +1つの実験ではサーバノード1台に対し複数のクライアントから負荷をかけた. +2つめの実験では複数のクライアントに対し同じ数のサーバノードを用意し数を増やしていき負荷を高めた. +どちらの実験もJungleがCassandraよりも良い結果を示すことを確認した. + \section{今後の課題} +\subsection{データ分割の実装} +現在Jungleの分散実装は全てのデータを全てのノードで保持している. +この方法ではメモリの使用量が高いこととネットワーク帯域に対しての +負荷が懸念される. +そのため, ノード単位で保持するデータを分ける実装が必要になる. +ノード毎に木構造単位で別々のデータを保持し, 持っていない木のデータ +に対して要求がくると他からとってきて返すといった機能が必要になる. -\subsection{データ分割の実装} \subsection{Mergerアルゴリズムの設計} -\subsection{Compactionの実装・分断耐性の実装} +JungleはMergeを使うことでデータ衝突の問題を解決をはかるが, この +Mergeはアプリケーション毎に考えなければならない. +今回, JungleにおけるMergeの例として掲示板プログラムにおけるMergeについて述べた. +だが掲示板のような単純なMergeですむアプリケーションは少ない. +また, アプリケーション毎でデータの保存の仕方といったものも違ってくる. +そのため, アプリケーションに合ったMergeアルゴリズムを設計しなければならない. + +\subsection{分断耐性の実装} +現在の実装のJungleは, プログラムの起動時にノードと接続を行う. +プログラムの途中で接続がきれるとトポロジーがくずれたままになる. +接続がきれたJungleは単独では稼働し続けるが, 復帰を行えるようにしたい. +そのためにはトポロジーに割り当てられた際に他ノードから自分の持っているデータとの +差分のデータを流してもらうといった機能が必要になってくる. %\subsection{Treeのバランスの問題} diff -r cff4aee4fcf6 -r 1d07365c60ff paper/master_paper.pdf Binary file paper/master_paper.pdf has changed