Crash Recovery

// EACH LOG RECORD contains:
// LSN (Log Sequence Number): a monotonically increasing unique identifier for this record
//   - Used to determine ordering of log records
//   - Each page in the buffer pool stores the LSN of the most recent log record
//     that modified it (pageLSN)
// TransactionID: which transaction performed this operation
// Type: BEGIN, UPDATE, COMMIT, ABORT, CHECKPOINT, COMPENSATION (CLR)
// PageID: which database page was modified (for UPDATE records)
// Offset: byte offset within the page where the modification starts
// Before Image (UNDO info): the value BEFORE the modification (for UNDO)
// After Image (REDO info): the value AFTER the modification (for REDO)
// PrevLSN: the LSN of the previous log record for this same transaction
//   - Forms a backward-linked list of all records for one transaction
//   - Used during UNDO to find the previous action for this transaction

// EXAMPLE LOG SEQUENCE:
// LSN  | TxnID | Type   | PageID | Before      | After       | PrevLSN
// -----+-------+--------+--------+-------------+-------------+--------
// 1000 | T1    | BEGIN  | -      | -           | -           | NULL
// 1010 | T1    | UPDATE | P5     | balance=5000| balance=4500| 1000
// 1020 | T2    | BEGIN  | -      | -           | -           | NULL
// 1030 | T2    | UPDATE | P7     | balance=2000| balance=2500| 1020
// 1040 | T1    | UPDATE | P6     | qty=100     | qty=99      | 1010
// 1050 | T1    | COMMIT | -      | -           | -           | 1040
// 1060 | T2    | UPDATE | P8     | price=280   | price=300   | 1030
// 1070 | SERVER CRASHES HERE
// T1 is committed (LSN 1050 is in log)
// T2 is active (no COMMIT record)

// ON RESTART:
// Recovery reads the log from the last checkpoint
// REDO: replay LSN 1010 (T1 update P5) — bring P5 to balance=4500
//       replay LSN 1030 (T2 update P7) — bring P7 to balance=2500
//       replay LSN 1040 (T1 update P6) — bring P6 to qty=99
//       skip LSN 1050 (T1 COMMIT) — no data change
//       replay LSN 1060 (T2 update P8) — bring P8 to price=300
// UNDO: T2 has no COMMIT → undo all T2 changes in REVERSE order
//       undo LSN 1060: restore P8.price from 300 → 280
//       undo LSN 1030: restore P7.balance from 2500 → 2000
// FINAL STATE: T1 committed correctly, T2 fully rolled back ✓

// REDO RULE for each log record with LSN = L and PageID = P:
//   IF page[P].pageLSN >= L:
//       SKIP — this change is already reflected in page P on disk
//   ELSE:
//       APPLY the change — write the after-image to page P
//       Set page[P].pageLSN = L

// WHY THIS IS SAFE AND NECESSARY:
// Consider: T1 commits at LSN 1050. Page P5 is eventually flushed to disk.
// The flush writes pageLSN=1010 into the page header on disk.
// Server crashes. Recovery starts.
// Log record LSN=1010 says: update P5 balance from 5000 to 4500.
// Check: pageLSN of P5 on disk = 1010 >= 1010 → SKIP
// The change is already on disk. No need to redo it.

// Now consider: T1 commits at LSN 1050. Page P6 was NEVER flushed to disk.
// pageLSN of P6 on disk = 0 (old value, pre-T1).
// Log record LSN=1040 says: update P6 qty from 100 to 99.
// Check: pageLSN of P6 on disk = 0 < 1040 → APPLY
// Write qty=99 to P6. Set pageLSN=1040.
// The change is now reflected on disk.

// IDEMPOTENCY: if recovery crashes mid-way and restarts again,
// it will re-read the same log records and re-check pageLSN.
// Records already applied have pageLSN ≥ their LSN → skip.
// Recovery is safe to run multiple times — converges to correct state.

