Re: UNDO with constant time recovery (CTR)

Hi Matthias,

> The title indicates constant-time recovery, but I don't see anything
> in this thread that supports this claim. Could you expand on the
> mechanisms you're using to guarantee this?

I built the v2 series and measured this, since it is checkable. Two
things, both on v2 (test_fileops is the knob: each call records one undo
record; the heap AM does not opt into UNDO, so ordinary DML generates
none).

First, a scoping note. The O(1) claim is stated for the sparse case
(README.undo:105): "a handful of filesystem or structural operations per
transaction ... O(1) from the client's perspective." It is not a claim
that total undo work is constant -- the design defers that work, it does
not remove it. So for the two client-visible costs below, the question is
really whether they stay flat as the undo chain grows past "a handful".

1) ROLLBACK latency vs undo-chain length N (one txn, N chmods, timing the
ROLLBACK only, median of 5, self-checked that the chain was actually
applied). ROLLBACK ms by undo_instant_abort_threshold regime:

- default (65536): N=200 is 0.37, N=1000 is 1.41, N=8000 is 9.74,
N=32000 is 37.6
- forced inline (large threshold): N=200 is 0.37, N=1000 is 1.81,
N=8000 is 9.43, N=32000 is 70.5
- forced deferred (threshold=1): N=200 is 0.37, N=1000 is 2.49,
N=8000 is 9.93, N=32000 is 39.1

It is linear in N in all three regimes (~1.2 us/record). Forcing the
deferred path does not make the client return in O(1): the chain is still
written and XLogFlush'd before ROLLBACK returns; deferral only moves the
physical reversal to the revert worker.

2) Crash recovery of an in-flight transaction. A backend builds N chmods
in an open txn, then the cluster is immediate-stopped. On restart the undo
phase is synchronous and the server log shows it finishing before the
cluster opens:

starting undo phase for incomplete transactions
UNDO recovery complete: 1 transactions rolled back, 128000 records applied
undo phase complete
database system is ready to accept connections (after the undo phase)

Undo phase duration, median of 2, records_applied == N every run:
N=2000 is 1.5 ms; N=32000 is 17.5 ms; N=128000 is 72.0 ms. The undo
phase is linear in N -- consistent with README.undo:119-127 (loser-txn
undo runs in the recovery pass), but it is the synchronous
undo-before-open that "constant time recovery" reads as avoiding.

None of this contradicts the mechanism -- deferring the undo of already
resolved aborts to a background worker is real and works. It is the title
and the headline O(1) that a reader takes literally. It might be worth
scoping both to the sparse case the README already assumes, or saying in
the docs that an in-flight transaction's undo is still applied at recovery
in O(chain length).

Attached are the three measurement scripts, the raw result tables, and
the recovery-log excerpt, so the numbers above can be reproduced:
ctr_rollback_latency.sh and ctr_knee.sh (test 1), ctr_recovery_time.sh
(test 2), the two .tsv outputs, and recovery_log_evidence.txt.

- Manu