読者です 読者をやめる 読者になる 読者になる

mrasu’s blog

読んだ物の内容など

Distributed Computing: Principles, Algorithms, and Systems (4章)

「Distributed Computing: Principles, Algorithms, and Systems」の4章
メモリダンプのように、分散システム全体に対する「現在状態」を取得する方法について
全コンピュータ同時に取ることはできないので、分散が牙を剥く

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems

Chapter4 Global state and snapshot recording algorithms

4.1 Introduction

グローバルな状態を取得できると、デッドロックの発見やデバッグ、復旧などに使えるが
共有メモリもなく、同一時間でもないので、特定の時刻の情報を取ることは難しい。

4.2 System model and definitions

送信中であるとは、「送信イベントは発生しているが、受信イベントは発生していない状態」を指す
グローバルの状態は、プロセスのイベントとチャネル中のイベントの総和なので、
送信イベントがあるなら、チャネルにあるか受信イベントがあるかのどちらか(チャネル中と受信を同時には満たさない)
送信イベントがないなら、チャネルにも受信イベントにもない
受信イベントがあるなら、送信イベントは必ずある

cut(断面?)がconsistentな状態とは、PASTに所属する全ての受信イベントの対になる送信イベントがPASTにある状態を言う。
consistentだと、全ての状態を並列実行できる

特定の時間に対するスナップショットにどのデータを入れるかは以下のルール

  1. 時間より前に送信したメッセージは含める
  2. 時間より後に送信したメッセージは含めない

つまり、スナップショットを取得する時は、別プロセスの送信イベントが含まれていないなら受信イベントも含まないようにする

4.3 Snapshot algorithms for FIFO channels

FIFOでメッセージが処理される場合の方法として、Marker sending rule

  1. プロセスpiが自分の状態を記録する
  2. 新たなメッセージを送信する前に、チャネル全体にマーカーを送信する(マーカー送信済みのプロセスには送らない)
  3. マーカーを受け取ったプロセスpjは、
    1. 記録していなければ、Marker sending ruleを実行する(状態記録とマーカー送信)
    2. 記録済みであれば、状態を記録した時からマーカーを受信するまでのメッセージを送信中メッセージとする

記録した状態を全プロセスに渡せば、各プロセスがグローバルな状態を見ることができる。
複数のスナップショット記録を並列で走らせたいなら、マーカーにユニークな印をつければいい。

4.4 Variations of the Chandy-Lamport algorithm

4.4.1 Spezialetti-Kearns algorithm

Chandy-Lamportのアルゴリズムでは、複数の取得処理があった場合全処理分のスナップショットが必要になる。
それを回避するためにregionという概念を用いる

各取得処理はそれぞれ固有のIDを持ち、各プロセスはマーカーについたIDからどの取得処理用のマーカーかを判断する。
スナップショットを持っていない状態でマーカーを受けたとき、スナップショットを作成するが、
スナップショットを持った状態で別IDのマーカーを受けたときは、スナップショットを取らない。
各プロセスはマーカーのIDを1つしか記録せず、同一のIDを持つプロセス群をregionと呼ぶ。

各プロセスは自身のIDに対してスナップショットを返すので、各regionは自プロセスたちの状態を把握する。
そして、region間でスナップショットの差分(量削減のため?)を交換して、region外のプロセスの状態を把握し、自分のプロセス達の状態と比較することで取得対象自国の状態を把握する(マージする)

4.4.2 Venkatesan's incremental snapshot algorithm

継続的に状態を把握したい場合に、逐一 Chandy-Lamportのアルゴリズムを使用すると効率が悪いので、
変更が起きたものだけを取得すればよいという発想のアルゴリズム

状態取得のメッセージに、バージョン番号をつける。
状態を取得したくなったら、バージョンを更新して、全体にinit_snapメッセージを投げる。
メッセージを受信したら、スナップショットを取り、前回から現在までにメッセージを送信した相手にregularメッセージと、親にackを投げる。
regularを受け取ったら、スパニングツリーの葉まで渡されたら葉はsnap_completedメッセージを投げる。
snap_completedを受け取ったら、それも親に返す。
根まで行ったら終了。

4.5 Snapshot algorithms for non-FIFO channels

FIFOを前提としないと、マーカーが正しい順番でくるとも限らないので、別のアルゴリズムが必要
Helaryのアルゴリズムではマーカーを送信したら、ackレスポンスかスナップショット自体がそのプロセスから帰ってくるまでメッセージを送らない

4.5.1 Lai-Yang algorithm

プロセスを赤と白の状態で区別する。

  1. 全プロセスを白で初期化する。スナップショットを取ったら赤にして、marker sending rule 発動
  2. メッセージは発信元のプロセスの色情報が添付して送信する。
  3. 白のプロセスは赤のメッセージが来る前にスナップショットを取らなくてはならない。(スナップショットを取るのでプロセスは赤になる)
  4. 白のプロセスは全ての白のメッセージを記録する
  5. プロセスが赤になったら、グローバルの状態を取りたがっているプロセス(initiator)に対してスナップショットと白メッセージの履歴を送信する
  6. initiatorは履歴をもとに、各メッセージの状態を計算する

