Re: UNDO with constant time recovery (CTR)

Shihao, Matthias,

Thanks for the careful review of v2. All three of your reports were
real bugs, and chasing them down led to a much larger round of
stabilization than I'd expected. v3 is attached, apologies for the length
of this email but there was a lot of churn and this isn't a small set of
changes.

Your three reports:
-------------------

1. Patch-split mistakes (059/061 setting a GUC that only 0005 added; test
modules only built in 0005). Fixed: tests live with the feature they
exercise, and every prefix of the series builds and passes its own tests.

2. CREATE DATABASE crash leaves the directory, for both wal_log and
file_copy. Fixed; the destination tree is now owned by FILEOPS and removed
on abort or crash (recovery/090). Following it up also found that a loser
whose UNDO predated the last checkpoint was never rolled back; the
checkpoint now records in-flight UNDO chains and recovery starts from them
(test_fileops/005).

3. An ordinary filesystem error turning into a PANIC inside a critical
section. Your diagnosis was exact and applied to every immediate
operation. The syscall now runs before the critical section, so a failure
is an ordinary ERROR with the usual message (test_fileops/004 / 016).

Correcting my earlier CTR claim
-------------------------------

Earlier in this thread I said the ATM lets recovery accept connections without
replaying UNDO. That is not entirely accurate.

- FLUX table and index UNDO: a live rollback applies the UNDO inline before
ROLLBACK returns, unless the chain exceeds undo_rollback_overflow_size
(16 MB) and an undo apply worker has room. After a crash, recovery queues
the losers and the per-backend undo workers revert them AFTER the database
is open, not the ATM.
- FILEOPS: cluster-wide UNDO for a crash loser is applied BEFORE the database
opens, linear in the loser's UNDO.

So "no UNDO replay before open" is true only for FLUX table/index UNDO,
via the per-backend workers, and not for FILEOPS. The cluster-wide
engine keeps UNDO in the WAL stream, so a long transaction pins WAL and
recovery walks loser chains.

"Constant time recovery" (CTR) in the SQL Server sense (a persistent
version store, O(1) abort, bounded recovery) was inspirational, but
recovery as of this version doesn't match that implementation or
claim. So, I have dropped the term and the O(1) claims from the code,
messages, and subject line of this email.

FILEOPS: what it is and is not
------------------------------

I'll admit up front that proper transactional FILEOPS is currently a
narrow transactional layer, but not yet a self-contained crash-atomic
resource manager. I have stopped calling this "constant time recovery",
that was a mistake, it's bounded and minimal but hardly "constant".

FILEOPS makes the filesystem mutations the server does outside the
buffer manager (CREATE/DROP DATABASE and TABLESPACE directories,
copydir) participate in transactions and in crash recovery, at wal_level
>= replica. It is NOT a replacement for smgr, and it is NOT a
self-contained crash-atomic resource manager yet, but that is the goal.
Right now here are the honest limitations (also in the README and the
commit message):

- a commit-time operation (delete/rename/rmdir at commit) is logged after the
commit record, so a crash in between can lose it (test_fileops/007 TODO);
- the syscall-before-WAL window;
- per-transaction, not per-operation, ownership of a crash loser's inverses;
- nothing for wal_level = minimal.

I've considered integration into the resource manager (self-contained
redo/undo from common WAL, durable intent before commit, per-operation
ownership) but I'm not sure where I'm going to take that idea next. I'm
open to ideas here.

FLUX
----

FLUX is an in-place-MVCC table access method here not as competition
with HEAP but more an illustration/research/proof-of-concept for an
UNDO-based table AM, not meant for production use (at this time).

Attempts to "make HEAP better by using UNDO" were all unsuccessful; HEAP
represents a set of trade-offs that are proven, well optimized, and
understood by all who use Postgres.

In FLUX, a row keeps its TID for its lifetime; the header carries
heap-shaped xmin/xmax/cid; older versions are reconstructed from the
per-backend UNDO log; row locks live in a shared, on-demand sLog (never
on the tuple).

v3 fixes a long list of correctness bugs this round turned up in testing
and benchmarking against HEAP. Lost updates and serialization
behaviour, DELETE/UPDATE classification after waiting, CREATE INDEX
CONCURRENTLY, index entries for INCLUDE and non-"equalimage" key
columns, partial-index membership, TOAST reclamation, the visibility
map's WAL ordering, BRIN summarization, and others. Each is a separate
commit with a test that fails before it and a heap twin.

Two FLUX notes worth stating up front:

