Bug in ProcArrayApplyRecoveryInfo for snapshots crossing 4B, breaking replicas

Hi,

There's a bug in ProcArrayApplyRecoveryInfo, introduced by 8431e296ea, 
which may cause failures when starting a replica, making it unusable. 
The commit message for 8431e296ea is not very clear about what exactly 
is being done and why, but the root cause is that at while processing 
RUNNING_XACTS, the XIDs are sorted like this:

     /*
      * Sort the array so that we can add them safely into
      * KnownAssignedXids.
      */
     qsort(xids, nxids, sizeof(TransactionId), xidComparator);

where "safely" likely means "not violating the ordering expected by 
KnownAssignedXidsAdd". Unfortunately, xidComparator compares the values 
as plain uint32 values, while KnownAssignedXidsAdd actually calls 
TransactionIdFollowsOrEquals() and compares the logical XIDs :-(

Triggering this is pretty simple - all you need is two transactions with 
XIDs before/after the 4B limit, and then (re)start a replica. The 
replica refuses to start with a message like this:

     LOG:  9 KnownAssignedXids (num=4 tail=0 head=4) [0]=32705 [1]=32706
           [2]=32707 [3]=32708
     CONTEXT:  WAL redo at 0/6000120 for Standby/RUNNING_XACTS: nextXid
               32715 latestCompletedXid 32714 oldestRunningXid
               4294967001; 8 xacts: 32708 32707 32706 32705 4294967009
               4294967008 4294967007 4294967006
     FATAL:  out-of-order XID insertion in KnownAssignedXids

Clearly, we add the 4 "younger" XIDs first (because that's what the XID 
comparator does), but then KnownAssignedXidsAdd thinks there's some sort 
of corruption because logically 4294967006 is older.

This does not affect replicas in STANDBY_SNAPSHOT_READY state, because 
in that case ProcArrayApplyRecoveryInfo ignores RUNNING_XACTS messages.


The probability of hitting this in practice is proportional to how long 
you leave transactions running. The system where we observed this leaves 
transactions with XIDs open for days, and the age may be ~40M. 
Intuitivelly, that's ~40M/4B (=1%) probability that at any given time 
there are transactions with contradicting ordering. So most restarts 
worked fine, until one that happened at just the "right" time.

This likely explains why we never got any reports about this - most 
systems probably don't leave transactions running for this long, so the 
probability is much lower. And replica restarts are generally not that 
common events either.

Attached patch is fixing this by just sorting the XIDs logically. The 
xidComparator is meant for places that can't do logical ordering. But 
these XIDs come from RUNNING_XACTS, so they actually come from the same 
wraparound epoch (so sorting logically seems perfectly fine).


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company