// IN POSTGRESQL:
-- Check WAL configuration:
SHOW wal_level;              -- minimal, replica, logical
SHOW wal_buffers;            -- WAL buffer size in memory before flush
SHOW synchronous_commit;     -- when WAL is flushed relative to COMMIT
SHOW wal_writer_delay;       -- how often background WAL writer flushes
-- View current WAL LSN:
SELECT pg_current_wal_lsn();
-- View WAL file location:
SELECT pg_walfile_name(pg_current_wal_lsn());

// CHECKPOINT LOG RECORD contains:
// 1. Transaction Table (ATT — Active Transaction Table):
//    List of all transactions active at checkpoint time
//    For each active transaction:
//      - TransactionID
//      - Status (running, committed but not yet flushed)
//      - lastLSN: the LSN of the most recent log record for this transaction
//    Purpose: during recovery, these are the transactions that MIGHT need UNDO

// 2. Dirty Page Table (DPT):
//    List of all pages currently in buffer pool that are dirty
//    For each dirty page:
//      - PageID
//      - recLSN: the LSN of the FIRST log record that made this page dirty
//                (the minimum LSN we need to replay to bring this page up to date)
//    Purpose: tells recovery the earliest point in the log it needs to start REDO from

// EXAMPLE CHECKPOINT RECORD:
// BEGIN_CHECKPOINT at LSN 2000
// ATT = {T2: lastLSN=1060, T3: lastLSN=1900}  (T1 already committed)
// DPT = {P5: recLSN=1010, P7: recLSN=1030, P8: recLSN=1060, P9: recLSN=1800}
// END_CHECKPOINT at LSN 2010

// MEANING:
// recLSN of P5 = 1010: to bring P5 to current state, replay from LSN 1010
// The earliest recLSN across all dirty pages = 1010 = "redo_lsn"
// Recovery only needs to replay from LSN 1010 onwards
// All log records before LSN 1010 are irrelevant — their pages are on disk

// POSTGRESQL CHECKPOINT:
-- Force a checkpoint:
CHECKPOINT;

-- Monitor checkpoint activity:
SELECT checkpoints_timed, checkpoints_req, buffers_checkpoint,
       checkpoint_write_time, checkpoint_sync_time
FROM pg_stat_bgwriter;

-- Configuration:
SHOW checkpoint_timeout;          -- max time between checkpoints (default: 5min)
SHOW max_wal_size;                -- trigger checkpoint if WAL exceeds this (default: 1GB)
SHOW checkpoint_completion_target; -- spread writes over this fraction of interval (default: 0.9)

// INITIAL STATE:
// Page P1: A = 100 (balance account A)
// Page P2: B = 200 (balance account B)
// Page P3: C = 300 (balance account C)

// TRANSACTIONS:
// T1: Transfer 50 from A to B (T1 commits before crash)
// T2: Transfer 30 from B to C (T2 is active at crash)

// COMPLETE WAL LOG BEFORE CRASH:
// LSN  | TxnID | Type       | PageID | Before | After | PrevLSN
// -----+-------+------------+--------+--------+-------+--------
// 1000 | T1    | BEGIN      | -      | -      | -     | NULL
// 1010 | T1    | UPDATE P1  | P1     | A=100  | A=50  | 1000
// 1020 | T1    | UPDATE P2  | P2     | B=200  | B=250 | 1010
// 1030 | T1    | COMMIT     | -      | -      | -     | 1020
// [CHECKPOINT at LSN 1040]
//   ATT = {} (T1 committed, no active transactions)
//   DPT = {P1: recLSN=1010, P2: recLSN=1020}
//   (P1 and P2 still dirty — not yet flushed to disk)
// 1050 | T2    | BEGIN      | -      | -      | -     | NULL
// 1060 | T2    | UPDATE P2  | P2     | B=250  | B=220 | 1050
// 1070 | T2    | UPDATE P3  | P3     | C=300  | C=330 | 1060
// [SERVER CRASHES at this point — T2 never commits]

