Backup Catalog: Chains, Retention, Synthetic Fulls and Legal Holds

Backup Catalog: Chains, Retention, Synthetic Fulls and Legal Holds

You've joined the infrastructure team that owns the backup catalog: the service that records every backup taken of the company's servers and decides, each night, which ones to delete. Backups are either full (self-contained) or incremental (only the changes since the *previous backup of the same server*, so it can only be restored together with everything before it, back to the last full). Timestamps are strings, YYYY-MM-DDTHH:MM, in UTC.

Last Sunday's prune deleted a full backup that kept incrementals still needed, and the on-call engineer's restore of the production database came back with half a chain (INC-4417). Fix that and the other retention bugs hiding next to it, then build the two features that are queued behind it.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh, empty catalog and returns one result per operation. Every operation is [name, *args]. Errors are returned as "error: <code>" strings, never raised. Arguments that are missing, extra, of the wrong type or malformed return "error: invalid arguments" (checked first, before any other error); an unknown name returns "error: unknown operation". Timestamps must match YYYY-MM-DDTHH:MM exactly and name a real minute (2026-02-30T01:00 is invalid). Names (server, ids) are non-empty strings; counts are integers (true/false are not integers).

Ids and order. Ids are "b-1", "b-2", ... in creation order, one counter for the whole catalog (not per server); a rejected operation does not use up an id. Backups are ordered by (taken_at, creation order): of two backups with the same taken_at the later-created one is newer, and b-10 is newer than b-9.

Chains. An incremental's *parent* is the previous backup taken for its server (full or incremental); a full has no parent. A backup's *chain* is its ancestors back to a full, then itself. Pruned backups are gone from the catalog but the server's "previous backup" is still remembered: an incremental taken after its base was pruned is accepted, and its chain is broken.

• backup: an incr for a server that never had any backup returns no base backup. A backup whose at is earlier than the server's previous backup's at returns out of order (equal is fine).
• generate is a bulk shortcut for the capacity tests: it behaves like count separate backup calls spaced step_minutes (integer >= 1) apart starting at start. Backup i (0-based) is a full when i == 0 or (full_every > 0 and i is a multiple of full_every), otherwise an incremental. count is 1..100000; full_every is an integer >= 0. It is all-or-nothing: if start is earlier than the server's previous backup, nothing is created.
• restore(server, at) targets the newest live backup with taken_at <= at (inclusive) and returns its chain's ids. No such backup (or an unknown server): no backup. If an ancestor of the target has been pruned: broken chain.
• A server with no override uses the default policy, which starts at 7 daily, 4 weekly, 6 monthly.

Worked example

[["backup", "db", "full", "2026-03-01T02:00"],
 ["backup", "db", "incr", "2026-03-02T02:00"],
 ["backup", "db", "incr", "2026-03-03T02:00"],
 ["backup", "db", "incr", "2026-03-04T02:00"],
 ["backup", "db", "full", "2026-03-08T02:00"],
 ["backup", "db", "incr", "2026-03-09T02:00"],
 ["set_default_policy", 1, 0, 0],
 ["prune", "db", "2026-03-10T00:00"],
 ["restore", "db", "2026-03-09T12:00"],
 ["restore", "db", "2026-03-03T12:00"]]

returns

["b-1", "b-2", "b-3", "b-4", "b-5", "b-6", true,
 ["b-1", "b-2", "b-3", "b-4"], ["b-5", "b-6"], "error: no backup"]

Part 1: Make retention safe (INC-4417)

Goal: prune implements the grandfather-father-son policy below and never deletes a backup that a kept backup depends on; restore and the ordering rules above hold everywhere. The failing test in tests/ is the symptom, not the whole list: the hidden tests cover the rest of the rules in this Part.

