Thread: Transaction ID wraparound: problem and proposed solution

We've expended a lot of worry and discussion in the past about what
happens if the OID generator wraps around.  However, there is another
4-byte counter in the system: the transaction ID (XID) generator.
While OID wraparound is survivable, if XIDs wrap around then we really
do have a Ragnarok scenario.  The tuple validity checks do ordered
comparisons on XIDs, and will consider tuples with xmin > current xact
to be invalid.  Result: after wraparound, your whole database would
instantly vanish from view.

The first thought that comes to mind is that XIDs should be promoted to
eight bytes.  However there are several practical problems with this:
* portability --- I don't believe long long int exists on all the
platforms we support.
* performance --- except on true 64-bit platforms, widening Datum to
eight bytes would be a system-wide performance hit, which is a tad
unpleasant to fix a scenario that's not yet been reported from the
field.
* disk space --- letting pg_log grow without bound isn't a pleasant
prospect either.

I believe it is possible to fix these problems without widening XID,
by redefining XIDs in a way that allows for wraparound.  Here's my
plan:

1. Allow XIDs to range from 0 to WRAPLIMIT-1 (WRAPLIMIT is not
necessarily 4G, see discussion below).  Ordered comparisons on XIDs
are no longer simply "x < y", but need to be expressed as a macro.
We consider x < y if (y - x) % WRAPLIMIT < WRAPLIMIT/2.
This comparison will work as long as the range of interesting XIDs
never exceeds WRAPLIMIT/2.  Essentially, we envision the actual value
of XID as being the low-order bits of a logical XID that always
increases, and we assume that no extant XID is more than WRAPLIMIT/2
transactions old, so we needn't keep track of the high-order bits.

2. To keep the system from having to deal with XIDs that are more than
WRAPLIMIT/2 transactions old, VACUUM should "freeze" known-good old
tuples.  To do this, we'll reserve a special XID, say 1, that is always
considered committed and is always less than any ordinary XID.  (So the
ordered-comparison macro is really a little more complicated than I said
above.  Note that there is already a reserved XID just like this in the
system, the "bootstrap" XID.  We could simply use the bootstrap XID, but
it seems better to make another one.)  When VACUUM finds a tuple that
is committed good and has xmin < XmaxRecent (the oldest XID that might
be considered uncommitted by any open transaction), it will replace that
tuple's xmin by the special always-good XID.  Therefore, as long as
VACUUM is run on all tables in the installation more often than once per
WRAPLIMIT/2 transactions, there will be no tuples with ordinary XIDs
older than WRAPLIMIT/2.

3. At wraparound, the XID counter has to be advanced to skip over the
InvalidXID value (zero) and the reserved XIDs, so that no real transaction
is generated with those XIDs.  No biggie here.

4. With the wraparound behavior, pg_log will have a bounded size: it
will never exceed WRAPLIMIT*2 bits = WRAPLIMIT/4 bytes.  Since we will
recycle pg_log entries every WRAPLIMIT xacts, during transaction start
the xact manager will have to take care to actively clear its pg_log
entry to zeroes (I'm not sure if it does that already, or just assumes
that new pg_log entries will start out zero).  As long as that happens
before the xact makes any data changes, it's OK to recycle the entry.
Note we are assuming that no tuples will remain in the database with
xmin or xmax equal to that XID from a prior cycle of the universe.

This scheme allows us to survive XID wraparound at the cost of slight
additional complexity in ordered comparisons of XIDs (which is not a
really performance-critical task AFAIK), and at the cost that the
original insertion XIDs of all but recent tuples will be lost by
VACUUM.  The system doesn't particularly care about that, but old XIDs
do sometimes come in handy for debugging purposes.  A possible
compromise is to overwrite only XIDs that are older than, say,
WRAPLIMIT/4 instead of doing so as soon as possible.  This would mean
the required VACUUM frequency is every WRAPLIMIT/4 xacts instead of
every WRAPLIMIT/2 xacts.

We have a straightforward tradeoff between the maximum size of pg_log
(WRAPLIMIT/4 bytes) and the required frequency of VACUUM (at least
every WRAPLIMIT/2 or WRAPLIMIT/4 transactions).  This could be made
configurable in config.h for those who're intent on customization,
but I'd be inclined to set the default value at WRAPLIMIT = 1G.