// ON DISK AT CRASH TIME:
// P1: A=100  (pageLSN=0, never flushed — still has original value!)
// P2: B=200  (pageLSN=0, never flushed — still has original value!)
// P3: C=300  (pageLSN=0, never flushed — still has original value!)

// ─────────────────────────────────────────────────────────────────
// PHASE 1: ANALYSIS (start from last checkpoint at LSN 1040)
// ─────────────────────────────────────────────────────────────────
// Start with checkpoint info:
//   ATT = {} (from checkpoint)
//   DPT = {P1: recLSN=1010, P2: recLSN=1020} (from checkpoint)

// Scan log forward from LSN 1040:
// LSN 1050 — T2 BEGIN: add T2 to ATT: ATT = {T2: status=active, lastLSN=1050}
// LSN 1060 — T2 UPDATE P2: update ATT: T2.lastLSN=1060
//             P2 already in DPT → no change to DPT
// LSN 1070 — T2 UPDATE P3: update ATT: T2.lastLSN=1070
//             P3 NOT in DPT → add: DPT[P3] = recLSN=1070

// END OF ANALYSIS:
// ATT = {T2: lastLSN=1070}  ← T2 is the "loser" (no commit)
// DPT = {P1: recLSN=1010, P2: recLSN=1020, P3: recLSN=1070}
// redo_lsn = min(recLSN in DPT) = min(1010, 1020, 1070) = 1010

// ─────────────────────────────────────────────────────────────────
// PHASE 2: REDO (start from redo_lsn = 1010)
// ─────────────────────────────────────────────────────────────────
// Process LSN 1010: UPDATE P1, A: 100→50
//   Is P1 in DPT? YES (recLSN=1010 ≤ 1010)
//   pageLSN of P1 on disk = 0 < 1010 → APPLY
//   Write A=50 to P1. P1.pageLSN = 1010.

// Process LSN 1020: UPDATE P2, B: 200→250
//   Is P2 in DPT? YES (recLSN=1020 ≤ 1020)
//   pageLSN of P2 on disk = 0 < 1020 → APPLY
//   Write B=250 to P2. P2.pageLSN = 1020.

// Process LSN 1030: T1 COMMIT — no data change, skip

// Process LSN 1040: CHECKPOINT — no data change, skip

// Process LSN 1050: T2 BEGIN — no data change, skip

// Process LSN 1060: UPDATE P2, B: 250→220
//   Is P2 in DPT? YES (recLSN=1020 ≤ 1060)
//   pageLSN of P2 = 1020 < 1060 → APPLY
//   Write B=220 to P2. P2.pageLSN = 1060.

// Process LSN 1070: UPDATE P3, C: 300→330
//   Is P3 in DPT? YES (recLSN=1070 ≤ 1070)
//   pageLSN of P3 = 0 < 1070 → APPLY
//   Write C=330 to P3. P3.pageLSN = 1070.

// END OF REDO:
// P1: A=50  (T1's change, committed ✓)
// P2: B=220 (T1 set 250, T2 set 220 — T2 uncommitted, will be undone)
// P3: C=330 (T2's change, uncommitted, will be undone)
// This is exactly the pre-crash state.

// ─────────────────────────────────────────────────────────────────
// PHASE 3: UNDO (undo T2 — the loser)
// ─────────────────────────────────────────────────────────────────
// T2.lastLSN = 1070. Process in reverse order via PrevLSN links.

// UNDO LSN 1070: T2 UPDATE P3, C: 300→330
//   Apply UNDO: write before-image C=300 to P3
//   Write CLR to log: LSN=1080, T2, CLR for LSN 1070, P3, C=300, undoNextLSN=1060
//   (CLR records the undo so if recovery crashes again, we know to skip LSN 1070)
//   P3: C=300 ✓ (T2's change undone)

// UNDO LSN 1060: T2 UPDATE P2, B: 250→220
//   Apply UNDO: write before-image B=250 to P2
//   Write CLR: LSN=1090, T2, CLR for LSN 1060, P2, B=250, undoNextLSN=1050
//   P2: B=250 ✓ (T2's change undone, T1's committed change preserved)