- index-only scans are not used on a FLUX table (a delete-marked index entry
can carry a key that no longer matches the row until VACUUM);
- FLUX must never depend on VACUUM for correctness; VACUUM reclaims space and
freezes for wraparound, as for HEAP.

The sLog that holds row locks allocates nothing at startup (a cluster that
never uses FLUX pays almost nothing) and grows on demand.

Measured on a quiet 64-vCPU host, release builds, pgbench scale 100, all
at 64 concurrent clients; each number is the median of five interleaved
60-second runs, in thousands of transactions per second (higher is
better). Three FLUX builds are compared against each other, with heap
on the same v3 build as a reference:

- FLUX/v2 : FLUX as posted in v2 (the old fixed-size row-lock table)
- FLUX/v3 : FLUX in this series (the on-demand row-lock sLog)
- heap/v3 : the heap AM on the v3 build, for reference

workload (what each pgbench transaction does) FLUX/v2 FLUX/v3 heap/v3 v3 vs v2
--------------------------------------------- ------- ------- ------- --------
SELECT FOR UPDATE one row, then UPDATE it 293.0 306.5 359.0 +4.6%
INSERT a child row (foreign-key check on parent) 497.1 505.3 529.9 +1.6%
plain UPDATE (pgbench -N, no row locks) 229.3 243.6 291.7 +6.2%
SELECT 10 rows FOR UPDATE in one transaction 273.8 306.6 285.7 +12.0%
SELECT 100 rows FOR UPDATE in one transaction 20.4 33.0 35.1 +62.1%

So FLUX's row-lock path is at or above the v2 fixed-table store
everywhere, and now beats it by 12% (10-row) and 62% (100-row) at 64
clients. Fresh-cluster shared memory is +776 KiB over master: the
row-lock store contributes zero startup bytes; the +776 KiB is the
per-backend UNDO structures (~418 KiB) plus the slots for the discard
worker and undo launcher (max_worker_processes 8 -> 12, ~395 KiB).
Those two workers are required for correctness (the discard worker
reclaims undo segments) and hibernate when idle; launching them on first
use is left as future work.

Series
------

0001 cluster-wide UNDO engine (records in the WAL stream)
0002 transactional filesystem operations (FILEOPS) backed by UNDO
0003 route filesystem mutations through FILEOPS
0004 per-backend UNDO logs
0005 the ATM, sLog, and logical revert worker
0006 nbtree: mark aborted index inserts dead via UNDO
0007 hash: mark aborted index inserts dead via UNDO
0008 nbtree: in-place delete-marking for stable-TID UPDATE
0009 tableam: let an AM declare that UPDATE keeps a row's TID
0010 executor: keep the pre-update row of an in-place UPDATE
0011 EvalPlanQual: fetch an in-place AM's reference rows with the query snapshot
0012 AFTER triggers: queue an in-place AM's row images with the event
0013 logical replication: pre-check unique keys an in-place UPDATE changes
0014 tableam: SO_RETURN_DELETED, and update_deleted detection for any AM
0015 tableam: let a block AM's size estimate use its own default fillfactor
0016 tableam: let REPACK (CONCURRENTLY) accept any AM whose changes are decoded
0017 vacuum: add parallel_vacuum_set_index_stats() and a bulkdel injection point
0018 pg_visibility: refuse tables of other table AMs in the tuple checks
0019 the FLUX in-place-MVCC table access method
0020 benchmarks: heap vs FLUX

The 0009-0018 commits are heap-neutral preparatory changes to the table-AM,
executor, trigger, EvalPlanQual, logical-replication, VACUUM and pg_visibility
interfaces; each is a no-op for heap and for any AM that does not opt in, and
all are ordered before 0019 (FLUX), which is the first commit that uses them.

Patches
-------

0001 Add a cluster-wide UNDO engine with records in the WAL stream
The UNDO substrate: records live in the common WAL stream; crash recovery
reverts loser transactions' structural changes through a recovery pass.
Changes since v2: 6 items (unused AM prepare hook removed; headerscheck
skips undormgrlist.h; recovery-model docs made accurate; buffer content
locks released before inline abort UNDO; failed-abort WAL-hold claim
corrected; UNDO docs promoted to a chapter).

0002 Add transactional filesystem operations (FILEOPS) backed by UNDO
WAL resource manager (RM_FILEOPS_ID) making structural filesystem
mutations crash-safe and rollback-safe; AtPrepare path for 2PC.
Changes since v2: report apply failures as failures; remove obsolete UNDO
file cleanup. Tests: drop logical_revert_naptime in 063/061; show a crash
right after commit loses deferred ops.

