Mercurial > hg > Papers > 2014 > nobuyasu-master

comparison paper/chapter3.tex @ 101:1d5736ae832f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed chapter4.tex
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Sat, 15 Feb 2014 04:47:28 +0900
parents 5c5d71d36c14
children eac8620cf9cd
comparison
equal deleted inserted replaced
100:ae161408bc1c 101:1d5736ae832f
1 \chapter{分散データベースJungleの設計} 1 \chapter{分散データベースJungleの設計}
2 前章では木構造データベースJungleの仕様について述べた. 2 　前章では木構造データベースJungleの仕様について述べた.
3 非破壊的木構造によりデータを破壊せずに保持するJungleは, 過去のデータ 3 非破壊的木構造によりデータを破壊せずに保持するJungleは, 過去のデータ
4 もみることができる. 4 もみることができる.
5 また, データ編集をした際には, TreeOperationLogとして履歴が残る. 5 また, データ編集をした際には, TreeOperationLogとして履歴が残る.
6 Jungleが分散設計をするにあたり, 参考にしているシステムとして分散バージョン 6 Jungleで分散設計をするにあたり, 参考にしているシステムとして分散バージョン
7 管理システムがある. 7 管理システムがある.
8 本章では分散バージョン管理システムとは何かを説明し, Jungleの分散データベース 8 本章では, 分散バージョン管理システムとは何かを説明し, Jungleの分散データベース
9 の設計について述べる. 9 の設計について述べる.
10 10
11 \section{分散バージョン管理システムによるデータの分散} 11 \section{分散バージョン管理システムによるデータの分散}
12 Jungleの分散設計はGitやMercurial といった分散バージョン管理システム（以下, 分散管理システム）の機能を参考に作る. 12 Jungleの分散設計はGitやMercurial といった分散バージョン管理システム（以下, 分散管理システム）の機能を参考に作る.
13 分散管理システムとは, 多人数によるソフトウェア開発において変更履歴を管理するシステムである. 13 分散管理システムとは, 多人数によるソフトウェア開発において変更履歴を管理するシステムである.
14 % 反対の意味の言葉として集中型バージョン管理システムがある. 14 % 反対の意味の言葉として集中型バージョン管理システムがある.
15 分散管理システムでは開発者それぞれがローカルにリポジトリのクローンを持ち, 開発はこのリポジトリを通すことで進められる(図\ref{fig:distributed_repo}). 15 分散管理システムでは開発者それぞれがローカルにリポジトリのクローンを持ち, 開発はこのリポジトリを通すことで進められる(図\ref{fig:distributed_repo}).
16 ローカルのリポジトリは独立に存在し, サーバ上にあるリポジトリや他人のリポジトリで行われた変更履歴を取り込みアップデートにかけることができる. 16 ローカルのリポジトリは独立に存在し, サーバ上にあるリポジトリや他人のリポジトリで行われた変更履歴を取り込みアップデートにかけることができる.
17 また逆に, ローカルのリポジトリに開発者自身がかけたアップデートを他のリポジトリへと反映させることもできる. 17 また, 逆にローカルのリポジトリに開発者自身がかけたアップデートを他のリポジトリへと反映させることもできる.
18 分散管理システムでは, どれかリポジトリが壊れたとしても, 別のリポジトリからクローンを行うことができる. 18 分散管理システムでは, どれかリポジトリが壊れたとしても, 別のリポジトリからクローンを行うことができる.
19 ネットワークに障害が発生しても, ローカルにある編集履歴をネットワーク復旧後に伝えることができる. 19 ネットワークに障害が発生しても, ローカルにある編集履歴をネットワーク復旧後に伝えることができる.
20 そのため, 可用性と分断耐性が高いと言える. 20 そのため, 可用性と分断耐性が高いと言える.
21 % 分散管理システムは結果整合性をとることを述べる. 21 % 分散管理システムは結果整合性をとることを述べる.
22 % 結果整合性の話を先にどっかでしたほうがいいかも 22 % 結果整合性の話を先にどっかでしたほうがいいかも
28 \end{center} 28 \end{center}
29 \end{figure} 29 \end{figure}
30 30
31 31
32 \subsection{分散管理システムのAPI} 32 \subsection{分散管理システムのAPI}
33 分散管理システムでは主に次の3つのAPIを使用することで, データの 33 分散管理システムでは, 主に次の3つのAPIを使用することで, データの
34 分散を行っている. 34 分散を行っている.
35 \begin{itemize} 35 \begin{itemize}
36 \item commit\\ 36 \item commit\\
37 前のバージョンのデータに変更を加えたことをリポジトリに登録する. 37 前のバージョンのデータに変更を加えたことをリポジトリに登録する.
38 \item push\\ 38 \item push\\
39 ローカルのリポジトリで行った変更履歴を別リポジトリへと伝える. 39 ローカルのリポジトリで行った変更履歴を別リポジトリへと伝える.
40 \item pull\\ 40 \item pull\\
41 他のリポジトリの変更履歴をローカルのリポジトリに受け取る. 41 他のリポジトリの変更履歴をローカルのリポジトリに受け取る.
42 \end{itemize} 42 \end{itemize}
43 commitによりローカルのリポジトリに変更履歴が積み重なり, pushをすることで 43 　commitによりローカルのリポジトリに変更履歴が積み重なり, pushをすることで
44 他のリポジトリにローカルで行ったデータ変更を伝える. 44 他のリポジトリにローカルで行ったデータ変更を伝える.
45 また, pullに好きなタイミングでデータの更新履歴を受け取ることができる. 45 また, pullに好きなタイミングでデータの更新履歴を受け取ることができる.
46 46
47 分散管理システムはデータ変更の履歴は自由に受け取ることが 47 分散管理システムはデータ変更の履歴を自由に受け取ることが
48 できるが, その変更履歴をそのまま適応できないときがある. 48 できるが, その変更履歴をそのまま適応できないときがある.
49 それはお互いが同じデータに対して編集を行っている場合である. 49 それはお互いが同じデータに対して編集を行っている場合である.
50 この状態を衝突という. 50 この状態を衝突という.
51 この衝突を解決する方法としてMergeがある. 51 この衝突を解決する方法としてMergeがある.
52 Mergeは衝突を起こしたデータ両方の編集履歴を適応したデータを作ることである. 52 Mergeは衝突を起こしたデータ両方の編集履歴を適用したデータを作ることである.
53 分散管理システムではこの衝突を解決する方法が必要になる. 53 分散管理システムではこの衝突を解決する方法が必要になる.
54 54
55 \subsection{Mergeによるデータ変更衝突の解決} 55 \subsection{Mergeによるデータ変更衝突の解決}
56 分散管理システムでは, データの更新時において衝突が発生する時がある. 56 分散管理システムでは, データの更新時において衝突が発生する時がある.
57 それは, 分散管理システムを参考にしている Jungle においても起こる問題である. 57 それは, 分散管理システムを参考にしている Jungle においても起こる問題である.
60 そのためデータは最新のものであるかは保証されない. 60 そのためデータは最新のものであるかは保証されない.
61 この場合, 古いデータに編集が加えられ, それを更に最新のデータへ伝搬させなければならない. 61 この場合, 古いデータに編集が加えられ, それを更に最新のデータへ伝搬させなければならない.
62 このように他のリポジトリにより先にデータ編集が行われており, データの伝搬が素直にできない状態を 62 このように他のリポジトリにより先にデータ編集が行われており, データの伝搬が素直にできない状態を
63 衝突という. 63 衝突という.
64 この衝突を解決する手段が必要である. 64 この衝突を解決する手段が必要である.
65 分散管理システムでは衝突に対してMergeと呼ばれる作業で解決をはかる. 65 分散管理システムでは, 衝突に対してMergeと呼ばれる作業で解決をはかる.
66 Mergeは, 相手のリポジトリのデータ編集履歴を受け取り, ローカルにあるリポジトリの編集と合わせる作業である. 66 Mergeは, 相手のリポジトリのデータ編集履歴を受け取り, ローカルにあるリポジトリの編集と合わせる作業である.
67 データ衝突に対して Jungle はアプリケーションレベルでのMergeを実装して貰うことで解決をはかる. 67 データ衝突に対して Jungle はアプリケーションレベルでのMergeを実装することで解決をはかる.
68 68
69 以下にMergeが必要な場合とそうでない場合のデータ編集についての図を示す(図\ref{fig:tree_conflict1},\ref{fig:tree_conflict2},\ref{fig:tree_conflict3}). 69 以下にMergeが必要な場合とそうでない場合のデータ編集についての図を示す(図\ref{fig:tree_conflict1},\ref{fig:tree_conflict2},\ref{fig:tree_conflict3}).
70 70
71 \begin{figure}[htpb] 71 \begin{figure}[htpb]
72 \begin{center} 72 \begin{center}
103 103
104 \subsection{ツリートポロジーの形成とルーティング} 104 \subsection{ツリートポロジーの形成とルーティング}
105 分散データーベス Jungle で形成されるネットワークトポロジーはツリー構造を想定している. 105 分散データーベス Jungle で形成されるネットワークトポロジーはツリー構造を想定している.
106 ツリー構造ならば, データの整合性をとる場合, 一度トップまでデータを伝搬させることで行える. 106 ツリー構造ならば, データの整合性をとる場合, 一度トップまでデータを伝搬させることで行える.
107 トップもしくはトップまでの間にあるサーバノードでデータ伝搬中に衝突が発生したらMergeを行い, Mergeの結果を改めて伝搬すれば 107 トップもしくはトップまでの間にあるサーバノードでデータ伝搬中に衝突が発生したらMergeを行い, Mergeの結果を改めて伝搬すれば
108 よいからである. 108 よいからである(図\ref{fig:topology_tree}).
109 また, リング型, スター型, メッシュ側ではデータ編集の結果を他サーバノードに流すとき 109 %また, リング型, スター型, メッシュ側ではデータ編集の結果を他サーバノードに流すとき
110 また, リング型(図\ref{fig:topology_ring}), メッシュ型(図\ref{fig:topology_mesh})ではデータ編集の結果を他サーバノードに流すとき
110 流したデータが自分自身にくることにより発生するループに気をつける必要がある. 111 流したデータが自分自身にくることにより発生するループに気をつける必要がある.
111 ツリー構造の場合は, サーバノード同士の繋がりで閉路が無い. 112 ツリー構造の場合は, サーバノード同士の繋がりで閉路が無い.
112 そのため, 自分自身が行ったデータ編集の履歴を繋がっているノードに送信するだけですむ. 113 そのため, 自分自身が行ったデータ編集の履歴を繋がっているノードに送信するだけですむ.
113 このルーティングの方式はスプリットホライズンと呼ばれるものである. 114 このルーティングの方式はスプリットホライズンと呼ばれるものである.
114 115