Comments?  Vadim, is any of this about to be superseded by WAL?
If not, I'd like to fix it for 7.1.
        regards, tom lane

At 17:47 3/11/00 -0500, Tom Lane wrote:
>* portability --- I don't believe long long int exists on all the
>platforms we support.

Are you sure of this, or is it just a 'last time I looked' statement. If
the latter, it might be worth verifying.


>* performance --- except on true 64-bit platforms, widening Datum to
>eight bytes would be a system-wide performance hit, 

Yes, OIDs are used a lot, but it's not that bad, is it? Are there many
tight loops with thousands of OID-only operations? I'd guess it's only one
more instruction & memory fetch.


>* disk space --- letting pg_log grow without bound isn't a pleasant
>prospect either.

Maybe this can be achieved by wrapping XID for the log file only.


>I believe it is possible to fix these problems without widening XID,
>by redefining XIDs in a way that allows for wraparound.  Here's my
>plan:

It's a cute idea (elegant, even), but maybe we'd be running through hoops
just for a minor performance gain (which may not exist, since we're adding
extra comparisons via the macro) and for possible unsupported OSs. Perhaps
OS's without 8 byte ints have to suffer a performance hit (ie. we declare a
struct with appropriate macros).


>are no longer simply "x < y", but need to be expressed as a macro.
>We consider x < y if (y - x) % WRAPLIMIT < WRAPLIMIT/2.

You mean you plan to limit PGSQL to only 1G concurrent transactions. Isn't
that a bit short sighted? ;-}


>2. To keep the system from having to deal with XIDs that are more than
>WRAPLIMIT/2 transactions old, VACUUM should "freeze" known-good old
>tuples. 

This is a problem for me; it seems to enshrine VACUUM in perpetuity.


>4. With the wraparound behavior, pg_log will have a bounded size: it
>will never exceed WRAPLIMIT*2 bits = WRAPLIMIT/4 bytes.  Since we will
>recycle pg_log entries every WRAPLIMIT xacts, during transaction start

Is there any was we can use this recycling technique with 8-byte XIDs?

Also, will there be a problem with backup programs that use XID to
determine newer records and apply/reapply changes?


>This scheme allows us to survive XID wraparound at the cost of slight
>additional complexity in ordered comparisons of XIDs (which is not a
>really performance-critical task AFAIK)

Maybe I'm really missing the amount of XID manipulation, but I'd be
surprised if 16-byte XIDs would slow things down much.


----------------------------------------------------------------
Philip Warner                    |     __---_____
Albatross Consulting Pty. Ltd.   |----/       -  \
(A.B.N. 75 008 659 498)          |          /(@)   ______---_
Tel: (+61) 0500 83 82 81         |                 _________  \
Fax: (+61) 0500 83 82 82         |                 ___________ |
Http://www.rhyme.com.au          |                /           \|                                |    --________--
PGP key available upon request,  |  /
and from pgp5.ai.mit.edu:11371   |/

Philip Warner <pjw@rhyme.com.au> writes:
>> * disk space --- letting pg_log grow without bound isn't a pleasant
>> prospect either.

> Maybe this can be achieved by wrapping XID for the log file only.

How's that going to improve matters?  pg_log is ground truth for XIDs;
if you can't distinguish two XIDs in pg_log, there's no point in
distinguishing them elsewhere.

> Maybe I'm really missing the amount of XID manipulation, but I'd be
> surprised if 16-byte XIDs would slow things down much.

It's not so much XIDs themselves, as that I think we'd need to widen
typedef Datum too, and that affects manipulations of *all* data types.

In any case, the prospect of a multi-gigabyte, ever-growing pg_log file,
with no way to recover the space short of dump/initdb/reload, is
awfully unappetizing for a high-traffic installation...
        regards, tom lane

