Document

チャネルが動的に増減する環境下での
分散スナップショットアルゴリズムとそ
の応用
2007.2.16
電子情報工学科４年
近山・田浦研究室
５０３７８澤井省吾
2007/2/16(Fri)
1
分散オブジェクト指向言語


プログラミングが難しい分散システムで高い生産性
Webサービスの融合
 データベースとそれを用いたアプリケーションが別のクラ
スタで動作しているなど

動的な資源の活用
分散システムのスナップショットをえることがで
きると非常に有用
2007/2/16(Fri)
2
分散スナップショット

デッドロックや計算の終了を知ることができる
 動的なネットワークではほとんど行われていない

応用
 分散GC

2007/2/16(Fri)
チャネルが動的に変化する環境下での分散GCはほと
んど提案されていない
3
本研究の貢献
動的なネットワークにおいて分散スナップ
ショットを得るアルゴリズムの提案
 フォーマルな証明と実験的な検証
 応用

 分散オブジェクト指向のミドルウェアを作成
 ミドルウェア上に分散GCを設計・実装した
2007/2/16(Fri)
4
ChandyとLamportの分散スナップショット
[K.Mani Chandy and Leslie Lamport, Distributed Snapshots:
Determining Global States of Distributed Systems]

静的なネットワークにおいて分散システムの
安定状態を知ることができる
A
process
B
E
message
C
2007/2/16(Fri)
分散スナップショットの例
D
5
ChandyとLamportの分散スナップ
ショットアルゴリズム
A
メッセージの記録が終了する
メッセージが記録される
B
END
END
相手からのメッセージマーカーメッセー
プロセスAの状態を
ジを送信
記録を記録する
2007/2/16(Fri)
プロセスBの状態を
記録
6
とれた分散スナップショット
A
2007/2/16(Fri)
B
7
ChandyとLamportの分散スナップ
ショットアルゴリズムの擬似コード

event receive_marker_msg:
if not recorded:
record_state
p.i = {}
broadcast_marker_msg
p.i = p.i + {from}

event receive_user_msg:
if recorded and ( not from ∈ p.i ):
save_message( from, user_message )
receive_message(user_message)
2007/2/16(Fri)
8
ChandyとLamportの分散スナップショットアルゴリズ
ムを動的なネットワークに適用してみようとすると・・・・
A
この瞬間に、AとBを
B
結ぶチャネルが切ら
れる
Bがスナップショットを
とる前だったので、当
然マーカーメッセージ
？？？は送られない。
プロセスAがスナップどうしていいのかわ
ショットを取る
からない
2007/2/16(Fri)
9
ChandyとLamportの分散スナップショット

静的なネットワークにのみ適用可能
動的なネットワークにおいても分散スナッ
プショットが得られば、発見することがで
きればうれしい
2007/2/16(Fri)
10
動的なネットワークにおける分散スナップショッ
トアルゴリズム

Monitoring Stable Properties in Dynamic Peer-to-Peer
Distributed Systems (Sathya Peri and Neeraj Mittal.
2005 )



スパニングツリーを作成する必要がある
脱退の際にスパニングツリーを再構成する必要がある
A Snapshot Algorithm for Distributed Mobile Systems
( 佐藤ら, 1996 )