とすることで、送信済みメッセージは送信中か受信済みかに分類され、未送信メッセージが処理されることもない

4.6 Snapshots in a causal delivery system

メッセージの因果順序が決定しているなら、複雑なことをしなくとも簡単にできる

4.6.1 Process state recording

トークンを全プロセスに送信し、受信したらスナップショットを取り送り返す。

これだけで、十分

4.6.2 Chnnel state recordning in Acharya-Badrinath algorighm

チャネルの状態を記録するには、
各プロセスが対象プロセスに送信したidと受信したid(idは連番)を記録し、スナップショットに付加することで、
initiatorは対象のチャネル上にある送信中メッセージを、受信id ~ 送信id の間と判断できる

4.6.3 Channel state reording in Alagar-Venkatesan algorithm

トークンより前のメッセージをoldなメッセージとする

  1. トークンを受け取ったら、スナップショットをとって、完了メッセージをinitiatorを送り返す。
  2. oldなメッセージを取得したら、チャネル中のメッセージに加える
  3. initiatorはすべての完了メッセージを取得したら、全プロセスに終了メッセージを送る
  4. 終了メッセージを受けたら、oldの取得も終了する

4.7 Monitoring global state

プロセスの変数の集合である「システムの状態」を把握することはデバッガのようなアプリケーションにとって必要
Kearnsは、simultaneous regionsを用いて
プロセス中の変数が変化したら、monitorに報告を上げ、別プロセスに対しても状態を報告するように支持を出す
monitorはその情報からグローバルな状態を把握する
i番目とi+1番目のイベントの間の期間が i+1 simultaneous regionとして報告される

4.8 Necessary and sufficient conditions for consistent global snapshots

ローカルの状態を記録することも重要で、loocal chckpointと呼ばれる
各プロセスのスナップショットが合わさってグローバルな状態を作るが、consistentであるひつようもある
consistentだと、処理が再開した時に、送っていないメッセージを受信したことにならなず、不整合にならないから。

consistentな状態の必要十分条件をzigzag pathと表現し、
別プロセスの2つのスナップショットの間で、前に取られた方より後に送信され、後に取られた方では受信しているメッセージが存在する時がzigzag pathがあるといい、
Lamportの事前関係を一般化したもの。

この関係があると、consistentにはならない

4.8.1 Zigzag paths and consistent global snapshots

zipzag pathの定義と、zigzag pathを利用して、consistentなスナップショットを構成するチェックポイント群を発見する方法を見出す

consistentであるとは、すべてのチェックポイント間で因果関係がないことが条件だが、
事前の関係がなくとも、consistentではない場合がある。

定義4.1 zigzag path があるとは、2チェックポイント間(プロセスx,y)で以下を満たすメッセージ群(m1...mn)がある時を言う

  1. メッセージm1がプロセスxから、チェックポイント後に送信される
  2. メッセージmkを第三者プロセスzが受信し、同一インターバルか後のインターバルでzがmk+1を送信する(mk+1の送信はmkの受信と前後を問わない)
  3. メッセージmnをプロセスyがチェックポイント前に受信する

定義4.2 zigzag path の起点と終点が同じチェックポイント内にあるとき、zigzag cycle にあると言う

NetzerとXuにより、チェックポイント群でzigzag path が存在しない時、チェックポイントはconsistentになることと、その逆が示された。

4.9 Finding consisent global snapshots in a distributed computation

スナップショット群に対して、consistentなスナップショットの組み合わせを得る

4.9.1 FFinding consistent global snashots

Z-pathが存在しないあるチェックポイント集合Sがあるとき、consistentな状態を維持できる他のチェックポイントを探す

  1. Sとチェックポイントの間にZ-pathがないものが候補。(これを満たすチェックポイントの集合をZ-coneと呼ぶ)
  2. Sとチェックポイントの間にZ-pathがなく、チェックポイントがz-cycleでなければ、Sに含むことができる
  3. S以外のチェックポイントで、上記を満たすチェックポイントの集合をT(Tuseful)とすると、T内にZ-pathがなければ、S∪Tはconsistent

4.9.2 Manivannan-NetzerSinghal algorithm for enumerating consistent snapshots

consistentなものをすべて求めるには、
与えられた集合に含まれていないプロセスで、Tusefulなものを順に取り出すようにすれば、すべて出せる

4.9.3 Finding Z-paths in a distributed computation

以下を満たすR-graph G = (V,E)

  1. 頂点Vは全チェックポイント
  2. 辺(Cpi,Cqj)は
    1. p = q and i = j+1
    2. p ≠ q and プロセスpのi番目のインターバルからプロセスqのj番目のインターバルへメッセージがある
      のどちらかを満たす

これを作ると、
CpiとCqjにZ-pathがあるのは、

  1. p = q and i < j
  2. CpiからCqjへの経路がR-graphにある

のどちらかを満たすとき