1
|
1 -title: 連邦型Lindaによる分散アルゴリズムをデバッグするためのメタプロトコル
|
|
2
|
|
3 --author: 赤嶺悠太, 小野雅俊, 河野真治
|
|
4
|
5
|
5 --はじめに
|
2
|
6
|
4
|
7 分散アプリケーションが多数開発されている近年、
|
|
8 ノードやネットワークの動的な変化、故障、性能の多様性を考慮した
|
|
9 フレームワークが必要である。
|
|
10 分散環境ではスケーラビリティを確保すること重要である。ここでの
|
|
11 スケーラビリティとはノードの規模の増大にも関わらず、
|
|
12 アプリケーションの性能を維持できることを指す。
|
|
13 分散アルゴリズムの作成には、論理的なプログラムの正しさだけでなく、
|
|
14 スケーラビリティのデバッグを可能にする必要がある。
|
|
15 つまり、デバッガ自体をスケーラブルに作る必要がある。
|
|
16 そのため、分散
|
|
17 フレームワークとして本研究室が提案しているFederated Lindaに、
|
|
18 スケーラビリティなデバッグを行う為のメタな通信を行うプロトコルエンジン
|
|
19 を設計し実装した。
|
|
20
|
|
21 分散プログラムの
|
|
22 デバッグを行う際には通信は必須であるが、その通信によって
|
|
23 本来の通信に影響を及ぼす恐れがある。
|
|
24 ここでは、スケーラビリティには若干問題があるが、
|
|
25 本来の通信に影響を与えないように、一つのトークンをリング上に
|
5
|
26 流す方法を提案\cite{kono03f,kono03d}している。本論文ではPCクラスタ上で実際の通信を行ない、100台程度の
|
4
|
27 分散プログラムでの評価を行なった。
|
|
28
|
5
|
29 --Scaleする分散プログラム
|
|
30
|
|
31 Internet 上で動作している分散プログラムは、例えば、DNS、
|
|
32 SMTP、NNTP、あるいは、さまざまなP2PやDHTなどがある。
|
|
33 これらのサービスで重要なのは、Scalability つまり、
|
|
34 サービスの規模が大きくなっても、応答速度などの要求仕様を
|
|
35 満たすことである。このようなプログラムは、一つのコンピュータ
|
|
36 に閉じた逐次型のプログラムや、マルチスレッドのプログラムとは
|
|
37 様相が異なる。
|
|
38
|
7
|
39 Federated Linda\cite{kono05b,kono05f} は、計算モデルが明解なLinda\cite{linda} を
|
5
|
40 複数接続することで、分散プログラムの作り方を明確なモデル
|
|
41 上で学ぶことができるようにするように設計されている。
|
|
42
|
7
|
43 我々は、この上で投票システムやCompact Routing\cite{Abraham04compactname-independent,kono08c} 等を
|
5
|
44 実装して来たが、分散プログラムは、それ自体が複雑なだけで
|
|
45 なく、デバッグ自体の困難さが問題であることがわかってきた。
|
|
46
|
|
47 最初の目標は、琉大情報工学科にある200台規模のPCクラスタ
|
|
48 上で、Federated Linda を用いた分散プログラムを作成し
|
|
49 デバッグすることである。
|
|
50
|
|
51 分散プログラムは正しい答えを出すだけでなく、Scalability
|
|
52 があるかどうかを調べることが必要である。PCクラスタ上の
|
|
53 デバッグでは、デバッグ自体に通信が必要であり、その通信が
|
|
54 Scalability に影響しないようにする必要がある。
|
|
55
|
|
56
|
2
|
57 --プロトコルエンジンとタプル空間
|
|
58
|
4
|
59 Federated Lindaとは、複数のタプル空間を相互に
|
|
60 結ぶプロトコルエンジンによって
|
|
61 接続する分散プログラミングモデルである。
|
|
62 Lindaと同じAPIを持つが、
|
|
63 Lindaが一つのタプル空間を共有するのに対し、
|
|
64 Federated Lindaは複数のタプル空間を個別に持つ。
|
|
65 クライアントのアクセス数に対応して、
|
|
66 タプルスペースの数を増やし処理を分散させる事により、スケーラビリティを保つ。
|
|
67
|
5
|
68 % タプルスペース内の情報はプロトコルエンジンが切断されても
|
|
69 % そこに残る。プロトコルエンジンは、再接続することにより、自然に
|
|
70 % 計算を再開できる。このように、Federated Linda は実際のインターネット
|
|
71 % 上で起きる通信切断に強いフレームワークとなっている。
|
|
72
|
|
73 % この耐切断性を実現するためには、タプルスペースの持続性(Persistency)
|
|
74 % が重要であるが、一方で、プロトコルエンジンが状態を持たないように
|
|
75 % することが望ましい。
|
|
76 % ってことは、プロトコルエンジンがトランザクションをサポート
|
|
77 % した方が良いってことだよな〜
|
|
78
|
|
79
|
2
|
80 --プログラミング例
|
|
81
|
4
|
82 Federated Lindaは以下の様にして通信を行う。
|
|
83
|
|
84 \begin{itemize}
|
|
85 \item public PSXLinda open(String \_host,int \_port)
|
|
86
|
|
87 Linda Serverに対し、接続を行う。引数はホスト名とポート番号をとる。返り値はタプルスペースの番号となる。
|
|
88
|
|
89 \item public PSXReply in(int id)
|
|
90
|
|
91 タプルスペース番号より引数で指定したidのタプルの受け取りを要求する。
|
|
92 受け取りは、返値のPSXReplyをチェックすることにより非同期に行なう。
|
|
93 in では待ち合わせは行なわれない。Call back 形式でタプルを受け取る
|
|
94 ことも出来る。
|
|
95
|
|
96 \item public PSXReply out(int id, ByteBuffer data)
|
|
97
|
|
98 引数で指定したidでByteBuffer内のデータを送信する。
|
|
99
|
|
100 \item public int sync(long mtimeout)
|
|
101
|
|
102 接続しているLinda Serverとタプルの送受信のポーリングを行う。
|
|
103
|
|
104 \end{itemize}
|
|
105
|
|
106 Protocol Engineとはタプルスペースを介してデータをやり取りするEngineである。
|
|
107 二つのサーバー間でやり取りを行う場合、以下のようなプログラムとなる。
|
|
108 \begin{verbatim}
|
|
109 FederatedLinda fdl;
|
|
110 PSXLinda getpsx;
|
|
111 PSXLinda sendpsx;
|
|
112 PSXReply in;
|
|
113 ByteBuffer data = ByteBuffer.allocate(10);
|
|
114
|
|
115 //通信を初期化する
|
|
116 fdl = FederatedLinda.init();
|
|
117 //データを取ってくるホストと受け渡すホストとの接続開始
|
|
118 getpsx = fdl.open("cs100",10000);
|
|
119 sendpsx = fdl.open("cs101",10001);
|
|
120 //取ってくるホストからinを指定してデータを取得
|
|
121 in = getpsx.in(10)
|
|
122 data = in.getData();
|
|
123 //受け渡すホストに対しデータとidを指定して同期
|
|
124 sendpsx.out(10,data);
|
|
125 fdl.sync();
|
|
126 \end{verbatim}
|
|
127
|
5
|
128 callback のAPIも用意されていて、{\tt fdl.sync() } した時に、
|
|
129 {\tt in, rd} の結果が戻っていれば、そのcallback が実行される
|
|
130 ようになっている。
|
|
131
|
2
|
132 --デバッグするには?
|
|
133
|
5
|
134 Federated Linda 上でデバッグする一つの方法は、デバッガ
|
7
|
135 からタプルスペースへ問い合わせの通信を行なうことである(図\ref{集中型デバッガ})。
|
|
136 <center><img src="fig/comDebug.jpg" alt="集中型デバッガ"></center>
|
5
|
137
|
|
138 この方法では、Linda Serverのad-hocな改変が必要であり、
|
|
139 デバッガは各Linda Serverへ1対多の集中的な通信を行なう
|
|
140 必要がある。この方法では、デバッガはLinda Server への
|
|
141 直接の通信路を持つ必要があるが、分散環境では、ファイアウォール
|
|
142 などの関係で、それが可能であるとは限らない。
|
2
|
143
|
5
|
144 デバッグ自体は、
|
|
145 タプル空間に直接アクセス出来るプロトコルエンジンと
|
|
146 考えることができ、Federated Lindaのメタエンジン
|
|
147 ととらえることができる。メタエンジンのAPIを
|
|
148 Linda にそろえることにより、Linda Serverへの
|
|
149 ad-hoc な改変を、決まったAPI上のデバッグプロトコル
|
7
|
150 の設計にすることができる(図\ref{Debugger})。
|
|
151 <center><img src="fig/debugger.jpg" alt="Debugger"></center>
|
5
|
152
|
|
153 デバッグ自体をScalableにして、分散計算への影響を少なく
|
|
154 するためには、デバッグ用の通信自体がScalable である必要が
|
|
155 ある。
|
2
|
156
|
5
|
157 それには、デバッグプロトコル自体が、Federated Linda に
|
|
158 よってScalable だと示されたプロトコルであることが望ましい。
|
|
159 つまり、最初に情報収集などに適したプロトコルをFederated
|
|
160 Linda で作成し、それをそのままデバッガのプロトコルに
|
|
161 採用できることが望ましい。
|
7
|
162 <center><img src="fig/obj2meta.jpg" alt="メタへの移行"></center>
|
5
|
163
|
|
164
|
|
165
|
|
166
|
|
167 --メタエンジン
|
|
168
|
4
|
169 デバッグ用の通信はLinda Server内部に直接アクセス出来なければ
|
|
170 ならない。これをLinda Server内のMeta Protocol Engine に
|
7
|
171 よって実現する(図\ref{メタエンジン})。
|
4
|
172
|
|
173 Meta Engine は、
|
|
174 通常のFederatedLindaと同様のin/out APIを持つ。
|
|
175 Meta Engine では、\verb+sync()+が、属するLinda Server
|
|
176 自体のポーリングを行なう。\verb+sync()+の間は、
|
|
177 通信は行なわれず タプル空間は変化しない。
|
|
178 Meta Engine は安全にタプル空間にアクセス出来る。
|
|
179 Meta Engine のプログラムは、
|
|
180 Linda Serverのメインループで指定することが出来、
|
|
181 Server 毎に独自の動作をさせることが可能である。
|
7
|
182 <center><img src="fig/meta.jpg" alt="メタエンジン"></center>
|
4
|
183
|
5
|
184 --メタエンジンの実装
|
|
185
|
|
186 ここでの Linda Server は、Single Thread に実装されており、
|
|
187 Java nio のselect で待ち、通信パケットを受け取って処理する
|
|
188 というメインループを持っている。
|
|
189 メタエンジンは、このメインループを置き換える形で
|
|
190 実装した。つまり、メタエンジン自体が{\tt sync()}
|
7
|
191 しながらループするという構造を持っている(図\ref{メタエンジン})。
|
5
|
192
|
|
193 メタエンジンは、Linda serverの立ち上げ時、または、
|
|
194 メタエンジンそのものから、特殊なものに置き換えるAPI
|
|
195 を用意する。
|
|
196
|
|
197 APIは、通常のLindaのAPIだが、メタエンジンでは、
|
|
198 タプルスペースに対して直接アクセスする。
|
|
199
|
|
200 Single Thread Server上のメインループの一部として
|
|
201 実現されているので、タプルスペースをlockすることなく
|
|
202 自由にアクセスすることができる。ここでのLinda API
|
|
203 は{\tt in,rd}で待ち合わせしない仕様になっていて、
|
|
204 待ち合わせは、{\tt sync()}とポーリング、または、
|
|
205 call back によって実現されている。従って、
|
|
206 メインループの一部としても、{\tt in,rd}の待ち合わせ
|
|
207 によってデッドロックするようなことはない。
|
|
208
|
2
|
209
|
|
210 --分散プログラムのデバッグ手法
|
|
211
|
6
|
212 Federated Linda では、プロトコルエンジンは、
|
|
213 タプルスペース(Linda Server)から、
|
|
214 タプルを受け取って、それに計算を施して、
|
|
215 他のタプルスペースへ引き渡す。従って、
|
|
216 バグは、あるタプルを受け取って、どのような
|
|
217 タプルを出力するかというのを見ることになる。
|
2
|
218
|
6
|
219 個々のプロトコルエンジンの計算が正しくても、
|
|
220 大域的なエラーが起きる場合も存在するので、
|
|
221 個々の処理だけでなく、全体的な状態の情報も
|
|
222 必要となる場合がある。
|
2
|
223
|
6
|
224 通信状態を含めた大域的な状態は分散スナップショット
|
|
225 と呼ばれる。分散スナップショットを取ること自体に
|
|
226 通信が必要である。また、分散スナップショットは、
|
|
227 未来からの通信が含まれている場合は、
|
|
228 再実行可能でないことがある。再実行可能なスナップ
|
|
229 ショットを取るためには、通常の通信に制限をかける
|
|
230 ことが必要である。
|
2
|
231
|
6
|
232 デバッグプロトコルには、個々のTuple Space の情報収集
|
|
233 とともに、スナップショットを取る機能が必要である。
|
|
234 スナップショットが取れれば、そのイメージを
|
|
235 調べることによりデッドロック検出も可能となる。
|
|
236
|
7
|
237 Scalability の検証では、通信の集中を見つける必要がある。
|
|
238 そのためには、タプルスペース側での通信のlogの監視を
|
|
239 行なう必要がある。すべてのlog情報を一ヶ所に集める
|
|
240 ことなく、通信の集中を調べる機能が必要である。
|
6
|
241
|
7
|
242 --デバッグプロトコル
|
2
|
243
|
7
|
244 分散環境で情報を集めるには、デバッグのための通信そのものが
|
|
245 分散プログラムになる。ここでは、PCクラスタ上でのシミュレーション
|
|
246 を想定して、ターゲットの通信を妨げないデバッグ通信を考える。
|
|
247 200台規模では、単一のリング上の通信が良いと考えている。
|
|
248
|
|
249 メタエンジン上にリングを構成し、デバッガフロントエンドは、
|
|
250 そのリングを通して、コマンドを送ったり情報を収集したりする
|
|
251 構成である(図\ref{Debugger})。
|
2
|
252
|
|
253 --Simulation
|
|
254
|
7
|
255 デバッグプロトコルを実装するために、PCクラスタによるシミュレーション
|
|
256 を行なった。メタエンジン上にリングを構成し、その周回時間をパケットの
|
|
257 大きさを変えて調べる。これにより、リングを使うことによるデバッグの
|
|
258 ユーザへの応答性能と、デバッグを行なう情報を交換する時のパケットの
|
|
259 適切な大きさを調べることができる。これらの数値は、その時その時の
|
|
260 技術に依存している。
|
2
|
261
|
4
|
262 本稿では
|
|
263 分散通信に影響を最低限にするために、Ringで性能を評価する。
|
|
264 3台のLinda Server間でMeta Engineがデータをやり取りする場合
|
|
265 のUMLシーケンス図は
|
|
266 図\ref{ringthree}のようになる。
|
|
267 \begin{figure}[htbp]
|
|
268 \begin{center}
|
7
|
269 \includegraphics[scale=0.2]{fig/meta_ring_three.eps}
|
4
|
270 \caption{3台間の通信}
|
|
271 \label{ringthree}
|
|
272 \end{center}
|
|
273 \end{figure}
|
|
274
|
|
275 Ring では通信パケットは一つのみであり、デバッグ対象への
|
|
276 影響が小さい。
|
|
277 しかし、スナップショットや一時停止などの
|
|
278 デバッグ操作をするためには、全ノードを周回する必要がある。
|
|
279 %これはo(n)であり、十分にスケーラビリティがあるとは言えない。
|
|
280 %しかし、もっとも影響が少ない方法なので、どの程度まで使える
|
|
281 %かを測定することには意味がある。
|
|
282
|
|
283 ここでは、通信パケットの大きさを変えて、
|
|
284 3〜100までの台数でデータが1周(図\ref{metaring})する時間、
|
|
285 および1000周(図\ref{metaring1000})した時に掛かった時間を測定する。
|
|
286 前者では接続の手間を含む通信時間、後者では通信のみの時間を
|
|
287 計ることが出来る。
|
|
288
|
|
289 実験は、
|
|
290 琉球大学
|
|
291 情報工学科のクラスタ上(Core Duo 2GHz,メモリ1GB)で、
|
|
292 クラスタジョブ管理システム
|
|
293 Torqueを用いて行なった。
|
|
294 ネットワークはAlaxalA Gigabit Ethernet Switchで構成されている。
|
|
295 クラスタ自体は180台あるが、
|
|
296 安定して動作する100台までを使用して測定を行なった。
|
|
297
|
|
298 \begin{figure}[htbp]
|
|
299 \begin{center}
|
7
|
300 \includegraphics[scale=0.3]{fig/metaring1.eps}
|
4
|
301 \caption{接続を含む一周の時間}
|
|
302 \label{metaring}
|
|
303 \end{center}
|
|
304 \end{figure}
|
7
|
305
|
|
306 X軸が台数、Y軸がミリ秒、ラインの色が通信するデータサイズを表す。
|
|
307 両図から見てわかる通り、データの量にはあまり依存する事はなくほぼ同じラインを形作っている。
|
|
308 データを1周のみした場合は1サイクルあたり約14000ms、一台あたり約140ms掛かっている計算になる。
|
|
309 これは、TCPの接続時間がかなり大ききことを示している。1MB程度の通信を
|
|
310 隠すほど接続時間のオーバヘッドは大きい。
|
|
311 14秒はインタラクティブな
|
|
312 デバッガとしては容認できないと思われる。
|
|
313 従って、毎回、新しく接続するようなHTMLのような
|
|
314 通信を採用することはできないことがわかる。
|
|
315
|
|
316
|
4
|
317 \begin{figure}[htbp]
|
|
318 \begin{center}
|
7
|
319 \includegraphics[scale=0.3]{fig/metaring1000.eps}
|
4
|
320 \caption{千周の平均周回時間}
|
|
321 \label{metaring1000}
|
|
322 \end{center}
|
|
323 \end{figure}
|
|
324
|
|
325 それに対し1000周した際に掛かった時間は、1サイクルおよそ60ms、一台につき約0.6msとなっている。
|
|
326 これより、一度、接続してしまえば、
|
|
327 Meta Engine での通信は実際に100台程度のデバッグに使用するのに十分な性能を
|
|
328 持っていることが確認出来た。
|
|
329
|
7
|
330 パケット1KBから100KBまでの差は2倍程度であり、それ以上はパケットサイズに
|
|
331 リニアに時間がかかる。従って、数十KB程度以下にデータを抑えることは、
|
|
332 応答時間的には意味がない。
|
2
|
333
|
|
334
|
|
335 --比較
|
4
|
336
|
|
337
|
|
338 本稿ではデバッグを行う為に通常通信とは他に、Metaで通信するMeta Protocol Engineを実装し評価した。
|
|
339 今回は、スナップショットなどの実際のデバッグ機能を実装することは出来なかった。
|
|
340 通信の実験においても、
|
|
341 同クラスタ上で別のRing通信や他のMetaLinda通信等があった場合の干渉の程度
|
|
342 などを測定する必要があると考えられる。
|
|
343
|
|
344
|