グローバルスナップショットと状態

グローバルスナップショットは、システムを停止させることなく、分散計算の状態（各プロセスのローカル状態と転送中のメッセージ）の一貫したビューを捉えます。

Definition

一貫性のあるグローバル状態とは、一貫性のあるカットに対応するローカルプロセス状態とチャネル内容の集合です。一貫性のあるカットとは、記録されたすべてのメッセージ受信に対して、対応する送信も記録されているようなカットであり、グローバルな瞬間が観測されなかったとしても、その状態が計算中に発生した可能性があることを意味します。

Scope

このトピックでは、一貫性のあるグローバル状態とその状態を定義するカットの概念、Chandy-Lamportのマーカーベースのスナップショットアルゴリズムとその前提条件（FIFOチャネル、信頼性の高い配信）、および終了検出やデッドロック検出などの安定特性検出、分散チェックポイントとリカバリへのスナップショットの適用について説明します。

Core questions

• 記録されたグローバル状態が不可能な状態ではなく一貫性があるのはなぜですか？
• 計算が継続している間に、そのような状態をどのように記録できますか？
• 終了やデッドロックのような安定特性は、スナップショットからどのように検出されますか？

Key theories

一貫性のあるカット

グローバル状態は、プロセスのイベントシーケンスを横断するカットに対応します。このカットは、happened-before関係の下で閉じている場合にのみ一貫性があり、記録された状態においてメッセージが送信される前に受信されることがないことを保証します。

Chandy-Lamportスナップショットアルゴリズム

イニシエータは自身の状態を記録し、各送信チャネルにマーカーを送信します。各プロセスは、最初にマーカーを受信すると自身の状態を記録し、その後、他のチャネルからのマーカーが到着するまで、それらのチャネル上の受信メッセージを記録してチャネルの内容を捕捉します。

安定特性検出

スナップショットはシステムが取り得た状態を捉えるため、スナップショットで検出された安定特性（一度真になると真であり続ける特性、例えば終了やデッドロック）は実際に真であり、スナップショットを一般的な検出ツールとしています。

Clinical relevance

スナップショットアルゴリズムは、フォールトリカバリのための分散チェックポイント/再起動を強化します。これには、現代のストリーム処理エンジンが厳密に一度だけの保証を提供するために使用する非同期スナップショット、および長時間実行される計算におけるデッドロックと終了の検出が含まれます。

History

ChandyとLamportによる1985年のアルゴリズムは、システムを停止させることなく一貫性のあるグローバル状態を記録する最初の実用的な方法を提供しました。Matternらは基礎となるカット理論を一般化し、この技術は後にフォールトトレラントなストリーム処理の基盤となりました。

Key figures

• K. Mani Chandy
• Leslie Lamport
• Friedemann Mattern

Seminal works

• chandy1985
• mattern1989
• lynch1996

Frequently asked questions

スナップショットを撮るにはシステムを一時停止する必要がありますか？

いいえ。Chandy-Lamportアルゴリズムは、計算が継続している間に一貫性のあるグローバル状態を記録します。これは、チャネルに沿ってマーカーを伝播させることによって行われます。記録された状態は、システムが全体的に停止されたことがないにもかかわらず、システムが取り得た状態の一つです。