Tom Lane wrote:
> 
> Philip Warner <pjw@rhyme.com.au> writes:
> >> * disk space --- letting pg_log grow without bound isn't a pleasant
> >> prospect either.
> 
> > Maybe this can be achieved by wrapping XID for the log file only.
> 
> How's that going to improve matters?  pg_log is ground truth for XIDs;
> if you can't distinguish two XIDs in pg_log, there's no point in
> distinguishing them elsewhere.
> 
> > Maybe I'm really missing the amount of XID manipulation, but I'd be
> > surprised if 16-byte XIDs would slow things down much.
> 
> It's not so much XIDs themselves, as that I think we'd need to widen
> typedef Datum too, and that affects manipulations of *all* data types.
> 
> In any case, the prospect of a multi-gigabyte, ever-growing pg_log file,
> with no way to recover the space short of dump/initdb/reload, is
> awfully unappetizing for a high-traffic installation...

Agreed completely.  I'd like to think I could have such an installation
in the next year or so :)  

To prevent a performance hit to those who don't want, is there a
possibility of either a compile time option or 'auto-expanding' the
width of the XID's and other items when it becomes appropriate?  Start
with int4, when that limit is hit goto int8, and should -- quite
unbelievibly so but there are multi-TB databases -- it be necessary jump
to int12 or int16?   Be the first to support Exa-objects in an RDBMS. 
Testing not necessary ;)

Compiletime option would be appropriate however if theres a significant
performance hit.

I'm not much of a c coder (obviously), so I don't know of the
limitations.  plpgsql is my friend that can do nearly anything :)

Hmm... After reading the above I should have stuck with lurking.

One idea I had from this is actually truncating pg_log at some point if
we know all the tuples have the special committed xid.  It would prevent
the file from growing without bounds.

Vadim, can you explain how WAL will make pg_log unnecessary someday?


> We've expended a lot of worry and discussion in the past about what
> happens if the OID generator wraps around.  However, there is another
> 4-byte counter in the system: the transaction ID (XID) generator.
> While OID wraparound is survivable, if XIDs wrap around then we really
> do have a Ragnarok scenario.  The tuple validity checks do ordered
> comparisons on XIDs, and will consider tuples with xmin > current xact
> to be invalid.  Result: after wraparound, your whole database would
> instantly vanish from view.

--  Bruce Momjian                        |  http://candle.pha.pa.us pgman@candle.pha.pa.us               |  (610)
853-3000+  If your life is a hard drive,     |  830 Blythe Avenue +  Christ can be your backup.        |  Drexel Hill,
Pennsylvania19026
 

> One idea I had from this is actually truncating pg_log at some point if
> we know all the tuples have the special committed xid.  It would prevent
> the file from growing without bounds.

Not truncating, but implementing pg_log as set of files - we could remove
files for old xids.

> Vadim, can you explain how WAL will make pg_log unnecessary someday?

First, I mentioned only that having undo we could remove old pg_log after
postmaster startup because of only committed changes would be in data
files and they would be visible to new transactions (small changes in tqual
will be required to take page' startup id into account) which would reuse xids.
While changing a page first time in current startup, server would do exactly
what Tom is going to do at vacuuming - just update xmin/xmax to "1" in all items
(or setting some flag in t_infomask), - and change page' startup id to current.

I understand that this is not complete solution for xids problem, I just wasn't
going to solve it that time. Now after Tom' proposal I see how to reuse xids
without vacuuming (but having undo): we will add XidWrapId (XWI) - xid wrap
counter - to pages and set it when we change page. First time we do this for
page with old XWI we'll mark old items (to know later that they were changed
by xids with old XWI). Each time we change page we can mark old xmin/xmax
with xid <= current xid as committed long ago (basing on xact TTL restrinctions).

All above assumes that there will be no xids from aborted transactions in pages,
so we need not lookup in pg_log to know is a xid committed/aborted, - there will
be only xids from running or committed xactions there.

And we need in undo for this.

Vadim

Tom Lane wrote:
> 
> We've expended a lot of worry and discussion in the past about what
> happens if the OID generator wraps around.  However, there is another
> 4-byte counter in the system: the transaction ID (XID) generator.
> While OID wraparound is survivable, if XIDs wrap around then we really
> do have a Ragnarok scenario.  The tuple validity checks do ordered
> comparisons on XIDs, and will consider tuples with xmin > current xact
> to be invalid.  Result: after wraparound, your whole database would
> instantly vanish from view.
> 
> The first thought that comes to mind is that XIDs should be promoted to
> eight bytes.  However there are several practical problems with this:
> * portability --- I don't believe long long int exists on all the
> platforms we support.