Rules for prune(server, now) (it only touches that server's backups):

1. Backups with taken_at > now (clock skew) are never deleted and do not count toward any bucket below.
2. For each of the three granularities, group the remaining backups into buckets: day = UTC calendar date; week = ISO 8601 week (Monday to Sunday; week 1 is the week with the year's first Thursday, so 2025-12-29 through 2026-01-04 is one week, 2026-W01); month = UTC calendar month.
3. A bucket's representative is its newest backup (by the ordering above). The policy keeps the representatives of the newest daily day buckets, the newest weekly week buckets and the newest monthly month buckets, counting only buckets that contain at least one backup (a quiet fortnight does not use up slots). A count of 0 keeps none for that granularity. A backup may be kept by several rules.
4. Dependencies: every ancestor of a kept backup is also kept, even if no rule selected it.
5. Everything else is deleted. prune returns the deleted ids oldest first ([] if nothing, or if the server is unknown). A second prune with the same arguments deletes nothing.

The worked example above is exactly the incident: the current code deletes b-5, the full that b-6 is built on.

Part 2: Synthetic fulls and immutability locks (INFRA-882)

Goal: long incremental chains are slow to restore and keep old fulls alive forever. Let the team merge a chain into a new *synthetic full*, and let compliance lock individual backups so they cannot be pruned for a while.

Synthetic fulls

1. synthesize(server, id) creates a new backup (next id) of kind full with taken_at equal to the target's and no parent. It is flagged synthetic. The target and its ancestors are left untouched.
2. Every live backup whose parent is the target is rebased onto the new full: from now on its chain is the new full followed by itself.
3. Normally the "previous backup" a future incremental is based on is the last backup *taken*, and a synthetic full never counts as taken. The one exception: if the target is that previous backup, the synthetic full takes its place, so the next incremental is based on it.
4. backup_id must be a live backup of that server, else backup not found. A full (synthetic or not) is already full. A target whose chain has a pruned ancestor is broken chain.
5. Synthetic fulls take part in everything else like any other backup (ordering, restore, prune buckets). In particular the synthetic full is newer than its target (same taken_at, later creation), so it is the representative of any bucket they share.

Locks

1. A lock keeps a backup alive until until (exclusive): it is active at now iff until > now. Expiry is judged lazily: nothing is ever deleted or flipped when a lock passes its until; each operation judges the lock against its *own* now argument (the now values of successive operations need not increase).
2. lock(id, until, now): until <= now is lock in the past. If the backup already has a lock that is active at now, until earlier than the current one is lock shortened (equal or later extends it). A lock that is not active at now is simply replaced.
3. Ids given to lock, lock_status, hold and synthesize must be live backups (not pruned), else backup not found. lock_status returns {"locked": true, "until": <until>} when a lock is active at now, else {"locked": false, "until": null}.
4. prune(server, now) never deletes a backup whose lock is active at now. Locks do not affect which backups the bucket rules select (a locked backup does not take or free a slot) but a locked backup is kept, and so are its ancestors (rule 4 of Part 1). Locks only protect that one backup.

Example (fresh catalog)

[["backup", "db", "full", "2026-03-01T02:00"],
 ["backup", "db", "incr", "2026-03-02T02:00"],
 ["backup", "db", "incr", "2026-03-03T02:00"],
 ["synthesize", "db", "b-3"],
 ["backup", "db", "incr", "2026-03-04T02:00"],
 ["restore", "db", "2026-03-04T12:00"],
 ["restore", "db", "2026-03-03T12:00"],
 ["restore", "db", "2026-03-02T12:00"]]

returns ["b-1", "b-2", "b-3", "b-4", "b-5", ["b-4", "b-5"], ["b-4"], ["b-1", "b-2"]]. b-4 is the synthetic full for b-3; b-5 was taken on top of it.

A lock example (fresh catalog; lock is [id, until, now]):

[["backup", "db", "full", "2026-03-01T02:00"],
 ["backup", "db", "full", "2026-03-02T02:00"],
 ["backup", "db", "full", "2026-03-03T02:00"],
 ["set_default_policy", 1, 0, 0],
 ["lock", "b-1", "2026-03-10T00:00", "2026-03-04T00:00"],
 ["prune", "db", "2026-03-05T00:00"],
 ["lock_status", "b-1", "2026-03-11T00:00"],
 ["prune", "db", "2026-03-11T00:00"]]

returns ["b-1", "b-2", "b-3", true, true, ["b-2"], {"locked": false, "until": null}, ["b-1"]].

Part 3: Per-server policies, legal holds and the prune report (REQ-2231)

Goal: the requirements changed. Retention differs per server (and the team in Tokyo wants "a day" to mean *their* day), legal can freeze evidence, and auditors want to see why each backup survived. Part 1's rules change accordingly; everything earlier must keep working.

Per-server policy and local time

1. set_policy gives one server its own policy, replacing any earlier override for it; servers without one keep using the default (set_default_policy, always UTC). utc_offset is an integer number of minutes east of UTC, -720..840. The three counts are integers >= 0.
2. This changes the bucket rules of Part 1: a server's day, week and month buckets are those of its local time, taken_at + utc_offset minutes (a backup taken at 2026-03-01T15:10 UTC with offset 540 is on local day 2026-03-02). Which backup is *newest* in a bucket is still decided by the UTC order. The future check (taken_at > now) and lock expiry stay in UTC.
3. A policy applies from the next prune on; nothing is re-evaluated retroactively.

Legal holds

1. hold(case, id) pins the backup and its entire restore chain as it is right now: the backup and every ancestor reachable through the current parent links. A held backup is never pruned regardless of any lock or policy. Placing the same case on the same backup twice is allowed (still one hold). backup not found if id is not live.
2. Several cases can hold the same backup. release(case, id) removes only that case's hold; the backup stays pinned while any other case holds it. Releasing a hold that does not exist (including for a backup that is gone) is hold not found.
3. The pin is recomputed at every prune from the *current* parent links (rebasing from Part 2 changes what a hold pins).

The prune report

report(server) returns what the most recent prune of that server decided: one row [id, taken_at, verdict] for every backup of that server that was live when that prune began (including the ones it deleted), ordered oldest first (the ordering above). It is a snapshot: later operations do not change it, and an earlier prune's rows are never mixed in. no prune yet if that server was never pruned (pruning an unknown server counts, and its report is []).

verdict is "pruned", or "kept:" followed by the reasons that apply, comma-separated, always in this order: hold, lock, future, daily, weekly, monthly, dependency

• hold: pinned by a hold (the held backup and its whole chain).
• lock: its lock is active at that prune's now.
• future: taken_at > now.
• daily / weekly / monthly: selected as a representative by that rule.
• dependency: it is an ancestor of some backup that is kept for any of the reasons above. (So a held backup's ancestors are hold,dependency.)

Scale. The nightly job prunes catalogs holding tens of thousands of backups, some in chains thousands long, and in the hidden tests several such prunes share one run. The whole suite has a few seconds.

Example (fresh catalog)

[["backup", "db", "full", "2026-03-01T02:00"],
 ["backup", "db", "incr", "2026-03-02T02:00"],
 ["backup", "db", "incr", "2026-03-03T02:00"],
 ["backup", "db", "full", "2026-03-04T02:00"],
 ["backup", "db", "incr", "2026-03-05T02:00"],
 ["set_default_policy", 1, 0, 0],
 ["hold", "CASE-7", "b-2"],
 ["prune", "db", "2026-03-06T00:00"],
 ["report", "db"],
 ["release", "CASE-7", "b-2"],
 ["prune", "db", "2026-03-07T00:00"],
 ["report", "db"]]

returns

[..., true,
 ["b-3"],
 [["b-1", "2026-03-01T02:00", "kept:hold,dependency"],
  ["b-2", "2026-03-02T02:00", "kept:hold"],
  ["b-3", "2026-03-03T02:00", "pruned"],
  ["b-4", "2026-03-04T02:00", "kept:dependency"],
  ["b-5", "2026-03-05T02:00", "kept:daily"]],
 true,
 ["b-1", "b-2"],
 [["b-1", "2026-03-01T02:00", "pruned"],
  ["b-2", "2026-03-02T02:00", "pruned"],
  ["b-4", "2026-03-04T02:00", "kept:dependency"],
  ["b-5", "2026-03-05T02:00", "kept:daily"]]]

(the first five results are the ids "b-1" to "b-5", then true for the policy.)

And a policy example (fresh catalog; Tokyo is UTC+9, 540):

[["set_policy", "web", 2, 0, 0, 540],
 ["backup", "web", "full", "2026-03-01T14:30"],
 ["backup", "web", "full", "2026-03-01T15:10"],
 ["backup", "web", "full", "2026-03-01T16:00"],
 ["prune", "web", "2026-03-02T00:00"]]

returns [true, "b-1", "b-2", "b-3", ["b-2"]]. Locally, b-1 is on day 2026-03-01 and b-2, b-3 are on 2026-03-02 (b-3 is that day's representative), so daily = 2 keeps b-1 and b-3. In UTC all three share a day and only b-3 would survive.

Notes

• checks.py, config.py, errors.py and models.py are known-good.
• You may use the AI assistant freely; you are expected to verify what it produces.
• Later parts must not break earlier ones; hidden tests re-check earlier behaviour after later features exist.
• Parts 1 and 2 are the core; Part 3 is where the design changes underneath you.