Mercurial > hg > Papers > 2014 > nobuyasu-master

annotate paper/chapter3.tex @ 72:97d4c219ae76

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