UNDO with constant time recovery (CTR) - Mailing list pgsql-hackers

Hello hackers,

Postgres from the start has not implemented the concept of UNDO WAL log
records depending only on REDO during recovery to return to a consistent
state.  This was an intentional omission, not an oversight and a good
one that has stood the test of time.

Famously the ZHeap project implemented UNDO as a stepping stone to a new
table AM by that name to replace HEAP.  The idea was to avoid some of
the pitfalls of HEAP's MVCC design, primarily "bloat" in tables and
indexes which requires VACUUM to eliminate.  Another attempt at UNDO was
in the Zedstore table AM, a hybrid row/column system with UNDO.  Both
these projects showed great promise, but neither delivered.

So UNDO has a history here, and it is important to recognize that up
front.  I'd like to acknowledge that this work builds directly on a
decade of prior work by many people.  So much so that I'm sure I've left
someone or something off this list, apologies in advance and feel free
to reply with more links referencing more of the history of UNDO in
Postgres.

   Undo logs, Thomas Munro
     https://postgr.es/m/CAEepm=2EqROYJ_xYz4v5kfr4b0qw_Lq_6Pe8RTEC8rx3upWsSQ@mail.gmail.com
   Undo worker and transaction rollback, Dilip Kumar
     https://postgr.es/m/CAFiTN-sYQ8r8ANjWFYkXVfNxgXyLRfvbX9Ee4SxO9ns-OBBgVA@mail.gmail.com
   POC: Cleaning up orphaned files using undo logs, Thomas Munro, later Antonin Houska
     https://postgr.es/m/CAEepm=0ULqYgM2aFeOnrx6YrtBg3xUdxALoyCG+XpssKqmezug@mail.gmail.com
     https://postgr.es/m/20190203100944.qwcf2ctclf75so7c@alap3.anarazel.de
     https://postgr.es/m/45455.1637848942@antos
   zheap: a new storage format for PostgreSQL, Amit Kapila et al.
     https://github.com/EnterpriseDB/zheap
     https://postgr.es/m/CAA4eK1+YtM5vxzSM2NZm+pC37MCwyvtkmJrO_yRBQeZDp9Wa2w@mail.gmail.com
   Logical decoding for operations on zheap tables, Amit Kapila
     https://postgr.es/m/CAA4eK1JeGWBKR6nRMMUXQhSMsEQHUPHm3XVLHfUrDvrceN+WFg@mail.gmail.com
   Zedstore - compressed in-core columnar storage, Ashwin Agrawal
     https://postgr.es/m/CALfoeiuF-m5jg51mJUPm5GN8u396o5sA2AF5N97vTRAEDYac7w@mail.gmail.com
   undo: zedstore vs. zheap, Robert Haas
     https://postgr.es/m/CA+TgmoYeTeQSmALox0PmSm5Gh03oe=UNjhmL+K+btofY_U2jFQ@mail.gmail.com
   Orphaned relation files after crash recovery, Masahiko Sawada
     https://postgr.es/m/CA+fd4k7KHw0E5t9_4LFmsiFYL7SQrtwK312TQQ8q0gUDmy3jkw@mail.gmail.com

I started working on this by first resurrecting the ZHeap UNDO code,
then resurrecting Zedstore.  This work dovetails my other major thread
about "Tepid" which builds on PHOT and the heap-only tuple (HOT)
optimizations.

All these authors and more deserve credit for their hard work, thank
you.  In the case of ZHeap and Zedstore the ultimate goal was a new table
AM.  I'm not going to boil that ocean up front, here is where I'm going
to diverge from those past projects.

* there is no change to HEAP in this patch set
* there are some changes to nbtree and hash, but they are additive and
   gated by a new index_undo reloption; they consume 0001 but touch no
   existing index behavior when a transaction commits, foundational for
   review only designed to trigger discussion at this point
* there is a new table AM in this patch set called FLUX, but it is a
  prototype/demo/not finished and not intended to replace HEAP

There is nothing wrong with the way Postgres does WAL logging or
recovery today.  And the HEAP table AM is a thing of beauty, despite its
appearances, that has carried production load for the lifetime of
Postgres at a scale never anticipated by anyone involved. The process of
vacuuming tables has dramatically improved over the years and continues
to be an area of active development addressing the bloat issue head on
with continued refinement of the autovacuum process, the
concurrency/efficiency of vacuuming, and now we have REPACK.  So why
resurrect UNDO?