動的にチャネルが変化するプロセスは、１hopで静的なネットワーク
に接続されていなければならない（トポロジーに制限がある）
一般的な分散システムには適用できない
2007/2/16(Fri)
11
動的なネットワークに対するアプローチ
B
B
A
従来のチャネル表現
2007/2/16(Fri)
A
本アルゴリズムにおけるチャネル表現
12
チャネルを接続するときの動作
B
Bにおいて、Aからの内向きチャ
ネルができたことを知らせる
（もしBがすでにスナップショットを
取っていれば、マーカーメッセー
ジを先に送る）
A
2007/2/16(Fri)
13
チャネルを切断するときの動作
B
AからBにむかう、Aの外向きの
チャネルが切れたことを知らせる
BがAからのマーカーメッセー
ジを待っている時、Bはこの
チャネルのメッセージ列の記
録を終了する。
A
2007/2/16(Fri)
14
チャネルの増減の擬似コード
event create_incomming_channel:
c = new_incomming_channel
q = new_queue(p2,p1)
if recorded:
q = q + {MRK}
q = q + {M_n}
event close_incomming_channel:
q = q \ {M_c}
if recorded and (c in i):
i[c] = GotMRK
2007/2/16(Fri)
event create_outgoing_channel:
c=
new_outgoing_channel(p1,p1,p2)
q = q \ {M_n}
C = C ∪ {c}
event close_outgoing_channel:
q = q + {M_c}
C = C \ {c}
15
分散スナップショットアルゴリズムの擬似コード
event receive_MRK:
q = q \ {MRK}
if not recorded:
record_state( p )
i = record_incomming_channel()
set all value of i to Recording
for ∀q_ ∈ Q( outgoing channel from p1 )
q_ = q_ + {MRK}
recorded = True
i[c] = GotMRK
event receive_user_message:
q = q \ {M_u}
if recorded and (c in i) and (i[c] is Recording):
record_message(c,M_u)
2007/2/16(Fri)
16
ChandyとLamportの分散スナップショットでは問題で
あったところがどうなるのか？
A
B
ここで記録を終了する
2007/2/16(Fri)
17
アルゴリズムの証明の概要
スナップショットをとったプロセスは必ず終了
条件を満たす
 記録されるメッセージ列は、スナップショットの
瞬間に飛んでいたメッセージ列
 無矛盾な分散スナップショット

2007/2/16(Fri)
18
分散スナップショットアルゴリズムの検証
•
各プロセスがTOKEN（パケット）をランダムに投げ合う
•
大域的にTOKENの総数は一定
67ノードを用い、各プロセ
スには100個ずつTOKEN
を持たせ、0～0.99[sec]ご
とに送信するとし、各プロ
セスが１秒間に一回チャネ
ルを接続・切断する環境下
であっても正しく動作する
ことを確認した。
2007/2/16(Fri)
19
分散GCの設計と実装
分散スナップショットアルゴリズムを用いて、
各プロセスにおいてオブジェクトグラフの断片
を得る
 その情報を用いて、マークスイープを行う。

2007/2/16(Fri)
20
分散スナップショットアルゴリズムを使う意図
分散スナップショットアルゴリズム自体がさま
ざまな状況において有用である
 ローカルで行う作業と、リモートで行う作業を
きれいに分けることができる

 結果としてシンプルになる

リファレンスカウントと異なり、循環参照も削
除できる
2007/2/16(Fri)
21
オブジェクトグラフ断片


ローカルに持っているリモートリファレンスからどのリモートリファレンスにた
どることができるのか？
分散スナップショットの時に、飛んでいたリモートリファレンスは必ずルートに
なるとする。
remote object
F
A
B
remote object (root)
D
E
2007/2/16(Fri)
C
22
オブジェクトグラフ断片のマージ

ひとつの計算機にオブジェクトグラフの断片を集め
ることで、トレーシングにかかる通信による遅延を極
力抑える。
remote object
remote object (root)
2007/2/16(Fri)
23
終わりに

まとめ
 分散スナップショットアルゴリズムはフォーマルに
証明する事ができ、実験的に検証をおこなった
 分散GCを実装し、正しく動作していることを確認
した

今後の課題
 よりスケーラビリティの高い分散GC
2007/2/16(Fri)
24
分散スナップショットアルゴリズムの検証


オブジェクトで木構造をつくりルートから色を塗っていく。
スナップショットはこの塗りつぶし過程のある瞬間の木を得る
ことができる
ちゃんと実装できていな
ければ、親が塗られて
いないのに、子が塗ら
れているという、
矛盾したスナップショット
が得られてしまう。
2007/2/16(Fri)
25

Download Report