Mercurial > hg > Papers > 2014 > nobuyasu-master
annotate paper/chapter3.tex @ 21:a4dfb70496ee
Added figure
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 23 Jan 2014 16:35:50 +0900 |
| parents | a7fbd5db80fb |
| children | 56753cfbeeab |
| rev | line source |
|---|---|
|
4
d42d2acf5d1d
Added some tex files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 \chapter{Jungleの分散実装} |
|
10
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
2 \section{TreeOperationLogを用いての分散データベースの実装} |
| 12 | 3 Jungle でデータ扱うと TreeOperationLog として残ることは述べた. |
|
10
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
4 この TreeOperationLog を他のサーバへと送り, Jungle の編集を行って |
|
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
5 貰うことでデータの分散を行うことができる. |
| 12 | 6 ここで問題になることはネットワークトポロジーの形成方法であった. |
| 7 | |
| 8 Jungle で使用するネットワークトポロジーはツリー型を考えている. | |
| 9 しかし, リング型といった他のネットワークトポロジーによる実装に関しても試す余地はある. | |
| 10 自由にネットワークトポロジーの形成を行うことができる必要があった. | |
| 11 | |
| 12 そこで当研究室で開発を行っている並列分散フレームワークである Alice を使用することにした. | |
| 13 Alice により提供されるネットワークトポロジー形成を用いて TreeOperationLog を各サーバノードへ | |
| 14 配ることで並列分散フレームワークの実装を行う. | |
| 11 | 15 |
| 12 | 16 % トポロジー形成の説明をする. 重要さなども。 |
| 17 % トポロジーの形成は容易ではない. | |
| 18 % Alice が必要な機能を提供してくれることを述べる | |
| 19 % Alice はトポロジー形成の機能を提供している | |
| 20 % トポロジー間でのデータの受け渡す機能も提供している | |
| 21 \begin{figure}[htpb] | |
| 22 \begin{minipage}{0.5\hsize} | |
| 23 \begin{center} | |
| 24 \includegraphics[scale=0.7]{figures/network_topology_ring.pdf} | |
| 25 \caption{リング型のNetwork Topology} | |
| 26 \label{fig:topology_ring} | |
| 27 \end{center} | |
| 28 \end{minipage} | |
| 29 \begin{minipage}{0.5\hsize} | |
| 30 \begin{center} | |
| 31 \includegraphics[scale=0.7]{figures/network_topology_tree.pdf} | |
| 32 \caption{ツリー型のNetwork Topology} | |
| 33 \label{fig:topology_tree} | |
| 34 \end{center} | |
| 35 \end{minipage} | |
| 36 \end{figure} | |
| 11 | 37 |
| 38 \section{並列分散フレームワークAlice} | |
|
15
7df3a9a13b22
Writed research
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
12
diff
changeset
|
39 Alice は当研究室で開発している並列分散フレームワークである. |
|
16
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
40 Alice はデータを DataSegment, コードを CodeSegment という単位で扱うプログラミングを提供している. |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
41 DataSegment として扱われるデータは |
|
15
7df3a9a13b22
Writed research
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
12
diff
changeset
|
42 |
|
10
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
43 |
|
16
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
44 |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
45 % DataSegment, CodeSegment はなしにしたほうがいいかもしれない. Alice が論文の主題じゃないから |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
46 % それとこの2つの説明をするとしたら結構な量になる |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
47 |
| 20 | 48 \section{Alice のトポロジーマネージャーの利用} |
| 49 Alice はサーバノード同士によるネットワークトポロジー形成の機能を持つ. | |
| 50 トポロジーマネージャーの起動は\ref{src:alice_dot}の様にポート番号の指定と dot ファイルを引数として渡すことで行う. | |
| 51 (\ref{src:alice_ntm_run}). | |
| 52 \begin{lstlisting}[frame=lrbt,label=src:alice_ntm_run,caption=Alice によるネットワークトポロジーマネージャーの起動,numbers=left] | |
| 53 % java -cp Alice.jar alice.topology.manager.TopologyManager -p 10000 -conf ./topology/tree5.dot | |
| 54 \end{lstlisting} | |
| 55 | |
| 56 | |
| 57 ポート番号は Alice により記述された並列分散プログラムの起動時に渡す必要がある. | |
| 58 dot ファイルには, トポロジーをどのように形成するかが書かれている. | |
| 59 以下に, サーバノード数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
|
60 \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
|
61 % cat tree5.dot |
|
16
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
62 digraph test { |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
63 node0 -> node1 [label="child1"] |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
64 node0 -> node2 [label="child2"] |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
65 node1 -> node0 [label="parent"] |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
66 node1 -> node3 [label="child1"] |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
67 node1 -> node4 [label="child2"] |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
68 node2 -> node0 [label="parent"] |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
69 node3 -> node1 [label="parent"] |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
70 node4 -> node1 [label="parent"] |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
71 } |
|
18
fc14b1876141
Modified description of topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
72 \end{lstlisting} |
|
fc14b1876141
Modified description of topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
73 |
| 20 | 74 node0 や node1 はサーバノードの名前を示す. |
| 75 サーバノードの間にはラベルがあり, Alice 上ではこのラベル | |
| 76 に指定される文字列(キー)を使うことで他のサーバノードのデータへアクセスすることができる. | |
| 77 node0 -> node1 はサーバノード同士の繋がりを示している. | |
| 78 次に続く label="child1" は, node0 が node1 のデータに"child1"という文字列を使うことでアクセス | |
| 79 できることを示す. | |
|
18
fc14b1876141
Modified description of topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
80 |
| 21 | 81 dot ファイルを読み込んだ Alice のトポロジーマネージャーに対して, サーバノードは |
| 20 | 82 誰に接続を行えばよいかを訪ねる. |
| 83 トポロジーマネージャーは訪ねてきたサーバノードに対してノード番号を割り振り, dot ファイル | |
| 84 に記述している通りにサーバノード同士が接続を行うよう指示をだす. | |
|
18
fc14b1876141
Modified description of topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
17
diff
changeset
|
85 |
| 20 | 86 トポロジーマネージャーは接続要求先を聞いてくるサーバノードに対して名前を割り振り, 接続相手を伝える. |
| 87 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
|
88 |
| 20 | 89 \newpage |
|
16
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
90 |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
91 \begin{figure}[htpb] |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
92 \begin{center} |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
93 \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
|
94 \caption{Alice によるネットワークトポロジー形成} |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
95 \label{fig:tree_topology} |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
96 \end{center} |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
97 \end{figure} |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
98 |
| 19 | 99 |
|
17
dfa2fd4658b2
Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
100 矢印に書かれている文字列は, 相手のデータにアクセスするキーを示す. |
|
dfa2fd4658b2
Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
101 "child1", "child2", "parent" というキーを使うことで別のサーバノードにあるデータを取得することができる. |
|
dfa2fd4658b2
Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
102 %子共となるノードは "parent" キーにより親の DSM (Remote DSM) にアクセスすることができる. |
|
dfa2fd4658b2
Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
103 %また, 親も子供となるノードの DSM に対して "child1" や "child2" キーによりアクセスすることが可能となる. |
|
16
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
104 |
| 20 | 105 トポロジーマネージャーに最初に接続要求を行う並列分散プログラム側は, 次のように記述する(\ref{src:alice_start}) |
| 106 \begin{lstlisting}[frame=lrbt,label=src:alice_start,caption=Alice を使用してのトポロジー形成,numbers=left] | |
| 107 public static void main( String[] args ) throws Exception | |
| 108 { | |
| 109 RemoteConfig conf = new RemoteConfig(args); | |
| 110 new TopologyNode(conf, new StartBBSCodeSegment(args, conf.bbsPort)); | |
| 111 } | |
| 112 \end{lstlisting} | |
| 113 | |
| 114 | |
| 21 | 115 そして, プログラムの起動時にはトポロジーマネージャーが動いているサーバのドメインとポート番号を |
| 116 渡すことでトポロジーの形成が行われれプログラムの処理がはしる. | |
| 117 例えば, mass00.cs.ie.u-ryukyu.ac.jp というサーバ上でポート番号10000を指定してトポロジーマネージャーを | |
| 118 起動した場合は次のようになる(\ref{src:run_program}). | |
| 119 \begin{lstlisting}[frame=lrbt,label=src:run_program,caption=トポロジーマネージャーの利用,numbers=left] | |
| 120 % java Program -host mass00.cs.ie.u-ryukyu.ac.jp -port 10000 | |
| 121 \end{lstlisting} | |
|
17
dfa2fd4658b2
Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
122 |
|
dfa2fd4658b2
Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
123 % MessagePackの説明もここに簡単に入れたほうがいいかも. |
|
dfa2fd4658b2
Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
124 |
|
dfa2fd4658b2
Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
125 \section{Aliceを用いての分散実装} |
| 21 | 126 形成されたトポロジー上でのデータの送受信を行う部分について述べる. |
|
10
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
127 |
| 11 | 128 |
|
4
d42d2acf5d1d
Added some tex files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
129 \section{ログのシリアライズ} |
| 21 | 130 ここでログのシリアライズについて述べる. |
|
17
dfa2fd4658b2
Modified abstract
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
16
diff
changeset
|
131 |
|
16
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
132 シリアライズとは, データをネットワーク上に流しても良い形式に変換することである. |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
133 |
|
e16dad3b80fc
Writed topology manager
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
15
diff
changeset
|
134 |
|
4
d42d2acf5d1d
Added some tex files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
135 \section{Jungleの永続性の実装} |
| 21 | 136 |
| 137 | |
| 138 \section{マージの実装} | |
| 139 Jungle への分散実装を行うことである問題が発生する. | |
| 140 それは更新されたデータ同士が衝突を起こした時の処理である. | |
| 141 Jungle はリクエストがきた場合, 現在もっているデータを返す. | |
| 142 しかしそのデータは最新のものであるかは保証されない. | |
| 143 よって, 別のサーバノードで動いている Jungle からの更新データと衝突する可能性がある. | |
| 144 | |
| 145 この問題に対して Jungle はアプリケーションレベルでのマージを実装して貰うことで解決をはかる. | |
| 146 今回 Jungle に分散を行うにあたり掲示板プログラムを実装した. | |
| 147 掲示板プログラムに実装を行ったマージの例について述べる. | |
|
10
02c7fc1cda10
Writed description of TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
4
diff
changeset
|
148 |
| 21 | 149 Jungle を用いた掲示板プログラムのデータ保持方法を示したのが図\ref{fig:merge1}になる. |
| 150 \begin{figure}[htpb] | |
| 151 \begin{center} | |
| 152 \includegraphics[scale=0.70]{figures/merge1.pdf} | |
| 153 \caption{Jungle による掲示板プログラムのデータ保持方法} | |
| 154 \label{fig:merge1} | |
| 155 \end{center} | |
| 156 \end{figure} | |
| 157 | |
| 158 掲示板プログラムでは各掲示板毎に1つの木構造が作成される. | |
| 159 また, この時作成された木構造データのルートノードを保持する木構造が別にある. | |
| 160 | |
| 161 | |
| 162 |