Mercurial > hg > Papers > 2014 > nobuyasu-master

annotate paper/chapter2.tex @ 48:6553b7a3717c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Modified chapter3
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Fri, 31 Jan 2014 09:31:57 +0900
parents b303f22d8b0d
children faa708c2958b
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
25
67880a2ca650 Modfied chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
1 \chapter{木構造データベースJungleの分散設計}
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
2 Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
3 一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
4 ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している.
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
5 現在 Java と Haskell によりそれぞれ言語で開発されており本研究で扱うのは Java 版である.
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
6
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
7 本章ではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ分散の設計について述べる.
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
8 \subsection{破壊的木構造}
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
9 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
10 図\ref{fig:destractive}は破壊的木構造の編集を表している.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
11
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
12 \begin{figure}[htpb]
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
13 \begin{center}
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
14 \includegraphics[scale=0.7]{figures/destructive_tree.pdf}
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
15 \caption{破壊的木構造の編集}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
16 \label{fig:destractive}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
17 \end{center}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
18 \end{figure}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
19
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
20 破壊的木構造は, 編集を行う際に木のロックを掛ける必要がある.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
21 この時, データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり, 閲覧者が
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
22 いる場合は木の走査が終わるまで書き換えをまたなければならない.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
23 これではロックによりスケーラビリティが損なわれてしまう.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
24
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
25 \subsection{非破壊的木構造}
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
26 非破壊的木構造は破壊的木構造とは違い, 一度作成した木を破壊することはない.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
27 非破壊的木構造においてデータの編集は, ルートから編集を行うノードまでコピーを
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
28 行い新しく木構造を作成することで行われる.
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
29 図\ref{fig:nondestractive}は非破壊的木構造のデータ編集を示している.
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
30
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
31 \begin{figure}[htpb]
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
32 \begin{center}
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
33 \includegraphics[scale=0.7]{figures/non_destructive_tree.pdf}
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
34 \caption{非破壊的木構造の編集}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
35 \label{fig:nondestractive}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
36 \end{center}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
37 \end{figure}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
38
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
39 非破壊的木構造におけるデータ編集の手順を以下に示す.
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
40
7
8afa5d2f1459 Added discription of how to non destractive edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
41 \begin{enumerate}
8afa5d2f1459 Added discription of how to non destractive edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
42 \item ルートから編集を行うノードまでのパスを調べる(図\ref{fig:nondestractive_edit1}).
8afa5d2f1459 Added discription of how to non destractive edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
43 \item 編集を行うノードのコピーをとる. コピーをとったノードへデータの編集を行う(図\ref{fig:nondestractive_edit2}).
8afa5d2f1459 Added discription of how to non destractive edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
44 \item 調べたパスに従いルートからコピーしたノードまでの間のノードのコピーをとり繋げる(図\ref{fig:nondestractive_edit3}).
8
7072254f5e11 Modified some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
45 \item コピーしたルートノードは編集を行っていないノードへの参照を貼り新しい木構造を作る(図\ref{fig:nondestractive_edit4}).
7
8afa5d2f1459 Added discription of how to non destractive edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
46 \end{enumerate}
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
47
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
48 \begin{figure}[htpb]
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
49 \begin{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
50 \includegraphics[scale=0.7]{figures/non_destructive_edit1.pdf}
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
51 \caption{非破壊的木構造の編集手順1}
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
52 \label{fig:nondestractive_edit1}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
53 \end{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
54 \end{figure}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
55
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
56 \begin{figure}[htpb]
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
57 \begin{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
58 \includegraphics[scale=0.7]{figures/non_destructive_edit2.pdf}
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
59 \caption{非破壊的木構造の編集手順2}
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
60 \label{fig:nondestractive_edit2}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
61 \end{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
62 \end{figure}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
63
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
64 \begin{figure}[htpb]
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
65 \begin{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
66 \includegraphics[scale=0.7]{figures/non_destructive_edit3.pdf}
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
67 \caption{非破壊的木構造の編集手順3}
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
68 \label{fig:nondestractive_edit3}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
69 \end{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
70 \end{figure}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
71
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
72 \begin{figure}[htpb]
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
73 \begin{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
74 \includegraphics[scale=0.7]{figures/non_destructive_edit4.pdf}
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
75 \caption{非破壊的木構造の編集手順4}
6
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
76 \label{fig:nondestractive_edit4}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
77 \end{center}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
78 \end{figure}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
79
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
80 \newpage
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
81
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
82 非破壊的木構造においてデータのロックが必要となる部分は, 木のコピーを作終えた後に
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
83 ルートノードを更新するときだけである.
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
84 データ編集を行っている間ロックが必要な破壊的木構造に比べ, 編集中においてもデータの読み込みが
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
85 可能である(図\ref{fig:nondestractive_merit}).
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
86 そのため, 破壊的木構造に比べスケールがしやすくなっている.
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
87
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
88 \begin{figure}[htpb]
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
89 \begin{center}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
90 \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
91 \caption{非破壊的木構造による利点}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
92 \label{fig:nondestractive_merit}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
93 \end{center}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
94 \end{figure}
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
95
9
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
96
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
97 \section{Jungle におけるデータへのアクセス}
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
98 Jungle ではデータをそれぞれの Node が attribute として保持する.
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
99 attribute は String 型の Key と ByteBuffer の value のペアにより表される.
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
100 Jungle でデータへのアクセスは, この Node へのアクセスをさす.
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
101 Node へのアクセスは, 木の名前と Node を指すパスにより行える.
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
102 このパスは NodePath と呼ばれる(図\ref{fig:nodepath}).
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
103
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
104 \begin{figure}[htpb]
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
105 \begin{center}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
106 \includegraphics[scale=0.7]{figures/nodepath.pdf}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
107 \caption{Node の attribute と NodePath}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
108 \label{fig:nodepath}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
109 \end{center}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
110 \end{figure}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
111
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
112
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
113
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
114 \section{Jungle におけるデータ編集}
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
115
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
116 \subsection{NodeOperation}
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
117 Jungle による最小のデータ編集は Node の編集を指す.
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
118 Node 編集のために API が用意されており, この API は NodeOperation と呼ばれる.
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
119 NodeOperation には次の4つの API が用意されている.
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
120 \begin{itemize}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
121 \item \verb|addNewChild(NodePath _path, int _pos)|
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
122 NodePath で指定された Node に子供となる Node を追加する API である.
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
123 pos で指定された番号に子供として追加を行う.
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
124 \item \verb|deleteChildAt(NodePath _path, int _pos)|
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
125 NodePath と pos により指定される Node を削除する API である.
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
126 \item \verb|putAttribute(NodePath _path, String _key, ByteBuffer _value)|
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
127 Node に attribute を追加する API である.
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
128 NodePath は attribute を追加する Node を指す.
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
129 \item \verb|deleteAttribute(NodePath _path, String _key)|
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
130 \verb|_key| が示す attribute の削除を行う API である.
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
131 NodePath は Node を示す.
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
132 \end{itemize}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
133
47
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
134 NodeOperationはNodePathとセットで扱わなければならず, このセットを
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
135 TreeOperationという.
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
136 TreeOperationが1つのデータ編集の単位になるが, これはあくまで最小のデータ編集の単位である.
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
137 Jungle によるデータの編集はTreeOperationが複数集まった単位でcommitされていく.
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
138 このTreeOperationの集まりをTreeOperationLogという.
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
139
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
140 \subsection{TreeOperationLog}
47
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
141 Jungle 内部ではTreeOperationは順次ログに積まれていき, 最終的に
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
142 commitされることで編集が完了する.
b303f22d8b0d Modified
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
143 この時, ログに積まれた複数のTreeOperationはTreeOperationLogとして扱われる.
48
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
144 TreeOperationLogの仕様を\ref{src:treeoperationlog}に示す.
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
145 \begin{lstlisting}[frame=lrbt,label=src:treeoperationlog,caption=TreeOperationLogの仕様,numbers=left]
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
146 public interface TreeOperationLog extends Iterable<TreeOperation>
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
147 {
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
148 public TreeOperationLog add(NodePath _p,NodeOperation _op);
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
149 public TreeOperationLog append(TreeOperationLog _log);
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
150 public int length();
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
151 }
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
152 \end{lstlisting}
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
153 \verb|Iterable<TreeOperation>|を継承しているためIteratorによりTreeOperationを取り出せるようになっている.
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
154 addやappendメソッドを使ってTreeOperationを積み上げていくことができる
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
155
6553b7a3717c Modified chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
156 次にデータ編集により発生するTreeOperationLogの具体的な例を示す(\ref{src:treelog}).
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
157 \begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left]
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
158 [APPEND_CHILD:<-1>:pos:0]
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
159 [PUT_ATTRIBUTE:<-1,0>:key:author,value:oshiro]
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
160 [PUT_ATTRIBUTE:<-1,0>:key:mes,value:hello]
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
161 [PUT_ATTRIBUTE:<-1,0>:key:timestamp,value:0]
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
162 \end{lstlisting}
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
163 このログは今回の研究で使用したベンチマーク用掲示板プログラムにおける書き込みにより行われるログである(図\ref{fig:treeoperationlog}).
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
164
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
165 大文字の英字は実行した NodeOperation の種類を表す.
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
166 \verb|<>| により囲まれている数字は NodePath を示す.
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
167 NodePath の表記以降は Node の position や attribute の情報を表している.
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
168 \begin{figure}[htpb]
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
169 \begin{center}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
170 \includegraphics[scale=0.7]{figures/treeoperationlog1.pdf}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
171 \caption{TreeOperationLog の具体例}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
172 \label{fig:treeoperationlog}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
173 \end{center}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
174 \end{figure}
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
175
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
176 図\ref{fig:treeoperationlog}の説明を行う.
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
177 まず, \verb|APPEND_CHILD| により Root Node の 0 番目の子供となる Node の追加を行う.
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
178 次に, 追加を行った Node に対して \verb|PUT_ATTRIBUTE| により attribute の情報を持たせていく.
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
179 attribute の内容に作者の情報を表す auther, メッセージの内容を表す mes, そしてタイムスタンプ
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
180 を timestamp とそれぞれキーにすることで追加される.
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
181
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 30
diff changeset
182 以上が掲示板プログラムにおける1つの書き込みで発生する TreeOperationLog である.
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
183
28
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
184 \section{分散バージョン管理システムによるデータの分散}
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
185 Jungle は Git や Mercurial といった分散バージョン管理システムの機能を参考に作られている.
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
186 分散バージョン管理システムとは, 多人数によるソフトウェア開発において変更履歴を管理するシステムである.
29
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
187 % 反対の意味の言葉として集中型バージョン管理システムがある.
28
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
188 分散管理システムでは開発者それぞれがローカルにリポジトリのクローンを持ち, 開発はこのリポジトリを通すことで進められる(図\ref{fig:distributed_repo}).
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
189 ローカルのリポジトリは独立に損刺し, サーバ上にあるリポジトリや他人のリポジトリで行われた変更履歴を取り込みアップデートにかけることができる.
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
190 また逆に, ローカルのリポジトリに開発者自身がかけたアップデートを他のリポジトリへと反映させることもできる.
29
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
191 分散管理システムでは, どれかリポジトリが壊れたとしても, 別のリポジトリからクローンを行うことができる.
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
192 ネットワークに障害が発生しても, ローカルにある編集履歴をネットワーク復旧後に伝えることができる.
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
193 そのため, 可用性と分断耐性が高いと言える.
28
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
194 % 分散管理システムは結果整合性をとることを述べる.
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
195 % 結果整合性の話を先にどっかでしたほうがいいかも
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
196 \begin{figure}[htpb]
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
197 \begin{center}
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
198 \includegraphics[scale=0.7]{figures/distributed_repository.pdf}
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
199 \caption{分散バージョン管理システム}
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
200 \label{fig:distributed_repo}
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
201 \end{center}
41200e0b6831 Added distrubited_repository
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
202 \end{figure}
27
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
203
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
204
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
205 \subsection{マージによるデータ変更衝突の解決}
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
206 分散管理システムでは, データの更新時において衝突が発生する時がある.
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
207 それは, 分散管理システムを参考にしている Jungle においても起こる問題である.
29
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
208 データの変更を行うときには, 元のデータに編集が加えられている状態かもしれない.
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
209 Jungle はリクエストがきた場合, 現在もっているデータを返す.
27
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
210 そのためデータは最新のものであるかは保証されない.
29
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
211 この場合, 古いデータに編集が加えられ, それを更に最新のデータへ伝搬させなければならない.
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
212 このように他のリポジトリにより先にデータ編集が行われており, データの伝搬が素直にできない状態を
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
213 衝突という.
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
214 この衝突を解決する手段が必要である.
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
215 分散管理システムでは衝突に対してマージと呼ばれる作業で解決をはかる.
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
216 マージは, 相手のリポジトリのデータ編集履歴を受け取り, ローカルにあるリポジトリの編集と合わせる作業である.
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
217 データ衝突に対して Jungle はアプリケーションレベルでのマージを実装して貰うことで解決をはかる.
27
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
218
36
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
219 以下にマージが必要な場合とそうでない場合のデータ編集についての図を示す(図\ref{fig:tree_conflict1},\ref{fig:tree_conflict2},\ref{fig:tree_conflict3}).
29
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
220
27
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
221 \begin{figure}[htpb]
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
222 \begin{center}
29
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
223 \includegraphics[scale=0.48]{figures/tree_conflict.pdf}
30
92bc4faa9a37 Added benchmark images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 29
diff changeset
224 \caption{衝突の発生しないデータ編集}
27
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
225 \label{fig:tree_conflict1}
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
226 \end{center}
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
227 \end{figure}
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
228
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
229 \begin{figure}[htpb]
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
230 \begin{center}
29
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
231 \includegraphics[scale=0.48]{figures/tree_conflict3.pdf}
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
232 \caption{自然に衝突を解決できるデータ編集}
36
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
233 \label{fig:tree_conflict2}
29
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
234 \end{center}
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
235 \end{figure}
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
236
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
237 \begin{figure}[htpb]
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
238 \begin{center}
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
239 \includegraphics[scale=0.48]{figures/tree_conflict2.pdf}
13cfa2b88fd1 Modified distributed management system
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
240 \caption{衝突が発生するデータ編集}
36
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
241 \label{fig:tree_conflict3}
27
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
242 \end{center}
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
243 \end{figure}
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
244
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
245
34
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
246 \section{ネットワークトポロジーの形成}
32
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
247 分散管理システムを参考に Jungle でもそれぞれのデータベースが独立に
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
248 動くようにしたい.
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
249 そのために必要なことはトポロジーの形成と, サーバノード間でのデータアクセス機構である.
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
250 また, データ分散のために形成したトポロジー上で扱うデータを決めなければならない.
27
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
251
34
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
252
32
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
253 \subsection{ツリートポロジーの形成}
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
254 分散データーベス Jungle で形成されるネットワークトポロジーはツリー構造を想定している.
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
255 ツリー構造ならば, データの整合性をとる場合, 一度トップまでデータを伝搬させることで行える.
34
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
256 トップもしくはトップまでの間にあるサーバノードでデータ伝搬中に衝突が発生したらマージを行い, マージの結果を改めて伝搬すれば
32
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
257 よいからである.
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
258 また, リング型, スター型, メッシュ側ではデータ編集の結果を他サーバノードに流すとき
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
259 流したデータが自分自身にくることにより発生するループに気をつける必要がある.
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
260 ツリー構造の場合は, サーバノード同士の繋がりで閉路が無い.
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
261 そのため, 自分自身が行ったデータ編集の履歴を繋がっているノードに送信するだけですむ.
33
a843327cde83 Writed CAP theorem
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
262 このルーティングの方式はスプリットホライズンと呼ばれるものである.
27
1abd3c17cff9 Added tree_conflict figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
263
34
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
264 \begin{figure}[htpb]
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
265 \begin{center}
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
266 \includegraphics[scale=0.70]{figures/network_topology_tree.pdf}
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
267 \caption{ツリー型のNetwork Topology}
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
268 \label{fig:topology_tree}
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
269 \end{center}
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
270 \end{figure}
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
271
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
272
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
273 \subsection{トポロジーの形成手段}
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
274 Jungle で使用するネットワークトポロジーはツリー型を考えているが, リング型やメッシュ型といった
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
275 他のネットワークトポロジーによる実装に関しても試す余地はある.
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
276 そのため, ツリーだけでなく, 自由にネットワークトポロジーの形成を行えるようにしたい.
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
277
35
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
278 \begin{figure}[htpb]
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
279 \begin{minipage}{0.5\hsize}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
280 \begin{center}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
281 \includegraphics[scale=0.7]{figures/network_topology_ring.pdf}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
282 \caption{リング型のトポロジー}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
283 \label{fig:topology_ring}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
284 \end{center}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
285 \end{minipage}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
286 \begin{minipage}{0.5\hsize}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
287 \begin{center}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
288 \includegraphics[scale=0.7]{figures/topology_mesh.pdf}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
289 \caption{メッシュ型のトポロジー}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
290 \label{fig:topology_mesh}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
291 \end{center}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
292 \end{minipage}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
293 \end{figure}
2849dc0ea23a Modified description of network topology
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 34
diff changeset
294
36
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
295
34
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
296 そこで当研究室で開発を行っている並列分散フレームワークである Alice を使用する.
36
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
297 Alice はユーザが望んだマシンへの接続や必要なデータへのアクセスを行う機構と, 接続トポロジー
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
298 形成機能を提供している.
34
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
299
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
300 % トポロジー形成の説明をする. 重要さなども。
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
301 % トポロジーの形成は容易ではない.
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
302 % Alice が必要な機能を提供してくれることを述べる
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
303 % Alice はトポロジー形成の機能を提供している
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
304 % トポロジー間でのデータの受け渡す機能も提供している
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
305
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
306
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
307 \section{並列分散フレームワークAlice}
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
308 Alice は当研究室で開発している並列分散フレームワークである.
36
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
309 Alice はデータを DataSegment, タスクを CodeSegment という単位で扱うプログラミングを提供している.
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
310 コードの部分となる CodeSegment は, 計算に必要なデータである DataSegment が揃い次第実行が行われる(図\ref{fig:cs_ds}).
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
311 CodeSegment の結果により出力される新たなデータでは, 別の CodeSegment が実行されるための DataSegment となる.
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
312 DataSegment と CodeSegment の組み合わせにより並列・分散プログラミングの依存関係が表される.
34
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
313
36
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
314 \begin{figure}[htpb]
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
315 \begin{center}
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
316 \includegraphics[scale=0.70]{figures/cs_ds.pdf}
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
317 \caption{DataSegment と CodeSegment によるプログラムの流れ}
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
318 \label{fig:cs_ds}
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
319 \end{center}
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
320 \end{figure}
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
321
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
322 \subsection{MessagePack によるシリアライズ}
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
323 Alice では DataSegment のデータ表現に MessagePack(http://msgpack.org) を利用している.
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
324 MessagePack はオブジェクトをバイナリへと変換させるシリアライズライブラリである.
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
325 Alice によりネットワークを介してデータにアクセスするときは, そのデータが MessagePack でシリアライズが
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
326 行えることが条件である.
34
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
327
7a829a3c2e19 Added topology figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 33
diff changeset
328
36
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
329
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
330 \section{Jungle のデータ分散}
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
331 Alice によりトポロジーの形成とデータアクセスの機構が提供された.
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
332 後はデータ分散の為にどのデータをネットワークに流すのか決めなければならない.
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
333 そこで選ばれたのが TreeOperationLog である.
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
334 TreeOperationLog はデータ編集の履歴になる.
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
335 どの Node にどのような操作をしたのかという情報が入っている.
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
336 この TreeOperationLog を Alice を使って他サーバノードに送り, データの編集をしてもらうことで
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
337 同じデータを持つことが可能となる.
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
338 Alice を用いるため, この TreeOperationLog は MessagePack によりシリアライズ可能な形にすることが
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
339 必要である.
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
340
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
341
36
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
342 \subsection{CAP 定理と Jungle}
32
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
343 ここまでの Jungle の設計を踏まえて, CAP 定理における Jungle の立ち位置を考える.
33
a843327cde83 Writed CAP theorem
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
344 分散管理バージョンのように独立したリポジトリもち, それぞれが独自の変更を加えることが
a843327cde83 Writed CAP theorem
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
345 行えることで一貫性はゆるい.
a843327cde83 Writed CAP theorem
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
346 だが, ネットワークから切断されてもローカルで行ったデータの変更をネットワーク復旧後で伝搬できる
a843327cde83 Writed CAP theorem
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
347 ことと, リクエストに対し持っているデータをすぐに返すことができる.
a843327cde83 Writed CAP theorem
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
348 つまり Jungle は可用性と分断耐性に優れたデータベースを目指している.
a843327cde83 Writed CAP theorem
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 32
diff changeset
349 第2章で紹介した既存のデータベースと Jungle との CAP 定理の関係を図\ref{fig:cap_theorem}に示す.
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
350
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
351 \begin{figure}[htpb]
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
352 \begin{center}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
353 \includegraphics[scale=0.7]{figures/cap_theorem.pdf}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
354 \caption{CAP 定理における各データベースの立ち位置}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
355 \label{fig:cap_theorem}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
356 \end{center}
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
357 \end{figure}
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
358
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
359
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
360
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
361
44
618adf0a9b2b Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 38
diff changeset
362 \section{ログによるデータの永続性}
36
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
363 % TreeOperationLog(ログ)をシリアライズ可能な形にしてデータをおくること
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
364 % シリアライズできる形にしたものをそのままHDに書き出すだけでログの永続性は行える
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
365 Jungle は非破壊でさらにオンメモリにデータを保持するため, 使用するメモリの容量が大きくなる.
38
559589aec976 Writed how to use alice topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
366 そのため, ハードディスクに書き出し, 一定の区切りで保持している過去のデータをメモリ上から掃除しなければならない.
36
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
367 そこで, ログによるデータの永続性の実装を行う.
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
368 ここでログをどのようなデータ表現でハードディスクへと書きだすかという問題が発生するが, これは Alice を使うことで
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
369 解決している.
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
370 Alice を用いるため MessagePack によりシリアライズ可能な TreeOperationLog ができる.
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
371 このシリアライズ可能な TreeOperationLog をそのままハードディスクへ書き込むこととでログの永続性ができる.
26
388cd4555b3d Added neo4j_replica, mongodb_sharding and cassandra_ring
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
372
36
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
373
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
374
65bd1b1250e9 Modified chapter2
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 35
diff changeset
375