Point-in-time recovery

Deep dive

How it works

Parts:

• base backup — consistent copy of the data plus the log position (LSN) it starts from (volume snapshot, or an online copy that replay makes consistent)
• log archive — completed segments of the write-ahead log (WAL, binlog, redo) copied to separate storage in LSN order
• catalog — backups with start/stop time and LSN, and the timelines that exist
• recovery target — stop condition: time, transaction id, LSN or named restore point
• timeline — id of one branch of history, kept in file names or a history file

Operations:

1. Backup: take a base backup and record its start LSN and stop time. PostgreSQL's pg_backup_stop waits until the segments the backup needs are archived.
2. Archive: copy each completed segment off the machine, never overwrite an existing file, alert when archiving stalls. Quiet systems fill segments slowly, so force a switch every minute or so.
3. Choose: the newest base backup whose stop time is before the target. A backup still running at T cannot recover to T.
4. Replay: copy the backup, fetch segments from its start LSN, verify each, apply records in order, stop at the first record past the target.
5. Check, then promote: query the paused result; if wrong, restart from the same backup with another target.
6. Branch: open as timeline n+1; new writes go there and the old future stays in the archive.

 base backup B1      B2 (newest before T)                  T      "now"
 ──────┬──────────────┬────────────────────────────────────┬───────┬──────▶ time
       │ log archive: ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ (all in LSN order)
       │                                                    ╰ replay stops here
 timeline 1 ───────────────────────────────────────────────────────────▶ (old future kept)
 timeline 2                                  ╰─ new writes branch here ─▶

PostgreSQL targets: recovery_target_time, _xid, _lsn, _name (made with pg_create_restore_point()) and immediate; at most one may be set. LSN, xid and named points are exact, a time is an approximation: create a restore point before every risky deploy.

Code

use std::collections::BTreeMap;
use std::time::Instant;

type State = BTreeMap<String, String>;

#[derive(Clone)]
pub enum Op { Put(String, String), Del(String) }

#[derive(Clone)]
pub struct Rec { pub lsn: u64, pub ts: u64, pub op: Op } // ts: any monotone clock, here ms

pub struct Backup { pub lsn: u64, pub ts: u64, pub state: State } // state as of record `lsn`

#[derive(Debug, PartialEq)]
pub enum RecoverError { NoBackup, Gap { have_through: u64, missing: u64 } }

#[derive(Default)]
pub struct Db {
    pub state: State,
    pub timeline: u32,
    pub last_lsn: u64,
    pub archive: Vec<Rec>, // stands in for WAL segments shipped to separate storage
    pub backups: Vec<Backup>,
}

fn apply(s: &mut State, op: &Op) {
    match op {
        Op::Put(k, v) => { s.insert(k.clone(), v.clone()); }
        Op::Del(k) => { s.remove(k); }
    }
}

impl Db {
    pub fn exec(&mut self, ts: u64, op: Op) -> u64 {
        self.last_lsn += 1;
        apply(&mut self.state, &op);
        self.archive.push(Rec { lsn: self.last_lsn, ts, op });
        self.last_lsn
    }

    /// Consistent copy of the state plus the log position it corresponds to.
    pub fn take_base_backup(&mut self, ts: u64) {
        self.backups.push(Backup { lsn: self.last_lsn, ts, state: self.state.clone() });
    }

    /// State as of `target_ts`, opened as a new timeline; `self` stays untouched.
    pub fn recover(&self, target_ts: u64) -> Result<Db, RecoverError> {
        let b = self.backups.iter().rev().find(|b| b.ts <= target_ts).ok_or(RecoverError::NoBackup)?;
        let mut db = Db { state: b.state.clone(), last_lsn: b.lsn, timeline: self.timeline + 1, ..Db::default() };
        let start = self.archive.partition_point(|r| r.lsn <= b.lsn); // archive is sorted by lsn
        for r in &self.archive[start..] {
            if r.lsn != db.last_lsn + 1 {
                return Err(RecoverError::Gap { have_through: db.last_lsn, missing: db.last_lsn + 1 });
            }
            if r.ts > target_ts { break; } // recovery target reached
            apply(&mut db.state, &r.op);
            db.last_lsn = r.lsn;
        }
        Ok(db)
    }
}

fn put(k: &str, v: &str) -> Op { Op::Put(k.into(), v.into()) }

fn main() {
    let mut db = Db::default();
    db.exec(10, put("alice", "100"));
    db.take_base_backup(15);
    db.exec(20, put("bob", "50"));
    db.exec(30, put("alice", "120"));
    db.exec(40, Op::Del("bob".into())); // the "bad deploy" at t=40
    db.exec(50, put("carol", "7"));

    let before = db.recover(39).unwrap(); // just before the bad delete
    assert_eq!(before.state.get("bob").map(String::as_str), Some("50"));
    assert_eq!(before.state.get("alice").map(String::as_str), Some("120"));
    assert_eq!(before.timeline, 1); // new branch; the old future is untouched
    assert_eq!(db.recover(u64::MAX).unwrap().state, db.state); // target "now" == live state
    assert_eq!(db.recover(5).err(), Some(RecoverError::NoBackup)); // older than the oldest backup

    db.archive.remove(2); // lose one archived record (a missing segment)
    assert_eq!(db.recover(u64::MAX).err(), Some(RecoverError::Gap { have_through: 2, missing: 3 }));

    let mut big = Db::default();
    big.take_base_backup(0);
    for i in 0..1_000_000u64 { big.exec(i, put(&format!("k{}", i % 10_000), "v")); }
    let t = Instant::now();
    let r = big.recover(u64::MAX).unwrap();
    println!("replayed {} records in {:?}", r.last_lsn, t.elapsed());
}

