Mercurial > hg > Papers > 2016 > nozomi-thesis
view paper/main.tex @ 8:ef17e4dc6216
after check
author | Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 17 Feb 2016 19:51:47 +0900 |
parents | 5fa2e97fe3c6 |
children | 90aaf305aed6 |
line wrap: on
line source
\documentclass[a4j,12pt]{jreport} \usepackage[dvipdfmx,hiresbb]{graphicx} \usepackage{mythesis} \usepackage{multirow} \usepackage{listings} \usepackage{url} \lstset{% language={Java},%使用言語 basicstyle={\small},%書体 commentstyle={\small\itshape},%コメントの書体 keywordstyle={\small\bfseries},%キーワードの書体 %identifierstyle={\small},% %ndkeywordstyle={\small},% stringstyle={\small},%文字列の書体 frame={trlb},%外枠 breaklines=true,%改行 columns=[l]{fullflexible},% xrightmargin=0zw,% xleftmargin=3zw,% numbers=left,%行番号の表示 numberstyle={\scriptsize},%行番号の書体 numbersep=1zw,% stepnumber=1, lineskip=-0.5ex,% captionpos=b,%キャプションの位置 } \renewcommand{\lstlistingname}{Code} \usepackage{here} \setlength{\itemsep}{-1zh} \title{分散フレームワークAliceのMeta Data Segment} \icon{ \includegraphics[width=50mm,bb=0 0 595 842]{fig/ryukyu.pdf} } \year{平成27年度 卒業論文} \belongto{琉球大学工学部情報工学科} \author{e125769 照屋 のぞみ \\ 指導教員 {河野 真治} } %% %% プリアンブルに記述 %% Figure 環境中で Table 環境の見出しを表示・カウンタの操作に必要 %% \makeatletter \newcommand{\figcaption}[1]{\def\@captype{figure}\caption{#1}} \newcommand{\tblcaption}[1]{\def\@captype{table}\caption{#1}} \makeatother \setlength\abovecaptionskip{0pt} \begin{document} % タイトル \maketitle \baselineskip 17pt plus 1pt minus 1pt \setcounter{page}{0} \tableofcontents % 目次 %\listoffigures % 図目次 %\listoftables % 表目次 %以下のように、章ごとに個別の tex ファイルを作成して、 % main.tex をコンパイルして確認する。 %章分けは個人で違うので下のフォーマットを参考にして下さい。 % はじめに \chapter{Meta Computation による分散プ ログラミングの信頼性向上} \pagenumbering{arabic} スマートフォンやタブレット端末の普及率が増加している。 それに伴いインターネット利用者数も増加しており、ネットワーク上のサービスには、信頼性とスケーラビリティーが要求される。 ここでいう信頼性とは、定められた環境下で安定して仕様に従った動作を行うことをさす。 またスケーラビリティーとは、サービスの利用者が増大した場合、メモリ等のリソースを追加するだけでサービスを維持できる性能をさす。 しかし、これらをもつ分散プログラムをユーザーが一から記述することは容易ではない。 これらの問題の解決のために、データをData Segment、タスクをCode Segmentという単位で記述するプログラミング手法を導入した分散フレームワークAlice\cite{senkokenkyu}\cite{senkokenkyu2} の開発を実現した。 Data Segmentは整数や文字列や構造体などの基本的なデータの集まりである。 Code Segmentは入力となるData Segmentが全て揃ったら処理を開始し計算結果のData Segmentを出力するタスクである。 さらにAliceでは、計算の本質的な処理をComputation、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。 分散アプリケーションにおいて、分散環境の構築や通信処理部分はMeta Computationと言える。 それらの処理をAliceがMeta Computationとして提供することで、プログラマは目的の処理の記述だけで分散処理が実現できる。 また、Meta Computationを指定するだけでComputationを大きく変更せずにプログラムの細かな挙動が変えられるため、変更前の信頼性を破壊せずに拡張ができる。 本研究では、Alice上に実用的な分散アプリケーションの例題である画面共有システムTreeVNC \cite{treeVNC} を構築した。 構築するにあたって、配信される画面データはAliceのData Segementに対応するため、AliceのMeta Data Segmentとして圧縮機能が必要となった。 これらの機能はTreeVNCではad-hocに実装されているが、AliceではこれをMeta Computationとして実装した。 そして、性能・コード量の観点からTreeVNCとの比較を行い、Aliceの実用性を示すと共にAliceのMeta Computationの役割と有効性の評価を行った。 % 基礎概念 \chapter{分散フレームワークAliceの概要} \section{Code Segment と Data Segment} AliceではCode Segment(以下CS)とData Segment(以下DS)の依存関係を記述することでプログラミングを行う。 CSは実行に必要なDSが全て揃うと実行される。CSを実行するために必要な入力されるDSのことをInputDS、CSが計算を行った後に出力されるDSのことをOutput DSと呼ぶ。 データの依存関係にないCSは並列実行が可能である(図 \ref{fig:CS} )。 CSの実行においてDSが他のCSから変更を受けることはない。そのためAliceではデータが他から変更され整合性がとれなくなることはない。 \begin{figure}[htbp] \begin{center} \includegraphics{images/dsandcs2.pdf} \end{center} \caption{CodeSegmentの依存関係 } \label{fig:CS} \end{figure} AliceはJavaで実装されており、DSはJava Objectに相当する。CSはRunnableなObject(void run()を持つObject)に相当する。 プログラマがCSを記述する際は、CodeSegmentクラスを継承する。 DSは数値や文字列などの基本的なデータの集まりを指し、Aliceが内部にもつデータベースによって管理されている。このデータベースをAliceではDS Managerと呼ぶ。 CSは複数のDS Managerを持っている。DSには対になるString型のkeyが存在し、それぞれのManagerにkeyを指定してDSにアクセスする。 一つのkeyに対して複数のDSをputするとFIFO的に処理される。なのでData Segment Managerは通常のデータベースとは異なる。 \section{Data Segment Manager} DS Manager(以下DSM)にはLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のデータベースである。 Remote DSMは他ノードのLocal DSMに対応するproxyであり、接続しているノードの数だけ存在する(図 \ref{fig:Remote DSM} )。 他ノードのLocal DSMに書き込みたい場合はRemote DSMに対して書き込めば良い。 Remote DSMを立ち上げるには、DataSegmentクラスが提供するconnectメソッドを用いる。 接続したいノードのipアドレスとport番号、そして任意のManager名を指定することで立ちあげられる。 その後はManager名を指定してData Segment APIを用いてDSのやり取りを行うため、プログラマはManager名さえ意識すればLocalへの操作もRemoteへの操作も同じ様に扱える。 \begin{figure}[h] \begin{center} \includegraphics[width=150mm]{images/remote_datasegment.pdf} \end{center} \caption{Remote DSMは他のノードのLocal DSMのproxy } \label{fig:Remote DSM} \end{figure} \newpage \section{Data Segment API} DSの保存・取得にはAliceが提供するAPIを用いる。 putとupdate、flipはOutput DS APIと呼ばれ、DSをDSMに保存する際に用いる。 peekとtakeはInput DS APIと呼ばれ、DSをDSMから取得する際に使用する。 \begin{itemize} \item {\ttfamily void put(String managerKey, String key, Object val)} \end{itemize} DSをDSMに追加するためのAPIである。第一引数はLocal DSMかRemote DSMかといったManager名を指定する。そして第二引数で指定されたkeyに対応するDSとして第三引数の値を追加する。 \begin{itemize} \item {\ttfamily void update(String managerKey, String key, Object val)} \end{itemize} updateもDSをDSMに追加するためのAPIである。putとの違いは、queueの先頭のDSを削除してからDSを追加することである。そのためAPI実行前後でqueueの中にあるDSの個数は変わらない。 \begin{itemize} \item{\ttfamily void flip(String managerKey, String key, Receiver val)} \end{itemize} flipはDSの転送用のAPIである。取得したDSに対して何もせずに別のKeyに対し保存を行いたい場合、一旦値を取り出すのは無駄である。flipはDSを受け取った形式のまま転送するため無駄なコピーなくDSの保存ができる。 \begin{itemize} \item {\ttfamily void take(String managerKey, String key)} \end{itemize} takeはDSを読み込むためのAPIである。読み込まれたDSは削除される。要求したDSが存在しなければ、CSの待ち合わせ (Blocking)が起こる。putやupdateによりDSに更新があった場合、takeが直ちに実行される。 \begin{itemize} \item {\ttfamily void peek(String managerKey, String key)} \end{itemize} peekもDSを読み込むAPIである。takeとの違いは読み込まれたDSが削除されないことである。 \newpage \section{Code Segmentの記述方法} CSをユーザーが記述する際にはCodeSegmentクラスを継承して記述する(ソースコード \ref{src:StartCodeSegment} , \ref{src:CodeSegment})。 継承することによりCode Segmentで使用するData Segment APIを利用する事ができる。 Alice には、Start CS (ソースコード \ref{src:StartCodeSegment} )というC の main に相当するような最初に実行される CS がある。 Start CSはどのDSにも依存しない。つまりInput DSを持たない。 このCSをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。 \begin{table}[html] \lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java} \lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java} \end{table} \newpage ソースコード \ref{src:StartCodeSegment} は、5行目で次に実行させたいCS(ソースコード \ref{src:CodeSegment} )を作成している。 8行目でOutput DS APIを通してLocal DSMに対してDSをputしている。 Output DS APIはCSの{\tt ods}というフィールドを用いてアクセスする。 {\tt ods}は{\tt put}と{\tt update}と{\tt flip}を実行することができる。 TestCodeSegmentはこの"cnt"というkeyに対して依存関係があり、8行目でputが行われるとTestCodeSegmentは実行される。 CSのInput DSは、CSの作成時に指定する必要がある。指定はCommandType(PEEKかTAKE)、DSM名、そしてkey よって行われる。 Input DS API はCSの{\tt ids}というフィールドを用いてアクセスする。 Output DSは、{\tt ods}が提供するput/update/flipメソッドをそのまま呼べばよかったが、Input DSの場合{\tt ids}にpeek/takeメソッドはなく、create/setKeyメソッド内でCommandTypeを指定して実行する。 ソースコード\ref{src:CodeSegment}は、0から9までインクリメントする例題である。 2行目では、Input DS APIがもつcreateメソッドでInput DSを格納する受け皿(Receiver)を作っている。 引数には{\tt PEEK}または{\tt TAKE}を指定する。 \begin{itemize} \item {\ttfamily Receiver create(CommandType type)} \end{itemize} 4行目から6行目はコンストラクタである。コンストラクタはオブジェクト指向のプログラミング言語で新たなオブジェクトを生成する際に呼び出されて内容の初期化を行う関数である。 % TestCodeSegmentのコンストラクタが呼ばれた際には、 % \begin{enumerate} % \item CSが持つフィールド変数 {\tt Receiver input}に{\tt ids.create(CommandType.TAKE)}が行われ、{\tt input}が初期化される。 % \item 5行目にあるTestCodeSegmentのコンストラクタのTAKEが実行される。 % \end{enumerate} 5行目は、2行目のcreateで作られたReceiverが提供するsetKeyメソッドを用いてLocal DSMからDSを取得している。 \begin{itemize} \item \verb+void setKey(String managerKey, String key)+ \end{itemize} setKeyメソッドはpeek/takeの実行を行う。どのDSMのどのkeyに対してpeekまたはtakeコマンドを実行させるかを指定できる。コマンドの結果がレスポンスとして届き次第CSは実行される。 実行されるrunメソッドの内容は \begin{enumerate} \item 10行目で取得されたDSをInteger型に変換してcountに代入する。 \item 12行目でcountをインクリメントする。 \item 16行目で次に実行されるCSが作られる。(この時点で次のCSはInput DSの待ち状態に入る) \item 17行目でcountをLocal DSMにputする。Input DSが揃い待ち状態が解決されたため、次のCSが実行される。 \item 13行目が終了条件であり、countの値が10になれば終了する。 \end{enumerate} となっている。 \chapter{AliceのMeta Computation} \section{Computetion と Meta Computation} Aliceでは、処理をComputationとMeta Computationに階層化し、コアな仕様と複雑な例外処理に分離する。 AliceのComputationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理と捉えられる。 それに対して、AliceのMeta Computation は、Remoteノードとの通信時のトポロジーの構成や切断・再接続の処理と言える。 つまりトポロジーの構成はAliceのComputationを支えているComputationとみなすことができる。 Aliceの機能を追加するということはプログラマ側が使うMeta Computationを追加すると言い換えられる。 AliceではMeta Computationとして分散環境の構築等の機能を提供するため、プログラマはCSを記述する際にトポロジー構成や切断、再接続という状況を予め想定した処理にする必要はない。 プログラマは目的の処理だけ記述し、切断や再接続が起こった場合の処理をMeta Computationとして指定する。 このようにプログラムすることで、通常処理と例外処理を分離することができるため、仕様の変更を抑えたシンプルなプログラムを記述できる。 現在Aliceには、トポロジーの構成・管理機能、ノードの生存確認機能、ノードの切断・再接続時の処理管理機能などのMeta Computationが用意されている。 \newpage \section{Meta Code Segment と Meta Data Segment} Alice提供するMeta ComputationもCS/DSにより実現される。 CSの処理を支える処理をMeta CS、Meta CSに管理されるMeta DSとして考える。 図\ref{fig:metaCS}は、AliceのMeta CS/Meta DSの接続関係の例である。 プログラマ側はCSとDSの依存関係を記述するが、その裏ではMeta CSやMeta DSが間に接続されて処理を行っている。 \begin{figure}[h] \begin{center} \includegraphics[width=120mm]{images/MetaCSDS.pdf} \end{center} \caption{CS/DSの間にMetaCS/MetaDSが接続される} \label{fig:metaCS} \end{figure} Meta DSは基本的にAliceを構成するCSによってのみ管理され、プログラマは認識できない。 しかし一部のMeta DSはプログラマがアプリケーションに利用することもできる。 例えば、トポロジー管理のMeta Computationなどで使われる"\_CLIST"というMeta DSには、利用可能なRemote DSMの情報が管理されている。 プログラマはこのMeta DSを取得しRemote DSM名を指定することで、動的にDSの伝搬などを行うことができる。 \newpage \section{Topology Manager} Aliceでは、ノード間の接続管理やトポロジーの構成管理を、Topology ManagerというMeta Computationが提供している。 プログラマはトポロジーファイルを用意し、Topology Managerに読み込ませるだけでトポロジーを構成することができる。 トポロジーファイルはDOT Language\cite{dot}という言語で記述される。 DOT Languageとは、プレーンテキストを用いてデータ構造としてのグラフを表現するためのデータ記述言語の一つである。 ソースコード\ref{src:topologyfile}は3台のノードでリングトポロジーを組むときのトポロジーファイルの例である。 \begin{table}[html] \lstinputlisting[label=src:topologyfile, caption=トポロジーファイルの例]{source/TopologyFile.dot} \end{table} DOT Languageファイルはdotコマンドを用いてグラフの画像ファイルを生成することができる。そのため、記述したトポロジーが正しいか可視化することが可能である。 \newpage Topology Managerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきクライアントのIPアドレスやポート番号、接続名を送る(図\ref{fig:topologymanager})。 また、トポロジーファイルでlavelとして指定した名前はRemote DSMの名前としてTopology Nodeに渡される。 そのため、Topology NodeはTopology ManagerのIPアドレスさえ知っていれば自分の接続すべきノードのデータを受け取り、ノード間での正しい接続を実現できる。 \begin{figure}[h] \begin{center} \includegraphics{images/topologymanager.pdf} \end{center} \caption{Topology Managerが記述に従いトポロジーを構成} \label{fig:topologymanager} \end{figure} また、実際の分散アプリケーションでは参加するノードの数が予め決まっているとは限らない。 そのためTopology Managerは動的トポロジーにも対応している。 トポロジーの種類を選択してTopology Managerを立ち上げれば、あとは新しいTopology Nodeが参加表明するたびに、Topology ManagerからTopology Nodeに対して接続すべきTopology Nodeの情報がput され接続処理が順次行われる。 そしてTopology Managerが持つトポロジー情報が更新される。 現在Topology Managerでは動的なトポロジータイプとして二分木に対応している。 \newpage \section{Keep Alice} ノード間通信はRemote DSMに対してputやtakeを行うことでのみ発生する。 アプリケーション次第では長時間通信が行われない可能性があり、その間にノード間接続が切れた場合、次の通信が行われるまで切断を発見することができない。 また、接続状態ではあるが応答に時間がかかる場合もある。 これらの問題を検知するために、KeepAliveという定期的にheart beatを送信し生存確認を行うMeta Computationがある。この機能もCS/DSを用いて実装されている。 一定時間内にノードからの応答がない場合、KeepAliveにより、そのノードのRemote DSMが切断される。 また、トポロジーからノードが切断された際にトポロジーを再構成する機能もTopology Managerに用意した。 例えばツリートポロジーでノードが切断された場合、そのノードの子ノードは全体のトポロジーから分断されてしまう。 ノードは切断を検知するとただちにTopology Managerに再接続すべきノード情報を要求し、木を構成し直す。 \section{切断・再接続時の処理} MMORPGでは、試合の最中にサーバーからユーザーが切断された場合、自動的にユーザーが操作するキャラクターをゲームの開始時の位置に戻すという処理が実行される。 同様に、Aliceを用いたアプリケーションでもノードの切断時に対する処理を用意したい場合がある。 そこで、Aliceが切断を検知した際に任意のCSを実行できる機能(ClosedEventManager)を追加した。 プログラマは切断の際に実行したいCSを書き、ClosedEventManagerに登録しておけば良い。 また、再接続してきたノードに対し通常の処理とは別の処理を行わせたい場合がある。 そのため、切断時と同様に再接続してきたノードに任意のCSを実行できるMeta Computationも用意した。 % AliceVNC \chapter{AliceのTreeVNCへの応用} AliceのMeta Computationが実用的なアプリケーションの記述において有用であることを確認する。 そのために、TreeVNCをAliceを用いて実装したAliceVNCの作成を行った\cite{sigOS}。 \section{TreeVNC} TreeVNCとは、当研究室で開発を行っている授業向け画面共有システムである。 オープンソースのVNCであるTightVNC \cite{tightVNC} をもとに作られている。 授業でVNCを使う場合、1つのコンピュータに多人数が同時につながるため、性能が大幅に落ちてしまう(図 \ref{fig:vncstructure})。 この問題をノード同士を接続させ、木構造を構成することで負荷分散を行い解決したものがTreeVNCである(図 \ref{fig:treestructure})。 \begin{figure}[htbp] \begin{tabular}{cc} \begin{minipage}{0.5\hsize} \begin{center} \includegraphics[width=80mm]{images/vnc.pdf} \caption{通常のVNCの構造} \label{fig:vncstructure} \end{center} \end{minipage} \begin{minipage}{0.5\hsize} \begin{center} \includegraphics[width=80mm]{images/treestructure.pdf} \caption{TreeVNCの構造} \label{fig:treestructure} \end{center} \end{minipage} \end{tabular} \end{figure} \newpage \section{AliceVNC} 図 \ref{fig:TreeVNC}はAliceVNCを実現するための構成である。leftとrightのRemote DSMを用意し子ノードと接続することで木構造を実現する。 \begin{figure}[h] \begin{center} \includegraphics[width=120mm]{images/AliceVNCstracture.pdf} \end{center} \caption{AliceVNC の構造} \label{fig:TreeVNC} \end{figure} TreeVNCは通信処理部分や画面データの処理部分が1つのコード内で記述され、大変複雑になっている。 しかし、Aliceで記述すればMeta Computationにより本質的な処理とそれを支える通信処理部分で分離できる。 TreeVNCでは3章で述べた動的なトポロジーの構成、切断ノードの発見、再接続・トポロジーの再構成といった通信処理のMeta Computationが活用できる。 そのため、TightVNCからの修正の少ない、見通しの良い記述で構成可能と期待される。 \newpage \chapter{圧縮のMeta Computationの追加} \section{圧縮のMeta Data Segment} TreeVNCは画面変更の差分を木構造にそって配信する際、差分は数MByteに達するため圧縮を行っている。 そのため、AliceVNCにも圧縮されたデータ形式を扱える機能が必要だと考えた。 しかし、ただデータを圧縮する機構を追加すればいいわけではない。 AliceVNCでは、ノードは受け取った画面データを描画すると同時に、子ノードのRemote DSMに送信する。 ノードはDSを受信するとそれを一度解凍して画面を表示し、再圧縮して子ノードに送信する。 しかし、受け取ったデータを自分の子ノードに対して送信する際には、解凍する必要はない。 圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる。 そこで、DSを複数作るのではなく1つのDS内で複数の表現を持たせ、必要に応じた形式でDSを扱うことを可能にした。 Meta DSに相当するReceiveData.classに、次の3種類の表現を同時に持つことができるようにしたことで、データの多態性を実現した。 \begin{enumerate} \item 一般的なJavaのクラスオブジェクト \item MessagePack for Java\cite{MessagePack}でシリアライズ化されたバイナリオブジェクト \item 2を圧縮したバイナリオブジェクト \end{enumerate} Local DSMにputされた場合は、(1)の一般的なJavaクラスオブジェクトとして追加される。 Remote DSMにputされた場合は、通信時に(2)のbyteArrayに変換されたバイナリオブジェクトに変換されたDSが追加される。 この2つの形式は従来のAliceが持っていた表現である。 今回、Remote DSMに圧縮形式での通信を行いたいため、(3)の圧縮表現を追加した。 \newpage ソースコード \ref{src:ReceiveData1} は変更前のReceiveData.classである。 変更前はDSの表現は1つでフラグによって、Local DSM にputする(1)の形式とRemote DSMにputする(2)の形式を判別していた。 しかしこの実装では圧縮形式と非圧縮形式を同時に持つことができないため、AliceVNCでは解凍・再圧縮が必要になってしまう。 変更後の実装ではソースコード \ref{src:ReceiveData1} のようになっている。 {\tt val}に(1) 一般的なJavaのクラスオブジェクト の表現でデータ本体が保存される。 {\tt messagePack}には(2) シリアライズ化されたバイナリオブジェクトが保存される。 そして、{\tt zMessagePack}には(3) 圧縮されたバイナリオブジェクトが保存される。 このようにDSが複数の表現を同時に保持することで、DSが圧縮表現を持っている場合に再圧縮する必要がなくなる。 プログラマ側がから見れば1つのDSであり直接これら3つの表現を操作することはないため、これらはAliceのMeta Data Segmentと言える。 \begin{table}[html] \lstinputlisting[label=src:ReceiveData1, caption=変更前のデータ表現]{source/beforeReceiveData.java} \end{table} \begin{table}[html] \lstinputlisting[label=src:ReceiveData2, caption=変更後のデータ表現]{source/ReceiveData.java} \end{table} \newpage \section{圧縮のMeta Code Segment} 圧縮表現を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerを追加した。 Compressed DSMの内部では、put/updateが呼ばれた際にReceiveData.classが圧縮表現を持っていればそれを使用し、持っていなければその時点で圧縮表現を作ってput/updateを行う。 Local Compressed DSM は表現の判別や変換を行うだけで、操作する対象は Local DSM と同じDSを指すため、DSの管理が別々になるわけではない。 ソースコード \ref{src:before} はRemote DSMに対しInt型のデータをputする記述である。 この通信を圧縮形式のDSで行いたい場合、ソースコード \ref{src:after} のように指定するDSM名の先頭に"compressed"をつければCompressed DSM内部の圧縮Meta Computationが走り圧縮形式に変換さ れたDSとなって通信が行われる。 \begin{table}[html] \lstinputlisting[label=src:before, caption=通常のDSを扱うCSの例]{source/beforeCompress.java} \end{table} \begin{table}[html] \lstinputlisting[label=src:after,caption=圧縮したDSを扱うCSの例]{source/afterCompress.java} \end{table} この機能は先述のMeta Data Segmentを扱うMeta Code Segmentと言える。 これによりユーザは指定するDSMを変えるだけで、他の計算部分を変えずに圧縮表現をDS内で持つことができる。 ノードは圧縮されたDSを受け取った後、そのまま子ノードにflipメソッドで転送すれば圧縮状態のまま送信されるので、送信の際の再圧縮がなくなる。 画面表示の際はReceiveData.class内のasClassメソッドを使うことで適切な形式でデータを取得できる。 asClassメソッドはDSを目的の型にcastするためのメソッドである。 AliceVNCで圧縮形式を指定してDSを送信すると、それを受け取るDSMは圧縮形式のみを持ったDSとして保存する。 そしてasClassメソッドが呼ばれて初めて、メソッド内で解凍してcastが行われDSが複数の表現を同時に持つようになる。 これによりDSの表現を必要になったときに作成できるため、プログラマはどんな形式でDSを受け取ってもDSを編集可能な形式として扱うことができる。 また、複数表現は必要なときにしか作成されないため、メモリ使用量も必要最低限に抑えることができる。 \newpage \section{Aliceの通信プロトコルの変更} 4.2で述べたように、Remoteからputされたデータは必ずシリアライズ化されておりbyteArrayで表現される。 しかし、データの表現に圧縮したbyteArrayを追加したため、RemoteからputされたbyteArrayが圧縮されているのかそうでないのかを判別がつかなくなった。 そこで、Aliceの通信におけるヘッダにあたるCommandMessage.class(ソースコード\ref {src:CommandMessage} 表 \ref{tb:variable})に圧縮状態を表すフラグを追加した。 これによってputされたDSMはフラグに応じた適切な形式でReceiveData.class内にDSを格納できる。 また、CommandMessage.classに圧縮前のデータサイズも追加したことで、適切な解凍が可能になった。 \begin{table}[html] \lstinputlisting[label=src:CommandMessage, caption=CommandMessage]{source/CommandMessage.java} \end{table} \begin{table}[htbp] \caption{CommandMessageの変数名の説明} \label{tb:variable} \begin{center} \begin{tabular} {|l|l|} \hline 変数名&説明\\ \hline type&CommandType {\tt PEEK, PUT}などを表す\\ \hline seq&\shortstack{Data Segmentの待ち合わせを行っている\\Code Segmentを表すunique number }\\ \hline key&どのKeyに対して操作を行うか指定する\\ \hline quickFlag&SEDAを挟まずCommandを処理を行うかを示す\\ \hline compressed&データ本体の圧縮状態を示す\\ \hline dataSize&圧縮前のデータサイズを表す\\ \hline \end{tabular} \end{center} \end{table} \newpage \chapter{DSとMetaDSのKeyの領域分け} DSとMeta DSは同じData Segment Managerで管理されており、同じAPIを利用してアクセスされる。 そのため誰でもMeta DSの変更が可能になってしまっている。 プログラマが定義しようとしたKeyが偶然AliceのMeta DSのKeyと衝突してしまった場合、ユーザーが意図した動作にならずエラーとなる状況は充分にありえる。 しかもMeta DSはプログラマ側からは認識できないため衝突の認識やエラーの解決がしづらくなっている。 このような事態を避けるためにも、DSの領域分けが必要である。 いままではLocalDataSegmentManager.classは1つだけだったが、もう1つ追加してMeta Local DSMとして登録した(ソースコード \ref{src:DSManagers})。 これでmanagerKey="local"ならばLocal DSMに、managerKey="metaLocal"ならばMeta Local DSMに対して操作できる。 \begin{table}[html] \lstinputlisting[label=src:DSManagers, caption=LocalDSMの追加]{source/DataSegmentManagers.java} \end{table} \newpage CodeSegment.classを継承したMetaCodeSegment.classを追加した(ソースコード \ref{src:MetaCS})。 MetaCodeSegmentは、idsとodsに対してCSかMeta CSかのフラグをセットする。 これを継承したクラスはDS Managerを指定せずにAPIを呼び出すと自動的にMetaDSMに対して操作したことになる。 \begin{table}[html] \lstinputlisting[label=src:MetaCS , caption=MetaCodeSegment.class]{source/MetaCodeSegment.java} \end{table} AliceのMeta CSは今までCS同様CodeSegment.classを継承して作られていたが、 継承元をMetaCodeSegment.classに変更する(ソースコード \ref{src:extendMeta} 1行目)だけでそれ以外は変更せずにDSの領域分けができる。 \begin{table}[html] \lstinputlisting[label=src:extendMeta ,caption=MetaCodeSegmentを継承]{source/BeforTopologyManager.java} \end{table} managerKey="metaLocal"を指定すれば通常のCSからもMeta DSの操作ができるが、Meta DSにtakeをした場合、そのDSをInputDSとして指定しているMeta CSが想定どおりに動作しないことが考えられる。 そのため、takeを行っても内部でpeekしか行わないようにした。 これにより通常のCSがtakeでDSを取得してもDSが削除されることはないため、Meta Computationに干渉することはない。 \newpage % 実験 \chapter{評価と考察} \section{圧縮のMeta Computationの評価} 圧縮のMeta Computationが正しく機能しているかを確認するために通信時間の計測を行った。 2台のPC間でお互いにデータを100回転送し合う。圧縮を指定したコードとしていないコードで5回計測した。 結果が表\ref{tb:compressmesure}である。 データサイズから見ても圧縮に成功していることがわかる。 通信においても、所要時間が1/3以下に抑えられていることから圧縮が効果的に作用している。 TreeVNCと同等の性能をだすために有用なMeta Computationが実装できたと言える。 \begin{table}[htbp] \caption{圧縮機能の測定結果} \label{tb:compressmesure} \begin{center} \begin{tabular} {|l|l|l|} \hline &圧縮なし&圧縮あり\\ \hline データサイズ&300KB&91KB\\ \hline 平均通信時間&6014ms&1764ms\\ \hline \end{tabular} \end{center} \end{table} \section{TreeVNCとAliceVNCのメッセージ伝達速度の比較} TreeVNCをAlice上で構築するために必要な機能をAliceのMeta Computationとして実装した。 これにより、AliceVNCが簡潔な記述でTreeVNCと同等の性能を出せれば、実用的な分散アプリケーションの実装においてAliceのMeta Computationは有用であるといえる。 そこで、TreeVNCとAliceVNCの性能評価としてメッセージ伝達速度の比較を、コードの評価としてコード量とその複雑度の比較を行った\cite{prosym}。 まず、木の段数ごとにメッセージの到達にどれぐらい時間がかかっているかを計測した。 講義内で学生に協力してもらい、最大17名の接続がある中でTreeVNC、AliceVNCの木の段数1〜3の測定を行った。 \textbf{実験内容} ルートノードから画面データを子ノードに伝搬する際に、計測用のヘッダをつけたパケットを子ノードに送信する。 各子ノードはパケットを受け取り自身のViewerに画面データを表示すると同時に、計測用ヘッダ部分のみのDSを作成し、親ノードに送り返す。 計測用DSは木を伝ってルートノードまで送り返され、ルートノードは受け取った計測用DSから到達時間を計算する。 計測用のヘッダは以下の要素で構成されている。 \begin{table}[htbp] \caption{計測用ヘッダの変数名の説明} \label{tb:mesure} \begin{center} \begin{tabular} {|l|l|} \hline 変数名&説明\\ \hline time&ルートノードがパケットを送信した時刻\\ \hline depth&木の段数。初期値=1。\\ \hline dataSize&送信時の形式に変換済みの画面データのサイズ\\ \hline \end{tabular} \end{center} \end{table} timeにはパケットの送信時刻を、dataSizeには圧縮された画面データのサイズを付けて送信する。 depthは各ノードに到達するごとにインクリメントされる。 到達時間の計算方法は、計測用DSを受け取った時刻とDSのtime(送信した時刻)の差をとる。 この到達時間は画面データがノードまで到達した時間と計測DSをルートまで送り返す時間を含めているが、送り返す時間は誤差として考える。 また、depthは各ノードに到達するごとにインクリメントされるため、送り返す際もインクリメントされる。そのため、木の段数を計算するにはdepthを1/2した値となる。 \textbf{実験結果} 3段目の測定結果の散布図を示す(図\ref{fig:TreeVNC_delay} 〜 \ref{fig:AliceVNC_compress_delay})。 X軸が画面データのサイズ(byte)、Y軸が計算した到達時間(ms)である。 実験時間の都合上、AliceVNCの計測時間が他より短くなってしまったためプロットされた点の数が少なくなっている。 また、それぞれの図で処理に10000ms以上かかっている点の集合が見られるが、これは今回の実験において3段目にPCのスペック上処理が遅いノードが1台あったためである。 そのため比較においてこの点集合は無視する。 図から同様の傾向があり、画面データのサイズが小さいうちは処理時間も5ms程度だが、50000byte以上から比例して処理時間も遅くなっている。 このことからAliceはTreeVNCと同等の処理性能を持つアプリケーションを実装するに十分な能力があることがわかる。 \begin{figure}[htbp] \begin{center} \includegraphics[width=100mm]{images/TreeVNC_depth3.pdf} \end{center} \caption{TreeVNCの測定結果} \label{fig:TreeVNC_delay} \begin{center} \includegraphics[width=100mm]{images/AliceVNC_compress_depth3.pdf} \end{center} \caption{AliceVNC(圧縮・転送機能あり)の測定結果} \label{fig:AliceVNC_compress_delay} \end{figure} \newpage \section{TreeVNCとAliceVNCのコード量比較} TreeVNCとAliceVNCのコード量を比較した表が表\ref{tb:code}である。 TightVNCを含むコード全体にwcを行い、行数と単語数を比較した。 また、hg diffでTightVNCからの変更行数を調べ変更量を比較した。 表からわかるように、Aliceを用いればコードの行数が25\%削減できる。 また、TreeVNCではTightVNCに大幅に修正を加えながら作成したため仕様の変更が多かった。 しかし、AliceVNCではTightVNCにほとんど修正を加えることなくトポロジー構成等のAliceのMeta Computationを使うために新しいクラスを作成したのみであった。 そのためTreeVNCに比べ75\%も仕様の変更が抑えられている。 \begin{table}[htbp] \label{tb:code} \begin{center} \begin{tabular} {|l|l|l|l|} \hline &行数&単語数&変更行数\\ \hline TreeVNC&19502&73646&7351\\%11369+8133=19502,47010+26636,2094+5257 \hline AliceVNC&14647&59217&1129\\%689+7094+6864=14647,23035+34610+1572,689+395+45 \hline 減少率(\%)&25&20&75\\ \hline \end{tabular} \end{center} \end{table} \section{TreeVNCとAliceVNCのコードの複雑度比較} コード量の比較で述べたように、TreeVNCはTightVNCからの変更が多い。 その理由の一つがトポロジーの構成や通信処理がコアな仕様と分離できておらず、 そのためTreeVNCは大変複雑な記述になってしまっている。 そこでTreeVNCとAliceVNCにおいてコードの複雑度を比較した。 今回、複雑度の指標としてThomas McCabeが提案した循環的複雑度\cite{complaxy}を用いた。 循環的複雑度とはコード内の線形独立な経路の数であり、if文やfor文が多ければ複雑度も高くなりバグ混入率も高まる。 一般的に、循環的複雑度が10以下であればバグ混入率の少ない非常に良いコードとされる。 計測にはIntelliJのCodeMetrics計測プラグインであるMetricsReloadedを使用した。 \newpage 表\ref{tb:complex}はTightVNC、TreeVNC、AliceVNCにおける循環的複雑度の比較である。 \begin{table}[htbp] \caption{複雑度の比較} \label{tb:complex} \begin{center} \begin{tabular} {|l|l|l|} \hline &平均値&最高値\\ \hline TightVNC&13.63&97\\ \hline TreeVNC&15.33&141\\ \hline AliceVNC&10.95&99\\%(4.12+13.64)/2 (4.12+9.16+19.59)/3 \hline \end{tabular} \end{center} \end{table} プロジェクト全体でのクラスの複雑度の平均値と最高値をとった。 平均値・最高値ともにAliceVNCのほうが複雑度が低いことから、Aliceではシンプルな記述が可能だということがわかる。 TreeVNCで最高値を出したTreeRFBProto.classは全てプログラマが記述したコードであり、データの待ち合わせのためのタイマー処理や通信処理、画面データの圧縮処理などの複数のスレッド処理が集中した複雑なコードになっている。 これをAliceで記述した場合、データの待ち合わせはCSが行うためプログラマがデータの不整合を気にする必要はなく、また通信処理や圧縮処理もMeta Computationが提供するためコードが複雑になることはない。 AliceVNCで複雑度の最高値を出したSwingViewerWindow.classはTightVNCで最高値を出したクラスと同じであり、コード量の比較でも示したようにAliceVNCで変更を加えた点がほとんどない。つまりこの複雑度は元来TightVNCが持っている複雑度と言える。 AliceVNCとTreeVNCの性能比較・コード比較から、AliceVNCはTreeVNCと同等の性能を持つ分散アプリケーションの記述ができ、かつコードの修正量・複雑度共に低く抑える能力を有することがわかった 。 \newpage \chapter{他言語等との比較} \section{MPICH} メッセージパッシング方式の標準規格であるMPIのC++/FORTRANの実装系がMPICHである。 メッセージパッシングとは、並列分散処理におけるプロセス間通信の一形態で、分散メモリ同士の書き込みをメールのようにメッセージの送受信で行う方式である。 プロセスごとにランクというidが付与され、プロセスはコミュニケーターという通信単位でグループ化できる。 コミュニケーターとランクをそれを指定してメッセージを送受信する。 APIはSender/Receiverメソッドが用意されており、宛先情報、データの種類・サイズ、そしてプログラマがメッセージに対し任意に命名できるタグを指定して送受信を行う。 Sender/ReceiverはAliceのput/takeに対応しており、コミュニケーターはDSM名、タグはKeyに対応している点が類似している。 しかし、Sender/Receiverは同期型と非同期型の2種類あり、プログラマはそれらを組み合わせて同期を意識しながらプログラミングしなければならない。 一方、AliceではDSの待ち合わせ処理をCSが自動で行うためそのような負担が少ない。 また、MPICHはAliceのMeta Computationに対応するものはない。そのため分散環境の構築やデータの圧縮は全てプログラマ側が記述しなければならない。 一方、Aliceでは分散環境の構築はTopology ManagerなどのMeta Computationが行うためプログラマはトポロジーを指定するだけで良い。 \section{Erlang} アクターモデルの並列指向プログラミング言語Erlang\cite{Erlang}は、プロセスと呼ばれるid付きの独立したタスクに対して、idを指定してデータをメッセージでやりとりする。 タスクをプロセスという細かい単位に分割して並列に動かす点や、メモリロックの仕組みを必要としない点はAliceと同様である。 Erlangもプロセス/アクターに直接データをやりとりする。MPICHにはメッセージにタグが付けられたが、Erlangにはデータには名前がない。 そのため、メッセージを受け取ったあとにその内容を確認した上で次にどう振る舞うかを判断する記述が必要となる。 一方Aliceでは、DSをCSに直接やりとりはせず、keyを指定してDSMにputする。 また、DSをtakeするときもkeyを指定して取り出すためどんなデータが入っているかを確認する必要がなく、扱い易い。 そして、Erlangでは静的な複数のデータの待ち合わせのための再帰処理も自分で書かなければならない。 一方、Aliceのプログラミング手法はCSが必要なデータが全て揃うまで待ち合わせを行うためその必要はない。 また、MPICH同様ErlangにもMeta Computationに対応する部分がないため、分散環境の構築等はすべてプログラマ自身が記述しなければならない。 \section{Akka} Akka\cite{Akka}はScala・Java向けの並列分散処理フレームワークである。 アクターモデルを採用しており、アクターと呼ばれるアドレスを持ったタスクに、データをメッセージでやりとりする点がErlangと似ている。 Akkaの特徴として、メッセージを送りたいプロセスのアドレスを知っていればアクターがどのマシン上にあるかを意識せずにプログラミングできるという点がある。 逆にAliceはどのRemote DSMに対してやり取りをするかを考慮するが、CSがOutputしたDSを次にどのCSに渡すかを意識する必要がない。 この点はアクターモデルとCS/DSモデルのパラダイムの違いと言える。 一方AliceとAkkaは提供されるAPIという点で類似している。 また、AkkaのメッセージAPIでは、メッセージを送るtellメソッドと、メッセージを送って返信を待つaskメソッドが用意されている。 これはAliceのDataSegment APIのput/takeメソッドに対応している。 Akkaのもう一つの特徴として、アクターで親子関係を構成できる点がある。 分散通信部分を子アクターに分離し、親アクターは子アクターのExceptionが発生した時に再起動や終了といった処理を指定できる。 さらにRouterという子アクターへのメッセージの流れを制御するアクターや、Dispatcherというアクターへのスレッドの割当を管理する機能をAkkaが提供している。 このように処理を階層化し複雑な処理をフレームワーク側が提供する仕組みはAliceのMeta Computationと共通している。 相違点としては、AliceのMeta DSのようにデータを分離し多態性を実現する機能はAkkaにはない。 例えば、データを圧縮して通信した場合は、用意されているcompress/uncompressメソッドを使い圧縮・伸長のコードをプログラマが挟まなければならない。 そのためコードを圧縮通信に変更したいときはメッセージの送信側と受信側を両方書き換えが必要になり、どちらか一方を書き忘れるとエラーとなる。 一方Aliceでは送信側がDSM名に"compress"をつけるだけで他を変更しなくとも圧縮通信に切り替えられるので、コードの変更量が抑えられ、変更前の信頼性が保存される。 % 今後の課題 \chapter{まとめ} 並列分散フレームワークAliceでは、スケーラブルかつ信頼性の高いプログラムを記述する環境を実現するため、CS / DSの計算モデルとMeta Computationによる実装の階層化を採用している。 Meta ComputationはMeta CS / Meta DS に分けられ、それらが通常の処理の間に挟まれることでプログラマ側の記述するComputationの変更を抑えた挙動変更を可能にする。 Aliceが実用的な分散アプリケーションを記述するために必要なMeta Computationとして、Meta DSに複数の形式を同時に持たせ、DSMを切り替えることで多態性を持つデータを扱う機能を実装した。 これにより、必要に応じた形式を扱うことができ、ユーザが記述するComputation部分を大きく変えずに自由度の高い通信を行うことが可能になった。 同様の手法を用いれば、圧縮形式以外にも暗号形式・JSON 形式などの複数のデータ表現をユーザに扱いやすい形で拡張することができる。 また、Data Segment のKeyの管理領域を分けたことで、DSとMeta DSのKeyの衝突を避け、CS / DSのプログラミングスタイルにおける信頼性向上を図った。 そしてMeta Computationを用いて分散アプリケーションTreeVNCをAlice上で実装し性能評価を行った。 その結果、TreeVNCで使用される基本機能はAliceでも実現でき、同等の性能を出すことに成功した。 また、コードの観点からTreeVNCとAliceVNCを比較した結果、Aliceが仕様の変更を抑えたシンプルな記述を実現できていた。 このことからAliceのMeta Computationが信頼性・拡張性の高い実用的な分散アプリケーションを構築するに有用であることが確認された。 \chapter{今後の課題} \section{AliceVNCのNAT超え通信の実装} 今後の課題としては、TreeVNCで実装が困難であったNATを超えたノード間通信をAliceVNCで実現し、その性能とコード修正量を比較することが挙げられる。 図\ref{fig:overNAT}は2つの違うプライベートネットワークを超えた接続の設計例である。 \begin{figure}[h] \begin{center} \includegraphics[width=120mm]{images/overNAT.pdf} \end{center} \caption{複数のTopology ManagerでNAT超えを実現} \label{fig:overNAT} \end{figure} 各ネットワークごとにTopoogy Managerを立ち上げることでネットワークを超えたノード間接続を実現する。 プライベートネットワークのTopoogy Managerは今までどおりネットワーク内に木を構築・管理する。 他のネットワークにあるノードBがノードAに接続したい場合は、グローバルアドレスを持ったTopology Managerに参加表明をすればノードAの情報が提供され、ノードAの子ノードとして接続される。 つまり、Topology Managerを複数用意するだけで、Topology Manager自体の「参加表明のあったノードで木を構成する」という仕様は全く変更しないで良い。 TreeVNCでは500行以上の変更が必要とされたが、Aliceでは複数のTopology Managerに接続するためのconfigファイルを変更するだけなので、AliceVNCの仕様の変更を抑えられると期待される。 この機能も実現できれば、AliceのMeta Computationが拡張性の高い環境を提供できると言える。 \section{APIの再設計} 2.4で示したように、DSを取得するときのAPIはpeek/takeが直接扱えず、create/setKeyを組み合わせてプログラミングしなければならない。 この設計だとプログラマにとってわかりづらく、コンストラクタ内でtakeを行いたい場合はsetKeyを必ず最後に呼ばなければならない等の注意点がある。 put/update/flipと同様に、peek/takeをそのまま呼べるように再設計する必要がある。 また、動的に複数のDSを取得する場合は、プログラマが末尾再帰処理を書かなければならない。 MPICHのReceiverメソッドは引数でタグと個数を指定することで複数のメッセージの待ち合わせができる。 複数DSを待ち合わせしたい場面は多いため、個数指定のできるAPIの追加も望ましい。 \section{DSの型情報のマネジメント} Aliceでは型情報がないので、peek/takeする際にどんな型のデータが入っているのかがわからない。 takeしたDSの型を確認したい場合には、そのDSをputしている部分を確認しなくてはならない。 そのため、型情報をサポートする機能が必要である。 \section{データの永続性の確保} 現在のAliceは、On memoryであるためプロセスの終了とともにData Segmentは全て失われてしまう。 この問題を解決するためには、Data Segmentを他のKey Value Store等のシステムに保存し、永続性を確保する昼用がある。 また、当研究室で開発しているJungle Database\cite{Jungle}のようにLogファイルとして出力することでも解決ができる。 \section{Java以外での実装} Alice に Garbage Collection は必要ない。Alice では、すべての Data Segment は Key Value に格納され、実行時の Data Segment は Code Segment が active な時のみにメモリ上にある。 この最大値を見積ることは、Active Task の量を見積もれば良い。したがって、Alice にはGarbage Collection は必要ない。 一方で、Key Value Store 上のデータは決して Garbage Collection の対象にならない。 しかし、それは Garbage Collector には負荷をかけてしまう。 つまり、Alice 自体は Java で実装するのには向いていない。 当研究室ではCode Segment/Data Segmentのプログラミング形式で記述する言語CbC (Continuation based C)\cite{CbC}と、CbCを用いて記述されるGears OS\cite{Gears}の開発を行っている。 そのため、CbCを用いてGears OSの分散機構の一部としてAliceを再設計することが望ましい。 % 参考文献 \input{bibliography.tex} % 謝辞 \chapter{謝辞} \hspace{1zw}本研究の遂行、また本論文の作成にあたり、ご多忙にも関わらず終始懇切なる御指導と御教授を賜わりました河野真治助教授に深く感謝したします。 そして、数々の貴重な御助言と技術的指導を戴いた杉本優さん、比嘉健太さん、伊波立樹さん、並びに並列信頼研究室の皆様に感謝いたします。 また、東京大学の横山大作教授をはじめ、OS研究会、プログラミング・シンポジウムにおいて多くのフィードバックを頂いた先生方に感謝いたします。 本研究を遂行するにあたり参考にさせていただいた先行研究のFederated Linda, Cerium, TreeVNC の設計・実装に関わった全ての先輩方に感謝いたします。 最後に、日々の研究生活を支えてくださった米須智子さん、情報工学科の方々、そして家族に心より感謝いたします。 \begin{flushright} 2016年 2月 \\ 照屋のぞみ \end{flushright} % 付録 %\input{appendix.tex} \end{document}