Mercurial > hg > Papers > 2018 > nozomi-master
changeset 162:15fed7e1263e
change chapter 1
| author | Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sun, 04 Feb 2018 16:13:57 +0900 |
| parents | cc301066b983 |
| children | def221edf421 6d6fb11dbd57 |
| files | chapter1.mm paper/abstract.tex paper/nozomi-master.pdf paper/nozomi-master.tex paper/reference.bib |
| diffstat | 5 files changed, 141 insertions(+), 86 deletions(-) [+] |
line wrap: on
line diff
--- a/chapter1.mm Sat Feb 03 20:00:43 2018 +0900 +++ b/chapter1.mm Sun Feb 04 16:13:57 2018 +0900 @@ -8,19 +8,37 @@ <node CREATED="1517643751033" ID="ID_1609822651" MODIFIED="1517643758092" TEXT="可読性がバグを抑える"/> </node> <node CREATED="1517641615641" ID="ID_1949135210" MODIFIED="1517641667342" TEXT="分散性を意識して書けるプロトコルとそれを信頼性高く動かす環境"/> +<node CREATED="1517641818884" ID="ID_1201918526" MODIFIED="1517641835319" TEXT="拡張があったとき、できるだけ仕様を変更することなく記述できること"/> </node> </node> <node CREATED="1517639914032" ID="ID_1831889200" MODIFIED="1517639917192" TEXT="スケーラビリティ"> <node CREATED="1517640055580" ID="ID_718149200" MODIFIED="1517640057010" TEXT="分散ソフトウェアに対して単純にノードを 追加するだけで性能を線形的に上昇させることができる性質"/> -<node CREATED="1517641818884" ID="ID_1201918526" MODIFIED="1517641835319" TEXT="拡張があったとき、できるだけ仕様を変更することなく記述できること"/> +<node CREATED="1517656112336" ID="ID_1367174953" MODIFIED="1517656118247" TEXT="分散アルゴリズム"/> +</node> +</node> +<node CREATED="1517639946066" ID="ID_1859525676" MODIFIED="1517639956125" POSITION="right" TEXT="しかしそれらの記述は容易ではない"> +<node CREATED="1517656182435" ID="ID_851631258" MODIFIED="1517667405717" TEXT="場所を選択するときラベルを使うが、使い方が何が良いかわからない"> +<node CREATED="1517656223748" ID="ID_495480288" MODIFIED="1517656290983" TEXT="同じ動きをするものは同じラベルを使いたい"> +<node CREATED="1517656251938" ID="ID_1524899027" MODIFIED="1517656258784" TEXT="ParentとかChildとか"/> +</node> +<node CREATED="1517656280358" ID="ID_228362146" MODIFIED="1517656288989" TEXT="Akkaは名前問題を解決してない"/> +<node CREATED="1517656295099" ID="ID_765240484" MODIFIED="1517656303869" TEXT="Hezelcastは基本マルチキャスト"/> </node> </node> -<node CREATED="1517639946066" ID="ID_1859525676" MODIFIED="1517639956125" POSITION="right" TEXT="しかしそれらの記述は容易ではない"/> +<node CREATED="1517657306606" ID="ID_1090720398" MODIFIED="1517657321833" POSITION="right" TEXT="それぞれを比較項目ごとに記述"> +<node CREATED="1517657325260" ID="ID_1461423334" MODIFIED="1517660845968" TEXT="記述パラダイム"/> +<node CREATED="1517667503872" ID="ID_853748861" MODIFIED="1517667513663" TEXT="分散を支える機能"> +<node CREATED="1517667517673" ID="ID_1194027129" MODIFIED="1517667523121" TEXT="トポロジー構成"/> +<node CREATED="1517667523618" ID="ID_344829747" MODIFIED="1517667534179" TEXT="障害耐性"/> +<node CREATED="1517667534933" ID="ID_1353573731" MODIFIED="1517667537820" TEXT="圧縮"/> +<node CREATED="1517667538484" ID="ID_927048052" MODIFIED="1517667542455" TEXT="NAT越え"/> +</node> +</node> <node CREATED="1517640070838" ID="ID_292966082" MODIFIED="1517640077416" POSITION="right" TEXT="Akkaでは"> -<node CREATED="1517640078256" ID="ID_562974138" MODIFIED="1517649427560" TEXT="信頼性（どんなプロトコルと記述？）"> +<node CREATED="1517640078256" ID="ID_562974138" MODIFIED="1517660843661" TEXT="信頼性（どんなプロトコルと記述？）"> <node CREATED="1517640082329" ID="ID_476332761" MODIFIED="1517640091606" TEXT="アクターモデルでの非同期メッセージパッシング"> <node CREATED="1517640136278" ID="ID_888508971" MODIFIED="1517640147254" TEXT="ケース文でわける"> -<node CREATED="1517640874767" ID="ID_222143205" MODIFIED="1517640883560" TEXT="複数のインプットを待つときに見づらい"/> +<node CREATED="1517640874767" ID="ID_222143205" MODIFIED="1517657242419" TEXT="複数のインプットを待つ場合が書きづらい"/> <node CREATED="1517640169940" ID="ID_1326641875" MODIFIED="1517640189162" TEXT="受け取ったデータで通信が一箇所集中してケース文が多くなる問題"/> </node> <node CREATED="1517640175850" ID="ID_1543233769" MODIFIED="1517640885545" TEXT="トポロジー的にどこにいくのか明確ではない"/> @@ -41,7 +59,7 @@ </node> <node CREATED="1517640110954" ID="ID_1574294271" MODIFIED="1517640115678" POSITION="right" TEXT="Hazelcastでは"> <node CREATED="1517641246512" ID="ID_1824306437" MODIFIED="1517649436578" TEXT="信頼性（どんなプロトコルと記述？）"> -<node CREATED="1517645390188" ID="ID_562382539" MODIFIED="1517649350818" TEXT="キーと値の1対1でデータを管理インメモリ・データグリッド"> +<node CREATED="1517645390188" ID="ID_562382539" MODIFIED="1517662221258" TEXT="キーと値の1対1でデータを管理インメモリ・データグリッド"> <node CREATED="1517649277675" ID="ID_1581252535" MODIFIED="1517649581233" TEXT="複数のサーバが同じメモリを持っているように扱う？"/> <node CREATED="1517647444870" ID="ID_1010639767" MODIFIED="1517652069585" TEXT="どこに投げるか意識しない"/> <node CREATED="1517652047551" ID="ID_492718831" MODIFIED="1517652057195" TEXT="どんなトポロジーかよくわかんない"/> @@ -69,13 +87,21 @@ <node CREATED="1517640292149" ID="ID_1696068134" MODIFIED="1517640297907" TEXT="Meta Computation"> <node CREATED="1517640298432" ID="ID_1446452598" MODIFIED="1517649497129" TEXT="TopologyManager"> <node CREATED="1517641052633" ID="ID_1901942381" MODIFIED="1517641090468" TEXT="簡単に分散トポロジーにノードの追加ができる"/> +<node CREATED="1517641576766" ID="ID_635736281" MODIFIED="1517656580812" TEXT="NAT越えを実装しようとしたが今のAliceでは困難であると判明"/> +<node CREATED="1517656657193" ID="ID_1883681508" MODIFIED="1517656661221" TEXT="KeepAlive"/> <node CREATED="1517641282796" ID="ID_1309059520" MODIFIED="1517642964180" TEXT="NAT超えも実装できればよりスケーラブルな環境が提供できる"/> </node> -<node CREATED="1517641555723" ID="ID_1694410938" MODIFIED="1517655026043" TEXT="仕様変更を抑えたデータ形式の変更"/> +<node CREATED="1517641555723" ID="ID_1694410938" MODIFIED="1517655026043" TEXT="仕様変更を抑えたデータ形式の変更"> +<node CREATED="1517656415785" ID="ID_1088495911" MODIFIED="1517656424176" TEXT="圧縮/flip"/> </node> </node> </node> -<node CREATED="1517641576766" ID="ID_635736281" MODIFIED="1517643002604" POSITION="right" TEXT="NAT越えを実装しようとしたが今のAliceでは困難であると判明"/> -<node CREATED="1517640214443" ID="ID_12686996" MODIFIED="1517643014382" POSITION="right" TEXT="更に今よりもユーザーフレンドリーなシンタックスにすることで分散計算の見通しを良くする"/> +</node> +<node CREATED="1517656384632" ID="ID_1478018271" MODIFIED="1517656552057" POSITION="right" TEXT="Christieでは"> +<node CREATED="1517640214443" ID="ID_12686996" MODIFIED="1517656562565" TEXT="更に今よりもユーザーフレンドリーなシンタックスにすることで分散計算の見通しを良くする"> +<node CREATED="1517656350176" ID="ID_234692256" MODIFIED="1517656353790" TEXT="記述の煩雑さ"/> +<node CREATED="1517656366330" ID="ID_1587578721" MODIFIED="1517656376368" TEXT="ラベルはstaticに記述したほうが見通しが良い"/> +</node> +</node> </node> </map>
--- a/paper/abstract.tex Sat Feb 03 20:00:43 2018 +0900 +++ b/paper/abstract.tex Sun Feb 04 16:13:57 2018 +0900 @@ -5,7 +5,6 @@ この手法を用いて、スケーラブルな分散プログラムを信頼性高く記述できることを目的とした並列分散フレームワークAliceを開発した。 Aliceでは通常の処理の間にMeta Computationという処理を挟むことで、コードを大きく変更せずに挙動変更を可能にしている。 - Aliceが実用的な分散アプリケーションを記述でき、Meta Computationが仕様の変更を抑えた信頼性の高い拡張を可能にするということはTreeVNCの例題などから確認された。 しかし、NAT越えなどのMetaComputationを実装しようとした際、現状では拡張が困難であり再設計が望ましいことが判明した。 @@ -14,7 +13,6 @@ 本研究ではAliceで得られた知見を元に分散フレームワークChristieの設計を行った。 Christieでは、APIにJavaのアノテーションを用いることでシンプルな記述で信頼性の高いプログラミングを実現する。 また、Data Gear Managerを複数立ち上げられるようにしたことでNAT越えなどの拡張に対応した。 -そして他フレームワークとAPIの比較を行った。
--- a/paper/nozomi-master.tex Sat Feb 03 20:00:43 2018 +0900 +++ b/paper/nozomi-master.tex Sun Feb 04 16:13:57 2018 +0900 @@ -97,31 +97,68 @@ %chapters -\chapter{分散プログラミングの信頼性向上} +\chapter{分散フレームワークへの要求事項} スマートフォンやタブレット端末の普及率が増加している。 それに伴いインターネット利用者数も増加しており、ネットワーク上のサービスには、信頼性とスケーラビリティーが要求される。 + ここでいう信頼性とは、定められた環境下で安定して仕様に従った動作を行うことを指す。 +これには仕様を記述しやすさも含まれ、可読性が高いほどバグを抑えた信頼性が高いと言える。 + またスケーラビリティーとは、分散ソフトウェアに対して単純にノードを追加するだけで性能を線形的に上昇させることができる性質である。 +分散フレームワークには分散トポロジーの構成などの分散アルゴリズムが求められる。 + しかし、これらをもつ分散プログラムをユーザーが一から記述することは容易ではない。 +なぜなら、並列で動く分散した資源を意識しながら記述するのは容易ではなく、また、どのように分散したノードの選択を行えば良いのか明確ではないからである。 + +本章では、分散フレームワークであるAkka\cite{Akka}、Hazelcast\cite{Hazelcast}と当研究室で開発したAlice\cite{Alice1}\cite{Alice2}の記述モデル・分散処理を支える機能を比較しながら、本論文で設計するChristieの設計目標を述べる。 -これらの問題を解決するために、当研究室ではデータをData Segment、タスクをCode Segmentという単位で記述するプログラミング手法を導入した分散フレームワークAlice を開発した。 +\section{記述モデル} +Akkaではアクターモデルという、アクターと呼ばれるオブジェクト同士が並列で非同期メッセージを送受信するモデルを採用している。 +アクターはそれぞれメッセージボックスを持っており、受け取ったメッセージをcase文を使って順次処理していく。 +アクター同士は固有のアドレスで指定してメッセージを送り合う。 -Aliceが実用的な分散アプリケーションを記述でき、仕様の変更を抑えた信頼性の高い拡張を可能にするということは、水族館の例題やTreeVNCの例題から確認された。 -しかし、AliceにNAT越えの機能を実装しようとした際、Data Segment Managerが1つしか持てないために拡張が困難であることが分かった。 -また、AliceではAPI設計が煩雑で、プログラマが処理の順番やデータの型を考慮して書く必要があった。 -これではバグを引き起こす可能性が高いため、信頼性を上げるにはより直感的なAPIで再設計すべきだと考えた。 +また、Hazelcastはキーと値の1対1でデータを管理するインメモリ・データグリッドであり、複数のサーバが同じメモリかのように扱う。 +プログラマはサーバを意識せずに共有のMapに対してデータをget/putできる。 + +AliceはタスクをCode Segment、データをData Segmentという単位で記述し、Code SegmentはインプットとなるData Segmentが全て揃うと並列に実行される。 +Data SegmentはData Segment Managerというノードごとに存在するデータベースによって管理される。 +各ノードにはラベル付きのプロキシであるRemote Data Segment Managerを立て、ラベルを指定してアクセスする。 + +Akkaでは、メッセージが集中した場合にそれを処理するcase文が増えてしまう問題や、複数のインプットを待ち合わせたい場合に記述が煩雑になる問題があった。 +しかしAliceはインプットを明確に記述でき、複数のインプットを持てるため、そのような煩雑さがない。 -本研究では、Aliceから得られた知見をもとに、分散フレームワークChristieの設計を行う。 -Christieでは、シンプルな記述で信頼性の高いスケーラブルな分散プログラムの作成を可能にする。 -また、当研究室で開発している言語CbCと互換可能な設計を目指す。 +また、Hazelcastではロケーション透過性が高く、データはマルチキャストで通信するため、プログラマがトポロジーを把握しにくかった。 +Akkaでは送り先をドメインで指定するためどのような処理をするアクターにメッセージを渡しているのか分かりづらかった。 +一方でAliceでは他のノードにラベルでアクセスするため、分散計算の見通しが良い。 + +しかしAliceのAPIシンタックスは直感的でなく、プログラマが処理の順番やデータの型を考慮して書く必要があった。 +これではバグを引き起こす可能性が高いため、信頼性を上げるにはよりユーザーフレンドリーなシンタックスで再設計すべきだと考えた。 +\section{分散処理を支える機能} +ここではスケーラビリティの指標として特にトポロジーの構成、フォールト・トレランス性、圧縮通信、NAT越えについて比較する。 + +AkkaではAkka Streamという機能で処理の流れが記述できる。 +N入力1出力、1入力N出力、出力のみ、などが用意されたJunctionsと呼ばれる要素をつなぎ合わせることでトポロジーを記述する。 +また、Akkaではアクターで親子関係を構成でき、親アクターは子アクターを監視し障害が起こった際に再起動や終了といった処理を指定できる。 -%分散フレームワークへの要求 -%・スケーラブルなプログラミングの実現 -% ・記述性の高さ、テストのしやすさがバグをおさえる。 -%・信頼性の高い分散トポロジーを意識した通信プロトコル。 +HazelcastにはMapやQueueといったメモリ空間内のデータ構造は指定できるが、具体的なノード間トポロジーを記述する機構がない。 +１つのサーバで障害が起きても他のサーバがデータを共有しているため、データを失うことなく素早く復旧ができる。 + +一方、AliceではTopologyManagerという機構が分散ノードを管理しており、静的・動的なトポロジーを自動構成する。静的トポロジーではプログラマがトポロジーを図として記述できるため、より分かりやすく詳細な設定ができる。 +また、TopologyManagerのKeepAlive機能がノードを監視しており、どこかのノードに障害が起こればトポロジーを再構成するといった対応ができる。 + +\newpage -% 分散計算の見通しを良くする +また、通信するデータの圧縮を指定したい場合、Akka・Hazelcastはシリアライザが用意されているため、そのメソッドを呼び出すことでzip/unzipを行う。 +一方でAliceは圧縮したままの転送を想定した圧縮・転送機能を持っている。 +Data Segment内に圧縮と非圧縮の両形式を同時に持てるため、受け取った圧縮データを展開をしながら圧縮したまま別ノードに転送することができる。 +また、圧縮するには送信する宛先ラベルに"compressed"とつけるだけでよく、データ取得時に自動で展開もされるため、プログラマがコードを追加する必要がなく圧縮・非圧縮を簡単に切り替えられる。 + +HazelcastではNAT越えをサポートする機能はなく、プログラマが自前で書かなければならない。 +Akkaではノードの設定にグローバルアドレスとプライベートアドレスを両方登録することでNATを越えた通信を可能にする。 +AliceにNAT越えの機能はないが、TopologyManagerが各ノードのData Segment Managerと通信してトポロジー管理をしており、TopologyManager/Data Segment Managerを複数立ち上げることによりプライベートトポロジーとグローバルトポロジーの同時構成が可能だと考えた。 +しかし、Aliceが複数のData Segment Managerを持てない実装だったため、AliceのままでNAT越えを実装することは困難であると判明した。 +よりスケーラブルな分散環境を提供するためにも、Aliceを再設計する必要がある。 @@ -154,7 +191,6 @@ 一つのkeyに対して複数のDSをputするとFIFO的に処理される。なのでData Segment Managerは通常のデータベースとは異なる。 -\newpage \section{DataSegmentManager} DS Manager（以下DSM）にはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。 @@ -162,6 +198,7 @@ Remote DSMは他ノードのLocal DSMに対応するproxyであり、接続しているノードの数だけ存在する（図 \ref{fig:Remote DSM} ）。 他ノードのLocal DSMに書き込みたい場合はRemote DSMに対して書き込めば良い。 +\newpage \begin{figure}[h] \begin{center} @@ -733,16 +770,60 @@ そのため子クラスは親クラスのデータ形式を保持しながら新しいデータ形式を持つ形になっている。 クラスを見るだけで今どの形式を保持しているかわかるようになったため、デバッグがしやすくなった。 +\section{通信フロー} +本章で説明したChristieの設計をいくつか例をあげてChristieの通信のフローをシーケンス図を用いて解説する。 +図\ref{fig:localSequence}はLocalDGMにTakeを行い、LocalDGM内にDGがあったときの処理の流れである。 + +\begin{figure}[h] +\begin{center} +\includegraphics[width=160mm]{images/LocalSequence.pdf} +\end{center} +\caption{LocalDGMにTakeしたときのフロー} +\label{fig:localSequence} +\end{figure} + +プログラマはmainでCGMとStartCGを生成する。 +CGMと同時にLocalDGMは作られる。 +CGが生成され、setupメソッドが呼ばれるとアノテーションからTAKEコマンドが作られ実行される。 +CGは生成したインプットコマンドの総数を初期値としたカウンタを持っており、コマンドが解決される（InputDGが揃う）たびにカウンタは減っていき、0になるとrun内の処理がThreadPoolへ送られる。 -\chapter{Christieの評価} -\section{Aliceとの分散性能測定} +\newpage + +図\ref{fig:remotePutSequence}は、LocalDGMにTakeを行うが、LocalDGM内にDGがなかったためにPutの待ち合わせをするときの処理の流れである。 +mainなどの最初の処理は図\ref{fig:localSequence}と同様のため省略する。 + +\begin{figure}[h] +\begin{center} +\includegraphics[width=160mm]{images/RemotePutSequence.pdf} +\end{center} +\caption{RemoteDGMにPutしたときのフロー} +\end{figure} +LocalまたはリモードノードからPUTコマンドが実行された際、もしwaitListにPutしたDGを待っているコマンドがあれば実行される。 + + +\newpage +図\ref{fig:remoteTakeSequence}は、RemoteDGMにTakeを行ったときの処理の流れである。 -\section{他フレームワークとの比較} -\subsection{Akka} -\subsection{Corba} -\subsection{Erlang} -\subsection{Hazelcast} +\begin{figure}[h] +\begin{center} +\includegraphics[width=165mm]{images/RemoteTakeSequence.pdf} +\end{center} +\caption{RemoteDGMにTakeしたときのフロー} +\label{fig:remoteTakeSequence} +\end{figure} + +StartCGで事前にRemoteDGMを生成しておく。 +RemoteTakeアノテーションからRemoteDGMに対するTakeコマンドを生成し実行する。 +RemoteTakeのようにリモートからの応答を待つコマンドはRemoteDGMのwaitListに入る。 +そして、MessagePack形式に変換したRemoteCommandを作成し、それをRemoteDGMが参照している別ノードのLocalDGMに送る。 + +それを受け取った側のLocalDGMは、DGがあればREPLYコマンドを生成して送り返す。 +もしDGがなければ、リモートから来たコマンドもローカルの場合と同様にLocalDGMのwaitListに入る。 + +REPLYを受け取るとRemoteDGMはwaitListに入っていたコマンドを解決する。 + + \chapter{まとめ} @@ -761,7 +842,9 @@ \section{実用性の検証} -%Aliceと同等の性能を持っているかを分散処理の例題を用いて測定する必要がある。 +本論文ではChristieの設計と基本実装までを行ったが、それがどれほどの分散性能を持っているのかはまだ計測していない。 +CG/DGのプログラミングモデルなどの基本的にはAliceと同じであるが、アノテーションの処理がどれほどのオーバーヘッドに繋がっているか現時点では不明である。 +そのため、Aliceと同等の速度性能を持っているか、コードの量や複雑度は抑えられているかなどを分散処理の例題を用いて測定する必要がある。 \section{GearsOSへの移行} GearsOSはまだ開発途中であったため、本論文の作成時点ではChristieのような分散機能を実装することが叶わなかった。 @@ -803,58 +886,6 @@ \lstinputlisting[label=src:setup, caption=reflectionAPIでフィールドの情報を取得]{source/christie/Setup.java} フィールドから取得したDGとアノテーションから取得したkeyからインプットコマンド（TAKE/PEEK）を生成し、DGMへ送って実行する。 -\newpage - -\section{通信フロー} -いくつか例をあげてChristieの通信のフローをシーケンス図を用いて解説する。 -図\ref{fig:localSequence}はLocalDGMにTakeを行い、LocalDGM内にDGがあったときの処理の流れである。 - -\begin{figure}[h] -\begin{center} -\includegraphics[width=160mm]{images/LocalSequence.pdf} -\end{center} -\caption{LocalDGMにTakeしたときのフロー} -\label{fig:localSequence} -\end{figure} - -プログラマはmainでCGMとStartCGを生成する。 -CGMと同時にLocalDGMは作られる。 -CGが生成され、setupメソッドが呼ばれるとアノテーションからTAKEコマンドが作られ実行される。 -CGは生成したインプットコマンドの総数を初期値としたカウンタを持っており、コマンドが解決される（InputDGが揃う）たびにカウンタは減っていき、0になるとrun内の処理がThreadPoolへ送られる。 - - -\newpage - -図\ref{fig:remotePutSequence}は、LocalDGMにTakeを行うが、LocalDGM内にDGがなかったためにPutの待ち合わせをするときの処理の流れである。 -mainなどの最初の処理は図\ref{fig:localSequence}と同様のため省略する。 - -\begin{figure}[h] -\begin{center} -\includegraphics[width=160mm]{images/RemotePutSequence.pdf} -\end{center} -LocalまたはリモードノードからPUTコマンドが実行された際、もしwaitListにPutしたDGを待っているコマンドがあれば実行される。 - - -\newpage -図\ref{fig:remoteTakeSequence}は、RemoteDGMにTakeを行ったときの処理の流れである。 - -\begin{figure}[h] -\begin{center} -\includegraphics[width=165mm]{images/RemoteTakeSequence.pdf} -\end{center} -\caption{RemoteDGMにTakeしたときのフロー} -\label{fig:remoteTakeSequence} -\end{figure} - -StartCGで事前にRemoteDGMを生成しておく。 -RemoteTakeアノテーションからRemoteDGMに対するTakeコマンドを生成し実行する。 -RemoteTakeのようにリモートからの応答を待つコマンドはRemoteDGMのwaitListに入る。 -そして、MessagePack形式に変換したRemoteCommandを作成し、それをRemoteDGMが参照している別ノードのLocalDGMに送る。 - -それを受け取った側のLocalDGMは、DGがあればREPLYコマンドを生成して送り返す。 -もしDGがなければ、リモートから来たコマンドもローカルの場合と同様にLocalDGMのwaitListに入る。 - -REPLYを受け取るとRemoteDGMはwaitListに入っていたコマンドを解決する。 \chapter{謝辞}