recover requires consecutive LSNs, so a lost segment is an error, not silently wrong data. The result is a new Db on timeline + 1; the live one is untouched. A real system also records the archive's final LSN, or a missing tail looks like a shorter log.

Complexity and constants

• Backup: O(data) per full backup, O(changed blocks) for incremental ones (pg_basebackup --incremental needs WAL summaries). Archive: sequential writes.
• Replay here (in memory): about 10 million records/s, measured on this Mac (Apple M4 Pro): 1 M Put records over 10 k keys in 95-98 ms, one String allocation per record. Real replay is bound by random page reads, so PostgreSQL prefetches blocks during recovery (recovery_prefetch, default try).
• RTO = base-backup copy time + log bytes since the backup / replay speed. RPO = age of the last archived record.

Efficiency

• Cost: one recovery moves one base backup plus the log up to the target: bound by network or object-store bandwidth for the copy and by random page I/O for replay (in-memory replay above: about 10 M records/s, measured on this Mac (Apple M4 Pro)). Standing cost: storage for kept backups and all log in the retention window, plus continuous upload.
• Levers:
  • more frequent, incremental or differential base backups — shorter replay, lower RTO, more storage — large databases with high write rates
  • short archive interval (PostgreSQL docs: archive_timeout of "a minute or so" is reasonable) or log streaming — lower RPO — when minutes of loss hurt
  • parallel segment fetch and block prefetch — lower RTO — Litestream downloads 8 files in parallel by default
  • compress log and backups — less storage and transfer — cold archives
• Naive → standard → state of the art:
  • nightly logical dump · RPO up to a day, indexes rebuilt on restore
  • base backups plus log archive · RPO = archive lag (seconds to minutes), RTO = copy + replay
  • incremental backups, parallel fetch, scheduled test restores into a scratch instance · RTO bounded by plan, backups proven

Implementation notes

• Verify by restoring. pg_verifybackup checks a backup against its manifest, including that the needed WAL is present and parseable, yet its docs say to still do test restores. Restore into a scratch instance on a schedule, run smoke queries, alert on failure.
• Checksum and scrub segments (CRC32C) and re-read the archive periodically (data scrubbing).
• Gaps. Number segments continuously and compare the archive with the catalog. Expire log only when no kept backup needs it: pgBackRest warns that PITR works only on a continuous WAL stream.
• Retention "any time in the last N days" means keeping the newest backup older than N days plus all log after it.
• Time targets. PostgreSQL rejects zone abbreviations and prefers a numeric UTC offset or a full zone name (Europe/Helsinki). Convert incident times to UTC yourself. recovery_target_inclusive defaults to on, so the transaction at exactly T is kept; turn it off for "just before", or use the LSN. The default recovery_target_action = pause lets you query before promoting.
• MySQL replays binary logs with mysqlbinlog; the manual prefers --start-position/--stop-position over datetimes, which risk missing events.

Pitfalls

• A backup that never restored: wrong key, missing WAL, bad permissions, found during the incident.
• Silent archive stall: unarchived WAL piles up on the primary until its disk fills. Monitor lag.
• Restoring over the live instance. Restore to a new instance, compare, then switch or copy the lost rows back (chunked backfill).
• Same LSN, different history. After a branch, two timelines hold different records at one LSN; identify records by (timeline, LSN).
• Logical dumps are not PITR: PostgreSQL docs say pg_dump output cannot be used with WAL replay.
• Target never reached: PostgreSQL shuts down with a fatal error if archive recovery ends before the target. A normal recovery to "now" also ends with a harmless file-not-found message.

Variants and alternatives

In production

• Databases: PostgreSQL continuous archiving, MySQL binary logs, Amazon RDS automated backups.
• File level: Litestream replicates SQLite to object storage; litestream restore -timestamp or -txid lands only on boundaries of replica files that still exist.
• Tools: pgBackRest, WAL-G, Barman. Snapshots: ZFS and cloud volumes for file systems and VMs.

Implementations

Sources

• PostgreSQL documentation, Continuous Archiving and Point-in-Time Recovery (PITR), including Timelines. docs
• PostgreSQL documentation, Write Ahead Log settings: Archive Recovery and Recovery Target. docs
• PostgreSQL documentation, pg_verifybackup. docs
• MySQL 8.4 Reference Manual, Point-in-Time (Incremental) Recovery, binary log method (Wayback copy). docs
• Amazon RDS User Guide, Restoring a DB instance to a specified time. docs
• Litestream documentation, litestream restore. docs
• pgBackRest user guide, Retention, Point-in-Time Recovery. docs
• Amazon S3 User Guide, Retaining multiple versions of objects with S3 Versioning. docs
• OpenZFS, zfs-send(8). docs