I suspect that gcc at least supports long long on all OS-s we support

> * performance --- except on true 64-bit platforms, widening Datum to
> eight bytes would be a system-wide performance hit, which is a tad
> unpleasant to fix a scenario that's not yet been reported from the
> field.

Complicating compares would also be a performance hit. It's hard to tell 
which one would be bigger

> * disk space --- letting pg_log grow without bound isn't a pleasant
> prospect either.

How will 2x size increase of xid cause "boundless" growth of pg_log ;)

> I believe it is possible to fix these problems without widening XID,
> by redefining XIDs in a way that allows for wraparound.  Here's my
> plan:

I'd hate to let go of any hope of restoring time travel.

I suspect that until postgres starts re-using space, time travel is in 
theory possible, provided one more file is kept with commit (wall-clock)
times of transactions or adding these times to pg_log.

BTW, is there somewhere a timetable of important changes in basic 
principles in postgres, so that I could get a CVS checkout just before 
them happening ?

I'd specially be intereted in following:

t0: system support for time-travel removed
t1: no longer a no-overwrite systems
t2: OIDs gone
t3: got rid of all OO-features ;)

----------
Hannu

Hannu Krosing writes:

> > The first thought that comes to mind is that XIDs should be promoted to
> > eight bytes.  However there are several practical problems with this:
> > * portability --- I don't believe long long int exists on all the
> > platforms we support.
> 
> I suspect that gcc at least supports long long on all OS-s we support

Uh, we don't want to depend on gcc, do we?

But we could make the XID a struct of two 4-byte integers, at the obvious
increase in storage size.

-- 
Peter Eisentraut      peter_e@gmx.net       http://yi.org/peter-e/

* Peter Eisentraut <peter_e@gmx.net> [001105 09:39]:
> Hannu Krosing writes:
> 
> > > The first thought that comes to mind is that XIDs should be promoted to
> > > eight bytes.  However there are several practical problems with this:
> > > * portability --- I don't believe long long int exists on all the
> > > platforms we support.
> > 
> > I suspect that gcc at least supports long long on all OS-s we support
> 
> Uh, we don't want to depend on gcc, do we?
Doesn't C99 *REQUIRE* long long?  I know the SCO UDK Compiler has had
it for a long time.  I know it's early in C99's life, but...


> 
> But we could make the XID a struct of two 4-byte integers, at the obvious
> increase in storage size.
What is the difference between a native long long and a struct of 2
long's? 


-- 
Larry Rosenman                      http://www.lerctr.org/~ler
Phone: +1 972-414-9812 (voice) Internet: ler@lerctr.org
US Mail: 1905 Steamboat Springs Drive, Garland, TX 75044-6749

Hannu Krosing <hannu@tm.ee> writes:
>> * disk space --- letting pg_log grow without bound isn't a pleasant
>> prospect either.

> How will 2x size increase of xid cause "boundless" growth of pg_log ;)

OK, 2^64 isn't mathematically unbounded, but let's see you buy a disk
that will hold it ;-).  My point is that if we want to think about
allowing >4G transactions, part of the answer has to be a way to recycle
pg_log space.  Otherwise it's still not really practical.
        regards, tom lane

Larry Rosenman <ler@lerctr.org> writes:
>> Uh, we don't want to depend on gcc, do we?

> Doesn't C99 *REQUIRE* long long?

What difference does that make?  It'll be a very long time before
Postgres can REQUIRE that people have a C99-compliant compiler.
Portability does not mean "we work great on just the newest and
spiffiest platforms"...
        regards, tom lane

