Mercurial > hg > Papers > 2014 > nobuyasu-master

comparison paper/chapter3.tex @ 56:1d07365c60ff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Writed conclstion
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Fri, 31 Jan 2014 21:37:40 +0900
parents faa708c2958b
children c5c761588168
comparison
equal deleted inserted replaced
55:cff4aee4fcf6 56:1d07365c60ff
1 \chapter{分散データベースJungleの設計} 1 \chapter{分散データベースJungleの設計}
2 2
3 \section{分散バージョン管理システムによるデータの分散}
4 Jungle は Git や Mercurial といった分散バージョン管理システムの機能を参考に作られている.
5 分散バージョン管理システムとは, 多人数によるソフトウェア開発において変更履歴を管理するシステムである.
6 % 反対の意味の言葉として集中型バージョン管理システムがある.
7 分散管理システムでは開発者それぞれがローカルにリポジトリのクローンを持ち, 開発はこのリポジトリを通すことで進められる(図\ref{fig:distributed_repo}).
8 ローカルのリポジトリは独立に損刺し, サーバ上にあるリポジトリや他人のリポジトリで行われた変更履歴を取り込みアップデートにかけることができる.
9 また逆に, ローカルのリポジトリに開発者自身がかけたアップデートを他のリポジトリへと反映させることもできる.
10 分散管理システムでは, どれかリポジトリが壊れたとしても, 別のリポジトリからクローンを行うことができる.
11 ネットワークに障害が発生しても, ローカルにある編集履歴をネットワーク復旧後に伝えることができる.
12 そのため, 可用性と分断耐性が高いと言える.
13 % 分散管理システムは結果整合性をとることを述べる.
14 % 結果整合性の話を先にどっかでしたほうがいいかも
15 \begin{figure}[htpb]
16 \begin{center}
17 \includegraphics[scale=0.7]{figures/distributed_repository.pdf}
18 \caption{分散バージョン管理システム}
19 \label{fig:distributed_repo}
20 \end{center}
21 \end{figure}
3 22
23
24 \subsection{マージによるデータ変更衝突の解決}
25 分散管理システムでは, データの更新時において衝突が発生する時がある.
26 それは, 分散管理システムを参考にしている Jungle においても起こる問題である.
27 データの変更を行うときには, 元のデータに編集が加えられている状態かもしれない.
28 Jungle はリクエストがきた場合, 現在もっているデータを返す.
29 そのためデータは最新のものであるかは保証されない.
30 この場合, 古いデータに編集が加えられ, それを更に最新のデータへ伝搬させなければならない.
31 このように他のリポジトリにより先にデータ編集が行われており, データの伝搬が素直にできない状態を
32 衝突という.
33 この衝突を解決する手段が必要である.
34 分散管理システムでは衝突に対してマージと呼ばれる作業で解決をはかる.
35 マージは, 相手のリポジトリのデータ編集履歴を受け取り, ローカルにあるリポジトリの編集と合わせる作業である.
36 データ衝突に対して Jungle はアプリケーションレベルでのマージを実装して貰うことで解決をはかる.
37
38 以下にマージが必要な場合とそうでない場合のデータ編集についての図を示す(図\ref{fig:tree_conflict1},\ref{fig:tree_conflict2},\ref{fig:tree_conflict3}).
39
40 \begin{figure}[htpb]
41 \begin{center}
42 \includegraphics[scale=0.48]{figures/tree_conflict.pdf}
43 \caption{衝突の発生しないデータ編集}
44 \label{fig:tree_conflict1}
45 \end{center}
46 \end{figure}
47
48 \begin{figure}[htpb]
49 \begin{center}
50 \includegraphics[scale=0.48]{figures/tree_conflict3.pdf}
51 \caption{自然に衝突を解決できるデータ編集}
52 \label{fig:tree_conflict2}
53 \end{center}
54 \end{figure}
55
56 \begin{figure}[htpb]
57 \begin{center}
58 \includegraphics[scale=0.48]{figures/tree_conflict2.pdf}
59 \caption{衝突が発生するデータ編集}
60 \label{fig:tree_conflict3}
61 \end{center}
62 \end{figure}
63
64
65 \section{ネットワークトポロジーの形成}
66 分散管理システムを参考に Jungle でもそれぞれのデータベースが独立に
67 動くようにしたい.
68 そのために必要なことはトポロジーの形成と, サーバノード間でのデータアクセス機構である.
69 また, データ分散のために形成したトポロジー上で扱うデータを決めなければならない.
70
71
72 \subsection{ツリートポロジーの形成}
73 分散データーベス Jungle で形成されるネットワークトポロジーはツリー構造を想定している.
74 ツリー構造ならば, データの整合性をとる場合, 一度トップまでデータを伝搬させることで行える.
75 トップもしくはトップまでの間にあるサーバノードでデータ伝搬中に衝突が発生したらマージを行い, マージの結果を改めて伝搬すれば
76 よいからである.
77 また, リング型, スター型, メッシュ側ではデータ編集の結果を他サーバノードに流すとき
78 流したデータが自分自身にくることにより発生するループに気をつける必要がある.
79 ツリー構造の場合は, サーバノード同士の繋がりで閉路が無い.
80 そのため, 自分自身が行ったデータ編集の履歴を繋がっているノードに送信するだけですむ.
81 このルーティングの方式はスプリットホライズンと呼ばれるものである.
82
83 \begin{figure}[htpb]
84 \begin{center}
85 \includegraphics[scale=0.70]{figures/network_topology_tree.pdf}
86 \caption{ツリー型のNetwork Topology}
87 \label{fig:topology_tree}
88 \end{center}
89 \end{figure}
90
91
92 \subsection{トポロジーの形成手段}
93 Jungle で使用するネットワークトポロジーはツリー型を考えているが, リング型やメッシュ型といった
94 他のネットワークトポロジーによる実装に関しても試す余地はある.
95 そのため, ツリーだけでなく, 自由にネットワークトポロジーの形成を行えるようにしたい.
96
97 \begin{figure}[htpb]
98 \begin{minipage}{0.5\hsize}
99 \begin{center}
100 \includegraphics[scale=0.7]{figures/network_topology_ring.pdf}
101 \caption{リング型のトポロジー}
102 \label{fig:topology_ring}
103 \end{center}
104 \end{minipage}
105 \begin{minipage}{0.5\hsize}
106 \begin{center}
107 \includegraphics[scale=0.7]{figures/topology_mesh.pdf}
108 \caption{メッシュ型のトポロジー}
109 \label{fig:topology_mesh}
110 \end{center}
111 \end{minipage}
112 \end{figure}
113
114
115 そこで当研究室で開発を行っている並列分散フレームワークである Alice を使用する.
116 Alice はユーザが望んだマシンへの接続や必要なデータへのアクセスを行う機構と, 接続トポロジー
117 形成機能を提供している.
118
119 % トポロジー形成の説明をする. 重要さなども。
120 % トポロジーの形成は容易ではない.
121 % Alice が必要な機能を提供してくれることを述べる
122 % Alice はトポロジー形成の機能を提供している
123 % トポロジー間でのデータの受け渡す機能も提供している
124
125
126 \section{並列分散フレームワークAlice}
127 Alice は当研究室で開発している並列分散フレームワークである.
128 Alice はデータを DataSegment, タスクを CodeSegment という単位で扱うプログラミングを提供している.
129 コードの部分となる CodeSegment は, 計算に必要なデータである DataSegment が揃い次第実行が行われる(図\ref{fig:cs_ds}).
130 CodeSegment の結果により出力される新たなデータでは, 別の CodeSegment が実行されるための DataSegment となる.
131 DataSegment と CodeSegment の組み合わせにより並列・分散プログラミングの依存関係が表される.
132
133 \begin{figure}[htpb]
134 \begin{center}
135 \includegraphics[scale=0.70]{figures/cs_ds.pdf}
136 \caption{DataSegment と CodeSegment によるプログラムの流れ}
137 \label{fig:cs_ds}
138 \end{center}
139 \end{figure}
140
141 \subsection{MessagePack によるシリアライズ}
142 Alice では DataSegment のデータ表現に MessagePack(http://msgpack.org) を利用している.
143 MessagePack はオブジェクトをバイナリへと変換させるシリアライズライブラリである.
144 Alice によりネットワークを介してデータにアクセスするときは, そのデータが MessagePack でシリアライズが
145 行えることが条件である.
146
147
148
149 \section{Jungle のデータ分散}
150 Alice によりトポロジーの形成とデータアクセスの機構が提供された.
151 後はデータ分散の為にどのデータをネットワークに流すのか決めなければならない.
152 そこで選ばれたのが TreeOperationLog である.
153 TreeOperationLog はデータ編集の履歴になる.
154 どの Node にどのような操作をしたのかという情報が入っている.
155 この TreeOperationLog を Alice を使って他サーバノードに送り, データの編集をしてもらうことで
156 同じデータを持つことが可能となる.
157 Alice を用いるため, この TreeOperationLog は MessagePack によりシリアライズ可能な形にすることが
158 必要である.
159
160
161 \subsection{CAP 定理と Jungle}
162 ここまでの Jungle の設計を踏まえて, CAP 定理における Jungle の立ち位置を考える.
163 分散管理バージョンのように独立したリポジトリもち, それぞれが独自の変更を加えることが
164 行えることで一貫性はゆるい.
165 だが, ネットワークから切断されてもローカルで行ったデータの変更をネットワーク復旧後で伝搬できる
166 ことと, リクエストに対し持っているデータをすぐに返すことができる.
167 つまり Jungle は可用性と分断耐性に優れたデータベースを目指している.
168 第2章で紹介した既存のデータベースと Jungle との CAP 定理の関係を図\ref{fig:cap_theorem}に示す.
169
170 \begin{figure}[htpb]
171 \begin{center}
172 \includegraphics[scale=0.7]{figures/cap_theorem.pdf}
173 \caption{CAP 定理における各データベースの立ち位置}
174 \label{fig:cap_theorem}
175 \end{center}
176 \end{figure}
177
178
179
180
181 \section{ログによるデータの永続性}
182 % TreeOperationLog(ログ)をシリアライズ可能な形にしてデータをおくること
183 % シリアライズできる形にしたものをそのままHDに書き出すだけでログの永続性は行える
184 Jungle は非破壊でさらにオンメモリにデータを保持するため, 使用するメモリの容量が大きくなる.
185 そのため, ハードディスクに書き出し, 一定の区切りで保持している過去のデータをメモリ上から掃除しなければならない.
186 そこで, ログによるデータの永続性の実装を行う.
187 ここでログをどのようなデータ表現でハードディスクへと書きだすかという問題が発生するが, これは Alice を使うことで
188 解決している.
189 Alice を用いるため MessagePack によりシリアライズ可能な TreeOperationLog ができる.
190 このシリアライズ可能な TreeOperationLog をそのままハードディスクへ書き込むこととでログの永続性ができる.
191
192
193
194
195