0003 Route filesystem mutations through FILEOPS
Wire in-tree DDL/storage callers (CREATE/DROP DATABASE, TABLESPACE,
copydir) through the FILEOPS API. (No "Changes since v2" block.)

0004 Add per-backend UNDO logs
Per-backend UNDO logs and the undo apply/discard workers; the engine FLUX
table/index UNDO reverts crash losers from, after the database opens.
Changes since v2: 38 items (2PC rollback chains; subxact undo dispatch;
non-permanent/temp undo handling; 3-page record spanning; FPIs on undo
pages; snapshot-limited recovery start; project formatting + pgperltidy).

0005 Add the ATM, sLog, and logical revert worker
The aborted-transaction map, the on-demand sLog row-lock store, and the
logical revert worker.
Changes since v2: 24 items + 3 tests (retention report; inline UNDO always
for non-index; new-database dir removed on abort/crash; roll back
in-flight UNDO preceding the checkpoint; prepared row locks restored
without clobbering owners; "a cluster that never uses UNDO costs what
master does").

0006 nbtree: mark aborted index inserts dead via UNDO
Changes since v2: 22 items + 2 tests (flush index UNDO before commit
record; newest-first apply in crash recovery; CLR redo consistency-checked;
index UNDO applied inline only).

0007 hash: mark aborted index inserts dead via UNDO
Changes since v2: 14 items + 1 test (restore UNDO abort ordering; persist
FILEOPS ownership for deferred crash losers; dead-tuples hint on hash
rollback; PANIC only when an inverse cannot be made durable).

0008 nbtree: support in-place delete-marking for stable-TID UPDATE
Changes since v2: 11 items + 1 test (uniqueness check asks the AM about a
delete-marked entry; atomic delete-mark of a full leaf via replace split;
amcheck handles delete-marked entries; tombstone trailer room).

0009 [prep] tableam: let an AM declare that UPDATE keeps a row's TID
0010 [prep] executor: keep the pre-update row of an in-place UPDATE
0011 [prep] EvalPlanQual: fetch an in-place AM's reference rows with the query
snapshot
0012 [prep] AFTER triggers: queue an in-place AM's row images with the event
0013 [prep] logical replication: pre-check unique keys an in-place UPDATE changes
0014 [prep] tableam: SO_RETURN_DELETED, and update_deleted detection for any AM
0015 [prep] tableam: let a block AM's size estimate use its own default fillfactor
0016 [prep] tableam: let REPACK (CONCURRENTLY) accept any AM whose changes are
decoded
(adds TableAmRoutine.am_logical_decoding; REPACK tests it instead of
naming heap.)
0017 [prep] vacuum: add parallel_vacuum_set_index_stats() and a bulkdel injection
point
0018 [prep] pg_visibility: refuse tables of other table AMs in the tuple checks
(0009-0018 have no "Changes since v2" block except 0016; they are the new
heap-neutral interface preparation split out of the FLUX commit.)

0019 Add the FLUX in-place-MVCC table access method
In-place MVCC table AM: a row keeps its TID; heap-shaped xmin/xmax/cid in
the header; older versions from the per-backend UNDO log; row locks in the
shared on-demand sLog, never on the tuple.
Changes since v2: 60+ items (invisible aborted writers; idempotent UNDO
keyed on version; helping; TOAST supersede; VACUUM reclaims aborted-INSERT
rows and truncates the whole empty tail; tombstone-removal horizon
reasoning; scan slots own a copy under a writer-excluding lock; VACUUM
never moves a live row; row locks not held per-row until commit;
user_catalog_table refused; project formatting + pgperltidy).

0020 Benchmarks: HEAP vs FLUX
Benchmark scaffolding comparing heap and FLUX. (No "Changes since v2".)

Changes since v2 (series-level)
-------------------------------
- The three v2 review reports (patch-split mistakes; CREATE DATABASE crash
leaving the directory; a filesystem error PANICking in a critical section)
are fixed; see the cover letter.
- The "constant time recovery / CTR" framing and the O(1) claims are dropped;
the README states the real recovery model.
- Rebased from the v2 base onto current origin/master (72b916a20db), 99
upstream commits of churn resolved; 4 merge conflicts, all in test-list /
docs files (recovery test 058/059 renumbered to 062/063 around upstream's
new 058/059; repack.sgml restructure; test_decoding + injection_points spec
lists), no code-logic conflicts.
- Full release gate green on the rebased tip (see cover-letter status block).

Review of 0001-0003 is most useful; I'd especially value a second look
at the FILEOPS abort-record ordering and the checkpoint in-flight record
in 0001.

best.

-greg