* Tom Lane <tgl@sss.pgh.pa.us> [001105 12:07]:
> Larry Rosenman <ler@lerctr.org> writes:
> >> Uh, we don't want to depend on gcc, do we?
> 
> > Doesn't C99 *REQUIRE* long long?
> 
> What difference does that make?  It'll be a very long time before
> Postgres can REQUIRE that people have a C99-compliant compiler.
> Portability does not mean "we work great on just the newest and
> spiffiest platforms"...
I understand, but long long should start appearing in mainstream stuff
now that the standard is out.  I do understand your concern, however.
I was just making a point that we should start seeing it. 
> 
>             regards, tom lane
-- 
Larry Rosenman                      http://www.lerctr.org/~ler
Phone: +1 972-414-9812 (voice) Internet: ler@lerctr.org
US Mail: 1905 Steamboat Springs Drive, Garland, TX 75044-6749

Peter Eisentraut wrote:
> 
> Hannu Krosing writes:
> 
> > > The first thought that comes to mind is that XIDs should be promoted to
> > > eight bytes.  However there are several practical problems with this:
> > > * portability --- I don't believe long long int exists on all the
> > > platforms we support.
> >
> > I suspect that gcc at least supports long long on all OS-s we support
> 
> Uh, we don't want to depend on gcc, do we?

I suspect that we do on many platforms (like *BSD, Linux and Win32).

What platforms we currently support don't have functional gcc ?

> But we could make the XID a struct of two 4-byte integers, at the obvious
> increase in storage size.

And a (hopefully) small performance hit on operations when defined as
macros,
and some more for less data fitting in cache.

what operations do we need to be defined ?

will >, <, ==, !=, >=, <== and ++ be enough ?

-------------
Hannu

* Hannu Krosing <hannu@tm.ee> [001105 15:21]:
> Peter Eisentraut wrote:
> > 
> I suspect that we do on many platforms (like *BSD, Linux and Win32).
Many, but not *ALL*.  I prefer to build my stuff using the Native
UnixWare 7 (UDK) Compiler.  As of the Feature Supplement (due out any
week now, I have a pre-release), we have WORKING C++, and the compiler
is C99, and the C++ is STD C++ (very very very close). 

GCC/G++ for this platform (at least from the SCO Skunkware side) is
NOT C99 nore STD C++.

> 
> What platforms we currently support don't have functional gcc ?
> 
> > But we could make the XID a struct of two 4-byte integers, at the obvious
> > increase in storage size.
> 
> And a (hopefully) small performance hit on operations when defined as
> macros,
> and some more for less data fitting in cache.
> 
> what operations do we need to be defined ?
> 
> will >, <, ==, !=, >=, <== and ++ be enough ?
> 
> -------------
> Hannu
-- 
Larry Rosenman                      http://www.lerctr.org/~ler
Phone: +1 972-414-9812 (voice) Internet: ler@lerctr.org
US Mail: 1905 Steamboat Springs Drive, Garland, TX 75044-6749

On Sunday 05 November 2000 13:02, Tom Lane wrote:
> OK, 2^64 isn't mathematically unbounded, but let's see you buy a disk
> that will hold it ;-).  My point is that if we want to think about
> allowing >4G transactions, part of the answer has to be a way to recycle
> pg_log space.  Otherwise it's still not really practical.

I kind of like vadim's idea of segmenting pg_log. 

Segments in which all the xacts have been commited could be deleted.

-- 
Mark Hollomon

Tom Lane wrote:
> 
> Philip Warner <pjw@rhyme.com.au> writes:
> >> * disk space --- letting pg_log grow without bound isn't a pleasant
> >> prospect either.
> 
> > Maybe this can be achieved by wrapping XID for the log file only.
> 
> How's that going to improve matters?  pg_log is ground truth for XIDs;
> if you can't distinguish two XIDs in pg_log, there's no point in
> distinguishing them elsewhere.

One simple way - start a new pg_log file at each wraparound and encode 
the high 4 bytes in the filename (or in first four bytes of file)

> > Maybe I'm really missing the amount of XID manipulation, but I'd be
> > surprised if 16-byte XIDs would slow things down much.
> 
> It's not so much XIDs themselves, as that I think we'd need to widen
> typedef Datum too, and that affects manipulations of *all* data types.

Do you mean that each _field_ will take more space, not each _record_ ?

> In any case, the prospect of a multi-gigabyte, ever-growing pg_log file,
> with no way to recover the space short of dump/initdb/reload, is
> awfully unappetizing for a high-traffic installation...

The pg_log should be rotated anyway either with long xids or long-long
xids.

