チェックポイントとリカバリ

チェックポイントは、システムの現在の状態を定期的に保存することで、障害発生時に最初から再起動するのではなく、整合性のある時点にロールバックして処理を再開できるようにします。

Definition

チェックポイントは、1つ以上のプロセスの状態を安定ストレージに記録することです。ロールバックリカバリは、これらのチェックポイントと、場合によってはログに記録されたメッセージを使用して、障害発生後にシステムを整合性のあるグローバル状態（リカバリライン）に復元し、そこから処理を再開します。

Scope

このトピックでは、チェックポイントベースおよびログベースのロールバックリカバリについて扱います。具体的には、非協調型、協調型、および通信誘発型チェックポイント、非協調型チェックポイントが引き起こす可能性のあるドミノ効果、そして最後のチェックポイントを超えてリカバリを可能にする悲観的、楽観的、および因果的メッセージロギングについて説明します。これは、グローバルスナップショットの整合カット理論に関連しています。

Core questions

• プロセス間のチェックポイントをどのように組み合わせて整合性のあるリカバリラインを形成できるか？
• ドミノ効果とは何か、そして協調がそれをどのように防ぐのか？
• メッセージロギングは、いつ最も新しいチェックポイントを超えたリカバリを可能にするのか？

Key theories

協調型チェックポイント

プロセスが協調して、それらのチェックポイントが整合性のあるグローバル状態を形成するようにすることで、利用可能なリカバリラインを保証し、同期オーバーヘッドを犠牲にして連鎖的なロールバックを回避します。

非協調型チェックポイントとドミノ効果

プロセスが独立してチェックポイントを作成する場合、リカバリには整合性のあるセットを見つけるために各プロセスをロールバックする必要があり、場合によっては最初まで連鎖的にロールバックする可能性があります（ドミノ効果）。協調またはロギングはこれを回避するために設計されています。

メッセージロギング

プロセスが受信するメッセージを（悲観的、楽観的、または因果的に）ロギングすることで、リカバリ中のプロセスはそれらを決定論的に再生し、最後のチェックポイントを超えて進行することができ、グローバルなロールバックなしに最近の作業を回復できます。

Clinical relevance

チェックポイント/再起動は、長時間実行される高性能計算や科学計算をノード障害に対して回復力のあるものにし、非同期チェックポイントは、最新のストリーム処理システムに「一度だけ」の障害回復保証を提供します。

History

ChandyとLamportの一貫性スナップショット理論に基づいて、KooとTouegは1987年に協調型チェックポイントを形式化しました。ロギングと非協調型スキームに関する数十年にわたる研究は、Elnozahyらが2002年に発表した調査論文（ロールバックリカバリに関する標準的な参考文献）にまとめられました。

Debates

協調型チェックポイントと非協調型チェックポイント

協調型チェックポイントはクリーンなリカバリラインを保証しますが、同期コストとグローバルな協調を追加します。非協調型チェックポイントはチェックポイント作成時には安価ですが、ドミノ効果と複雑なリカバリのリスクがあるため、適切な選択は障害発生率と規模に依存します。

Key figures

• K. Mani Chandy
• Leslie Lamport
• Sam Toueg
• Lorenzo Alvisi

Seminal works

• elnozahy2002
• koo1987
• chandy1985

Frequently asked questions

ロールバックリカバリにおけるドミノ効果とは何ですか？

プロセスが協調せずにチェックポイントを作成する場合、1つのプロセスをロールバックすると、依存するプロセスもロールバックせざるを得なくなり、計算全体にわたって連鎖的に逆方向に、場合によっては最初まで遡る可能性があります。協調型チェックポイントまたはメッセージロギングは、これを防ぐために使用されます。