Mercurial > hg > Papers > 2015 > nozomi-sigos
diff paper/chapter3.tex @ 5:4a7fa91ef60a
not fix English Abstract
author | Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 06 May 2015 05:23:37 +0900 |
parents | e13be99f69b6 |
children |
line wrap: on
line diff
--- a/paper/chapter3.tex Tue May 05 17:26:13 2015 +0900 +++ b/paper/chapter3.tex Wed May 06 05:23:37 2015 +0900 @@ -1,184 +1,107 @@ \section{Aliceの新機能} -水族館の例題によって、Aliceを用いて分散プログラムを記述可能であることを確認した。 -次に実用的なアプリケーションであるTreeVNCをAlice上で実装することで、Aliceに必要な機能を洗い出した。 - -\subsection{Dynamic Topologyへの対応} -第2章で示したように分散フレームワークAliceはTopology Fileを読み込むことでTopologyを構成する。 -つまり、予め参加するノードの台数が決まっている必要がある。また、Topologyに全ノードが参加するまでアプリケーションが起動しない。 - -実際のアプリケーションでは、参加するノードの数は決まっておらず、Topologyを動的に変化させる必要がある。 -そこで、AliceにDynamic Topology Managerを追加した。 - -Dynamic Topologyの場合は、新しくTopology Nodeがアプリケーションに参加するたびにTopology ManagerからTopology Nodeに対して、接続すべきTopology Nodeの情報がputされ接続処理が順次行われる。 -\subsection{Keep Alive} -ノード間の通信は、Remote DSMに対してputやpeekを行うことでのみ発生する。アプリケーション次第では長時間通信が行われない可能性がある。通信が行われない間にRemote DSMとの接続が切れた場合、次の通信が行われるまで切断を発見することができない。また、接続状態ではあるが問題が発生し、応答に時間がかかる場合も考えられる。 - -以上の問題を検知するためにアプリケーションではKeep Aliveという、定期的にheart beatを送り生存確認を行う機能を持つことが望ましい。そこで、Alice自体にKeep Aliveの機能を実装した。 - -一定時間内にノードから応答がない場合、Keep Aliveにより、そのノードのRemote DSMが切断される。 - - -図 \ref{fig:keepAlive}は、keepAliveの処理をコミュニケーションダイアグラムで示したものである。 -keepAliveは、タスクとタスクを実行するTaskExecuterと実行順序を管理するSchedulerによって実装されている。 -タスクの種類には、{\tt PING}、{\tt CLOSE}、{\tt CREATE}があり、TaskExecuterは、タスクの種類に従って処理を行なう。 -{\tt PING}は、指定されたRemote DSMに対してheartbeatを送信する。 -{\tt CLOSE}は、指定されたRemote DSMを削除する。 -{\tt CREATE}は{\tt PING}のタスクを作成し、Schedulerに登録する。 +実用的なアプリケーションであるTreeVNCをAlice上で実装することで、Aliceに必要な機能を洗い出した。 +\subsection{flip機能} +Data Segment APIのput、updateを呼ぶとOutput Data Segmentが毎回新しく作成される。そして出力するデータのコピーが行われる。 +しかし、AliceVNCのようにInput Data Segmentとして取得したデータをそのまま子ノードにOutput Data Segmentとして出力する場合、コピーを行なうのは無駄である。 + +そこで、このコピーを無くしData Segmentの更新におけるオーバーヘッドを減らす方法としてflip機能の実装を行った。 +ソースコード\ref{src:exampleFlip}のようにInput Data SegmentであるReceiverをflipメソッドに引数として渡すことで、無駄なコピーを減らす。 +\begin{table}[html] +\lstinputlisting[label=src:flipAlice, caption=Aliceにおけるflip]{source/flip.java} +\end{table} -タスクを作成する際に実行時間の指定をする。Schedulerにタスクを登録すると、Schedulerはタスクの実行時間に従って、タスクを実行順に並び替える。 -\begin{figure}[htbp] -\begin{center} -\includegraphics{images/keepAlive.pdf} -\end{center} -\caption{keepAliveの仕組み} -\label{fig:keepAlive} -\end{figure} - -\subsubsection{処理の流れ} -\begin{enumerate} -\item CreateTask(Code Segment)により{\tt PING}タスクが投入される。\label{enum:putPingTask} -\item TaskExecuterはSchedulerから次に実行すべき{\tt PING}タスクを受け取る。 -\item 指定された時間が訪れるとheartbeatがRemote DSM(Node B)に送信される。\label{enum:send} -\item \ref{enum:send}と同時にheartbeatを送信したRemote DSMとの接続を切断する{\tt CLOSE}タスクが投入される。\label{enum:putCloseTask} -\item \ref{enum:putCloseTask}で投入された{\tt CLOSE}タスクが実行されるまでに、Remote DSM(Node B)からのレスポンスがあった場合、RemoveTask(Code Segment)により{\tt CLOSE}タスクが削除される。 -%\item \ref{enum:putPingTask}に戻る。 -\end{enumerate} - -\ref{enum:putPingTask}で作られる{\tt PING}タスクは、接続しているRemote DSMの数だけ投入される。 -"\_CLSIT"というkeyには、アクセス可能なRemote DSMのkeyの一覧が保存されている。 -CreateTaskは、この一欄により動的にタスクを作成している。 - -以上で説明した処理の流れは、接続状態に問題がない場合である。 -接続状態に問題があり、{\tt CLOSE}タスクの実行されるまでにレスポンスがない場合は、{\tt CLOSE}タスクによりRemote DSMが削除される。 - -heartbeatは、Node AからNode Bに一方向に送られる訳ではなく、Node BからNode Aにも送られている。 - -\section{切断時の処理} -MMORPGでは、試合の最中にサーバーからユーザーが切断された場合、自動的にユーザーが操作するキャラクターをゲーム開始時の位置に戻すという処理が実行される。 -同様にTreeVNCでは切断を検知した場合、LostParentというメッセージがトップノードに対して送信される。 - -以上の例のように、アプリケーションはノードの切断に対する処理を用意したい場合がある。 -しかし、Aliceを用いたアプリケーションの場合、アプリケーション側で検知するのは難しい。 -切断自体は、Remote DSMに対してwriteまたはreadを行った際に出るExceptionにより判断することができる。 -だが、I/O の処理はCode Segmentを実行するThreadで行われない。専用のI/O Threadによって行われるため、Code Segment内でExceptionを捕まえられず、例外処理を行なうことができない。 - -そこで、Aliceが切断を検知した際に、任意のCode Segmentを実行できる機能 (ClosedEventManager)を追加した。 -ユーザはClosedEventManagerにCode Segmentを登録することで、切断時の処理として実行するCode Segmentを指定できる。 -\begin{table}[htbp] -\lstinputlisting[label=src:registerEvent, caption=切断時に実行されるCode Segmentの登録方法]{source/RegisterEvent.java} +\begin{table}[html] +\lstinputlisting[label=src:exampleFlip,caption=flipの使用例]{source/Sort.java} \end{table} -また、切断したRemote DSMの情報を利用したい場合は、Code Segmentをextends する代わりにClosed Event Code Segmentをextendsし、用意されているMethodを使うことで取得可能である(ソースコード \ref{src:CatchClosedEvent})。 - -\begin{table}[htbp] -\lstinputlisting[label=src:CatchClosedEvent, caption=CloseEventCodeSegmentを継承したCodeSegment]{source/CatchClosedEvent.java} -\end{table} -ClosedEventCodeSegmentを継承したCode Segmentに、Input Data Segmentを追加記述する事ができる。 -その際は、もちろんInput Data Segmentが全て揃うまでCode Segmentは実行されない。 - -\subsection{Topologyの再構成} -ノードは永続的にアプリケーションに参加し続ける訳ではない。目的を果たすとアプリケーションから離脱する。 -Topology次第では、アプリケーションに支障をきたす。 -例えば、AliceVNCは木構造であるため、子ノードを持つノードがアプリケーションから離脱した場合、その子ノードに対してデータを送信することができなくなる。 - -この問題を解決するには、アプリケーションからノードが切断するたびにTopologyの再構成を行なう必要がある。そこで、Dynamic Topology Managerに、Topologyの再構成を行う機能を追加した。 - -図 \ref{fig:TopologyFIx}、 \ref{fig:TopologyFIx2}、\ref{fig:TopologyFIx3}はTopologyの再構成をコラボレーションダイアグラムで表したものである。 +\subsection{Data Segmentの表現の追加(圧縮機能)} +TreeVNCでは画面配信の際、データを圧縮してノード間通信を行っている。 +そのため、AliceVNCにも圧縮されたデータ形式を扱える機能が必要だと考えた。 +しかし、ただデータを圧縮する機構を追加すればいいわけではない。 -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=120mm]{images/TopologyFIx.pdf} -\end{center} -\caption{切断ノードの検知} -\label{fig:TopologyFIx} -\end{figure} - -\begin{enumerate} -\item Keep AliveがNode1の切断を検知すると、Node3からTopology Managerに対して切断したノードの情報がputされる。keep Aliveは各ノードで動いているため、実際にはNode0とNode4もTopology Managerに対してNode1の情報をputする。 -\item Topology Managerは最後にアプリケーションに参加したNode6とその親Node2に対して互いを切断するための準備を行わせる、CLOSEMESSAGEをputする。 -\item 切断する準備ができるとお互いに準備完了を知らせるCLOSEREADYをputする。 -\item \label {tb:last}CLOSEREADYを受け取ると切断を行い、Remote DSMが使用不可能になる。 -\end{enumerate} +AliceVNCでは、ノードは受け取った画面データを描画すると同時に、子ノードのRemote DS Managerに送信する。 +ノードはDSを受信するとそれを一度解凍して画面を表示し、再圧縮して子ノードに送信する。 +しかし、受け取ったデータを自分の子ノードに対して送信する際には、解凍する必要はない。 +圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる。 -\begin{figure}[htbp] - \begin{minipage}{0.5\hsize} - \begin{center} - \includegraphics[width=90mm]{images/TopologyFix2.pdf} - \end{center} - \caption{接続すべきノード情報の送信} - \label{fig:TopologyFIx2} - \end{minipage} - \begin{minipage}{0.5\hsize} - \begin{center} - \includegraphics[width=80mm]{images/TopologyFix3.pdf} - \end{center} - \caption{再構成の完了} - \label{fig:TopologyFIx3} - \end{minipage} -\end{figure} +そこで、1つのData Segmentに対し複数の表現を持たせることで、必要に応じた形式でDSを扱うことを可能にした。 +DSを扱うReceiveData.classに、次の3種類の表現を同時に持つことができる。 \begin{enumerate} -\setcounter{enumi}{4} -\item Node1、Node3、Node4に対してNode6の情報を送り、接続を行わせる。 -\item Node6に対して、Node1、Node3、Node4の情報を送り、接続を行わせる。 -\item お互いにRemote DSMの名前を贈り合い、Remote DSMが利用可能になる。 + \item 一般的なJavaのクラスオブジェクト + \item MessagePack for Javaでシリアライズ化されたバイナリオブジェクト + \item 2を圧縮したバイナリオブジェクト \end{enumerate} -\subsection{再接続の処理} -MMORPGでは、試合の最中に障害などによりサーバーから離脱したユーザーが、試合が終わるまでに再びサーバーに接続してきた場合に、再びその試合に参加できるような再接続の処理が用意されている。 +ソースコード\ref {src:ReceiveData}はReceiveData.classが持つ表現であり、{\tt val}に1. 一般的なJavaのクラスオブジェクト の表現でデータ本体が保存される。{\tt messagePack}には2. シリアライズ化されたバイナリオブジェクトが保存され、通常のRemoteDSMへの通信にこの表現が扱われる。そして、{\tt zMessagePack}には3. 圧縮されたバイナリオブジェクトが保存される。 +\begin{table}[html] +\lstinputlisting[label=src:ReceiveData, caption=データを表現するクラス]{source/ReceiveData.java} +\end{table} -分散にアプリケーションでは、MMORPGの例のように再接続してきたノードに対して通常の処理とは別の処理を行わせたい場合がある。そこで、Aliceに再接続してきたノードに、任意のCode Segmentを実行できる機能を追加した。ユーザーはconfigにCode Segmentを継承したClassを登録することで、再接続時に実行されるCode Segmentを指定することができる。 +また、圧縮状態を持つDSを扱うDSMとしてLocalとRemoteそれぞれにCompressed Data Segment Managerの追加した。 +put/updateでは、ソースコード\ref{src:zput}のように指定するDSM名の先頭に"compressed"をつけることでDSは自動で圧縮状態も持つようになる。さらに、take/peekもソースコード\ref{src:ztake}のようにsetKeyを実行する際にDSM名の先頭に"compressed"をつけることで圧縮形式でDSを受け取ることができる。 +\begin{table}[html] +\lstinputlisting[label=src:zput, caption=圧縮DSのput]{source/compress_put.java} +\end{table} -\begin{table}[htbp] -\lstinputlisting[label=src:StartAquarium, caption=再接続に実行するCode Segmentの登録方法]{source/StartAquariumFX.java} +\begin{table}[html] +\lstinputlisting[label=src:ztake,caption=圧縮DSのtake]{source/compress_take.java} \end{table} -\subsection{Multicast Data Segment} -TreeVNCには、Multicastを利用して起動しているTreeVNCのRoot Nodeの情報の一覧にして表示する接続先自動検索システムという機能がある。この機能によりTreeVNCの起動の際にIPアドレスを入力する手間を省くことができる。 - -現在のAliceは起動時にTopology ManagerのIPアドレスを入力する必要があり、TreeVNCの接続先自動検索機能が必要と考えられる。 -その機能を実現するためにはMulticastに対応する必要がある。そこで、同じマルチキャストアドレスを持つ端末を1つのData Segmentとして扱うMuticast Data Segmentを追加した。 -Multicast Data Segmentも他のData Segment同様、Data Segment APIを用いて扱う。 +これによりユーザは指定するDSMを変えるだけで、他の計算部分を変えずに圧縮表現を持つDSを扱うことができる。 -\begin{figure}[htbp] -\begin{center} -\includegraphics[width=120mm]{images/multicast.pdf} -\end{center} -\caption{Multicast Data Segment} -\label{fig:multicast} -\end{figure} +ノードは圧縮されたDSを受け取った後、そのまま子ノードにflipすれば圧縮状態のまま送信されるので、送信の際の再圧縮がなくなる。 +また、画面表示の際は{\tt asClass()}(ソースコード\ref {src:asClass})を使うことで適切な形式でデータを取得できる。 +{\tt asClass()}はDSを目的の型にcastするメソッドであり、圧縮されていれば解凍してcastを行っている。 +これにより必要なDSを必要な時にだけ解凍できる。 -図 \ref{fig:multicast}はMulticast Data Segmentを図で表したものである。Node AのMulticast Data Segmentに対してputを行うとnode B、node C、node Dの3つのnodeに対してデータがputされる。同様にTakeを行うと3つのnodeからTakeに対する応答が来る。 +\begin{table}[html] +\lstinputlisting[label=src:asClass, caption=asClassの処理]{source/asClass.java} +\end{table} -Multicast Data SegmentはUDPを用いて実装されている。1つのUDPのパケットで運ぶことのできるデータが、65507bytes(65535bytesからIPヘッダの最低サイズ20bytesとUDPのヘッダのサイズ8bytesを引いた大きさ)である。 -現状、分割して送る処理をMulticast Data Segmentが持たない。従って、Multicast Data Segmentを利用する際には、データのサイズを65507bytes以下にしなければならない。 -\section{Multicast Data Segment Manager} -Multicast Data SegmentもRemote DSM同様Managerを経由して操作を行う。Multicast DSMを作成するとMulticast Data Segmentに対する送受信用のスレッドが作成される。 - -\begin{itemize} -\item {\ttfamily public static MulticastDataSegmentManager \\ -connectMulticast(String connectionKey ,String MCSTADDR, int port, String nis, SocketType type)} -\end{itemize} +\subsection{パケットの再設計} +2.4で述べたように、Remoteからputされたデータは必ずシリアライズ化されておりbyteArrayで表現される。 +しかし、putされたbyteArrayが全てシリアライズ化された状態であるとはいえない。Localからも一般的なJavaのクラスオブジェクトとしてbyteArrayが使用されている場合が存在する。例えば、AliceVNCで使われる画像データはbyteArrayで表現されているが、これはLocalからputされている。 +また、データの表現に圧縮形式を追加したことで、RemoteからでもputされたbyteArrayが圧縮されているのかそうでないのかが判断できなくなった。 -DataSegment classのstaticメソッドである、connectMulticastを呼ぶことでMulticast DSMが作成される。 -第1引数はMulticast DSMへのアクセスするためのkeyを指定できる。第2引数はマルチキャストアドレスを、第3引数はポート番号を、第4引数はネットワークインターフェイスを指定する。第5引数はSocketTypeを指定する。 -SocketTypeには、{\tt Sender}と{\tt Receiver}と{\tt Both}が存在する。{\tt Sender}を指定した場合は、第2引数で指定したマルチキャストアドレスに対して送信処理を行うスレッドを作成する。{\tt Receiver}を指定した場合は、第2引数で指定したマルチキャストアドレスに対して送信されたデータを受信するスレッドを作成する。{\tt Both}は、送受信両方のスレッドを作成する。 - -現在、Multicast Data Segmentは自動では作成されないため、ユーザー自身で作成する必要がある。 +ここからわかることは、データを表現するにはデータ単体をやりとりするだけでは不十分ということである。 +そこで、データとデータの状態を表すヘッダをまとめて1つのオブジェクトとして扱うように変更した。 +Aliceの通信におけるヘッダにあたるCommandMessage.class(ソースコード\ref {src:CommandMessage}にシリアライズ状態表すフラグと、圧縮状態を表すフラグを追加した。 +これによってputされたDSMはフラグに応じた適切な形式でReceiveData.class内にDSを格納できる。 +また、CommandMessage.classに圧縮前のデータサイズも追加したことで、適切な解凍が可能になった。 -ソースコード \ref {src:MulticastStartCodeSegment}と\ref {src:MulticastIncrement}は実際にMulticast Data Segmentを利用した例題である。送信側では送信専用のmulticast DSMを作成し、それに対して数字データを10回putしている。 -受信側では受信専用のmulticast DSMを作成し、送信されたDSを受け取り内容を表示している(ソースコード\ref {src:Receivemessage})。 - -\begin{table}[htbp] -\lstinputlisting[label=src:MulticastStartCodeSegment, caption=multicast DSの例題の送信側]{source/MulticastStartCodeSegment.java} +\begin{table}[html] +\lstinputlisting[label=src:CommandMessage, caption=変更後のCommandMessage]{source/CommandMessage.java} \end{table} \begin{table}[htbp] -\lstinputlisting[label=src:MulticastIncrement, caption=multicast DSの例題の受信側]{source/MulticastIncrement.java} +\caption{CommandMessageの変数名の説明} +\label{tb:variable} +\begin{center} +\begin{tabular} {|l|l|} + \hline + 変数名&説明\\ + \hline + type&CommandType {\tt PEEK, PUT}などを表す\\ + \hline + seq&Data Segmentの待ち合わせを行っている\\Code Segmentを表すunique number\\ + \hline + key&どのKeyに対して操作を行うか指定する\\ + \hline + + quickFlag&SEDAを挟まずCommandを処理を行うかを示す\\ + \hline + serialized&データ本体のシリアライズ状態を示す\\ + \hline + + compressed&データ本体のシリアライズ状態を示す\\ + \hline + + dataSize&圧縮前のデータサイズを表す\\ + \hline + +\end{tabular} +\end{center} \end{table} -\begin{table}[htbp] -\lstinputlisting[label=src:Receivemessage, caption=multicast DSMに対してsetKeyを行う]{source/ReceiveTask.java} -\end{table} -\subsection{圧縮機能} \ No newline at end of file