-----------
Hannu

On Sun, Nov 05, 2000 at 03:48:13PM +0200, Hannu Krosing wrote:
> Tom Lane wrote:
> > 
> > Philip Warner <pjw@rhyme.com.au> writes:
> > >> * disk space --- letting pg_log grow without bound isn't a pleasant
> > >> prospect either.
> > 
> > > Maybe this can be achieved by wrapping XID for the log file only.
> > 
> > How's that going to improve matters?  pg_log is ground truth for XIDs;
> > if you can't distinguish two XIDs in pg_log, there's no point in
> > distinguishing them elsewhere.
> 
> One simple way - start a new pg_log file at each wraparound and encode 
> the high 4 bytes in the filename (or in first four bytes of file)

Proposal:

Annotate each log file with the current XID value at the time the file 
is created.  Before comparing any two XIDs, subtract that value from 
each operand, using unsigned arithmetic. 

At a sustained rate of 10,000 transactions/second, any pair of 32-bit 
XIDs less than 2.5 days apart compare properly.

Nathan Myers
ncm@zembu.com

I have added this email thread to TODO.detail.

> We've expended a lot of worry and discussion in the past about what
> happens if the OID generator wraps around.  However, there is another
> 4-byte counter in the system: the transaction ID (XID) generator.
> While OID wraparound is survivable, if XIDs wrap around then we really
> do have a Ragnarok scenario.  The tuple validity checks do ordered
> comparisons on XIDs, and will consider tuples with xmin > current xact
> to be invalid.  Result: after wraparound, your whole database would
> instantly vanish from view.
> 
> The first thought that comes to mind is that XIDs should be promoted to
> eight bytes.  However there are several practical problems with this:
> * portability --- I don't believe long long int exists on all the
> platforms we support.
> * performance --- except on true 64-bit platforms, widening Datum to
> eight bytes would be a system-wide performance hit, which is a tad
> unpleasant to fix a scenario that's not yet been reported from the
> field.
> * disk space --- letting pg_log grow without bound isn't a pleasant
> prospect either.
> 
> I believe it is possible to fix these problems without widening XID,
> by redefining XIDs in a way that allows for wraparound.  Here's my
> plan:
> 
> 1. Allow XIDs to range from 0 to WRAPLIMIT-1 (WRAPLIMIT is not
> necessarily 4G, see discussion below).  Ordered comparisons on XIDs
> are no longer simply "x < y", but need to be expressed as a macro.
> We consider x < y if (y - x) % WRAPLIMIT < WRAPLIMIT/2.
> This comparison will work as long as the range of interesting XIDs
> never exceeds WRAPLIMIT/2.  Essentially, we envision the actual value
> of XID as being the low-order bits of a logical XID that always
> increases, and we assume that no extant XID is more than WRAPLIMIT/2
> transactions old, so we needn't keep track of the high-order bits.
> 
> 2. To keep the system from having to deal with XIDs that are more than
> WRAPLIMIT/2 transactions old, VACUUM should "freeze" known-good old
> tuples.  To do this, we'll reserve a special XID, say 1, that is always
> considered committed and is always less than any ordinary XID.  (So the
> ordered-comparison macro is really a little more complicated than I said
> above.  Note that there is already a reserved XID just like this in the
> system, the "bootstrap" XID.  We could simply use the bootstrap XID, but
> it seems better to make another one.)  When VACUUM finds a tuple that
> is committed good and has xmin < XmaxRecent (the oldest XID that might
> be considered uncommitted by any open transaction), it will replace that
> tuple's xmin by the special always-good XID.  Therefore, as long as
> VACUUM is run on all tables in the installation more often than once per
> WRAPLIMIT/2 transactions, there will be no tuples with ordinary XIDs
> older than WRAPLIMIT/2.
> 
> 3. At wraparound, the XID counter has to be advanced to skip over the
> InvalidXID value (zero) and the reserved XIDs, so that no real transaction
> is generated with those XIDs.  No biggie here.
> 
> 4. With the wraparound behavior, pg_log will have a bounded size: it
> will never exceed WRAPLIMIT*2 bits = WRAPLIMIT/4 bytes.  Since we will
> recycle pg_log entries every WRAPLIMIT xacts, during transaction start
> the xact manager will have to take care to actively clear its pg_log
> entry to zeroes (I'm not sure if it does that already, or just assumes
> that new pg_log entries will start out zero).  As long as that happens
> before the xact makes any data changes, it's OK to recycle the entry.
> Note we are assuming that no tuples will remain in the database with
> xmin or xmax equal to that XID from a prior cycle of the universe.
> 
> This scheme allows us to survive XID wraparound at the cost of slight
> additional complexity in ordered comparisons of XIDs (which is not a
> really performance-critical task AFAIK), and at the cost that the
> original insertion XIDs of all but recent tuples will be lost by
> VACUUM.  The system doesn't particularly care about that, but old XIDs
> do sometimes come in handy for debugging purposes.  A possible
> compromise is to overwrite only XIDs that are older than, say,
> WRAPLIMIT/4 instead of doing so as soon as possible.  This would mean
> the required VACUUM frequency is every WRAPLIMIT/4 xacts instead of
> every WRAPLIMIT/2 xacts.
> 
> We have a straightforward tradeoff between the maximum size of pg_log
> (WRAPLIMIT/4 bytes) and the required frequency of VACUUM (at least
> every WRAPLIMIT/2 or WRAPLIMIT/4 transactions).  This could be made
> configurable in config.h for those who're intent on customization,
> but I'd be inclined to set the default value at WRAPLIMIT = 1G.
> 
> Comments?  Vadim, is any of this about to be superseded by WAL?
> If not, I'd like to fix it for 7.1.
> 
>             regards, tom lane
> 


