|
19
|
1 \chapter{分散フレームワーク Alice の概要} \label{chapter:chapter1}
|
|
|
2 Aliceは、本研究室で開発を行っている分散タスク管理フレームワークである。Cell用のOpen CLに似たTask管理フレームワークCeriumとLindaを相互に接続した分散フレームワークであるFederated Lindaの開発を通して得られた知見が生かされている。
|
|
|
3
|
|
|
4 Ceriumでは、Taskを小さく分割して並列実行し、データ転送はパイプライン実行により隠される。Task間に依存関係があるが、実際にはデータの依存関係がそのままTaskの依存関係になることが多い。繰り返し使われるデータ構造の管理が重要であり、実行時にわかるデータ構造間の依存関係がTaskを複雑にしている。
|
|
|
5
|
|
|
6 Federated Lindaでは、Lindaサーバ内部にMeta Engineと呼ばれるLindaのタプル(データ構造)をやり取りする部分を作成した。Meta Engineでは、タプルのやり取りによって起動するcall backを使うが、call backによる記述が分散してしまい、可読性を落としてしまう。また、複数のタプルの待ち合わせが重要だが、その待ち合わせはsingle threadedなMeta Engine内部の状態に依存する。
|
|
|
7
|
|
|
8 これらが示しているのは、並列分散実行はコードの並列実行だけでなく、データの単位が重要だということである。そこで、AliceはData SegmentとCode Segmentという単位でデータと処理を細かく分割し、それぞれの依存関係を記述して分散プログラムを作成する。
|
|
|
9
|
|
|
10 Data SegmentはCode Segmentと分離されたデータ構造であり、オブジェクトではない。オブジェクト指向プログラミングが状態を複雑に持ち、並列実行や分散実行に向かないことは徐々に理解されてきている。一方で、状態自体は有限状態遷移機械(Finite State Machine/FSM)で記述するのが自然である。Code Segmentは状態遷移記述そのものであり、その状態遷移はData Segmentの到着によってトリガーされる。
|
|
|
11
|
|
|
12 カプセル化されたデータをプロセスがやり取りするのは、DFD(Data Flow Diagram)の古典的な手法であり、それ自体は新しくはない。むしろ、メインフレーム上でのソフトウェア開発に良く使われてきた手法である。Alice では、それを再実装する。
|
|
|
13
|
|
|
14 AliceはCode SegmentとData SegmentをJavaとMessage Packで実装したフレームワークである。Topology Managerを持ち、Blade上での
|
|
|
15 分散プログラムの実験を容易に行うことができる。また、SEDA Architectureを採用しており、マルチコア上でのスループットの向上を期待している。
|
|
|
16
|
|
|
17 \section{Data Segment}
|
|
|
18 Data Segmentはデータを細かく分割したものであり、数値や文字列などのデータを構造的に保持する。AliceはData Segmentをデータベースとして扱っている。Data Segmentには必ず対になるKeyが存在する。つまりKey Value Storeとして考える事ができる。
|
|
|
19
|
|
|
20 Aliceのデータベースは通常のKVSとは異なっている点がある。通常のKVSはプログラミング言語の連想配列やMapと同様に 「Key（キー）」と「Value（値）」がペアとなっている。そのため1つのKeyに対して値は1つである。しかし、Aliceの場合は「Key」と「Queue」がペアとなっているため、Keyに対して複数回putできる。従って取得できるValueも複数存在できる。Key毎の追加と取得はLindaに準じた設計になっている。
|
|
|
21
|
|
|
22 Data SegmentはData Segment Manager（以下DSM）によって管理されている。ノード毎にLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のKVSとなっている。従ってRemote DSMを指定するKeyはノード内部でuniqueなものである。Remote DSMは他のノードのLocal DSMのproxyと考えられる。つまりRemote DSMは複数存在し、それぞれに対応するノードは異なる。
|
|
|
23
|
|
|
24 \begin{figure}[htbp]
|
|
|
25 \begin{center}
|
|
|
26 \includegraphics{images/remote_datasegment.pdf}
|
|
|
27 \end{center}
|
|
|
28 \caption{Remote DSMは他のノードのLocal DSMのproxy }
|
|
|
29 \label{fig:RemoteDSM}
|
|
|
30 \end{figure}
|
|
|
31
|
|
|
32 KVSへのアクセスはqueueによって、ノード内部で逐次化される。それ以外は、すべてJavaのThread Poolにより並列実行される。
|
|
|
33 \subsection{Data Segment API}
|
|
|
34 以下が用意されているData Segment APIである。これらを用いてデータの送受信を行う。
|
|
|
35 \begin{itemize}
|
|
|
36 \item \verb+void put(String key, Value val)+
|
|
|
37 \item \verb+void update(String key, Value val)+
|
|
|
38 \item \verb+void peek(Receiver receiver, String key)+
|
|
|
39 \item \verb+void take(Receiver receiver, String key)+
|
|
|
40 \end{itemize}
|
|
|
41 \subsubsection{put}
|
|
|
42 putはデータをQueueに追加するためのAPIである。Lindaのout()に相当する。(図 \ref{fig:put})
|
|
|
43 \begin{figure}[htbp]
|
|
|
44 \begin{center}
|
|
|
45 \includegraphics[width=100mm]{images/put.pdf}
|
|
|
46 \end{center}
|
|
|
47 \caption{queueにデータを追加する}
|
|
|
48 \label{fig:put}
|
|
|
49 \end{figure}
|
|
|
50
|
|
|
51 \subsubsection{update}
|
|
|
52 updateはデータを置き換える特急メッセージのように動作する。Lindaのupdate()に相当する。(図 \ref{fig:update})
|
|
|
53 \begin{figure}[htbp]
|
|
|
54 \begin{center}
|
|
|
55 \includegraphics[width=100mm]{images/update.pdf}
|
|
|
56 \end{center}
|
|
|
57 \caption{update"は先頭データを取り除き、queueにデータを追加する}
|
|
|
58 \label{fig:update}
|
|
|
59 \end{figure}
|
|
|
60
|
|
|
61 \subsubsection{peek}
|
|
|
62 peekはデータを読み込むAPIである。読み込まれたデータはQueueに残る。要求したデータが存在しなければ、Code Segmentの待ち合わせ （Blocking）が起こる。putやupdateによりデータに更新があった場合、peekが直ちに実行される。Lindaのread()に相当する。(図 \ref{fig:peek})
|
|
|
63
|
|
|
64 \begin{figure}[htbp]
|
|
|
65 \begin{center}
|
|
|
66 \includegraphics[width=90mm]{images/peek.pdf}
|
|
|
67 \end{center}
|
|
|
68 \caption{peekはデータをreceiverに読み込む。希望のデータがない場合は保留する}
|
|
|
69 \label{fig:peek}
|
|
|
70 \end{figure}
|
|
|
71
|
|
|
72 \subsubsection{take}
|
|
|
73 takeもデータを読み込むためのAPIである。peekとの違いは読み込まれたデータはQueueから削除される。Lindaのin()に相当する。(図 \ref{fig:take})
|
|
|
74 \begin{figure}[htbp]
|
|
|
75 \begin{center}
|
|
|
76 \includegraphics[width=70mm]{images/take.pdf}
|
|
|
77 \end{center}
|
|
|
78 \caption{"take" はデータを receiver に読み込む。その際、読み込んだデータは削除される}
|
|
|
79 \label{fig:take}
|
|
|
80 \end{figure}
|
|
|
81
|
|
|
82 \subsection{Data Segment の表現}
|
|
|
83 Data Segmentの表現にはMessage Packを利用している。Message Packに関してJavaにおけるデータ表現は以下の3種類があり、制限を伴うが互いに変換可能である。
|
|
|
84 \begin{itemize}
|
|
|
85 \item {\ttfamily 一般的なJavaのクラスオブジェクト}
|
|
|
86 \item {\ttfamily MessagePack for JavaのValueオブジェクト}
|
|
|
87 \item {\ttfamily byte[]で表現されたbinary}
|
|
|
88 \end{itemize}
|
|
|
89
|
|
|
90 Data Segment APIの内部においてデータは、一般的なJavaのクラスオブジェクトまたはbyteArrayで表現されたbinaryで表現されている。
|
|
|
91 Localからデータがputされた場合は一般的なJavaのクラスオブジェクトの状態でenqueueされる。RemoteからデータがputされるとbyteArrayで表現されたbinaryの状態でenqueueされる。
|
|
|
92
|
|
|
93 ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを表現することができる。
|
|
|
94 この場合、クラス宣言時に@Messageというアノテーションをつける必要がある。もちろん、MessagePackで扱うことのできるデータのみをフィールドに入れなければならない。
|
|
|
95
|
|
|
96 Remoteに対してputできるデータは、@MessageをもつクラスオブジェクトかMessage Packで扱える型に限られる。
|
|
|
97
|
|
|
98 \section{Code Segment}
|
|
|
99 Code SegmentとはAlice上で実行されるタスクの単位である。ユーザーはCode Segmentを組み合わせることでプログラミングを行う。Code Segmentをユーザーが記述する際に、内部で使用するData Segmentの作成を記述する。入力時のData SegmentをInput Data Segment、出力時をOutput Data Segmentと呼ぶ。(図 \ref{fig:dsandcs})
|
|
|
100
|
|
|
101 \begin{figure}[htbp]
|
|
|
102 \begin{center}
|
|
|
103 \includegraphics[width=100mm]{images/dsandcs.pdf}
|
|
|
104 \end{center}
|
|
|
105 \caption{Code SegmentはInput Data Segment とOutput Data Segmentが存在する}
|
|
|
106 \label{fig:dsandcs}
|
|
|
107 \end{figure}
|
|
|
108
|
|
|
109 Input Data Segment と Output Data SegmentはCode Segmentに用意されているAPIを用いて作成する。
|
|
|
110 Input Data Segmentは、LocalかRemoteか、またkeyを指定する必要がある。Code Segmentは、記述したInput Data Segmentが全て揃うとThread poolに送られ、実行される。
|
|
|
111
|
|
|
112 Out Data SegmentもLocalかRemoteか、またkeyを指定する必要がある。
|
|
|
113
|
|
|
114 Input Data SegmentとOutput Data SegmentによってCode Segmentの間の依存関係が自動的に記述される。(図 \ref{fig:dsandcs2})
|
|
|
115
|
|
|
116 \begin{figure}[htbp]
|
|
|
117 \begin{center}
|
|
|
118 \includegraphics[width=110mm]{images/dsandcs2.pdf}
|
|
|
119 \end{center}
|
|
|
120 \caption{Input Data Segment とOut put Data SegmentがCode Segment間の依存関係を自動的に記述する}
|
|
|
121 \label{fig:dsandcs2}
|
|
|
122 \end{figure}
|
|
|
123 現在、Inputの場合はsetKeyを呼ぶ際、Outputはput(またはupdate)の際にノードとkeyの指定を行っている。
|
|
|
124 しかし、どの時点でノードとkeyの指定を行えばよいか、どのようなAPIを用意するべきかは、議論の余地がある。
|
|
|
125
|
|
|
126 \subsection{Code Segmentの実行方法}
|
|
|
127 Alice には、Start Code Segment (ソースコード \ref{src:StartCodeSegment})というC の main に相当するような最初に実行される Code Segment がある。
|
|
|
128 \begin{table}[html]
|
|
|
129 \lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java}
|
|
|
130 \end{table}
|
|
|
131
|
|
|
132 Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。
|
|
|
133 このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。
|
|
|
134
|
|
|
135 \subsection{Code Segmentの記述方法}
|
|
|
136 Code Segmentをユーザーが記述する際にはCode Segmentを継承して記述する(ソースコード \ref{src:CodeSegment})。
|
|
|
137 Code SegmentはInput/Output Data Segment Managerを利用することができる。
|
|
|
138
|
|
|
139 Input DSM はCode Segmentの{\tt ids}というフィールドを用いてアクセスする。
|
|
|
140
|
|
|
141 \begin{table}[html]
|
|
|
142 \lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java}
|
|
|
143 \end{table}
|
|
|
144
|
|
|
145 \begin{itemize}
|
|
|
146 \item {\ttfamily Receiver create(CommandType type)}
|
|
|
147 \end{itemize}
|
|
|
148 createでコマンドが実行された際に取得されるData Segmentが格納される受け皿を作る。引数にはCommandTypeが取られ、指定できるCommandTypeは{\tt PEEK}または{\tt TAKE}である。
|
|
|
149 \begin{itemize}
|
|
|
150 \item \verb+void setKey(String managerKey, String key)+
|
|
|
151 \end{itemize}
|
|
|
152 setKeyメソッドにより、どこのData Segmentのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定することができる。
|
|
|
153 コマンドの結果がレスポンスとして届き次第Code Segmentは実行される。
|
|
|
154
|
|
|
155 Output DSMはCode Segmentの{\tt ods}というフィールドを用いてアクセスする。
|
|
|
156 Output DSMは{\tt put}または{\tt update}を実行することができる。
|
|
|
157 \begin{itemize}
|
|
|
158 \item \verb+void put(String managerKey, String key, Object val)+
|
|
|
159 \item \verb+void update(String managerKey, String key, Object val)+
|
|
|
160 \end{itemize}
|
|
|
161
|
|
|
162
|
|
|
163 \section{Meta Data Segment}
|
|
|
164 Meta Data SegmentはData Segmentの一種である。Data Segmentは、ユーザーがput（またはupdate）したデータを管理するData Baseであるのに対して、Meta Data Segmentは、分散フレームワークAliceがputしたデータを管理するData Baseである。管理されているデータは、主にTopology Nodeの状態を表すメタデータである。ユーザーがメタデータを扱うこともできる。
|
|
|
165
|
|
|
166 例えば、"start"というkeyにはTopology NodeがStart Code Segmentを実行することができる状態を表す。他にも"\_CLIST"というkeyでは、利用可能なRemote Data Segmentの名前のリストが保存されている。ユーザーはリストをpeekし、putする際にリストにある名前を指定することで、動的にデータの伝搬などを行うことができる。
|
|
|
167
|
|
|
168 また、Input Data Segmentに付随しているものもある。Input Data SegmentはCode Segment内部でReceiverという入れ物に格納される。ユーザーは、Receiverに対して操作することでData Segmentを入手できる。
|
|
|
169 このReceiverには、fromというフィールドがあり、このデータを誰がputしたという情報が入っている。この情報をデータの伝搬する際に利用することで、データをputしたノードに送り返すことを防ぐことができる。
|
|
|
170
|
|
|
171 現在のAliceでは、メタデータはデータと同じ領域にputされているため、データと同じAPIを用いて取得できる。
|
|
|
172
|
|
|
173 \section{Meta Code Segment}
|
|
|
174 Meta Code SegmentはAliceを構成するCode Segmentである。
|
|
|
175
|
|
|
176
|
|
|
177
|
|
|
178 Alice自身が全てCode Segmentで記述されているため、AliceをMeta Code Segmentのかたまりと考える事ができる。
|
|
|
179
|
|
|
180
|
|
|
181 \section{Topology Manager}
|
|
|
182 Aliceは複数のノードで構成され、相互に接続される。通信するノードはURLにより直接指定するのではなくTopology Managerで管理する。
|
|
|
183 Topology Managerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきTopology NodeのIPアドレス、ポート番号、接続名を送りトポロジーファイルに記述されたとおりにトポロジーを作成する。(図\ref{fig:topologymanager})
|
|
|
184
|
|
|
185 \begin{figure}[htbp]
|
|
|
186 \begin{center}
|
|
|
187 \includegraphics[width=70mm]{images/topologymanager.pdf}
|
|
|
188 \end{center}
|
|
|
189 \caption{Topology Manager はトポロジーファイルの記述に従ってトポロジーを生成する}
|
|
|
190 \label{fig:topologymanager}
|
|
|
191 \end{figure}
|
|
|
192
|
|
|
193 Code Segment内部でRemote DSMにアクセスする場合はToplogyManagerによって指定されたノード内部だけで有効なlabel(文字列)を使う。これにより特定のURLがCode Segment内部に記述されることを防いでいる。
|
|
|
194
|
|
|
195 トポロジーファイルはグラフ構造を表現するデータ記述する言語の一種であるDOT Languageと呼ばれる言語で記述する。また、dotコマンドを用いてトポロジーファイルを可視化することができる。
|
|
|
196
|
|
|
197 \subsection{Topology Managerの参加表明処理}
|
|
|
198 Topology Managerへの参加表明は、Topology Node起動時にコマンドライン引数からTopology ManagerのIPアドレスとポート番号を指定すればよい。
|
|
|
199 指定されたTopology Managerに接続を行うと、Topology Manager側のキー"hosts"に、自分自身のIPアドレスとポート番号をputする。
|
|
|
200
|
|
|
201 参加表明を受け取ったTopology Managerは、抽象名を参加表明したTopology Nodeのキー"host"にputする。
|
|
|
202 その後、Topology Manager上のTopology Node名のキーに、接続すべきTopology Nodeの情報(IP アドレス、ポート番号等)を全てputする。Topology Nodeは、その情報を1つずつTakeし接続処理を行う。全ての接続処理が終わるとTopology ManagerからTopology Nodeに対してStart Code Segmentの実行命令が出され、アプリケーションが開始される。
|
|
|
203
|
|
|
204 \begin{figure}[htbp]
|
|
|
205 \begin{center}
|
|
|
206 \includegraphics[width=120mm]{images/topologymanagerandnode.pdf}
|
|
|
207 \end{center}
|
|
|
208 \caption{Topology ManagerとTopology Node間の通信}
|
|
|
209 \label{fig:topologymanagerandnode}
|
|
|
210 \end{figure}
|
|
|
211
|
|
|
212 \section{Aliceによるプログラミング手法}
|
|
|
213 AliceはCode SegmentとData Segmentによってプログラミングを行なう。Code Segmentから別にCode SegmentへData Segmentを引き渡す際、コンストラクタは使わない。Code SegmentがLocal / Remote Data Segmentに対してputを行い、別のCode SegmentがLocal / Remote Data Segmentに対してpeekを行うことで引き渡される。つまり、Code Segmentは実行前後にData Segmentへ通信が行われるのである。この通信の順序がCode Segmentの実行順序を決定している。
|
|
|
214 すなわち、Aliceによるプログラミングとは通信の管理を行うことであり、プロトコルを設計することと捉える事ができる。
|
