PostgreSQL source code (59) analysis of transaction ID allocation and overflow judgment methods

xid Value rule

xid yes uint32 Type of ,GetNewTransactionId Function xid stay ShmemVariableCache->nextXid The value of , however ShmemVariableCache->nextXid yes long int Type of .

unsigned int : 0           ~  4294967295 ( 0     ~ 2^32-1 )
int          : -2147483648 ~  2147483647 ( -2^31 ~ 2^31-1 )
long int     : -9223372036854775808 ~ 9223372036854775807 ( -2^63 ~ 2^63-1 )


GetNewTransactionId
  FullTransactionId full_xid;
  TransactionId xid;
  full_xid = ShmemVariableCache->nextXid;
  xid = XidFromFullTransactionId(full_xid);

therefore xid The value of will be from 0 To 4294967295 Return to zero again 4294967295 Keep cycling . and ShmemVariableCache->nextXid It has been rising , because ShmemVariableCache->nextXid The range is ( -2^63 ~ 2^63-1 ).

Be careful ShmemVariableCache->nextXid To positive maximum 9223372036854775807 After adding for a while, it overflows to the minimum value of negative number -9223372036854775808, At this time, strong turns to uint32 When is 0, Another cycle .

See the following example for the rule of value taking ：

ShmemVariableCache->nextXid
nextXid: 0 1 2 3 ... 4294967295 4294967296 4294967297 4294967298 ... 9223372036854775807
xid    : 0 1 2 3 ... 4294967295 0          1          2          ... 4294967295    


ShmemVariableCache->nextXid
nextXid: 9223372036854775807 -9223372036854775808 -9223372036854775807 ... 0
xid    : 4294967295          0                    1                        0

ShmemVariableCache->nextXid Self adding use FullTransactionIdAdvance function

• This function starts from 0 Began to increase nextXid Value , first if Guarantee nextXid Can return to 0、1、2 Value
• rearwards nextXid Add to 4294967296 when , Will go while Loop handle 4294967296、4294967297、4294967298 The value of skips , Because these three values are converted to uint32 It will become 0、1、2, Normal business ID Do not use these three values .
• rearwards nextXid Continue to increase every time you encounter the above situation , Will go while Skip the multiples of these three numbers .

static inline void
FullTransactionIdAdvance(FullTransactionId *dest)
{
	dest->value++;

	/* see FullTransactionIdAdvance() */
	if (FullTransactionIdPrecedes(*dest, FirstNormalFullTransactionId))
		return;

	while (XidFromFullTransactionId(*dest) < FirstNormalTransactionId)
		dest->value++;
}

xid Size judgment rule

has TransactionIdFollows Function as an example , The input parameters are two uint32（0 ~ 2^32-1）.

But when subtracting, the result is saved to diff yes int32（-2^31 ~ 2^31-1）.

typedef uint32 TransactionId;

/*
 * TransactionIdPrecedes --- is id1 logically < id2?
 */
bool
TransactionIdPrecedes(TransactionId id1, TransactionId id2)
{
	/*
	 * If either ID is a permanent XID then we can just do unsigned
	 * comparison.  If both are normal, do a modulo-2^32 comparison.
	 */
	int32		diff;

	if (!TransactionIdIsNormal(id1) || !TransactionIdIsNormal(id2))
		return (id1 < id2);

	diff = (int32) (id1 - id2);
	return (diff < 0);
}

• Be careful (id1 - id2) No matter how you subtract, the result is positive , Because these are two uint32 It's decreasing . This positive result represents the distance between these two values .

The current distance -5

id1 = 4294967290u
id2 = 4294967295u
id1 - id2 = 4294967291u
diff = (int32)(id1 - id2) = -5

id2 Keep growing , however id2 yes uint32 The maximum value is 4294967295u 了 , Continue to grow and overflow

id1 = 4294967290u
id2 = 10u
id1 - id2 = 4294967280u
diff = (int32)(id1 - id2) = -16

You can see the overflow , The result is still negative ,TransactionIdPrecedes The calculation of the function is correct id1 logically < id2.

But if id1 and id2 Too much distance , exceed 2^31 after , for example id2 From just now, 10 Continue to grow to 2147483647,id2 leading id1 The distance has exceeded 2^31：

id1 = 4294967290u
id2 = 2147483647u
id1 - id2 = 2147483643u
diff = (int32)(id1 - id2) = 2147483643

result diff It turned over again and became a positive number , although id1 Logically, it should <id2, But at this moment TransactionIdPrecedes The result has been false 了 .

obviously TransactionIdPrecedes Function calculation error .

summary

So in PG The existing xid Distribution mechanism , In order to ensure xid After rewinding, you can also compare the size correctly , Two xid The distance cannot exceed 2^31.

Convenient memory ： Business ID You can roll back , But the distance from the oldest to the latest cannot exceed 20 Billion , Otherwise, a second symbol flip will occur , Business ID All the calculation results will be wrong .