動的にチャネルが増減する環境下 での分散スナップショットアルゴリズ ム 澤井省吾 田浦健次朗 近山隆（東京大学） IPSJ PRO 2007/03/22(木) 2015/10/1 情報処理学会プログラミング研究会 1 分散システム クラスタを複数組み合わせたグリッドなど、 多数の計算機を用いた計算が盛んになっ ている。 適応的並列計算の必要性 動的に計算機が参加、脱退を行う 動的に計算機を結ぶチャネルを接続、切断す る。 2015/10/1 情報処理学会プログラミング研究会 2 分散スナップショット 分散システムの大域状態 デッドロック検出、計算の終了、分散GC、etc… ChandyとLamportらによって静的なネットワーク における分散スナップショットアルゴリズムが提 案されている。 動的なネットワークにおける分散スナップショット アルゴリズムはあまり提案されていない。 2015/10/1 情報処理学会プログラミング研究会 3 本研究の貢献 動的なネットワークにおける分散スナップ ショットアルゴリズムの提案 フォーマルな証明 2015/10/1 情報処理学会プログラミング研究会 4 分散システム プロセス チャネル 各プロセス間を結ぶ通信路 FIFO ポート 送信ポート 受信ポート 2015/10/1 情報処理学会プログラミング研究会 5 分散システムにおける計算 メッセージ イベント：メッセージの送受信や 計算など A B C 2015/10/1 情報処理学会プログラミング研究会 6 分散システムの大域状態 各プロセスのローカルな状態 それまでに起こったイベント列 各チャネルをその瞬間に流れていたメッ セージ列 送信したが、まだ受信されていないメッセージ 2015/10/1 情報処理学会プログラミング研究会 7 いかにして分散システムの大域 状態を得るのか 全システムを停止させて、そのときの各プ ロセスの状態と、流れていたメッセージを 記録すればよい 2015/10/1 情報処理学会プログラミング研究会 8 分散システムの大域状態 メッセージ イベント：メッセージの送受信や 計算など ある瞬間における、すべて のプロセスの状態 と、プ ロセス間のチャネルを流れ るメッセージ列 A B C 2015/10/1 情報処理学会プログラミング研究会 9 いかにして分散システムの大域 状態を得るのか 全システムを停止させて、そのときの各プ ロセスの状態と、流れていたメッセージを 記録すればよい さすがに全システムを困難であるので、各 プロセスが勝手に記録する。 2015/10/1 情報処理学会プログラミング研究会 10 だめな例 メッセージ プロセスがスナップショット を取った瞬間 A B C 2015/10/1 情報処理学会プログラミング研究会 11 だめな例 送信されてもいないメッ セージが、受信された ことになっている メッセージ プロセスがスナップショット を取った瞬間 Cからメッセージを受け 取った！！！！ BとCの証言が矛盾する A B C Bにメッセージなんて送っ てない！！！！ 2015/10/1 情報処理学会プログラミング研究会 12 いかにして分散システムの大域 状態を得るのか 全システムを停止させて、そのときの各プ ロセスの状態と、流れていたメッセージを 記録すればよい さすがに全システムをとめたくはないの で、各プロセスが勝手に記録する。 consistentなスナップショットをとりたい 2015/10/1 情報処理学会プログラミング研究会 13 ChandyとLamportの分散スナップショットアルゴリズム （CLアルゴリズム） [K.Mani Chandy and Leslie Lamport, Distributed Snapshots: Determining Global States of Distributed Systems] markerというプロトコルメッセージを用いて、 各プロセスのスナップショットのタイミングと、 メッセージの記録を制御する 2015/10/1 情報処理学会プログラミング研究会 14 CLアルゴリズム 初めてmarkerを受け取ったプロセスは、ス ナップショットを取り、すべての送信ポート にmarkerを送信する markerを受け取ったら、スナップショットを 取ったときからmarkerを受け取るまでの メッセージ列を記録する 2015/10/1 情報処理学会プログラミング研究会 15 分散スナップショット markerメッセージ メッセージ プロセスがスナップショット を取った瞬間 A B C 2015/10/1 情報処理学会プログラミング研究会 16 分散スナップショット メッセージ プロセスがスナップショット を取った瞬間 A B C 2015/10/1 情報処理学会プログラミング研究会 17 CLアルゴリズム 証明されているのは静的なネットワーク 動的なネットワークに拡張することはでき ないのか？ 2015/10/1 情報処理学会プログラミング研究会 18 CLアルゴリズムの単純な拡張 初めて、markerを受け取ると、スナップ ショットを取り、つながっているすべてのプ ロセスにmarkerを送信する。 markerを受け取ると、スナップショットを 取ってから、markerを受け取るまでのメッ セージを記録する。 チャネルが作成されても、削除されても何 もしない。 2015/10/1 情報処理学会プログラミング研究会 19 だめな例（チャネルができるとき） 記録されない メッセージ メッセージ プロセスがスナップショット を取った瞬間 矛盾する メッセージ A AとBの間に チャネルがで きた B この時点でAとBはつ ながっていなかった。 2015/10/1 AはBに対して markerを送信しない 情報処理学会プログラミング研究会 20 だめな例（チャネルが削除されるとき） メッセージ AはBからmarkerがくるのを待 つ。 プロセスがスナップショット を取った瞬間 AはBからmarkerがくるの A を永遠に待ち続けてしまう。 AとBの間にチャネルが切断された （BからAにメッセージを送信すること ができなくなった） B この時点でAとBはつ ながっていた。 2015/10/1 この時点で、BはAとは接続 していないためAにmarker を送信しない。 情報処理学会プログラミング研究会 21 CLアルゴリズム 動的な分散システムに何もしないまま適用 するのは難しい チャネルの増減の扱い方をきちんと考えて あげる必要がある。 2015/10/1 情報処理学会プログラミング研究会 22 動的なネットワークにおける分散スナップ ショットアルゴリズム 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で静的なネット ワークに接続されていなければならない（トポロジーに制限があ る） 一般的な分散システムには適用できない 2015/10/1 情報処理学会プログラミング研究会 23 発表の流れ 背景・貢献 関連研究 提案手法 仮定 チャネルの増減 スナップショットアルゴリズム 証明の概要 まとめ 2015/10/1 情報処理学会プログラミング研究会 24 仮定 任意のプロセスグラフ 双方向チャネル 作成、削除の際には一時的に単方向チャネル チャネルはFIFO チャネルは動的に増減する 2015/10/1 情報処理学会プログラミング研究会 25 チャネル AはBに向かう送信ポートが あるのでメッセージを送るこ とができる A 2015/10/1 B Bとの通信路 AはBからの受信ポートがあ るのでメッセージを受信する ことができる 情報処理学会プログラミング研究会 26 メッセージが受け取られない場合 メッセージが残っているにもかかわらず受 信ポートが受け取り側で削除されてしまう 送信されたメッセージが あるにもかかわらず、受 信ポートが削除された メッセージ 2015/10/1 情報処理学会プログラミング研究会 27 チャネルを削除する際のプロトコル 送ったメッセージは必ず相手に届く。 これ以上はメッセージを送らないという、プ ロトコルメッセージを用いればいい 2015/10/1 情報処理学会プログラミング研究会 28 チャネルを削除する際のプロトコル これ以上メッセージを送らないというプロトコル メッセージ（closechannel）を相手に送信する closechannelを受け取ると同時に closechannelを送信したと同時に 受信ポートが削除される 送信ポートが削除される メッセージ 2015/10/1 closechannel 情報処理学会プログラミング研究会 29 チャネルを作成するときのプロトコル 作成するときは削除するときとは逆に、受 信ポートができてから送信ポートができる べき プロトコルメッセージ（newchannel）を用い る 対応する送信ポート 2015/10/1 受信ポート 情報処理学会プログラミング研究会 30 チャネルを作成する際のプロトコル メッセージを受け取る準備ができたことを知らせ るためのプロトコルメッセージ（newchannel）を用 いる。 newchannelを受け取ると送信 受信ポートが作成され、同時に、 newchannelが送信される ポートが作成される メッセージ 2015/10/1 newchannel 情報処理学会プログラミング研究会 31 チャネルの増減のプロトコル 作成したいとき（A->B） Bが受信ポートを作り、Aにnewchannelを送信する Aはnewchannelを受け取ったら、送信ポートを作成 する A<-Bがなければ同様に作成する 1. 2. 3. 削除したいとき（A->B） 1. 2. 3. 2015/10/1 AがBに対してclosechannelを送信し、送信ポートを 閉じる Bはclosechannelを受け取ったら、送信ポートを閉じ る A<-Bが存在していれば、同様に削除する 情報処理学会プログラミング研究会 32 発表のながれ 背景・貢献 関連研究 提案手法 チャネルの増減 スナップショットアルゴリズム 証明の概要 まとめ 2015/10/1 情報処理学会プログラミング研究会 33 本研究のアプローチ チャネルの増減がなければCLアルゴリズムと同 じ動作 チャネルの増減がスナップショットのきっかけに はならない またアルゴリズムがチャネルの増減を妨げない あるプロセスがスナップショットをとった後、チャ ネルの増減があった時について考える。 送受信ポートが作成、削除される。４つのパターンに ついて、どうプロトコルを追加すればよいのかを考え る。実質、送信ポートが作成されたとき、受信ポートが 作成、削除されたときの３パターンについて考える。 2015/10/1 情報処理学会プログラミング研究会 34 だめな例（Aにおいて送信ポートが 新しく作られたとき） 送信ポートが send 作成された recv 受信ポートが 作成された プロセスがスナップショット Aが送ってないのに、 を取った瞬間 Bはなぜか受信したと いうメッセージ A send newchannel B recv この時点でAとBはつ ながっていなかった。 2015/10/1 Aは以後Bにメッセージを 送信することができる 情報処理学会プログラミング研究会 35 Aにおいて送信ポートが新しく作 られたとき 以後Bにメッセージを 送信ポートが 受信ポートが 送信することができる send recv 作成された 作成された send プロセスがスナップショット を取った瞬間 送信ポートができたら即 座にmarkerを送信する A newchannel B recv この時点でAとBはつ ながっていなかった。 2015/10/1 必ずAから何かメッセージを受け取 るよりも前にmarkerを受け取る 情報処理学会プログラミング研究会 36 だめな例（Aにおいて受信ポートが できるとき） スナップショットの時にBはすでに送信していた が、Aはスナップショットにはまだ受信していない メッセージなので、記録する必要がある。 A recv newchannel 記録されないメッセージ B send この時点でAとBはつ ながっていなかった。 2015/10/1 情報処理学会プログラミング研究会 37 Aにおいて受信ポートが作成さ れたとき newchannelを送信する前に、 すでにスナップショットを取って いれば、markerを送信する A recv newchannel send 以降メッセージを送った としても、Aは記録する 必要はない B この時点でAとBはつ ながっていなかった。 2015/10/1 情報処理学会プログラミング研究会 38 だめな例（チャネルが削除されるとき） メッセージ AはBからmarkerがくるのを待つ。 プロセスがスナップショット を取った瞬間 AはBからmarkerがくるの A を永遠に待ち続けてしまう。 AとBの間にチャネルが切断された （BからAにメッセージを送信すること ができなくなった） B この時点でAとBはつ ながっていた。 2015/10/1 この時点で、BはAとは接続 していないためAにmarker を送信しない。 情報処理学会プログラミング研究会 39 受信ポートが削除されたとき X send 送信ポートが 削除された X recv X recv 受信ポートが 削除された この時点でAはBからのメッ セージの記録を終了する A Bからmarkerがこない・・・ でも、接続が切れた X B send 2015/10/1 Bがスナップショットを取ったときAへの送信 はできないので、markerを送信しない 情報処理学会プログラミング研究会 40 新しく追加したプロトコル プロセスがすでにスナップショットを取っていたら 新しい送信ポートができたら、即座に markerを送信する 受信ポートを作成する際に、newchannel の前にmarkerを送信する。 markerを受け取るよりも前に、 closechannelを受け取ったら、メッセージ の記録を終了する 2015/10/1 情報処理学会プログラミング研究会 41 追加したプロトコルによって増え るメッセージ数 新しい送受信ポートができたときに、即座 にmarkerを送信する必要がある CLアルゴリズム エッジの数ｘ２ 本アルゴリズム エッジの数ｘ２＋増えたチャネルの数ｘ４ 2015/10/1 情報処理学会プログラミング研究会 42 発表の流れ 背景・貢献 関連研究 提案手法 証明の概要 まとめ 2015/10/1 情報処理学会プログラミング研究会 43 証明の流れ 終了 CLアルゴリズムの証明を再度行い、異な る部分について証明を行った。 2015/10/1 情報処理学会プログラミング研究会 44 本アルゴリズムの証明 終了 スナップショットを取ったプロセスというのは必 ず、メッセージの記録を終了する 得られるスナップショットの正しさの証明 2015/10/1 情報処理学会プログラミング研究会 45 本アルゴリズムの証明 終了 得られるスナップショットの正しさの証明 A->Bに流れていたメッセージ列として記録されるメッ セージ列は、「Aがスナップショットの前に送信したメッ セージ列から、Bがスナップショットの前に受信したメッ セージ列を引いたもの」である。 また、Bがスナップショットの前に受信したメッセージの 集合は、Aがスナップショットの前に送信したメッセー ジの集合に常に含まれる 2015/10/1 情報処理学会プログラミング研究会 46 まとめ チャネルの増減を扱うために、送受信ポー トの作成・削除に順序関係をつくった その上で動作する分散スナップショットア ルゴリズムを提案した。 メッセージ数は、CLアルゴリズムとあまり変わ らない また、そのアルゴリズムの正しさを証明し た。 2015/10/1 情報処理学会プログラミング研究会 47 参考文献 K. Mani Chandy and Leslie Lamport. Distributed snapshots: Determining global states of distributedsystems. ACM Trans. Comput. Syst., Vol. 3, No. 1, pp. 63–75, 1985. Sathya Peri and Neeraj Mittal. Monitoring stable properties in dynamic peer-to-peer distributed systems.In R. Ramanujam and Sandeep Sen, editors, FSTTCS, Vol. 3821 of Lecture Notes in Computer Science,pp. 420–431. Springer, 2005. Yasurou Satou, Michiko Inoue, Toshimitsu Masuzawa, and Hideo Fujiwara. A snapshot algorithm fordistributed mobile systems. In 16th International Conference on Distributed Computing Systems, pp.734–743, 1996. 2015/10/1 情報処理学会プログラミング研究会 48
© Copyright 2024 ExpyDoc