I feel that the flexibility of Postgres is one of its core strengths.
I'd like to see more innovation, different shapes of table and index AMs
supported in core and as extensions over time.  I'd like to offer users
of Postgres different operational trade-offs, in particular one that
shifts the burden of "bloat" from table/index to the WAL, which is what
UNDO can do and ZHeap targeted but never delivered.  That's a longer
term goal.  In my opinion, there exist a number of use cases for a
system that provides UNDO.  The ability to recover a stateful change to
a consistent state is valuable in a database.

One good example is "orphaned files" or other changes to the state of
filesystem objects at runtime [1].  It's my view that these stateful
changes should behave as anything else that is transactional, during
recovery they in-flight or aborted changes should be undone so as
provide a consistent state at startup.  So, rather than build a new
table AM as the first justification for UNDO I've built "transational
filesystem operations" (FILEOPS for short) and changed all our calls
from things like mkdir() to FileOpsMkdir().  Here's the list of
supported operations:

   FileOpsCreate(path, flags, mode, register_delete)
   FileOpsDelete(path, at_commit)
   FileOpsRename(oldpath, newpath)
   FileOpsWrite(path, offset, data, len)
   FileOpsTruncate(path, length)
   FileOpsChmod(path, mode)
   FileOpsChown(path, uid, gid)
   FileOpsMkdir(path, mode)
   FileOpsRmdir(path, at_commit)
   FileOpsRmdirRecursive(path, at_commit)
   FileOpsRmtree(path, at_commit)
   FileOpsSymlink(target, linkpath)
   FileOpsLink(oldpath, newpath)
   FileOpsSetXattr(path, name, value, len)
   FileOpsRemoveXattr(path, name)

If a transaction is in flight and creates a new file and then crashes to
me it makes sense that after recovery that new file is gone and the
system is consistent again.  I felt this would be a good, small but
important, first step into the use of UNDO in a few places in Postgres.

This isn't a new idea, I used to work for Sleepycat and write code
improving Berkeley DB years (decades!) ago and it includes the ability
to log filesystem changes in the WAL and then recover them to well known
state, so why not Postgres?

Another idea might be new work on LOB (or BLOB/CLOB) type that can use
UNDO to manage state stored on the filesystem or elsewhere.

The attached set of patches has a few that are very large, UNDO is split
across 0001 (cluster-wide), 0004 (per-backend), and 0005 (ATM/sLog), it
is not a small.  Obviously if FILEOPS was my only target for this major
addition to core the idea should be rejected and we should get back to
work on [1] or something similar.  I think adding UNDO as a generic
subsystem will bring new innovations to Postgres that are impossible or
too complex as the system stands today.  But I'm only once voice here in
this community, so before I invest more time in the prototype table AMs
based on UNDO I need to see if this is something we all agree should be
integrated into core.

The generic UNDO system in the attached patches provides two modes,
logging into the common WAL log along with all the REDO, etc. records is
one way and it's how FILEOPS is implemented.  But ZHeap had a different
idea, a WAL log per-backend, and my two prototype table AMs use that
model for UNDO. I'll not go into the differences or reasoning here, I've
attached two wiki page drafts and in the src/backend/access/undo/README
there is a ton of detail so please read that before responding with
thoughts.

The v1 patches are:

    0001  UNDO: add the cluster-wide UNDO engine
    0002  FILEOPS: transactional filesystem operations with UNDO in the common WAL
    0003  Route transactional filesystem operations through FILEOPS
    0004  UNDO: add the per-backend UNDO logs
    0005  UNDO: add the ATM, sLog, and logical revert worker
    0006  INDEX: nbtree UNDO for rollback without VACUUM
    0007  INDEX: hash UNDO for rollback without VACUUM
    0008  INDEX: nbtree delete-marking for in-place indexed-column UPDATE

0001 - is the engine: undo records written into the normal WAL stream, a
resource-manager dispatch so any access method can register an rm_undo
callback keyed by its own record id, transaction integration, and
application of an aborted transaction's undo chain inline at abort and
at the end of recovery. Nothing in 0001 knows about HEAP, indexes, or
any table AM; the core stays format-agnostic and interprets a record
only through the owning rmgr's callback.