--  Bruce Momjian                        |  http://candle.pha.pa.us pgman@candle.pha.pa.us               |  (610)
853-3000+  If your life is a hard drive,     |  830 Blythe Avenue +  Christ can be your backup.        |  Drexel Hill,
Pennsylvania19026
 

I think the XID wraparound matter might be handled a bit more simply.

Given a global variable X which is the earliest XID value in use at 
some event (e.g. startup) you can compare two XIDs x and y, using
unsigned arithmetic, with just (x-X < y-X).  This has the further 
advantage that old transaction IDs need be "frozen" only every 4G 
transactions, rather than Tom's suggested 256M or 512M transactions.  
"Freezing", in this scheme, means to set all older XIDs to equal the 
chosen X, rather than setting them to some constant reserved value.  
No special cases are required for the comparison, even for folded 
values; it is (x-X < y-X) for all valid x and y.

I don't know the role of the "bootstrap" XID, or how it must be
fitted into the above.

Nathan Myers
ncm@zembu.com

------------------------------------------------------------
> We've expended a lot of worry and discussion in the past about what
> happens if the OID generator wraps around.  However, there is another
> 4-byte counter in the system: the transaction ID (XID) generator.
> While OID wraparound is survivable, if XIDs wrap around then we really
> do have a Ragnarok scenario.  The tuple validity checks do ordered
> comparisons on XIDs, and will consider tuples with xmin > current xact
> to be invalid.  Result: after wraparound, your whole database would
> instantly vanish from view.
> 
> The first thought that comes to mind is that XIDs should be promoted to
> eight bytes.  However there are several practical problems with this:
> * portability --- I don't believe long long int exists on all the
> platforms we support.
> * performance --- except on true 64-bit platforms, widening Datum to
> eight bytes would be a system-wide performance hit, which is a tad
> unpleasant to fix a scenario that's not yet been reported from the
> field.
> * disk space --- letting pg_log grow without bound isn't a pleasant
> prospect either.
> 
> I believe it is possible to fix these problems without widening XID,
> by redefining XIDs in a way that allows for wraparound.  Here's my
> plan:
> 
> 1. Allow XIDs to range from 0 to WRAPLIMIT-1 (WRAPLIMIT is not
> necessarily 4G, see discussion below).  Ordered comparisons on XIDs
> are no longer simply "x < y", but need to be expressed as a macro.
> We consider x < y if (y - x) % WRAPLIMIT < WRAPLIMIT/2.
> This comparison will work as long as the range of interesting XIDs
> never exceeds WRAPLIMIT/2.  Essentially, we envision the actual value
> of XID as being the low-order bits of a logical XID that always
> increases, and we assume that no extant XID is more than WRAPLIMIT/2
> transactions old, so we needn't keep track of the high-order bits.
> 
> 2. To keep the system from having to deal with XIDs that are more than
> WRAPLIMIT/2 transactions old, VACUUM should "freeze" known-good old
> tuples.  To do this, we'll reserve a special XID, say 1, that is always
> considered committed and is always less than any ordinary XID.  (So the
> ordered-comparison macro is really a little more complicated than I said
> above.  Note that there is already a reserved XID just like this in the
> system, the "bootstrap" XID.  We could simply use the bootstrap XID, but
> it seems better to make another one.)  When VACUUM finds a tuple that
> is committed good and has xmin < XmaxRecent (the oldest XID that might
> be considered uncommitted by any open transaction), it will replace that
> tuple's xmin by the special always-good XID.  Therefore, as long as
> VACUUM is run on all tables in the installation more often than once per
> WRAPLIMIT/2 transactions, there will be no tuples with ordinary XIDs
> older than WRAPLIMIT/2.
> 
> 3. At wraparound, the XID counter has to be advanced to skip over the
> InvalidXID value (zero) and the reserved XIDs, so that no real transaction
> is generated with those XIDs.  No biggie here.
> 
> 4. With the wraparound behavior, pg_log will have a bounded size: it
> will never exceed WRAPLIMIT*2 bits = WRAPLIMIT/4 bytes.  Since we will
> recycle pg_log entries every WRAPLIMIT xacts, during transaction start
> the xact manager will have to take care to actively clear its pg_log
> entry to zeroes (I'm not sure if it does that already, or just assumes
> that new pg_log entries will start out zero).  As long as that happens
> before the xact makes any data changes, it's OK to recycle the entry.
> Note we are assuming that no tuples will remain in the database with
> xmin or xmax equal to that XID from a prior cycle of the universe.
> 
> This scheme allows us to survive XID wraparound at the cost of slight
> additional complexity in ordered comparisons of XIDs (which is not a
> really performance-critical task AFAIK), and at the cost that the
> original insertion XIDs of all but recent tuples will be lost by
> VACUUM.  The system doesn't particularly care about that, but old XIDs
> do sometimes come in handy for debugging purposes.  A possible
> compromise is to overwrite only XIDs that are older than, say,
> WRAPLIMIT/4 instead of doing so as soon as possible.  This would mean
> the required VACUUM frequency is every WRAPLIMIT/4 xacts instead of
> every WRAPLIMIT/2 xacts.
> 
> We have a straightforward tradeoff between the maximum size of pg_log
> (WRAPLIMIT/4 bytes) and the required frequency of VACUUM (at least
> every WRAPLIMIT/2 or WRAPLIMIT/4 transactions).  This could be made
> configurable in config.h for those who're intent on customization,
> but I'd be inclined to set the default value at WRAPLIMIT = 1G.
> 
> Comments?  Vadim, is any of this about to be superseded by WAL?
> If not, I'd like to fix it for 7.1.
> 
>             regards, tom lane

> > The first thought that comes to mind is that XIDs should be promoted to
> > eight bytes.  However there are several practical problems with this:
> > * portability --- I don't believe long long int exists on all the
> > platforms we support.

> >             regards, tom lane

How long will such platforms be supported?  When will 64bit be a
requirement?

The c.h has following lines in case there is not 64 bit ints:

/* Won't actually work, but fall back to long int so that code* compiles */
typedef long int int64;
typedef unsigned long int uint64;
#define INT64_IS_BUSTED


At the memont the int64 is mostly used in 'int8' case, so its
not too bad.  But probably there will be more cases where int64
is useful, so PostgreSQL will start misbehaving on those
platforms, which is worse than not supporting them officially.

Or should int64 be avoided at any cost?

-- 
marko

Marko Kreen <marko@l-t.ee> writes:
> When will 64bit be a requirement?

As far as I'm concerned, it will *never* be a requirement,
at least not for the foreseeable future.

I do want the option to compile with 8-byte OID and/or XID types.
That's not a requirement.
        regards, tom lane