// UNDO LSN 1050: T2 BEGIN — nothing to undo
//   Write ABORT record to log: LSN=1100, T2 ABORT
//   Remove T2 from ATT.

// FINAL RECOVERED STATE:
// P1: A=50   ← T1's transfer from A (COMMITTED) ✓
// P2: B=250  ← T1's transfer to B (COMMITTED) ✓
// P3: C=300  ← T2's update undone (T2 ROLLED BACK) ✓
//
// ACID PROPERTIES RESTORED:
// Atomicity: T2 fully rolled back — no partial effect
// Durability: T1's committed changes fully present
// The database is consistent.

// SHADOW PAGING MECHANISM:

// INITIAL STATE: a single page table points to all database pages
// Page Table: P1→disk_loc_A, P2→disk_loc_B, P3→disk_loc_C

// TRANSACTION T1 begins modifying pages:

// STEP 1: Copy the page table → creates "shadow page table"
// Shadow Table: P1→disk_loc_A, P2→disk_loc_B, P3→disk_loc_C (unchanged copy)

// STEP 2: T1 updates P1 — write new P1 to a NEW disk location (disk_loc_D)
// Current Table: P1→disk_loc_D, P2→disk_loc_B, P3→disk_loc_C
// Shadow Table: P1→disk_loc_A, P2→disk_loc_B, P3→disk_loc_C (unchanged)

// STEP 3: T1 updates P2 — write new P2 to disk_loc_E
// Current Table: P1→disk_loc_D, P2→disk_loc_E, P3→disk_loc_C
// Shadow Table: P1→disk_loc_A, P2→disk_loc_B, P3→disk_loc_C (unchanged)

// TO COMMIT: atomically swap current page table for shadow page table
// Write current page table to disk (single atomic write)
// The swap is the commit — either the new table is the active one, or the old one is
// On disk, the shadow table is the fallback

// ROLLBACK: trivial — just discard the current page table
// The shadow table still points to the original, unmodified pages
// Restore: discard current table, shadow table becomes the page table again

// CRASH RECOVERY:
// If crash before commit: shadow table is still active → pre-transaction state ✓
// If crash after commit (atomic swap): new table is active → post-transaction state ✓
// No log needed, no replay, no UNDO/REDO phases

// WHY SHADOW PAGING IS NOT USED IN MOST PRODUCTION DATABASES:
// 1. FRAGMENTATION: each transaction writes pages to new locations
//    Related pages become physically scattered across disk
//    Sequential scans lose their performance advantage (random I/O)
//    Periodically must compact/reorganise the entire database

// 2. PAGE TABLE COST: copying the entire page table for each transaction is expensive
//    For a large database with millions of pages, the page table is large

// 3. NO CONCURRENT TRANSACTIONS: shadow paging inherently supports only one
//    write transaction at a time (only one "current" and one "shadow" table)
//    Multi-transaction concurrency requires complex extensions

// USED IN: SQLite (simplified variant), some research databases
// NOT USED IN: PostgreSQL, MySQL, Oracle, SQL Server (all use WAL)

-- ─────────────────────────────────────────────────────────────────
-- STEP 1: Configure continuous WAL archiving (in postgresql.conf)
-- ─────────────────────────────────────────────────────────────────
wal_level = replica         -- must be replica or logical for archiving
archive_mode = on           -- enable WAL archiving
archive_command = 'cp %p /mnt/wal-archive/%f'
-- %p = full path to WAL file on the primary
-- %f = filename of the WAL file
-- This copies each completed WAL segment to the archive location
-- In production: use cloud storage (S3, Azure Blob, GCS)
-- archive_command = 'aws s3 cp %p s3://my-wal-archive/%f'

