Mercurial > hg > Papers > 2014 > nobuyasu-master
comparison paper/chapter3.tex @ 50:faa708c2958b
Added log
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 31 Jan 2014 17:13:59 +0900 |
| parents | 7b595f4b341e |
| children | 1d07365c60ff |
comparison
equal
deleted
inserted
replaced
| 49:7b595f4b341e | 50:faa708c2958b |
|---|---|
| 1 \chapter{Jungle の分散実装} | 1 \chapter{分散データベースJungleの設計} |
| 2 本章では Jungle に行った分散実装について述べる. | |
| 3 前章では Jungle のアーキテクチャと分散設計について説明した. | |
| 4 トポロジーの形成と他サーバノードのデータのアクセス方法には Alice を使用する. | |
| 5 また, Jungle ではデータ編集のログとして TreeOperationLog がある. | |
| 6 この TreeOperationLog を Alice により他サーバノードへ送ることでデータの分散を行う. | |
| 7 | |
| 8 \section{Alice のトポロジーマネージャーの利用} | |
| 9 | |
| 10 \subsection{トポロジーマネージャーの起動} | |
| 11 Alice を用いてサーバノードでトポロジーの形成を行う方法を述べる. | |
| 12 Alice のトポロジーマネージャーの起動は\ref{src:alice_dot}の様に行う. | |
| 13 (\ref{src:alice_ntm_run}). | |
| 14 \begin{lstlisting}[frame=lrbt,label=src:alice_ntm_run,caption=Alice によるネットワークトポロジーマネージャーの起動,numbers=left] | |
| 15 % java -cp Alice.jar alice.topology.manager.TopologyManager -p 10000 -conf ./topology/tree5.dot | |
| 16 \end{lstlisting} | |
| 17 -p オプションはトポロジーマネージャーが開くポートの番号, -conf オプションには dot ファイルのパスを渡す. | |
| 18 | |
| 19 ポート番号は Alice により記述された並列分散プログラムの起動時に渡す必要がある. | |
| 20 dot ファイルには, トポロジーをどのように形成するかが書かれている. | |
| 21 以下に, サーバノード数5で, 2分木ツリー構造を形成する dot ファイルの例を示す(\ref{src:alice_dot}). | |
| 22 \begin{lstlisting}[frame=lrbt,label=src:alice_dot,caption=ネットワークトポロジー設定用 dot ファイル,numbers=left] | |
| 23 % cat tree5.dot | |
| 24 digraph test { | |
| 25 node0 -> node1 [label="child1"] | |
| 26 node0 -> node2 [label="child2"] | |
| 27 node1 -> node0 [label="parent"] | |
| 28 node1 -> node3 [label="child1"] | |
| 29 node1 -> node4 [label="child2"] | |
| 30 node2 -> node0 [label="parent"] | |
| 31 node3 -> node1 [label="parent"] | |
| 32 node4 -> node1 [label="parent"] | |
| 33 } | |
| 34 \end{lstlisting} | |
| 35 | |
| 36 node0 や node1 はサーバノードの名前を示す. | |
| 37 サーバノードの間にはラベルがあり, Alice 上ではこのラベル | |
| 38 に指定される文字列(キー)を使うことで他のサーバノードのデータへアクセスすることができる. | |
| 39 node0 -> node1 はサーバノード同士の繋がりを示している. | |
| 40 次に続く label="child1" は, node0 が node1 のデータに"child1"という文字列を使うことでアクセス | |
| 41 できることを示す. | |
| 42 | |
| 43 dot ファイルを読み込んだ Alice のトポロジーマネージャーに対して, サーバノードは | |
| 44 誰に接続を行えばよいかを訪ねる. | |
| 45 トポロジーマネージャーは訪ねてきたサーバノードに対してノード番号を割り振り, dot ファイル | |
| 46 に記述している通りにサーバノード同士が接続を行うよう指示をだす. | |
| 47 | |
| 48 トポロジーマネージャーは接続要求先を聞いてくるサーバノードに対して名前を割り振り, 接続相手を伝える. | |
| 49 dot ファイル\ref{src:alice_dot}により形成されるトポロジーを図\ref{fig:tree_topology}に示す. | |
| 50 | 2 |
| 51 | 3 |
| 52 \begin{figure}[htpb] | |
| 53 \begin{center} | |
| 54 \includegraphics[scale=0.70]{figures/tree_topology.pdf} | |
| 55 \caption{Alice によるネットワークトポロジー形成} | |
| 56 \label{fig:tree_topology} | |
| 57 \end{center} | |
| 58 \end{figure} | |
| 59 | |
| 60 矢印に書かれている文字列は, 相手のデータにアクセスするキーを示す. | |
| 61 "child1", "child2", "parent" というキーを使うことで別のサーバノードにあるデータを取得することができる. | |
| 62 %子共となるノードは "parent" キーにより親の DSM (Remote DSM) にアクセスすることができる. | |
| 63 %また, 親も子供となるノードの DSM に対して "child1" や "child2" キーによりアクセスすることが可能となる. | |
| 64 これでトポロジーマネージャーが起動される. | |
| 65 | |
| 66 \subsection{アプリケーション側の記述} | |
| 67 次は Jungle 側のプログラムが最初に Alice のトポロジーノードと通信を行うようにする. | |
| 68 そのためには Alice の TopologyNode クラスに必要な情報を渡してインスタンスを生成する(\ref{src:app_start}). | |
| 69 \begin{lstlisting}[frame=lrbt,label=src:app_start,caption=アプリケーションの起動,numbers=left] | |
| 70 public static void main( String[] args ) throws Exception | |
| 71 { | |
| 72 RemoteConfig conf = new RemoteConfig(args); | |
| 73 new TopologyNode(conf, new StartJungleCodeSegment(args, conf.bbsPort)); | |
| 74 } | |
| 75 \end{lstlisting} | |
| 76 TopologyNode クラスは第2引数として CodeSegment を受け取る. | |
| 77 TopologyNode のインスタンスはまず初めにトポロジーマネージャーへ接続を行う. | |
| 78 次にトポロジーマネージャーから受け取った情報を元に別のサーバノードとトポロジーの形成を行う. | |
| 79 その後, 第2引数で渡された StartJungleCodeSegment の実行を行う. | |
| 80 StartJungleCodeSegment には通常のアプリケーションの処理が書かれる. | |
| 81 | |
| 82 アプリケーションの起動時にはコンフィグの情報として, トポロジーマネージャーが動いているサーバのドメインとポート番号を | |
| 83 渡す必要がある. | |
| 84 例えば, mass00.cs.ie.u-ryukyu.ac.jp というサーバ上でポート番号10000を指定してトポロジーマネージャーを | |
| 85 起動した場合は次のようになる(\ref{src:run_program}). | |
| 86 \begin{lstlisting}[frame=lrbt,label=src:run_program,caption=トポロジーマネージャーの利用,numbers=left] | |
| 87 % java Program -host mass00.cs.ie.u-ryukyu.ac.jp -port 10000 | |
| 88 \end{lstlisting} | |
| 89 | |
| 90 \section{Alice を用いての分散実装} | |
| 91 Aliceのポロジー形成と他のサーバのデータへのアクセスする機構を用いるためには, Aliceが | |
| 92 提供するプログラミングスタイルに沿わなければならない. | |
| 93 それはDataSegment(データ)とCodeSegment(タスク)によるプログラムである. | |
| 94 ここではまずDataSegmentとCodeSegmentによるプログラムの方法について説明し, 他サーバとの | |
| 95 通信部分の実装について述べる. | |
| 96 | |
| 97 \subsection{Alice によるプログラミング} | |
| 98 AliceはDataSegment（データ）とCodeSegment（タスク）単位でプログラミングを行うことを述べた. | |
| 99 CodeSegmentには計算に必要なDataSegmentが登録される. | |
| 100 そしてDataSegmentが準備され次第CodeSegmentによる計算が実行される. | |
| 101 DataSegmentの取得は文字列のキーを使うことで行える. | |
| 102 以下のコードにCodeSegmentの例を示す. | |
| 103 \begin{lstlisting}[frame=lrbt,label=src:syslog_nfconntrack,caption=CodeSegmentの実行,numbers=left] | |
| 104 public class TestCodeSegment extends CodeSegment { | |
| 105 public Receiver arg1 = ids.create(CommandType.TAKE); | |
| 106 | |
| 107 public TestCodeSegment() { } | |
| 108 | |
| 109 public void run() { | |
| 110 int count = ds.asInteger(); | |
| 111 count++; | |
| 112 System.out.println("count = "+count); | |
| 113 if(c > 10) { exit(0); } | |
| 114 CodeSegment cs = new TestCodeSegment(); | |
| 115 cs.setKey("count"); | |
| 116 ods.update("local", "count", c); | |
| 117 } | |
| 118 | |
| 119 public static void main(String[] args) { | |
| 120 CodeSegment cs = new TestCodeSegment(); | |
| 121 cs.arg1.setKey("local", "count"); // setKey API | |
| 122 cs.ods.update("local", "count", 0); | |
| 123 } | |
| 124 } | |
| 125 \end{lstlisting} | |
| 126 これは, 数字を1から10まで出力を行い終了するプログラムである. | |
| 127 コードの説明を行う. | |
| 128 17行目から19行目の処理が最初に行われる. | |
| 129 まずTestCodeSegmentというCodeSegmentのインスタンスcsを生成する. | |
| 130 csはarg1というReceiverクラスのフィールドを保持しており, Receiverクラスは | |
| 131 DataSegmentを受けとるためのクラスである. | |
| 132 arg1に対しsetKey APIを使うことで, 使用したいDataSegmentのキー"count"を登録することができる. | |
| 133 これによりキー"count"に対してデータが登録された場合, そのデータを受け取りcsの計算が自動で始まる. | |
| 134 setKey APIの第一引数に渡している"local"はどのマシンのDataSegmentにアクセスするのかを指定している. | |
| 135 この場合は自分自身を表す"local"になる. | |
| 136 | |
| 137 データの登録は\verb|ods.update|により行える. | |
| 138 上記のコード19行目ではupdateにより"count"をキーとして数値の0を登録している. | |
| 139 updateがされるとcsの計算が始まり別スレッドにより8行目からの処理が行われる. | |
| 140 | |
| 141 updateによりキー"count"に登録された数値0はReceiverであるdsを使って取ることができる. | |
| 142 7行目から13行目では\verb|ds.asInteger()|により, "count"に登録したデータの中身を受け取りインクリメントし出力する. | |
| 143 そして最後には\verb|ods.update|を行っている. | |
| 144 新たなTestCodeSegmentも生成しており, これはインクリメントされた"count"がupdateされることで実行される. | |
| 145 この一連の処理を"count"の数値が10以上になるまで行う. | |
| 146 | |
| 147 DataSegmentへデータの追加とCodeSegmentの実行について表した図\ref{fig:testcodesegment}になる. | |
| 148 \begin{figure}[htpb] | |
| 149 \begin{center} | |
| 150 \includegraphics[scale=0.70]{figures/testcodesegment.pdf} | |
| 151 \caption{DataSegmentとCodeSegmentによるプログラムの例} | |
| 152 \label{fig:testcodesegment} | |
| 153 \end{center} | |
| 154 \end{figure} | |
| 155 | |
| 156 | |
| 157 % Alice の他サーバノードへの"log"のputの問題 | |
| 158 | |
| 159 \subsection{他サーバノードのDataSegmentへアクセス} | |
| 160 Aliceにおける基本的なプログラミングは述べた. | |
| 161 次はネットワークを介して他サーバノードのDataSegmentにアクセスするプログラムについて述べる. | |
| 162 | |
| 163 まず, Aliceにより2分木3ノードのトポロジーが形成された場合を想定する. | |
| 164 その時に実際に作られるトポロジーを図\ref{fig:remote_cs}に示す. | |
| 165 \begin{figure}[htpb] | |
| 166 \begin{center} | |
| 167 \includegraphics[scale=0.70]{figures/remote_codesegment.pdf} | |
| 168 \caption{トポロジーの形成} | |
| 169 \label{fig:remote_cs} | |
| 170 \end{center} | |
| 171 \end{figure} | |
| 172 | |
| 173 ネットワークを介したDataSegmentへのアクセスはそのサーバノードを示す | |
| 174 文字列のキーを追加することで行える. | |
| 175 他サーバノードを示す文字列のキーとは図\ref{fig:remote_cs}に矢印の隣に書かれている文字列 | |
| 176 "parent", "child1", "child2" のことを指す. | |
| 177 例えば, server node0 が server node1のDataSegmentに入っている"count"というデータを | |
| 178 を使用したい場合は, 次のようにsetKeyを行えばよい（\ref{src:remote_cs1}）. | |
| 179 \begin{lstlisting}[frame=lrbt,label=src:remote_cs1,caption=CodeSegmentで他サーバノードのDataSegmentを使用する,numbers=left] | |
| 180 CodeSegment cs = new RemoteCodeSegment(); | |
| 181 cs.arg1.setKey("child1", "count"); | |
| 182 \end{lstlisting} | |
| 183 また, 他サーバノードのDataSegmentにデータを送りたい場合は, putを行うときにサーバノードへのキーを | |
| 184 追加すればよい. | |
| 185 例として, server node1やserver node2がserver node0のDataSegmentに"message"というキーでデータを追加したい場合 | |
| 186 次のようになる（\ref{src:remote_cs2}）. | |
| 187 \begin{lstlisting}[frame=lrbt,label=src:remote_cs2,caption=他サーバーノードのDatasSegmentにデータを追加する,numbers=left] | |
| 188 ods.put("parent", "message", "Hello parent"); | |
| 189 \end{lstlisting} | |
| 190 | |
| 191 \subsection{独自クラスのインスタンスの送受信} | |
| 192 最後に, 独自クラスのインスタンスのDataSegmentでの扱い方について述べる. | |
| 193 AliceではMessagePackを用いてシリアライズを行い他サーバノードへと送信している. | |
| 194 MessagePackはクラス単位でシリアライズを行うことができる. | |
| 195 そのため, Aliceではプリミティブな型に限らずクラスのインスタンスをDataSegmentとして | |
| 196 扱うことができる. | |
| 197 | |
| 198 MessagePackによりシリアライズとなるクラスはいくつか制限がある. | |
| 199 それはそのクラスに@Messageアノテーションを付けることと, そのクラスが保持するフィールドが | |
| 200 MessagePackによりシリアライズ可能であることである. | |
| 201 例えば次のようなクラスである. | |
| 202 \begin{lstlisting}[frame=lrbt,label=src:msgpack1,caption=MessagePackによりシリアライズ可能なクラス1,numbers=left] | |
| 203 import org.msgpack.annotation.Message | |
| 204 | |
| 205 @Message | |
| 206 public class Student { | |
| 207 String name; | |
| 208 int age; | |
| 209 } | |
| 210 \end{lstlisting} | |
| 211 上記のStudenクラスはプリミティブ型しか保持していない. | |
| 212 そのためシリアライズが可能である | |
| 213 また, 次のようなクラスもシリアライズ可能な型となる. | |
| 214 \begin{lstlisting}[frame=lrbt,label=src:msgpack2,caption=MessagePackによりシリアライズ可能なクラス2,numbers=left] | |
| 215 import org.msgpack.annotation.Message | |
| 216 | |
| 217 @Message | |
| 218 public class Class { | |
| 219 List<Student> studentList; | |
| 220 } | |
| 221 \end{lstlisting} | |
| 222 この場合, フィールドはプリミティブな型でないStudentクラスのフィールドを保持している. | |
| 223 しかし, Studentクラスはシリアライズ可能な形で作成しているため, クラスのフィールドとして | |
| 224 保持しても問題はない. | |
| 225 | |
| 226 これらの制約にそった形で作成しDataSegmentにネットワークを介してクラスのインスタンス | |
| 227 をupdateすることができる. | |
| 228 DataSegmentから受け取ったデータはそのままではシリアライズされたものため, 一度手元で | |
| 229 元のクラスにコンバートすることで扱う. | |
| 230 例として, AliceにおけるStudenクラス(Listing\ref{src:msgpack1})のコンバートを次に示す. | |
| 231 \begin{lstlisting}[frame=lrbt,label=src:msgpack3,caption=DataSegment,numbers=left] | |
| 232 // public Receiver arg1 = ids.create(CommandType.PEEK); | |
| 233 Student s = arg1.asClass(Student.class); | |
| 234 \end{lstlisting} | |
| 235 MessagePackでシリアライズ可能な形としているためDataSegmentはネットワークを介して | |
| 236 送受信が可能である. | |
| 237 | |
| 238 | |
| 239 \section{ログのシリアライズ} | |
| 240 Jungleの具体的な分散実装について述べる. | |
| 241 実装にあたり, 解決しなければならない問題はまず, ログをDataSegmentで扱える形にすることである. | |
| 242 そのためには, @Messageアノテーションを付けたログのクラスの作成を行わなければならない. | |
| 243 | |
| 244 | |
| 245 \subsection{TreeOperationLogのシリアライズ} | |
| 246 TreeOperationLogをシリアライズ可能な形にするにあたって気をつけなければならないのが, フィールドを | |
| 247 シリアライズ可能にする部分である. | |
| 248 TreeOperationLogはTreeOperationをいくつも保持し, TreeOperationはNodePathとNodeOperationを保持するものであった. | |
| 249 そのため, これら全てシリアライズ可能な形にしなければならない. | |
| 250 | |
| 251 基本的にこれらの実装は, フィールドを全てプリミティブなものだけにすればよい. | |
| 252 MessagePackはListを扱うこともできるため, TreeOperationLogで継承されていたIterableの挙動もListを使うことで | |
| 253 実装を行うことができた. | |
| 254 | |
| 255 \subsection{ログに対する情報の追加} | |
| 256 TreeOperationLogをシリアライズ可能な形にした後, 問題が発生した. | |
| 257 それは, TreeOperationLog事態は木の名前を保持していないというものである. | |
| 258 そのため, TreeOperationLogだけを受け取っても, そのログがどの木に対して行われるのか | |
| 259 わからなかった. | |
| 260 そこで, TreeOperationLogの情報だけでなく, 木の名前とUUID, それとtimestampの情報も付与 | |
| 261 してシリアライズが可能なNetworkTreeOperationLogの実装を行った. | |
| 262 | |
| 263 \subsection{NetworkTreeOperationLogの実装} | |
| 264 NetworkTreeOperationLogの実装の一部を以下に示す. | |
| 265 | |
| 266 | |
| 267 | |
| 268 | |
| 269 | |
| 270 % TreeOperationLog に木の名前の情報がない | |
| 271 % そのため木の名前を追加して持たせた | |
| 272 % 木がなければそのばでつくるようにした | |
| 273 | |
| 274 \subsection{local専用の編集の用意} | |
| 275 | |
| 276 | |
| 277 \subsection{} | |
| 278 | |
| 279 | |
| 280 | |
| 281 \section{掲示板プログラムにおけるマージの実装} | |
| 282 Jungle に分散実装を行った後の問題としてデータ衝突がある. | |
| 283 他のサーバノードから送られてくるデータが既に手元で変更を加えた木構造を対象とした | |
| 284 場合に発生する問題である. | |
| 285 Jungle ではこれをアプリケーション毎にマージを実装することで解決させる. | |
| 286 | |
| 287 今回分散実装を行い, 例題として掲示板プログラムを用意した. | |
| 288 掲示板プログラムに実装を行ったマージについて述べる. | |
| 289 まず Jungle を用いた掲示板プログラムのデータ保持方法を図\ref{fig:merge2}に示す. | |
| 290 \begin{figure}[htpb] | |
| 291 \begin{center} | |
| 292 \includegraphics[scale=0.70]{figures/merge2.pdf} | |
| 293 \caption{Jungle による掲示板プログラムのデータ保持方法} | |
| 294 \label{fig:merge2} | |
| 295 \end{center} | |
| 296 \end{figure} | |
| 297 | |
| 298 掲示板プログラムでは各掲示板毎に1つの木構造が作成される. | |
| 299 掲示板への1つの書き込みは子ノードを1つ追加することに相当する. | |
| 300 また, 各子ノードは attributes として書き込みの内容である message と書き込まれた時間を表す timestamp を保持している. | |
| 301 先に追加された順で子ノードには若い番号が割り振られる. | |
| 302 | |
| 303 他サーバノードからの書き込みをそのまま子ノードの後ろに追加してしまうと, データの整合性が崩れてしまう. | |
| 304 この時の状態を表しているのが図\ref{fig:merge_imp1}と\ref{fig:merge_imp2}になる. | |
| 305 \begin{figure}[htpb] | |
| 306 \begin{center} | |
| 307 \includegraphics[scale=0.70]{figures/merge_imp1.pdf} | |
| 308 \caption{他サーバノードの編集データ反映による整合性の崩れ1} | |
| 309 \label{fig:merge_imp1} | |
| 310 \end{center} | |
| 311 \end{figure} | |
| 312 | |
| 313 \begin{figure}[htpb] | |
| 314 \begin{center} | |
| 315 \includegraphics[scale=0.70]{figures/merge_imp2.pdf} | |
| 316 \caption{他サーバノードの編集データ反映による整合性の崩れ2} | |
| 317 \label{fig:merge_imp2} | |
| 318 \end{center} | |
| 319 \end{figure} | |
| 320 | |
| 321 \newpage | |
| 322 | |
| 323 図\ref{fig:merge_imp2}の server node0 の木の状態にするのが理想である. | |
| 324 掲示板のへの書き込みの表示は, 書き込みされた時間が早い順に表示されるようにしたい. | |
| 325 これを timestamp を利用することで行う. | |
| 326 他サーバノードから来たデータに関しては, timestamp を参照し, 次に自分の保持している | |
| 327 木の子ノードの timestamp と比べていくことでデータの追加する場所を決める. | |
| 328 これが今回実装を行った掲示板システムにおけるマージになる. | |
| 329 | |
| 330 %単一サーバで動いている時の Jungle はただ子ノードとして後ろに追加するだけだが, 分散 | |
| 331 %環境下においては timestamp に従い子ノードを追加する位置を決めるようにする. | |
| 332 | |
| 333 | |
| 334 | |
| 335 |