Mercurial > hg > Papers > 2017 > suruga-sigos

comparison paper/sigos.tex @ 24:64a017ca89a4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
done
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Mon, 23 Apr 2018 23:01:03 +0900
parents b81702f6108a
children 8bad8d17b4c1
comparison
equal deleted inserted replaced
23:b81702f6108a 24:64a017ca89a4
39 \title{分散フレームワークChristieと分散木構造データベースJungle} 39 \title{分散フレームワークChristieと分散木構造データベースJungle}
40 % 英文表題 40 % 英文表題
41 \etitle{} 41 \etitle{}
42 42
43 % 所属ラベルの定義 43 % 所属ラベルの定義
44 \affilabel{2}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.} 44 \affilabel{1}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}
45 45
46 % 和文著者名 46 % 和文著者名
47 \author{ 47 \author{
48 河野 真治\affiref{1} 48 河野 真治\affiref{1}
49 } 49 }
57 \contact{河野真治\\ 57 \contact{河野真治\\
58 〒903-0213 沖縄県西原町千原1番地\\ 58 〒903-0213 沖縄県西原町千原1番地\\
59 琉球大学工学部情報工学科\\ 59 琉球大学工学部情報工学科\\
60 TEL: (098)895-2221\qquad FAX: (098)895-8727\\ 60 TEL: (098)895-2221\qquad FAX: (098)895-8727\\
61 email: kono@ie.u-ryukyu.ac.jp} 61 email: kono@ie.u-ryukyu.ac.jp}
62
63
62 64
63 % 和文概要 65 % 和文概要
64 \begin{abstract} 66 \begin{abstract}
65 現代のインターネットやアプリケーションで使われるデータは、複雑な構造を持っており、RDBの第一正規系には納まらないようになってきている。 67 現代のインターネットやアプリケーションで使われるデータは、複雑な構造を持っており、RDBの第一正規系には納まらないようになってきている。
66 また、RDBでは、編集中にロックがかけられ、複雑な構造に対する変更に向いていない。 68 また、RDBでは、編集中にロックがかけられ、複雑な構造に対する変更に向いていない。
75 本研究ではJungleの木と Index の編集機能の改善を行う。 77 本研究ではJungleの木と Index の編集機能の改善を行う。
76 直線的なリスト構造に適したPush/Popと差分リストを提案し、実装と評価を行なった。 78 直線的なリスト構造に適したPush/Popと差分リストを提案し、実装と評価を行なった。
77 巨大な木が必要な場合は、木を特定のKeyを用いてbalanceさせることにより、変更をO(log n)にすることができる。 79 巨大な木が必要な場合は、木を特定のKeyを用いてbalanceさせることにより、変更をO(log n)にすることができる。
78 Jungleは分散構造を取ることもできる。 80 Jungleは分散構造を取ることもできる。
79 複数の木を複数の分散したJungleノード間で通信することにより、Jungleをスケールさせる。 81 複数の木を複数の分散したJungleノード間で通信することにより、Jungleをスケールさせる。
80 Jungleの木の変更Logを当研究室で開発した分散フレームワークAlice\cite{alice}を用いて通信する。 82 Jungleの木の変更Logを当研究室で開発した分散フレームワークAlice\cite{kono16a}を用いて通信する。
81 それぞれの木は、ルートノードに集約され、集約の過程で、競合する変更のMergeを行う。 83 それぞれの木は、ルートノードに集約され、集約の過程で、競合する変更のMergeを行う。
82 分散Jungleの性能を測定する手法について述べる。 84 分散Jungleの性能を測定する手法について述べる。
83 \end{abstract} 85 \end{abstract}
84 86
85 % 表題などの出力 87 % 表題などの出力
107 ネットワーク上のサービスには、利用者数の爆発的な増加を受け入れるスケールアウト(サーバの数を増やすことによりサービスの質を維持する手法) 109 ネットワーク上のサービスには、利用者数の爆発的な増加を受け入れるスケールアウト(サーバの数を増やすことによりサービスの質を維持する手法)
108 が必須である。 110 が必須である。
109 安定したネットワークサービスを提供するためには、分散プログラムに信頼性とスケーラビリティが要求される。 111 安定したネットワークサービスを提供するためには、分散プログラムに信頼性とスケーラビリティが要求される。
110 ここでいう信頼性とは、定められた環境下で安定して仕様に従った動作を行うことを指す。 112 ここでいう信頼性とは、定められた環境下で安定して仕様に従った動作を行うことを指す。
111 113
112 分散プログラムには以下の３つの要素がある\cite{Framework}。 114 分散プログラムには以下の３つの要素がある\cite{kono05f}。
113 \begin{itemize} 115 \begin{itemize}
114 \item {ノード内の計算} 116 \item {ノード内の計算}
115 \item {ノード間通信} 117 \item {ノード間通信}
116 \item {地理的に分散したノード} 118 \item {地理的に分散したノード}
117 \end{itemize} 119 \end{itemize}
138 木に対する変更をlogとして記録し、それをAliceによって通信し、分散データベースを構成している。 140 木に対する変更をlogとして記録し、それをAliceによって通信し、分散データベースを構成している。
139 141
140 Jungle では、木のノードの位置を NodePath クラスを使って表す。 NodePath クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。 NodePath クラスを用いて \textless -1,0,2,3 \textgreater を表している際の例を(図\ref{fig:nodepath})に示す。 142 Jungle では、木のノードの位置を NodePath クラスを使って表す。 NodePath クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。 NodePath クラスを用いて \textless -1,0,2,3 \textgreater を表している際の例を(図\ref{fig:nodepath})に示す。
141 \begin{figure}[htpb] 143 \begin{figure}[htpb]
142 \begin{center} 144 \begin{center}
143 \includegraphics[width=60mm]{pic/nodepath.pdf} 145 \includegraphics[width=50mm]{pic/nodepath.pdf}
144 \end{center} 146 \end{center}
145 \caption{NodePath} 147 \caption{NodePath}
146 \label{fig:nodepath} 148 \label{fig:nodepath}
147 \end{figure} 149 \end{figure}
148 150
176 簡単な方法を実装した。多数決などの複雑な分散機構を載せることも将来的には可能である。 178 簡単な方法を実装した。多数決などの複雑な分散機構を載せることも将来的には可能である。
177 通信部分はAliceを用いて実装されているので、Jungleの分散構成は Alice のToplogy Manager によって動的あるいは静的に構成される。 179 通信部分はAliceを用いて実装されているので、Jungleの分散構成は Alice のToplogy Manager によって動的あるいは静的に構成される。
178 180
179 \begin{figure}[htbp] 181 \begin{figure}[htbp]
180 \centering 182 \centering
181 \includegraphics[width=100mm]{pic/tree.pdf} 183 \includegraphics[width=50mm]{pic/tree.pdf}
182 \caption{ツリー型のトポロジー} 184 \caption{ツリー型のトポロジー}
183 \label{fig:tree} 185 \label{fig:tree}
184 \end{figure} 186 \end{figure}
185 187
186 (図\ref{fig:tree}）の矢印の流れを以下に示す。 188 (図\ref{fig:tree}）の矢印の流れを以下に示す。
221 実行される CS がある。 223 実行される CS がある。
222 Start CSはどのDSにも依存しない。つまりInput DSを持たない。 224 Start CSはどのDSにも依存しない。つまりInput DSを持たない。
223 このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 225 このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。
224 226
225 227
226 \lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java} 228 \lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegment]{source/StartCodeSegment.java}
227 \lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java} 229 \lstinputlisting[label=src:CodeSegment, caption=CodeSegment]{source/TestCodeSegment.java}
228 230
229 \newpage 231 \newpage
230 232
231 ソースコード \ref{src:StartCodeSegment} は、5行目で次に実行させたいCS(ソースコード \ref{src:CodeSegment} )を作成している。 233 ソースコード \ref{src:StartCodeSegment} は、5行目で次に実行させたいCS(ソースコード \ref{src:CodeSegment} )を作成している。
232 8行目でOutput DS APIを通してLocal DSMに対してDSをputしている。 234 8行目でOutput DS APIを通してLocal DSMに対してDSをputしている。
286 このように、InputDSを記述するには、一度フィールドでReceiverをcreateして、その後Reveiverに対してsetKeyで待ち合わせるkeyを指定しなければならない。 288 このように、InputDSを記述するには、一度フィールドでReceiverをcreateして、その後Reveiverに対してsetKeyで待ち合わせるkeyを指定しなければならない。
287 このようにインプットの処理が分離されてしまっていては、記述が煩雑な上にコードを読んだ際にどのkeyに対して待ち合わせを行っているのか直感的に分からない。 289 このようにインプットの処理が分離されてしまっていては、記述が煩雑な上にコードを読んだ際にどのkeyに対して待ち合わせを行っているのか直感的に分からない。
288 290
289 さらに、setKeyは明確な記述場所が決まっていないため、そのDSを待ち合わせているCS以外からも呼び出せてしまう(ソースコード\ref{src:StartSetKey})。 291 さらに、setKeyは明確な記述場所が決まっていないため、そのDSを待ち合わせているCS以外からも呼び出せてしまう(ソースコード\ref{src:StartSetKey})。
290 292
291 \lstinputlisting[label=src:StartSetKey, caption=setKeyを外部から呼び出す例]{source/StartSetKey.java} 293 \lstinputlisting[label=src:StartSetKey, caption=setKey]{source/StartSetKey.java}
292 \lstinputlisting[label=src:SetKey, caption=外部setKeyによりどのkeyを待っているかがわからないCSの例]{source/SetKey.java} 294 \lstinputlisting[label=src:SetKey, caption=Seprated setKey]{source/SetKey.java}
293 295
294 このような書き方をされると、CSだけを見てどのkeyに対して待ち合わせを行っているのかわからないため、setKeyを呼び出しているコードを辿る必要がある。 296 このような書き方をされると、CSだけを見てどのkeyに対して待ち合わせを行っているのかわからないため、setKeyを呼び出しているコードを辿る必要がある。
295 これでは見通しが悪いため、どこでkeyを指定するのか明確にすべきである。 297 これでは見通しが悪いため、どこでkeyを指定するのか明確にすべきである。
296 298
297 可読性の低いコードはプログラマの負担となるため、CSが何を待ち合わせているのかそのCSを見ただけで理解できるように記述の分離問題を改善しなくてはならない。 299 可読性の低いコードはプログラマの負担となるため、CSが何を待ち合わせているのかそのCSを見ただけで理解できるように記述の分離問題を改善しなくてはならない。
370 このように、アノテーションを用いたことで、Aliceの記述の分離問題が解決された。 372 このように、アノテーションを用いたことで、Aliceの記述の分離問題が解決された。
371 また、keyを変数名にしたことで、動的なkeyの指定や、keyと変数名の不一致による可読性の低下を防ぐことができた。 373 また、keyを変数名にしたことで、動的なkeyの指定や、keyと変数名の不一致による可読性の低下を防ぐことができた。
372 374
373 リモートノードに対してTake/Peekする際は、TakeFrom/PeekFromのアノテーションを用いる(ソースコード\ref{src:remotetake})。 375 リモートノードに対してTake/Peekする際は、TakeFrom/PeekFromのアノテーションを用いる(ソースコード\ref{src:remotetake})。
374 376
375 \lstinputlisting[label=src:remotetake, caption=TakeFromの例]{src/RemoteInputDG.java} 377 \lstinputlisting[label=src:remotetake, caption=TakeFrom]{src/RemoteInputDG.java}
376 378
377 なお、圧縮のMeta ComputationはAliceと同様で、指定する際にDGM名の前にcompressedをつける(ソースコード\ref{src:compresslocal})。 379 なお、圧縮のMeta ComputationはAliceと同様で、指定する際にDGM名の前にcompressedをつける(ソースコード\ref{src:compresslocal})。
378 380
379 \lstinputlisting[label=src:compresslocal, caption=Remoteから圧縮して受け取る例]{src/CompressLocal.java} 381 \lstinputlisting[label=src:compresslocal, caption=Remoteから圧縮して受け取る例]{src/CompressLocal.java}
380 382
381 383
382 OutputAPIにはput/flipを用意した。 384 OutputAPIにはput/flipを用意した。
383 基本的なシンタックスはAliceと同様だが、Christieではput/flipのメソッドはCodeGear.classに用意されている。 385 基本的なシンタックスはAliceと同様だが、Christieではput/flipのメソッドはCodeGear.classに用意されている。
384 そのためCodeGear.classを継承するCGで直接putメソッドを呼ぶことができる(ソースコード\ref{src:remoteput})。 386 そのためCodeGear.classを継承するCGで直接putメソッドを呼ぶことができる(ソースコード\ref{src:remoteput})。
385 387
386 \lstinputlisting[label=src:remoteput, caption=putの例]{src/RemotePut.java} 388 \lstinputlisting[label=src:remoteput, caption=put]{src/RemotePut.java}
387 389
388 そのため、ChristieにはAliceのODSにあたる部分がない。 390 そのため、ChristieにはAliceのODSにあたる部分がない。
389 ODSを経由するより直接DGMに書き込むような記述のほうが直感的であると考えたためである。 391 ODSを経由するより直接DGMに書き込むような記述のほうが直感的であると考えたためである。
390 圧縮を指定してのputも、Alice同様DGM名の前にcompressedをつける。 392 圧縮を指定してのputも、Alice同様DGM名の前にcompressedをつける。
391 393
420 AliceではnewすればCGが待ちに入ったが、Christieでは一度CGをnewしないとアノテーションから待ち合わせを行う処理ができないため、newの後にsetupを行う。 422 AliceではnewすればCGが待ちに入ったが、Christieでは一度CGをnewしないとアノテーションから待ち合わせを行う処理ができないため、newの後にsetupを行う。
421 そのため、CGの生成には必ずCGMが必要になる。 423 そのため、CGの生成には必ずCGMが必要になる。
422 runでCGMを受け渡すのはこのためである。 424 runでCGMを受け渡すのはこのためである。
423 なお、StartCGはインプットを持たないため、setupを行う必要がなく、newされた時点でrunが実行される。 425 なお、StartCGはインプットを持たないため、setupを行う必要がなく、newされた時点でrunが実行される。
424 426
425 \subject{まとめ} 427 \section{Unixファイルシステムとの比較}
428
429 Christie を分散ファイルシステムとして使うのと、Unixファイルシステム上の分散ファイルシステムとの違いについて考察する。
430
431 Christie に格納されるのはオブジェクトであり、型のないテキストファイルとは異なる。もちろん、文字列をそのまま格納することも
432 できるが、巨大な文字列にはなんらかの構造を与えてランダムアクセスなどができるようにする。その意味で、Unixファイルシステム
433 でもファイルには必ず構造が入っている。
434
435 Unixファイルにはディレクトリ構造があり、ディレクトリの構造にはトランザクションが導入されている。Christieの場合は、
436 Christie の同期機構としてトランザクションが定義される。
437
438 Unixファイル全体はiノードを使ったB-Tree構造を持つ。これらはディレクトリ構造による木構造のパスでアクセスされる。
439 Christie ではパスとディレクトリは木構造のデータベースとして定義される。
440
441 Unixファイルの持続性はディスク上のiノードの持続性によって実現される。Christieは持続性のあるノードに木構造を
442 複製することによって持続性を実現する。
443
444 Unixファイルはread/writeによりアクセスするが、Christieではメモリ上のオブジェクトであり、read/writeではなく
445 名前で指定された木に対する get/put で変更を行う。
446
447 持続性のあるノードに複製されたChristieのオブジェクトはメモリ上から削除しても良い。再度必要な場合は、パスを
448 用いて持続性のあるノードから複製する。
449
450 \section{まとめ}
426 451
427 分散木構造データベースJungleと、分散フレームワークAliceについて考察し、両者を統一する形で、分散フレームワークChristieを 452 分散木構造データベースJungleと、分散フレームワークAliceについて考察し、両者を統一する形で、分散フレームワークChristieを
428 提案した。 453 提案した。
429 454
430 Christie ではアノテーションを用いて、Aliceの欠点であった記述の分離と型の整合性をコンパイル時に解決できない問題を解決した。 455 Christie ではアノテーションを用いて、Aliceの欠点であった記述の分離と型の整合性をコンパイル時に解決できない問題を解決した。
438 463
439 464
440 465
441 %参考文献　 466 %参考文献　
442 \bibliographystyle{ipsjunsrt} 467 \bibliographystyle{ipsjunsrt}
443 \bibliography{sigos} 468 \bibliography{ref}
444 469
445 \end{document} 470 \end{document}