-- ─────────────────────────────────────────────────────────────────
-- STEP 2: Take base backup (the starting point for PITR)
-- ─────────────────────────────────────────────────────────────────
-- Use pg_basebackup to take a consistent backup:
pg_basebackup -h localhost -U replication_user -D /backup/base -Ft -z -P
-- -Ft: tar format  -z: gzip compress  -P: show progress
-- The backup includes a backup_label file with the starting WAL LSN

-- ─────────────────────────────────────────────────────────────────
-- STEP 3: DISASTER SCENARIO — accidental table drop at 14:32:15
-- ─────────────────────────────────────────────────────────────────
-- DROP TABLE orders;  ← someone ran this at 14:32:15
-- Goal: recover to 14:32:00 (15 seconds before the drop)

-- ─────────────────────────────────────────────────────────────────
-- STEP 4: Restore base backup
-- ─────────────────────────────────────────────────────────────────
-- Stop the crashed/wrong PostgreSQL instance
-- Restore the base backup to the data directory:
rm -rf /var/lib/postgresql/data
tar -xzf /backup/base/base.tar.gz -C /var/lib/postgresql/data

-- ─────────────────────────────────────────────────────────────────
-- STEP 5: Configure recovery target
-- ─────────────────────────────────────────────────────────────────
-- Create recovery.conf (PostgreSQL 11 and earlier) or
-- use postgresql.conf + standby.signal (PostgreSQL 12+):

-- In postgresql.conf:
restore_command = 'cp /mnt/wal-archive/%f %p'
-- Tells PostgreSQL where to find archived WAL segments

recovery_target_time = '2024-03-15 14:32:00'
-- Stop replaying WAL at exactly this timestamp (before the DROP)

recovery_target_action = 'promote'
-- After reaching target: promote to a live primary (resume normal operation)

-- Create recovery signal file (PostgreSQL 12+):
touch /var/lib/postgresql/data/recovery.signal

-- ─────────────────────────────────────────────────────────────────
-- STEP 6: Start PostgreSQL — it replays WAL automatically
-- ─────────────────────────────────────────────────────────────────
-- PostgreSQL starts, finds recovery.signal
-- Restores WAL segments from archive one by one
-- Replays changes until 14:32:00
-- Stops, promotes to primary
-- orders table is restored as of 14:32:00 ✓

-- MONITOR RECOVERY PROGRESS:
SELECT pg_is_in_recovery();    -- true during recovery
SELECT pg_last_wal_replay_lsn(); -- current replay position
SELECT recovery_target_lsn, recovery_target_time FROM pg_control_recovery;

-- ON PRIMARY: postgresql.conf
wal_level = replica
max_wal_senders = 10      -- max concurrent standby connections
wal_keep_size = 1GB       -- keep this much WAL for slow standbys

-- ON PRIMARY: pg_hba.conf (allow replication connections)
host replication replication_user 10.0.1.0/24 md5

-- ON STANDBY: postgresql.conf
primary_conninfo = 'host=10.0.1.100 port=5432 user=replication_user'
-- Signal that this is a standby:
touch /var/lib/postgresql/data/standby.signal

-- MONITOR REPLICATION LAG (on primary):
SELECT
    client_addr,
    state,
    sent_lsn,
    write_lsn,
    flush_lsn,
    replay_lsn,
    pg_wal_lsn_diff(sent_lsn, replay_lsn) AS replication_lag_bytes,
    write_lag,
    flush_lag,
    replay_lag
FROM pg_stat_replication;

-- SYNCHRONOUS vs ASYNCHRONOUS REPLICATION:
-- Asynchronous (default): primary commits without waiting for standby
--   Pros: no performance impact on primary
--   Cons: if primary crashes, standby may be slightly behind (data loss window)
-- Synchronous: primary waits for standby to confirm WAL receipt before commit
--   Pros: zero data loss on primary failure (RPO = 0)
--   Cons: each commit is slower (must wait for network round-trip to standby)

-- Configure synchronous:
synchronous_standby_names = 'standby1'  -- wait for this standby to confirm