Mercurial > hg > Papers > 2014 > nobuyasu-master
annotate paper/chapter2.tex @ 22:56753cfbeeab
Added merge_imp.pdf
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 23 Jan 2014 19:05:44 +0900 |
parents | a7fbd5db80fb |
children | 67880a2ca650 |
rev | line source |
---|---|
9
c09b83fe37ef
Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
8
diff
changeset
|
1 \chapter{木構造データベースJungleの実装と分散設計} |
22
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
2 |
20 | 3 |
10
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
4 |
4
d42d2acf5d1d
Added some tex files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 \section{木構造データベースJungle} |
5
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
6 Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである. |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
7 一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
8 ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している. |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
9 |
10
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
10 まず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ編集の実装について述べる. |
6
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
11 \subsection{破壊的木構造} |
5
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
12 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う. |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
13 図\ref{fig:destractive}は破壊的木構造の編集を表している. |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
14 |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
15 \begin{figure}[htpb] |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
16 \begin{center} |
10
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
17 \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
|
18 \caption{破壊的木構造の編集} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
19 \label{fig:destractive} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
20 \end{center} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
21 \end{figure} |
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 この時, データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり, 閲覧者が |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
25 いる場合は木の走査が終わるまで書き換えをまたなければならない. |
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 |
6
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
28 \subsection{非破壊的木構造} |
5
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
29 非破壊的木構造は破壊的木構造とは違い, 一度作成した木を破壊することはない. |
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 行い新しく木構造を作成することで行われる. |
6
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
32 図\ref{fig:nondestractive}は非破壊的木構造のデータ編集を示している. |
5
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
33 |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
34 \begin{figure}[htpb] |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
35 \begin{center} |
6
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
36 \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
|
37 \caption{非破壊的木構造の編集} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
38 \label{fig:nondestractive} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
39 \end{center} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
40 \end{figure} |
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
41 |
6
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
42 非破壊的木構造におけるデータ編集の手順を以下に示す. |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
43 |
7
8afa5d2f1459
Added discription of how to non destractive edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
6
diff
changeset
|
44 \begin{enumerate} |
8afa5d2f1459
Added discription of how to non destractive edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
6
diff
changeset
|
45 \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
|
46 \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
|
47 \item 調べたパスに従いルートからコピーしたノードまでの間のノードのコピーをとり繋げる(図\ref{fig:nondestractive_edit3}). |
8
7072254f5e11
Modified some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
7
diff
changeset
|
48 \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
|
49 \end{enumerate} |
6
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
50 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
51 \begin{figure}[htpb] |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
52 \begin{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
53 \includegraphics[scale=0.7]{figures/non_destructive_edit1.pdf} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
54 \caption{非破壊的木構造の編集1} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
55 \label{fig:nondestractive_edit1} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
56 \end{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
57 \end{figure} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
58 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
59 \begin{figure}[htpb] |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
60 \begin{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
61 \includegraphics[scale=0.7]{figures/non_destructive_edit2.pdf} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
62 \caption{非破壊的木構造の編集2} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
63 \label{fig:nondestractive_edit2} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
64 \end{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
65 \end{figure} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
66 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
67 \begin{figure}[htpb] |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
68 \begin{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
69 \includegraphics[scale=0.7]{figures/non_destructive_edit3.pdf} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
70 \caption{非破壊的木構造の編集3} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
71 \label{fig:nondestractive_edit3} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
72 \end{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
73 \end{figure} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
74 |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
75 \begin{figure}[htpb] |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
76 \begin{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
77 \includegraphics[scale=0.7]{figures/non_destructive_edit4.pdf} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
78 \caption{非破壊的木構造の編集4} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
79 \label{fig:nondestractive_edit4} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
80 \end{center} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
81 \end{figure} |
f47f11ea0e28
Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
5
diff
changeset
|
82 |
10
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
83 \newpage |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
84 |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
85 非破壊的木構造により, データの読み込みと編集を同時に行うことが可能になる. |
5
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
86 |
10
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
87 \begin{figure}[htpb] |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
88 \begin{center} |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
89 \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
|
90 \caption{非破壊的木構造による利点} |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
91 \label{fig:nondestractive_merit} |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
92 \end{center} |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
93 \end{figure} |
5
a6aa6af4b80f
Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
94 |
9
c09b83fe37ef
Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
8
diff
changeset
|
95 |
c09b83fe37ef
Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
8
diff
changeset
|
96 |
10
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
97 \section{Jungleにおけるデータ編集} |
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 のペアにより表される. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
100 Jungle でデータ編集を行う場合, この Node に対して削除や attribute の追加等を行うことを指す. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
101 どの Node へデータの編集を行うかはパスで示す. |
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 |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
112 Node の編集は Node の追加・削除, それと attribute の追加・削除を行うことを指す. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
113 Node の編集のためには次の4つの API が用意されている. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
114 \begin{itemize} |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
115 \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
|
116 NodePath で指定された Node に子供となる Node を追加する API である. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
117 pos で指定された番号に子供として追加を行う. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
118 \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
|
119 NodePath と pos により指定される Node を削除する API である. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
120 \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
|
121 Node に attribute を追加する API である. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
122 NodePath は attribute を追加する Node を指す. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
123 \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
|
124 \verb|_key| が示す attribute の削除を行う API である. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
125 NodePath は Node を示す. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
126 \end{itemize} |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
127 |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
128 この Node 編集の為の API は NodeOperation と呼ばれる. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
129 \subsection{TreeOperationLog} |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
130 API を使用すると, Jungle 内部では NodeOperation として順次ログに積まれていき, 最終的に |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
131 commit されることで編集が行われる. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
132 この時ログに積まれる複数の NodeOperation を TreeOperationLog という. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
133 Jungle ではこの TreeOperationLog 単位でデータの編集が行われる. |
22
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
134 以下に TreeOperationLog の具体的な例を示す(\ref{src:treelog}). |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
135 \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
|
136 [APPEND_CHILD:<-1>:pos:0] |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
137 [PUT_ATTRIBUTE:<-1,1>:key:author,value:oshiro] |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
138 [PUT_ATTRIBUTE:<-1,1>:key:mes,value:hello] |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
139 [PUT_ATTRIBUTE:<-1,1>:key:key,value:hoge] |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
140 [PUT_ATTRIBUTE:<-1,1>:key:timestamp,value:0] |
22
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
141 \end{lstlisting} |
10
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
142 このログは今回の研究で使用したベンチマーク用掲示板プログラムにおける書き込みにより行われるログである(図\ref{fig:treeoperationlog}). |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
143 |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
144 大文字の英字は実行した NodeOperation を表す. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
145 <> により囲まれている数字は NodePath を示す. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
146 NodePath の表記以降は Node の position や attribute の情報を表している. |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
147 \begin{figure}[htpb] |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
148 \begin{center} |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
149 \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
|
150 \caption{TreeOperationLog の具体例} |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
151 \label{fig:treeoperationlog} |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
152 \end{center} |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
153 \end{figure} |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
154 |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
155 |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
156 |
22
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
157 \section{データ衝突時におけるマージによる解決} |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
158 Jungle への分散実装を行うことである問題が発生する. |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
159 それは更新されたデータ同士が衝突を起こした時の処理である. |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
160 Jungle はリクエストがきた場合, 現在もっているデータを返す. |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
161 しかしそのデータは最新のものであるかは保証されない. |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
162 よって, 別のサーバノードで動いている Jungle からの更新データと衝突する可能性がある. |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
163 |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
164 この問題に対して Jungle はアプリケーションレベルでのマージを実装して貰うことで解決をはかる. |
10
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
165 |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
166 |
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
9
diff
changeset
|
167 |
22
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
168 |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
169 |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
170 |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
171 |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
172 |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
173 |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
174 |
56753cfbeeab
Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
20
diff
changeset
|
175 |