Re: UNDO with constant time recovery (CTR)

> On Oct 5, 2026, at 2:41 PM, Manu <manuelreyesbravo(at)gmail(dot)com> wrote:
>
> 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).

Hey Manu,

Thank you for digging into this and doing some work to measure. I blame
myself for being overly excited and essentially including click-bait
verbiage like "CTR" from the papers I cited to Matthias in the last reply
in the subject for this thread.

I'll do better next time. I'll read your scripts and when I update my
patch (soon I hope) I'll include some timing of my own and then restate
or refute the claim, fair?

> 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
> <ctr_rollback_latency.sh.txt><ctr_knee.sh.txt><ctr_recovery_time.sh.txt><ctr_knee.tsv.txt><ctr_recovery_time.tsv.txt><recovery_log_evidence.txt>

best.

-greg