|
0
|
1 \chapter{分散フレームワーク Alice の概要} \label{chapter:chapter1}
|
|
1
|
2
|
|
20
|
3 \section{Data SegmentとCode Segment}\label{subsection:computation}
|
|
18
|
4 AliceはデータをData Segment、タスクをCode Segmentという単位に分割してプログラミングを行なう。
|
|
|
5 Code SegmentはInput Data SegmentとOutput Data Segmentを持つ(図 \ref{fig:dsandcs})。Input Data SegmentはそのCode Segmentを実行するために必要なデータ群であり、Output Data SegmentはCode Segmentが計算を行った結果を格納するデータ群である。
|
|
|
6
|
|
|
7
|
|
|
8 Data SegmentはAliceが内部にもつデータベースによって管理されている。
|
|
|
9 Input Data Segmentを取得する際とOutput Data Segmentを保存する際にデータベースに通信を行う。
|
|
|
10 取得するData SegmentはData Segmentに対して一意であるKEYを用いて指定する。
|
|
|
11 Input Data Segmentの取得に失敗した場合、Code SegmentはDatabaseでData Segmentの待ち合わせを行う。
|
|
|
12 Input Data Segmentが揃った場合にCode Segmentは実行される。
|
|
|
13
|
|
|
14
|
|
|
15 \begin{figure}[htbp]
|
|
|
16 \begin{center}
|
|
|
17 \includegraphics[width=100mm]{images/dsandcs.pdf}
|
|
|
18 \end{center}
|
|
|
19 \caption{Code SegmentはInput Data Segment とOutput Data Segmentが存在する}
|
|
|
20 \label{fig:dsandcs}
|
|
|
21 \end{figure}
|
|
|
22
|
|
|
23 Code Segmentに依存するデータ群であると出力されるデータ群を記述することにより、Code Segmentが実行される順番が決定される(図 \ref{fig:dsandcs2})。データの依存関係にないCode Segmentは並列実行が可能であるため、並列度を上げるためにはCode Segmentの処理内容を細かく分割して依存するデータを少なくするのが望ましい。
|
|
|
24
|
|
|
25
|
|
|
26 \begin{figure}[htbp]
|
|
|
27 \begin{center}
|
|
|
28 \includegraphics[width=110mm]{images/dsandcs2.pdf}
|
|
|
29 \end{center}
|
|
|
30 \caption{Input Data Segment とOut put Data SegmentがCode Segment間の依存関係を自動的に記述する}
|
|
|
31 \label{fig:dsandcs2}
|
|
|
32 \end{figure}
|
|
|
33
|
|
20
|
34 \section{ComputationとMeta Computation}
|
|
|
35 AliceのComputationは\ref{subsection:computation}で示したように、keyで指し示されるData Segmentを待ち合わせてCode Segmentを実行させるというものである。アプリケーションを作成するためにはアルゴリズムをAliceのComputationで表現する必要がある。
|
|
19
|
36
|
|
|
37 また、アプリケーションでAliceのComputationを設定するComputationを利用することができる。このComputationをMeta Computationと呼ぶ。
|
|
18
|
38
|
|
20
|
39 例えば、Aliceのトポロジーと再接続の管理はMeta Computationとみなすことができる。
|
|
|
40 Code Segment単位ではトポロジーや切断を想定せずにアプリケーションを記述することができる。
|
|
|
41 トポロジーのMeta Computationを利用することで、トポロジーが2分木からn分木に変わってもアプリケーションは動く。
|
|
|
42 再接続のMeta Computationを利用すれば、アプリケーションはノードが再接続してきた場合でも、切断してないノードと同様に動かすことができる。
|
|
18
|
43
|
|
|
44
|
|
|
45 \section{Aliceの実装}
|
|
20
|
46 ここではAliceがどのように実装されているかを説明する。
|
|
|
47 \section{Data Segment}
|
|
18
|
48 Data Segmentは数値や文字列などのデータを構造的に保持する。AliceはData Segmentをデータベースとして扱っている。Data Segmentには必ず対になるKeyが存在する。つまりKey Value Storeとして考える事ができる。
|
|
|
49
|
|
|
50 Aliceのデータベースは通常のKVSとは異なっている点がある。通常のKVSはプログラミング言語の連想配列やMapと同様に 「Key（キー）」と「Value（値）」がペアとなっている。そのため1つのKeyに対して値は1つである。しかし、Aliceの場合は「Key」と「Queue」がペアとなっているため、Keyに対して複数回putできる。従って取得できるValueも複数存在する。
|
|
|
51
|
|
|
52 Data SegmentはData Segment Manager（以下DSM）によって管理されている。ノード毎にLocal DSMとRemote DSMが存在する。Local DSMは各ノード固有のKVSとなっている。従ってRemote DSMを指定するKeyはノード内部でuniqueなものである。Remote DSMは他のノードのLocal DSMのproxyと考えられる。つまりRemote DSMは複数存在し、それぞれに対応するノードは異なる。
|
|
|
53
|
|
|
54 \begin{figure}[htbp]
|
|
|
55 \begin{center}
|
|
|
56 \includegraphics{images/remote_datasegment.pdf}
|
|
|
57 \end{center}
|
|
|
58 \caption{Remote DSMは他のノードのLocal DSMのproxy }
|
|
|
59 \label{fig:RemoteDSM}
|
|
|
60 \end{figure}
|
|
|
61
|
|
|
62 KVSへのアクセスはqueueによって、ノード内部で逐次化される。それ以外は、すべてJavaのThread Poolにより並列実行される。
|
|
|
63 \subsubsection{Data Segment の表現}
|
|
|
64 Data Segmentの表現にはMessage Packを利用している。Message Packに関してJavaにおけるデータ表現は以下の3種類があり、制限を伴うが互いに変換可能である。
|
|
|
65 \begin{itemize}
|
|
|
66 \item {\ttfamily 一般的なJavaのクラスオブジェクト}
|
|
|
67 \item {\ttfamily MessagePack for JavaのValueオブジェクト}
|
|
|
68 \item {\ttfamily byte[]で表現されたbinary}
|
|
|
69 \end{itemize}
|
|
|
70
|
|
|
71 Data Segment APIの内部においてデータは、一般的なJavaのクラスオブジェクトまたはbyteArrayで表現されたbinaryで表現されている。
|
|
|
72 Localからデータがputされた場合は一般的なJavaのクラスオブジェクトの状態でenqueueされる。RemoteからデータがputされるとbyteArrayで表現されたbinaryの状態でenqueueされる。
|
|
|
73
|
|
|
74 ユーザーが一般的なクラスをIDL(Interface Definition Language)のように用いてデータを表現することができる。
|
|
|
75 この場合、クラス宣言時に@Messageというアノテーションをつける必要がある。もちろん、MessagePackで扱うことのできるデータのみをフィールドに入れなければならない。
|
|
|
76
|
|
|
77 Remoteに対してputできるデータは、@MessageをもつクラスオブジェクトかMessage Packで扱える型に限られる。
|
|
17
|
78
|
|
20
|
79 \subsubsection{Data Segment API}
|
|
|
80 \section{Code Segment}
|
|
18
|
81 Code SegmentとはAlice上で実行されるタスクの単位である。ユーザーはCode Segmentを組み合わせることでプログラミングを行う。Code Segmentをユーザーが記述する際に、内部で使用するData Segmentの作成を記述する。
|
|
3
|
82
|
|
18
|
83 Input Data Segment と Output Data SegmentはCode Segmentに用意されているAPIを用いて作成する。
|
|
|
84 Input Data Segmentは、LocalかRemoteか、またkeyを指定する必要がある。Code Segmentは、記述したInput Data Segmentが全て揃うとThread poolに送られ、実行される。
|
|
|
85
|
|
|
86 Output Data SegmentもLocalかRemoteか、またkeyを指定する必要がある。
|
|
|
87 Inputの場合はsetKeyを呼ぶ際、Outputの場合はput(またはupdate)の際にノードとkeyの指定を行っている。
|
|
|
88 しかし、どの時点でノードとkeyの指定を行えばよいか、どのようなAPIを用意するべきかは、議論の余地がある。
|
|
|
89
|
|
|
90
|
|
20
|
91 \subsection{Code Segmentの実行方法}
|
|
18
|
92 Alice には、Start Code Segment (ソースコード \ref{src:StartCodeSegment})というC の main に相当するような最初に実行される Code Segment がある。
|
|
|
93 \begin{table}[html]
|
|
|
94 \lstinputlisting[label=src:StartCodeSegment, caption=StartCodeSegmentの例]{source/StartCodeSegment.java}
|
|
|
95 \end{table}
|
|
|
96
|
|
|
97 Start Code SegmentはどのData Segmentにも依存しない。つまりInput Data Segmentを持たない。
|
|
|
98 このCode Segmentをmainメソッド内でnewし、executeメソッドを呼ぶことで実行を開始させることができる。
|
|
|
99
|
|
|
100
|
|
20
|
101 \subsection{Code Segmentの記述方法}
|
|
18
|
102 Code Segmentをユーザーが記述する際にはCode Segmentを継承して記述する(ソースコード \ref{src:CodeSegment})。
|
|
|
103 Code SegmentはInput/Output Data Segment Managerを利用することができる。
|
|
1
|
104
|
|
18
|
105 Input DSM はCode Segmentの{\tt ids}というフィールドを用いてアクセスする。
|
|
|
106
|
|
|
107 \begin{table}[html]
|
|
|
108 \lstinputlisting[label=src:CodeSegment, caption=CodeSegmentの例]{source/TestCodeSegment.java}
|
|
|
109 \end{table}
|
|
|
110
|
|
|
111 \begin{itemize}
|
|
|
112 \item {\ttfamily Receiver create(CommandType type)}
|
|
|
113 \end{itemize}
|
|
|
114 createでコマンドが実行された際に取得されるData Segmentが格納される受け皿を作る。引数にはCommandTypeが取られ、指定できるCommandTypeは{\tt PEEK}または{\tt TAKE}である。
|
|
|
115 \begin{itemize}
|
|
|
116 \item \verb+void setKey(String managerKey, String key)+
|
|
|
117 \end{itemize}
|
|
|
118 setKeyメソッドにより、どこのData Segmentのあるkeyに対してpeekまたはtakeコマンドを実行させるかを指定することができる。
|
|
|
119 コマンドの結果がレスポンスとして届き次第Code Segmentは実行される。
|
|
|
120
|
|
|
121 Output DSMはCode Segmentの{\tt ods}というフィールドを用いてアクセスする。
|
|
|
122 Output DSMは{\tt put}または{\tt update}を実行することができる。
|
|
|
123 \begin{itemize}
|
|
|
124 \item \verb+void put(String managerKey, String key, Object val)+
|
|
|
125 \item \verb+void update(String managerKey, String key, Object val)+
|
|
|
126 \end{itemize}
|
|
|
127
|
|
|
128 %
|
|
17
|
129 \subsection{Meta Data Segment}
|
|
18
|
130 %
|
|
17
|
131 \subsection{Meta Code Segment}
|
|
18
|
132
|
|
17
|
133 \subsection{Topology Manager}
|
|
2
|
134 Aliceは複数のノードで構成され、相互に接続される。通信するノードはURLにより直接指定するのではなくTopology Managerで管理する。
|
|
3
|
135 Topology Managerはトポロジーファイルを読み込み、参加を表明したクライアント(以下、Topology Node)に接続するべきTopology NodeのIPアドレス、ポート番号、接続名を送りトポロジーファイルに記述されたとおりにトポロジーを作成する。(図\ref{fig:topologymanager})
|
|
2
|
136
|
|
|
137 \begin{figure}[htbp]
|
|
|
138 \begin{center}
|
|
3
|
139 \includegraphics[width=70mm]{images/topologymanager.pdf}
|
|
2
|
140 \end{center}
|
|
|
141 \caption{Topology Manager はトポロジーファイルの記述に従ってトポロジーを生成する}
|
|
|
142 \label{fig:topologymanager}
|
|
|
143 \end{figure}
|
|
|
144
|
|
|
145 Code Segment内部でRemote DSMにアクセスする場合はToplogyManagerによって指定されたノード内部だけで有効なlabel(文字列)を使う。これにより特定のURLがCode Segment内部に記述されることを防いでいる。
|
|
|
146
|
|
15
|
147 トポロジーファイルはグラフ構造を表現するデータ記述する言語の一種であるDOT Languageと呼ばれる言語で記述する。また、dotコマンドを用いてトポロジーファイルを可視化することができる。
|
|
3
|
148
|
|
17
|
149 \subsubsection{Topology Managerの参加表明処理}
|
|
3
|
150 Topology Managerへの参加表明は、Topology Node起動時にコマンドライン引数からTopology ManagerのIPアドレスとポート番号を指定すればよい。
|
|
|
151 指定されたTopology Managerに接続を行うと、Topology Manager側のキー"hosts"に、自分自身のIPアドレスとポート番号をputする。
|
|
|
152
|
|
|
153 参加表明を受け取ったTopology Managerは、抽象名を参加表明したTopology Nodeのキー"host"にputする。
|
|
|
154 その後、Topology Manager上のTopology Node名のキーに、接続すべきTopology Nodeの情報(IP アドレス、ポート番号等)を全てputする。Topology Nodeは、その情報を1つずつTakeし接続処理を行う。全ての接続処理が終わるとTopology ManagerからTopology Nodeに対してStart Code Segmentの実行命令が出され、アプリケーションが開始される。
|
|
|
155
|
|
|
156 \begin{figure}[htbp]
|
|
|
157 \begin{center}
|
|
|
158 \includegraphics[width=120mm]{images/topologymanagerandnode.pdf}
|
|
|
159 \end{center}
|
|
|
160 \caption{Topology ManagerとTopology Node間の通信}
|
|
|
161 \label{fig:topologymanagerandnode}
|
|
|
162 \end{figure}
|
|
4
|
163
|
|
17
|
164
|
|
18
|
165 \section{Aliceによるプログラミング手法}
|
|
19
|
166 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は実行前後にデータベースへ通信が行われるのである。この通信の順序がCode Segmentの実行順序を決定している。
|
|
14
|
167 すなわち、Aliceによるプログラミングとは通信の管理を行うことであり、プロトコルを設計することと捉える事ができる。
|
