# クラッシュリカバリ ## 定義 クラッシュリカバリ(crash recovery)とは、データベースシステムがクラッシュ・電源断・ノード障害から回復し、コミット済みトランザクションの変更が確実に反映され、未コミットのトランザクションの変更が反映されない一貫性のある状態に復元するプロセスである。トランザクションの ACID 特性のうち「耐久性(Durability)」を、障害が発生した場合にも保証するための仕組みが復旧サブシステムである。(Source: [[@2014__ICDE__Rethinking Main Memory OLTP Recovery]]) **復旧の基本要件**: - クラッシュ前にコミットしたトランザクションの変更はすべてデータベースに反映される - クラッシュ時に実行中だった未コミットのトランザクションの変更は反映されない **復旧の起点**: - **WAL + チェックポイント方式**: ディスク上の最新チェックポイントから、WAL のログエントリを再適用(Redo)し、必要であれば未コミット変更を取り消す(Undo) - **コマンドロギング方式**: トランザクション整合性のあるスナップショット(チェックポイント)から、コマンドログに記録されたトランザクションを順番に再実行する ## WAL規約と黄金律からの導出(Saltzer & Kaashoek の教科書的整理) [[@2009__MITOCW__Principles of Computer System Design - Chapter 9 Atomicity - All-or-Nothing and Before-or-After]] は、WAL(write-ahead-log)規約を独立した工学的知恵としてではなく、**原子性の黄金律(golden rule of atomicity)**——唯一のコピーを決して書き換えるな——から導かれる帰結として提示する。ログは追記(append)であり黄金律を自然に満たすが、セル記憶へのインストールは上書きであり黄金律に反する。そこで両者の順序を「ログをインストールより先に記録せよ」という**WAL規約(write-ahead-log protocol)**として固定することで、クラッシュ時に復旧手続きがログだけを頼りにセル記憶を再構成できるようにする。CHANGEレコードは行為の識別子・redoアクション・undoアクションの3要素からなり、OUTCOMEレコードを記録した瞬間がそのアクションのコミット点になる。(Source: [[@2009__MITOCW__Principles of Computer System Design - Chapter 9 Atomicity - All-or-Nothing and Before-or-After]] §9.3.1–§9.3.2) 本書はさらに、インストールのタイミングをOUTCOMEレコードの前後どちらに寄せるかという設計選択が、リカバリ手続きの3種類を生み出すことを体系的に示す。(1) **undo/redo混在**: インストールのタイミングを規律しない一般形では、クラッシュ時に未完了だったアクション(loser)をundoし、コミット済みだが完了前だったアクション(winner)をredoする必要がある。(2) **ロールバックリカバリ(undo専用)**: すべてのインストールをOUTCOMEレコード記録前に完了させる規律を課せば、コミット済みアクションのインストールは既に完了しているとみなせるためredo走査そのものが不要になる。(3) **roll-forwardリカバリ(redo専用)**: 逆にすべてのインストールをOUTCOMEレコード後に行う規律を課せば、クラッシュ前にインストールは一切起きていないためundoが不要になる。**チェックポイント**は、係属中のアクション一覧をログへ書き出すことで、リカバリ時のログ走査範囲をチェックポイント以降に限定する補助機構として導入される。(Source: [[@2009__MITOCW__Principles of Computer System Design - Chapter 9 Atomicity - All-or-Nothing and Before-or-After]] §9.3.3–§9.3.5) ## 横断的知見 - **メインメモリ OLTP では復旧時間よりスループットが優先される**: Malviya+ 2014([[@2014__ICDE__Rethinking Main Memory OLTP Recovery]])は、コマンドロギングの復旧時間が生理ロギングより 1.5×〜5× 遅いことを示したが、本番 OLTP はレプリケーションにより単一ノード障害をマスクできるため、復旧速度よりも実行時スループットの方が重要であると結論した。障害は週 1 回以下の頻度であるという議論も論文に示されている。(Source: [[@2014__ICDE__Rethinking Main Memory OLTP Recovery]]) - **インデックス再構築はスナップショット復元と並行化できる**: VoltDB ではディスクスナップショットにインデックスを含まないため、復旧時にインデックスを再構築する必要がある。コマンドロギング・生理ロギングともに、インデックス再構築はスナップショット復元と並行して実行できる。(Source: [[@2014__ICDE__Rethinking Main Memory OLTP Recovery]]) - **生理ロギングの Redo フェーズは高度に並列化可能**: 異なるパーティションのログレコードは任意の順序で再適用できるため、コア数に比例してリニアスケールアップを達成する。コマンドロギングの再実行は直列(グローバル順序を守る必要がある)であり、並列化に制約がある。(Source: [[@2014__ICDE__Rethinking Main Memory OLTP Recovery]]) - **LLM 訓練チェックポイントとの類比**: データベースクラッシュリカバリは「スナップショット + ログ再適用」の構造を持ち、LLM 訓練の「チェックポイント + 勾配ステップの再実行」と同型の設計である。ただし意味論(commit/abort vs 最終損失収束)が異なる。(Source: [[@2014__ICDE__Rethinking Main Memory OLTP Recovery]], [[@2024__NSDI__MegaScale - Scaling Large Language Model Training to More Than 10,000 GPUs]]) - **クラウド分散ストレージへの Redo 処理移譲により、リカバリは「連続的なフォアグラウンド処理」として実行される**: 伝統的な ARIES ベースのリカバリはデータベースがオフライン中にチェックポイントからログを順次再適用する（直列・同期）。Aurora([[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]])はストレージ層が常時バックグラウンドで Redo を適用するため、クラッシュ発生時点でほぼ全 Redo が完了済みである。起動後は各 PG の読み込みクォーラムで VDL を特定してログを切り捨てる truncation のみで済む。結果として 100,000 書き込み/秒のクラッシュでも 10 秒以内に復旧。チェックポイント間隔の短縮というトレードオフは不要になる。(Source: [[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]]) - **リカバリ速度 vs スループットのトレードオフはアーキテクチャ設計で変化する**: Malviya 2014([[@2014__ICDE__Rethinking Main Memory OLTP Recovery]])ではコマンドロギングがリカバリ時間 1.5〜5 倍増と引き換えに実行時スループットを向上させた。Aurora はリカバリをフォアグラウンド処理に分散させることで、実行時スループット向上とリカバリ高速化の両方を同時に達成した。これはトレードオフの「軸」が設計選択によって変わることを示す。(Source: [[@2014__ICDE__Rethinking Main Memory OLTP Recovery]], [[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]]) - **エポックベースフェンシングによりクラッシュリカバリ後の「ゾンビインスタンス」問題を解決できる**: 伝統的な分散システムでは、クラッシュしたノードが再起動中に古い接続でストレージにアクセスし続ける「ゾンビ問題」をリース有効期限で対処する。Aurora 2018([[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]])はリース待ちの代わりにボリュームエポックをインクリメントし、storage metadata service の書き込みクォーラムに記録する。古いエポックからのリクエストはストレージノードに即座に拒否される（「鍵を取り替える」）。これにより最大 30 秒かかりうるリース有効期限待ちが不要になり、フェイルオーバー時間が短縮される。(Source: [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]) - **Undo はリカバリ後にユーザー活動と並行して実行できる**: Aurora のクラッシュリカバリで行うのは「VCL の再計算 + ラグドエッジの truncation」のみ。アクティブトランザクションの Undo はデータベースを開いた後にバックグラウンドで実行する。これは伝統的な ARIES ベースリカバリ（Redo → Undo の直列処理）と異なり、ユーザー向けサービス再開までの時間をさらに短縮する。(Source: [[@2018__SIGMOD__Amazon Aurora - On Avoiding Distributed Consensus for I Os, Commits, and Membership Changes]]) - **詳説 データベースが示す教科書的な「WAL + ファジーチェックポイント + ARIES 3フェーズ」モデルは、Aurora が根本的に置き換えた対象そのものである**: 詳説 データベース5章§5.2.1・§5.2.4は、復旧の起点をファジーチェックポイント(begin_checkpoint〜end_checkpointで区切られた非同期フラッシュ)に置き、クラッシュ後に分析→redo→undoという3フェーズを直列に実行するという、Mohan1992由来の標準モデルを述べる。既存知見が示す Aurora のリカバリ革新(ストレージ層が常時バックグラウンドで Redo を適用し、起動後は VDL 算定と truncation のみで済む)は、この教科書的な直列3フェーズモデルの何を・なぜ置き換えたのかを、この標準モデルとの対比で初めて具体的に説明できる。教科書(基準点)と論文(革新)を突き合わせることで、Aurora が「リカバリの高速化」ではなく「リカバリという概念そのものの分解(Redoの継続的実行への移動)」を行ったことが明確になる。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] §5.2.1, §5.2.4, [[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]]) - **steal/force ポリシーという教科書の語彙で、Malviya 2014 のコマンドロギングと ARIES 生理ロギングの復旧速度差を再解釈できる**: 詳説 データベース5章§5.2.3は steal(未コミットページのフラッシュ許容)と no-steal(許容しない)、force(コミット前に全変更ページをフラッシュ)と no-force(許容しない)という2軸4象限を定義し、no-stealならredoのみでのリカバリが可能になると説明する。既存知見が示す「生理ロギングの Redo フェーズはパーティション間で任意順に再適用でき高度に並列化可能」という性質は、この no-steal 的な性質(古いコピーがディスク上のページに残っているためredoのみで復元できる)の帰結として理解でき、コマンドロギングの復旧が直列(グローバル順序を要する)なのは、コマンドログがトランザクションの再実行という論理操作そのものであり、redoのみでの独立適用という no-steal の恩恵を受けられない設計だからだと説明できる。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] §5.2.3, [[@2014__ICDE__Rethinking Main Memory OLTP Recovery]]) - **Saltzer & Kaashoek の undo専用(ロールバックリカバリ)・redo専用(roll-forwardリカバリ)という2分類は、詳説 データベースの steal/force 2軸4象限のうち特定の2象限に厳密に対応する**: Saltzer & Kaashoek Ch.9 §9.3.4は、全インストールをOUTCOMEレコード記録**前**に完了させる規律(ロールバックリカバリ)は undo のみで済み、全インストールをOUTCOMEレコード記録**後**に行う規律(roll-forwardリカバリ)は redo のみで済むと導く。前者は「コミット前にインストールが起こりうる(steal的)が、コミット時点までに全インストールが完了している(force的)」という steal+force 象限に、後者は「コミット前にはインストールが一切起きない(no-steal的)が、コミット後のインストールタイミングは規律しない(no-force的)」という no-steal+no-force 象限に、それぞれ過不足なく対応する。詳説 データベースが定義する steal/force という2軸4象限の語彙は、Saltzer & Kaashoek が具体的な規律として個別に導出した2つのリカバリ方式を統一的に分類する上位概念として機能し、逆に Saltzer & Kaashoek の導出は steal/force の各象限がなぜそのリカバリ動作(undo要/不要・redo要/不要)を要求するのかを、具体的なプロトコル設計から遡って説明する。(Source: [[@2009__MITOCW__Principles of Computer System Design - Chapter 9 Atomicity - All-or-Nothing and Before-or-After]] §9.3.4, [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] §5.2.3) - **Saltzer & Kaashoek の「winners/losers」という語彙は、[[ARIES]]・詳説 データベースの分析(analysis)フェーズが特定する「損失トランザクション集合」と同一の役割を果たす**: 本書のRECOVER手続き(§9.3.4)はログを後方走査してcompletedでないアクションを losers として収集し、それらのCHANGEレコードをundoする。これは ARIES の3フェーズ(analysis→redo→undo)のうち analysis フェーズがロス確定を行う設計と機能的に等価だが、Saltzer & Kaashoek は analysis を独立フェーズとして切り出さず、undoスキャンに統合している点が異なる。両者を比較すると、ARIES がフェーズを分離するのはチェックポイント以降のダーティページテーブル復元という追加要件のためであり、Saltzer & Kaashoek の簡潔な2パス構成はチェックポイントを持たない最小構成での説明として補完関係にある。(Source: [[@2009__MITOCW__Principles of Computer System Design - Chapter 9 Atomicity - All-or-Nothing and Before-or-After]] §9.3.4, [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] §5.2.4) - **Lustre の Version-Based Recovery (VBR) が inode ごとに保持するバージョン番号は、ARIES の PageLSN と同型の「オブジェクトに刻まれた更新履歴の目印」だが、判定の意味が異なる**: ARIES は PageLSN とログレコードの LSN を比較し、PageLSN が既に新しければそのログレコードの redo を skip する(=「既に適用済みか」の判定)。Lustre VBR は、リクエストが運ぶ pre-operation version と対象 inode の現在の version が一致するかだけを見て、一致すれば「このリクエストは当該オブジェクトに対して次に適用されるべきものである」と判定しリプレイを進める(ch.38 §38.2.7, §38.4)。前者は「redo 済みか否か」の冪等性判定、後者は「リプレイシーケンスの整合性(欠落クライアントによるギャップをまたいでも安全か)」の判定であり、単調な per-object バージョンという同じ道具を、単一ログの冪等リプレイと、分散クライアント群のリプレイ順序整合性検証という異なる目的に転用している。(Source: [[@2026__Whamcloud__Lustre Operations Manual - Chapter 38 Lustre File System Recovery]] §38.2.7, §38.4, [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] §5.2.3, [[@2009__MITOCW__Principles of Computer System Design - Chapter 9 Atomicity - All-or-Nothing and Before-or-After]] §9.3.4) - **Lustre のリカバリは steal/force の語彙で言えば no-force(サーバはディスクコミットを待たずに応答する)を常用しており、その代償(未コミット状態がクライアント側にしか記憶されない)をクライアントの再送・リプレイという分散した仕組みで埋め戻している**: 詳説 データベースの steal/force 分類(既存知見参照)は単一ノードの WAL/ページキャッシュ内で完結する設計選択だが、Lustre では「コミット前に応答してよい」という no-force 的な選択の結果、クラッシュ後にサーバのディスクだけを見ても失われた更新を復元できず、生きているクライアントが保持するリプレイリストの参加が復旧の必須条件になる(ch.38 §38 要約, §38.2.4)。Commit on Share (COS) は、依存関係のある操作だけを選択的に force してからでないと応答しない仕組みであり、全操作を一律 force する古典的な force ポリシーに対して、依存関係が生じた箇所だけをピンポイントで force する縮小版として位置づけられる(ch.38 §38.5.1)。(Source: [[@2026__Whamcloud__Lustre Operations Manual - Chapter 38 Lustre File System Recovery]] §38.1, §38.2.4, §38.5.1, [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] §5.2.3) ## 未解決の問い - メインメモリデータベースにおいて、レプリケーション(高可用性)とコマンドロギング(耐久性)の組み合わせで、単一ノード障害と全ノード障害(電源断等)それぞれに対してどの程度のデータロスウィンドウが生じるか？ - コマンドロギングの復旧時間はトランザクション再実行速度に依存するが、復旧速度と実行時スループットのトレードオフはグループコミット間隔のチューニングでどの程度調整可能か？ - スナップショット頻度(180 秒固定)を動的に調整した場合、障害からの復旧時間分布はどう変化するか？ - Aurora の VDL 算定と truncation はリカバリ時に読み込みクォーラムへのネットワーク通信を必要とするが、AZ 障害直後のクォーラム再確立を含めると実際の 10 秒以内復旧はどのような条件で成立するか？ - 詳説 データベースのファジーチェックポイント(begin_checkpoint/end_checkpoint)は非同期フラッシュを許容する点で Aurora の連続的 Redo に思想的に近いが、教科書の記述はあくまで「起動時の作業量削減」を目的とし、Aurora のような「クラッシュ発生前にほぼ全 Redo を完了させておく」という発想までは踏み込まない。ファジーチェックポイントの間隔を極限まで短縮した場合、Aurora 的な連続 Redo にどこまで近づけるか、その場合のオーバーヘッドは何か。 - Saltzer & Kaashoek の undo専用/redo専用の2分類が steal/force の特定2象限に対応すること(本節参照)を確認した。残る2象限(no-steal+force=undo・redoともに不要、steal+no-force=undo・redoともに必要)は本書のどの記述に対応するか。前者はインメモリDBの単純なケース(§9.3.3、Figure 9.22)に近いと見られるが、明示的な対応は本文にない。後者(ARIES の一般形)への言及は本書にあるか、原文の再確認が必要。 - Saltzer & Kaashoek の「winners/losers」語彙とARIESのanalysisフェーズの機能的対応(本節参照)を踏まえ、Saltzer & Kaashoek の2パス構成にチェックポイントを追加した場合(§9.3.5で簡潔に触れられる)、ARIESのanalysisフェーズが担うダーティページテーブル復元と同等の機構が必要になるか、それとも本書の設計はチェックポイント併用時でも analysis フェーズの分離を要さないか。 - Lustre の VBR はバージョン不一致を検知した時点でリクエスト単位の evict にとどめるが、ARIES/WAL の PageLSN skip 判定は単一ノードのログ内で完結するため「一部だけリプレイ不能」という状態が原理的に生じない。分散システムがログ(サーバ)とキャッシュ(クライアント)を分離して持つことで生まれるこの部分的リプレイ失敗という現象は、単一ノードの steal/force 分類のどの拡張として定式化できるか。 - Lustre の Commit on Share は依存関係を検知した箇所だけを force する選択的ポリシーだが、その依存関係検出(VBR のバージョン比較を利用すると推測される)の具体的な実装原理は原本(ch.38 §38.5)には明記されていない。ARIES のようなログベースの依存追跡と同じ機構を使っているのか、独立した仕組みかは要確認。 ## 関連 - [[Write-Ahead Logging (WAL)]] — 復旧の基本手法 - [[ARIES]] — 生理ロギングに基づく復旧アルゴリズム - [[コマンドロギング]] — 軽量な代替復旧手法 - [[チェックポイント]] — 復旧の出発点 - [[メインメモリデータベース]] — 復旧設計が特に重要な環境 - [[フォールトトレランス]] — より広い障害許容の文脈 - [[コンピュートストレージ分離]] — Redo をストレージ層に移す Aurora の設計文脈 - [[クォーラムベースレプリケーション]] — Aurora のリカバリが依拠するストレージ層クォーラム - [[バージョン履歴]] — セル記憶の上書きを避ける、ログとは異なる全か無かの原子性の実現方式 - [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] — WAL+ファジーチェックポイント+ARIES 3フェーズという標準的復旧モデルの教科書的定義 - [[@2009__MITOCW__Principles of Computer System Design - Chapter 9 Atomicity - All-or-Nothing and Before-or-After]] — 原子性の黄金律からのWAL規約の導出、undo専用/redo専用リカバリの体系的分類 - [[@2026__Whamcloud__Lustre Operations Manual - Chapter 38 Lustre File System Recovery]] — 分散ファイルシステムにおけるクライアント参加型リプレイ・VBR・Commit on Share・Imperative Recovery ## 出典 - [[@2014__ICDE__Rethinking Main Memory OLTP Recovery]](コマンドロギングと生理ロギングの復旧時間比較) - [[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]](ストレージ層での継続的 Redo・VDL 算定・10 秒以内リカバリ) - [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]](§5.2.1 ファジーチェックポイント、§5.2.3 steal/forceポリシー、§5.2.4 ARIES3フェーズ復旧の標準モデル) - Jerome H. Saltzer and M. Frans Kaashoek, *Principles of Computer System Design: An Introduction*, Version 5.0, 2009, Chapter 9 §9.3.1–9.3.5. MIT OpenCourseWare, CC BY-NC-SA 3.0 US.(原子性の黄金律・WAL規約・undo専用/redo専用リカバリ・チェックポイント) - [[@2026__Whamcloud__Lustre Operations Manual - Chapter 38 Lustre File System Recovery]](*Lustre Software Release 2.x Operations Manual*, Whamcloud, built 2026-05-26, Chapter 38。VBR・Commit on Share・Imperative Recovery)