Mercurial > hg > Papers > 2014 > nobuyasu-master

annotate paper/chapter3.tex @ 32:04af243ddd7c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Modified routing
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Mon, 27 Jan 2014 22:24:02 +0900
parents 9eb676914f1d
children 7a829a3c2e19
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
4
d42d2acf5d1d Added some tex files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 \chapter{Jungleの分散実装}
31
9eb676914f1d Writed description of jungle edit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 25
diff changeset
2
32
04af243ddd7c Modified routing
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 31
diff changeset
3 \section{TreeOperationLogを用いての分散実装}
12
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
4 Jungle でデータ扱うと TreeOperationLog として残ることは述べた.
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
5 この TreeOperationLog を他のサーバへと送り, Jungle の編集を行って
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
6 貰うことでデータの分散を行うことができる.
12
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
7 ここで問題になることはネットワークトポロジーの形成方法であった.
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
8
24
5316b4791570 Added master_paper.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
9 % なぜツリー型なのか説明をしたほうがいい？
5316b4791570 Added master_paper.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
10 % マージの利用のためツリー型？
12
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
11 Jungle で使用するネットワークトポロジーはツリー型を考えている.
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
12 しかし, リング型といった他のネットワークトポロジーによる実装に関しても試す余地はある.
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
13 自由にネットワークトポロジーの形成を行うことができる必要があった.
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
14
24
5316b4791570 Added master_paper.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
15 そこで当研究室で開発を行っている並列分散フレームワークである Alice を使用する.
12
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
16 Alice により提供されるネットワークトポロジー形成を用いて TreeOperationLog を各サーバノードへ
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
17 配ることで並列分散フレームワークの実装を行う.
11
b87deec129df Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
18
12
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
19 % トポロジー形成の説明をする. 重要さなども。
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
20 % トポロジーの形成は容易ではない.
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
21 % Alice が必要な機能を提供してくれることを述べる
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
22 % Alice はトポロジー形成の機能を提供している
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
23 % トポロジー間でのデータの受け渡す機能も提供している
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
24 \begin{figure}[htpb]
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
25 \begin{minipage}{0.5\hsize}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
26 \begin{center}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
27 \includegraphics[scale=0.7]{figures/network_topology_ring.pdf}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
28 \caption{リング型のNetwork Topology}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
29 \label{fig:topology_ring}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
30 \end{center}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
31 \end{minipage}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
32 \begin{minipage}{0.5\hsize}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
33 \begin{center}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
34 \includegraphics[scale=0.7]{figures/network_topology_tree.pdf}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
35 \caption{ツリー型のNetwork Topology}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
36 \label{fig:topology_tree}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
37 \end{center}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
38 \end{minipage}
449ddefdfa32 Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
39 \end{figure}
11
b87deec129df Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
40
b87deec129df Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
41 \section{並列分散フレームワークAlice}
15
7df3a9a13b22 Writed research
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
42 Alice は当研究室で開発している並列分散フレームワークである.
16
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
43 Alice はデータを DataSegment, コードを CodeSegment という単位で扱うプログラミングを提供している.
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
44 DataSegment として扱われるデータは
15
7df3a9a13b22 Writed research
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
45
16
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
46 % DataSegment, CodeSegment はなしにしたほうがいいかもしれない. Alice が論文の主題じゃないから
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
47 % それとこの2つの説明をするとしたら結構な量になる
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
48
20
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
49 \section{Alice のトポロジーマネージャーの利用}
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
50 Alice はサーバノード同士によるネットワークトポロジー形成の機能を持つ.
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
51 トポロジーマネージャーの起動は\ref{src:alice_dot}の様にポート番号の指定と dot ファイルを引数として渡すことで行う.
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
52 (\ref{src:alice_ntm_run}).
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
53 \begin{lstlisting}[frame=lrbt,label=src:alice_ntm_run,caption=Alice によるネットワークトポロジーマネージャーの起動,numbers=left]
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
54 % java -cp Alice.jar alice.topology.manager.TopologyManager -p 10000 -conf ./topology/tree5.dot
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
55 \end{lstlisting}
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
56
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
57
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
58 ポート番号は Alice により記述された並列分散プログラムの起動時に渡す必要がある.
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
59 dot ファイルには, トポロジーをどのように形成するかが書かれている.
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
60 以下に, サーバノード数5で, 2分木ツリー構造を形成する dot ファイルの例を示す(\ref{src:alice_dot}).
18
fc14b1876141 Modified description of topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
61 \begin{lstlisting}[frame=lrbt,label=src:alice_dot,caption=ネットワークトポロジー設定用 dot ファイル,numbers=left]
fc14b1876141 Modified description of topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
62 % cat tree5.dot
16
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
63 digraph test {
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
64 node0 -> node1 [label="child1"]
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
65 node0 -> node2 [label="child2"]
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
66 node1 -> node0 [label="parent"]
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
67 node1 -> node3 [label="child1"]
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
68 node1 -> node4 [label="child2"]
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
69 node2 -> node0 [label="parent"]
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
70 node3 -> node1 [label="parent"]
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
71 node4 -> node1 [label="parent"]
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
72 }
18
fc14b1876141 Modified description of topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
73 \end{lstlisting}
fc14b1876141 Modified description of topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
74
20
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
75 node0 や node1 はサーバノードの名前を示す.
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
76 サーバノードの間にはラベルがあり, Alice 上ではこのラベル
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
77 に指定される文字列(キー)を使うことで他のサーバノードのデータへアクセスすることができる.
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
78 node0 -> node1 はサーバノード同士の繋がりを示している.
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
79 次に続く label="child1" は, node0 が node1 のデータに"child1"という文字列を使うことでアクセス
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
80 できることを示す.
18
fc14b1876141 Modified description of topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
81
21
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
82 dot ファイルを読み込んだ Alice のトポロジーマネージャーに対して, サーバノードは
20
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
83 誰に接続を行えばよいかを訪ねる.
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
84 トポロジーマネージャーは訪ねてきたサーバノードに対してノード番号を割り振り, dot ファイル
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
85 に記述している通りにサーバノード同士が接続を行うよう指示をだす.
18
fc14b1876141 Modified description of topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
86
20
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
87 トポロジーマネージャーは接続要求先を聞いてくるサーバノードに対して名前を割り振り, 接続相手を伝える.
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
88 dot ファイル\ref{src:alice_dot}により形成されるトポロジーを図\ref{fig:tree_topology}に示す.
16
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
89
20
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
90 \newpage
16
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
91
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
92 \begin{figure}[htpb]
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
93 \begin{center}
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
94 \includegraphics[scale=0.70]{figures/tree_topology.pdf}
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
95 \caption{Alice によるネットワークトポロジー形成}
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
96 \label{fig:tree_topology}
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
97 \end{center}
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
98 \end{figure}
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
99
19
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 18
diff changeset
100
17
dfa2fd4658b2 Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
101 矢印に書かれている文字列は, 相手のデータにアクセスするキーを示す.
dfa2fd4658b2 Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
102 "child1", "child2", "parent" というキーを使うことで別のサーバノードにあるデータを取得することができる.
dfa2fd4658b2 Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
103 %子共となるノードは "parent" キーにより親の DSM (Remote DSM) にアクセスすることができる.
dfa2fd4658b2 Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
104 %また, 親も子供となるノードの DSM に対して "child1" や "child2" キーによりアクセスすることが可能となる.
16
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
105
20
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
106 トポロジーマネージャーに最初に接続要求を行う並列分散プログラム側は, 次のように記述する(\ref{src:alice_start})
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
107 \begin{lstlisting}[frame=lrbt,label=src:alice_start,caption=Alice を使用してのトポロジー形成,numbers=left]
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
108 public static void main( String[] args ) throws Exception
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
109 {
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
110 RemoteConfig conf = new RemoteConfig(args);
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
111 new TopologyNode(conf, new StartBBSCodeSegment(args, conf.bbsPort));
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
112 }
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
113 \end{lstlisting}
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
114
a7fbd5db80fb chapter3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
115
21
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
116 そして, プログラムの起動時にはトポロジーマネージャーが動いているサーバのドメインとポート番号を
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
117 渡すことでトポロジーの形成が行われれプログラムの処理がはしる.
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
118 例えば, mass00.cs.ie.u-ryukyu.ac.jp というサーバ上でポート番号10000を指定してトポロジーマネージャーを
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
119 起動した場合は次のようになる(\ref{src:run_program}).
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
120 \begin{lstlisting}[frame=lrbt,label=src:run_program,caption=トポロジーマネージャーの利用,numbers=left]
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
121 % java Program -host mass00.cs.ie.u-ryukyu.ac.jp -port 10000
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
122 \end{lstlisting}
17
dfa2fd4658b2 Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
123
dfa2fd4658b2 Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
124 % MessagePackの説明もここに簡単に入れたほうがいいかも.
dfa2fd4658b2 Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
125
dfa2fd4658b2 Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
126 \section{Aliceを用いての分散実装}
21
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
127 形成されたトポロジー上でのデータの送受信を行う部分について述べる.
10
02c7fc1cda10 Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
128
11
b87deec129df Added images
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
129
25
67880a2ca650 Modfied chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
130
67880a2ca650 Modfied chapter1.tex
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
131
4
d42d2acf5d1d Added some tex files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
132 \section{ログのシリアライズ}
21
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
133 ここでログのシリアライズについて述べる.
17
dfa2fd4658b2 Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
134
16
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
135 シリアライズとは, データをネットワーク上に流しても良い形式に変換することである.
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
136
e16dad3b80fc Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
137
21
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
138
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
139
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
140 \section{掲示板プログラムにおけるマージの実装}
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
141 Jungle に分散実装を行った後の問題としてデータ衝突がある.
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
142 他のサーバノードから送られてくるデータが既に手元で変更を加えた木構造を対象とした
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
143 場合に発生する問題である.
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
144 Jungle ではこれをアプリケーション毎にマージを実装することで解決させる.
21
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
145
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
146 今回分散実装を行い, 例題として掲示板プログラムを用意した.
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
147 掲示板プログラムに実装を行ったマージについて述べる.
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
148 まず Jungle を用いた掲示板プログラムのデータ保持方法を図\ref{fig:merge2}に示す.
21
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
149 \begin{figure}[htpb]
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
150 \begin{center}
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
151 \includegraphics[scale=0.70]{figures/merge2.pdf}
21
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
152 \caption{Jungle による掲示板プログラムのデータ保持方法}
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
153 \label{fig:merge2}
21
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
154 \end{center}
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
155 \end{figure}
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
156
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
157 掲示板プログラムでは各掲示板毎に1つの木構造が作成される.
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
158 掲示板への1つの書き込みは子ノードを1つ追加することに相当する.
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
159 また, 各子ノードは attributes として書き込みの内容である message と書き込まれた時間を表す timestamp を保持している.
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
160 先に追加された順で子ノードには若い番号が割り振られる.
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
161
23
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
162 他サーバノードからの書き込みをそのまま子ノードの後ろに追加してしまうと, データの整合性が崩れてしまう.
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
163 この時の状態を表しているのが図\ref{fig:merge_imp1}と\ref{fig:merge_imp2}になる.
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
164 \begin{figure}[htpb]
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
165 \begin{center}
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
166 \includegraphics[scale=0.70]{figures/merge_imp1.pdf}
23
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
167 \caption{他サーバノードの編集データ反映による整合性の崩れ1}
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
168 \label{fig:merge_imp1}
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
169 \end{center}
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
170 \end{figure}
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
171
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
172 \begin{figure}[htpb]
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
173 \begin{center}
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
174 \includegraphics[scale=0.70]{figures/merge_imp2.pdf}
23
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
175 \caption{他サーバノードの編集データ反映による整合性の崩れ2}
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
176 \label{fig:merge_imp2}
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
177 \end{center}
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
178 \end{figure}
21
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
179
23
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
180 \newpage
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
181
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
182 図\ref{fig:merge_imp2}の server node0 の木の状態にするのが理想である.
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
183 掲示板のへの書き込みの表示は, 書き込みされた時間が早い順に表示されるようにしたい.
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
184 これを timestamp を利用することで行う.
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
185 他サーバノードから来たデータに関しては, timestamp を参照し, 次に自分の保持している
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
186 木の子ノードの timestamp と比べていくことでデータの追加する場所を決める.
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
187 これが今回実装を行った掲示板システムにおけるマージになる.
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
188
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
189 %単一サーバで動いている時の Jungle はただ子ノードとして後ろに追加するだけだが, 分散
21e1a110f258 Writed description of merge
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
190 %環境下においては timestamp に従い子ノードを追加する位置を決めるようにする.
21
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
191
a4dfb70496ee Added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
192
22
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
193
56753cfbeeab Added merge_imp.pdf
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
194