Mercurial > hg > Papers > 2014 > nobuyasu-master

annotate paper/chapter2.tex @ 9:c09b83fe37ef

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Writed abstract
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Thu, 16 Jan 2014 00:20:41 +0900
parents 7072254f5e11
children 02c7fc1cda10
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
9
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
1 \chapter{木構造データベースJungleの実装と分散設計}
4
d42d2acf5d1d Added some tex files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 \section{木構造データベースJungle}
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
3 Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
4 一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
5 ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
6
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
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}
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
14 \includegraphics[scale=0.8]{figures/destructive_tree.pdf}
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}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
51 \caption{非破壊的木構造の編集1}
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}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
59 \caption{非破壊的木構造の編集2}
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}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
67 \caption{非破壊的木構造の編集3}
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}
f47f11ea0e28 Added non destructive tree edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
75 \caption{非破壊的木構造の編集4}
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
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
80 非破壊的木構造により, 木構造を編集しながら走査することが可能となる.
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
81
9
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
82 \section{Jungleにおけるデータ編集}
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
83 Jungleではデータの編集のため次のAPIが用意されている.
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
84 \begin{itemize}
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
85 \item \verb|addNewChild(NodePath _path, int _pos)|
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
86 \item \verb|deleteChildAt(NodePath _path, int _pos)|
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
87 \item \verb|putAttribute(NodePath _path, String _key, ByteBuffer _value)|
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
88 \item \verb|deleteAttribute(NodePath _path, String _key)|
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
89 \end{itemize}
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
90
4
d42d2acf5d1d Added some tex files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 \section{Jungleの分散データベース設計}
5
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
92
a6aa6af4b80f Added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
93
9
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
94 \subsection{マージ}
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
c09b83fe37ef Writed abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 8
diff changeset
97