0002 and 0003 are the first consumer and a large part of why I think
this foundation is worth reviewing now: transactional filesystem
operations. CREATE DATABASE, tablespace directory creation, and the copy
paths currently leave orphaned files behind when a transaction or the
server dies at the wrong moment. FILEOPS runs constructive operations
(create, mkdir, chmod, symlink) immediately and registers an abort-time
undo action to remove them, and defers destructive operations (rename,
delete, rmdir, rmtree) to commit. On abort or crash the undo chain
removes exactly what the transaction created; on commit the deferred
removals run. It is carried correctly through 2PC. This is the problem
Thomas started on in the orphaned-files POC thread [1], approached
through the same undo machinery rather than a bespoke pending-ops list.

0004 and 0005 are the remaining pieces the table access methods I'm
working toward need, included here so the engine is complete rather than
a stub: per-backend undo logs (buffered, discardable undo segment
storage owned per top-level transaction), and constant-time rollback via
an aborted-transaction map plus a background worker that applies undo
chains asynchronously. Unlike 0001, these two have no in-tree consumer
in this thread; the FLUX and RECNO table AMs that use them come later.
I've kept them here so the foundation can be reviewed as a whole, but if
the list would rather I hold 0004 and 0005 until their first consumer,
say so and I'll drop them from this thread.

0006, 0007 and 0008 are the second consumer, and they exercise the
engine harder. 0006 and 0007 make an aborted transaction leave no index
work for VACUUM: each leaf entry a transaction inserts writes one small
record into the cluster-wide UNDO stream (heap TID, length, and a digest
of the key, not the tuple itself), and on abort the chain walk marks
just those entries LP_DEAD, wherever a later insert or a page split
moved them. It is a heap reloption, index_undo, on by default. 0008 adds
nbtree delete-marking, the piece a stable-TID in-place-UPDATE table AM
needs to keep a row's TID when an indexed column changes. Heap itself
writes no UNDO in any of this and is unchanged.

0009 is the FLUX table AM, a prototype that I've been tinkering with
during development of UNDO and included not as a replacement for HEAP.

The per-backend engine in 0004 derives from the ZHeap UNDO work; those
authors are credited in that patch's commit message. Where this design
differs from the 2019 patch set it is mostly in the directions Robert's
zedstore-vs-zheap notes pointed: UNDO chained per tuple, not per block;
a per-record apply callback, not per-page; the top-level xid used for
subtransactions; and a freshly inserted tuple needs no undo record for
visibility. Tuple locking is still the open question it was in that
thread; I use a heavyweight tuple lock for now and would welcome
opinions.

I know this is a large area with a long history. I've tried to make the
entry point small: 0001 plus FILEOPS (0002, 0003) is a complete,
testable feature set that stands on its own, and I'd value review of
that boundary first.

Design write-ups kept current with the code in
src/backend/access/undo/README and wiki pages.

For the record LLMs did participate in this process, but this was not a
"vibe-coded UNDO system".  You might find an LLM-ism or two somewhere, I
tried to audit all the code in my last review before sending but I'm not
perfect and neither are they.  I've worked on it extensively and I've
used LLMs to provide feedback, polish, find corner cases, find missing
but required features, do security reviews, etc.  This has been in the
works for over a year, I hope you're interested enough to give it a look
and let me know your thoughts.  The only part of this email an LLM
produced was the per-patch descriptions above, the rest is me.

Also, I realize that this kind of change takes a lot of time to gain
traction and adoption into core, if at all.  I'm ready for that, sure
we're working on v20 now and v19 is inching out the door maybe this
merges into v25 or maybe it gets shelved along the way for good reason.
Who knows, but I do know that it's worth the effort to advocate and to
have a durable record for others interested in it even if it doesn't get
merged in this time.  I look forward to seeing what happens.  :)

best.

-greg

PS: I have two UNDO-based table AMs that under development, FLUX and
RECNO, but neither is ready for production use or intended as a
replacement for HEAP.
https://github.com/gburd/postgres/tree/undo/src/backend/access/flux
https://github.com/gburd/postgres/tree/undo/src/backend/access/recno

[1]
https://postgr.es/m/Hjyy_5of-vqSTyKUyYgK8WjlA49tMG-GmitHDPI02SVcqz1ckxfTwpPo4R92neovTfeaQAlxWzOBVyx7bgKA07j1s9V3BeOsHYTuwTg0468%3D%40burd.me