Subject: Re: Slow standby snapshot

From: Michail Nikolaev <[email-masked]>
Date: Mon, 21 Feb 2022 10:12:56 +0300

Hello, Andrey.

Thanks for your efforts.

> Patch on barrier seems too complicated to me right now. I’d propose to focus on KnowAssignedXidsNext patch: it’s clean, simple and effective.
I'll extract it to the separated patch later.

> I’ve rebased the patch so that it does not depend on previous step. Please check out it’s current state, if you are OK with it - let’s mark the patch Ready for Committer. Just maybe slightly better commit message would make the patch easier to understand.
Everything seems to be correct.

Best regards,
Michail.

---

From: Michail Nikolaev <[email-masked]>
Date: Fri, 1 Apr 2022 02:18:41 +0300

Hello.

Just an updated commit message.

Thanks,
Michail.
From 934d649a18c66f8b448463e57375865b33ce53e7 Mon Sep 17 00:00:00 2001
From: nkey <[email-masked]>
Date: Fri, 1 Apr 2022 02:17:55 +0300
Subject: [PATCH v5] Optimize KnownAssignedXidsGetAndSetXmin by maintaining
 offset to next valid xid.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Currently KnownAssignedXidsGetAndSetXmin requires an iterative loop through KnownAssignedXids array,
including xids marked as invalid. Performance impact is especially noticeable in the presence of
long (few seconds) transactions on primary, high value (few thousands) of max_connections and high
read workload on standby. Most of the cpu spent on looping throw KnownAssignedXids while almost all
xid are invalid anyway. KnownAssignedXidsCompress removes invalid xids from time to time,
but performance is still affected.

To increase performance we lazily maintain an offset in the KnownAssignedXidsNext array to skip known
to be invalid xids. KnownAssignedXidsNext does not always point to “next” valid xid, it is just some
offset safe to skip (known to be filled by only invalid xids).

It helps to skip the gaps and could significantly increase performance - up to 10% more TPS on standby.

Thread: https://www.postgresql.org/message-id/flat/CALdSSPgahNUD_%3DpB_j%3D1zSnDBaiOtqVfzo8Ejt5J_k7qZiU1Tw%40mail.gmail.com

Benchmark:
https://www.postgresql.org/message-id/flat/CANtu0ohzBFTYwdLtcanWo4%2B794WWUi7LY2rnbHyorJdE8_ZnGg%40mail.gmail.com#379c1be7b8134ada5a574078d51b64c6
---
 src/backend/storage/ipc/procarray.c | 56 ++++++++++++++++++++++++-----
 1 file changed, 47 insertions(+), 9 deletions(-)

diff --git a/src/backend/storage/ipc/procarray.c b/src/backend/storage/ipc/procarray.c
index 13d192ec2b..b5cb3423fb 100644
--- a/src/backend/storage/ipc/procarray.c
+++ b/src/backend/storage/ipc/procarray.c
@@ -267,6 +267,7 @@ static PGPROC *allProcs;
  */
 static TransactionId *KnownAssignedXids;
 static bool *KnownAssignedXidsValid;
+static int32 *KnownAssignedXidsNext;
 static TransactionId latestObservedXid = InvalidTransactionId;
 
 /*
@@ -455,6 +456,12 @@ CreateSharedProcArray(void)
 			ShmemInitStruct("KnownAssignedXidsValid",
 							mul_size(sizeof(bool), TOTAL_MAX_CACHED_SUBXIDS),
 							&found);
+		KnownAssignedXidsNext = (int32 *)
+				ShmemInitStruct("KnownAssignedXidsNext",
+								mul_size(sizeof(int32), TOTAL_MAX_CACHED_SUBXIDS),
+								&found);
+		for (int i = 0; i < TOTAL_MAX_CACHED_SUBXIDS; i++)
+			KnownAssignedXidsNext[i] = 1;
 	}
 }
 
@@ -4544,7 +4551,13 @@ ExpireOldKnownAssignedTransactionIds(TransactionId xid)
  * XID entry itself.  This preserves the property that the XID entries are
  * sorted, so we can do binary searches easily.  Periodically we compress
  * out the unused entries; that's much cheaper than having to compress the
- * array immediately on every deletion.
+ * array immediately on every deletion. Also, we lazily maintain an offset
+ * in KnownAssignedXidsNext[] array to skip known to be invalid xids. It
+ * helps to skip the gaps; it could significantly increase performance in
+ * the case of long transactions on the primary. KnownAssignedXidsNext[] is
+ * updating while taking the snapshot. In general case KnownAssignedXidsNext
+ * contains not an offset to the next valid xid but a number which tends to
+ * the offset to next valid xid.
  *
  * The actually valid items in KnownAssignedXids[] and KnownAssignedXidsValid[]
  * are those with indexes tail <= i < head; items outside this subscript range
@@ -4582,7 +4595,7 @@ ExpireOldKnownAssignedTransactionIds(TransactionId xid)
  *		must happen)
  *	* Compressing the array is O(S) and requires exclusive lock
  *	* Removing an XID is O(logS) and requires exclusive lock
- *	* Taking a snapshot is O(S) and requires shared lock
+ *	* Taking a snapshot is O(S), O(N) next call; requires shared lock
  *	* Checking for an XID is O(logS) and requires shared lock
  *
  * In comparison, using a hash table for KnownAssignedXids would mean that
@@ -4642,12 +4655,13 @@ KnownAssignedXidsCompress(bool force)
 	 * re-aligning data to 0th element.
 	 */
 	compress_index = 0;
-	for (i = tail; i < head; i++)
+	for (i = tail; i < head; i += KnownAssignedXidsNext[i])
 	{
 		if (KnownAssignedXidsValid[i])
 		{
 			KnownAssignedXids[compress_index] = KnownAssignedXids[i];
 			KnownAssignedXidsValid[compress_index] = true;
+			KnownAssignedXidsNext[compress_index] = 1;
 			compress_index++;
 		}
 	}
@@ -4750,6 +4764,7 @@ KnownAssignedXidsAdd(TransactionId from_xid, TransactionId to_xid,
 	{
 		KnownAssignedXids[head] = next_xid;
 		KnownAssignedXidsValid[head] = true;
+		KnownAssignedXidsNext[head] = 1;
 		TransactionIdAdvance(next_xid);
 		head++;
 	}
@@ -4965,7 +4980,7 @@ KnownAssignedXidsRemovePreceding(TransactionId removeXid)
 	tail = pArray->tailKnownAssignedXids;
 	head = pArray->headKnownAssignedXids;
 
-	for (i = tail; i < head; i++)
+	for (i = tail; i < head; i += KnownAssignedXidsNext[i])
 	{
 		if (KnownAssignedXidsValid[i])
 		{
@@ -4988,7 +5003,7 @@ KnownAssignedXidsRemovePreceding(TransactionId removeXid)
 	/*
 	 * Advance the tail pointer if we've marked the tail item invalid.
 	 */
-	for (i = tail; i < head; i++)
+	for (i = tail; i < head; i += KnownAssignedXidsNext[i])
 	{
 		if (KnownAssignedXidsValid[i])
 			break;
@@ -5038,7 +5053,9 @@ KnownAssignedXidsGetAndSetXmin(TransactionId *xarray, TransactionId *xmin,
 	int			count = 0;
 	int			head,
 				tail;
-	int			i;
+	int			i,
+				prev,
+				prevOffset;
 
 	/*
 	 * Fetch head just once, since it may change while we loop. We can stop
@@ -5052,9 +5069,12 @@ KnownAssignedXidsGetAndSetXmin(TransactionId *xarray, TransactionId *xmin,
 	SpinLockAcquire(&procArray->known_assigned_xids_lck);
 	tail = procArray->tailKnownAssignedXids;
 	head = procArray->headKnownAssignedXids;
+	prev = tail;
+	prevOffset = KnownAssignedXidsNext[prev];
 	SpinLockRelease(&procArray->known_assigned_xids_lck);
 
-	for (i = tail; i < head; i++)
+
+	for (i = tail; i < head; i += KnownAssignedXidsNext[i])
 	{
 		/* Skip any gaps in the array */
 		if (KnownAssignedXidsValid[i])
@@ -5079,6 +5099,24 @@ KnownAssignedXidsGetAndSetXmin(TransactionId *xarray, TransactionId *xmin,
 
 			/* Add knownXid into output array */
 			xarray[count++] = knownXid;
+
+			if (prev != i)
+			{
+				int32 n = i - prev;
+				/*
+				 * Do not touch the cache if value is unchanged. This way we
+				 * can avoid additional cache miss.
+				 */
+				if (n != prevOffset)
+					KnownAssignedXidsNext[prev] = n;
+				/*
+				 * Remember this xid as previous valid. Also, manually store
+				 * prevOffset from current fetched value to avoid additional
+				 * atomic read.
+				 */
+				prev = i;
+				prevOffset = KnownAssignedXidsNext[i];
+			}
 		}
 	}
 
@@ -5104,7 +5142,7 @@ KnownAssignedXidsGetOldestXmin(void)
 	head = procArray->headKnownAssignedXids;
 	SpinLockRelease(&procArray->known_assigned_xids_lck);
 
-	for (i = tail; i < head; i++)
+	for (i = tail; i < head; i += KnownAssignedXidsNext[i])
 	{
 		/* Skip any gaps in the array */
 		if (KnownAssignedXidsValid[i])
@@ -5139,7 +5177,7 @@ KnownAssignedXidsDisplay(int trace_level)
 
 	initStringInfo(&buf);
 
-	for (i = tail; i < head; i++)
+	for (i = tail; i < head; i += KnownAssignedXidsNext[i])
 	{
 		if (KnownAssignedXidsValid[i])
 		{
-- 
2.17.1

---

From: Michail Nikolaev <[email-masked]>
Date: Sat, 2 Jul 2022 20:32:23 +0300

Hello, Simon.

Sorry for calling you directly, but you know the subject better than
anyone else. It is related to your work from 2010 - replacing
KnownAssignedXidsHash with the KnownAssignedXids array.

I have added additional optimization to the data structure you
implemented. Initially, it was caused by the huge usage of CPU (70%+)
for KnownAssignedXidsGetAndSetXmin in case of long (few seconds)
transactions on primary and high (few thousands) max_connections in
Postgres 11.

After snapshot scalability optimization by Andres Freund (2), it is
not so crucial but still provides a significant performance impact
(+10% TPS) for a typical workload, see benchmark (3).

Last patch version is here - (4).

Does such optimisation look worth committing?

Thanks in advance,
Michail.

[1]: https://github.com/postgres/postgres/commit/2871b4618af1acc85665eec0912c48f8341504c4#diff-8879f0173be303070ab7931db7c757c96796d84402640b9e386a4150ed97b179
[2]: https://commitfest.postgresql.org/29/2500/
[3]: https://www.postgresql.org/message-id/flat/CANtu0ohzBFTYwdLtcanWo4%2B794WWUi7LY2rnbHyorJdE8_ZnGg%40mail.gmail.com#379c1be7b8134ada5a574078d51b64c6
[4]: https://www.postgresql.org/message-id/flat/CANtu0ogzo4MsR7My9%2BNhu3to5%3Dy7G9zSzUbxfWYOn9W5FfHjTA%40mail.gmail.com#341a3c3b033f69b260120b3173a66382

---

From: Andrey Borodin <[email-masked]>
Date: Sun, 3 Jul 2022 14:42:51 +0500

> On 1 Apr 2022, at 04:18, Michail Nikolaev <[email-masked]> wrote:
> 
> Hello.
> 

I've looked into v5.

IMO the purpose of KnownAssignedXidsNext would be slightly more obvious if it was named KnownAssignedXidsNextOffset.
Also please consider some editorialisation:
s/high value/big number/g
KnownAssignedXidsNext[] is updating while taking the snapshot. -> KnownAssignedXidsNext[] is updated during taking the snapshot.
O(N) next call -> amortized O(N) on next call

Is it safe on all platforms to do "KnownAssignedXidsNext[prev] = n;" while only holding shared lock? I think it is, per Alexander's comment, but maybe let's document it?

Thank you!

Thanks! Best regards, Andrey Borodin.

---

From: Michail Nikolaev <[email-masked]>
Date: Wed, 20 Jul 2022 00:12:39 +0300

Hello, Andrey.

> I've looked into v5.
Thanks!

Patch is updated accordingly your remarks.

Best regards,
Michail.
From 1301a262dea7f541c11092851e82f10932150ee3 Mon Sep 17 00:00:00 2001
From: Michail Nikolaev <[email-masked]>
Date: Tue, 19 Jul 2022 23:50:53 +0300
Subject: [PATCH v6] Currently KnownAssignedXidsGetAndSetXmin requires an
 iterative loop through KnownAssignedXids array, including xids marked as
 invalid. Performance impact is especially noticeable in the presence of long
 (few seconds) transactions on primary, big number (few thousands) of
 max_connections and high read workload on standby. Most of the cpu spent on
 looping throw KnownAssignedXids while almost all xid are invalid anyway.
 KnownAssignedXidsCompress removes invalid xids from time to time, but
 performance is still affected.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

To increase performance we lazily maintain an offset in the KnownAssignedXidsNextOffset array to skip known
to be invalid xids. KnownAssignedXidsNextOffset does not always point to “next” valid xid, it is just some
offset safe to skip (known to be filled by only invalid xids).
---
 src/backend/storage/ipc/procarray.c | 57 ++++++++++++++++++++++++-----
 1 file changed, 48 insertions(+), 9 deletions(-)

diff --git a/src/backend/storage/ipc/procarray.c b/src/backend/storage/ipc/procarray.c
index dadaa958a8..f613ae2f09 100644
--- a/src/backend/storage/ipc/procarray.c
+++ b/src/backend/storage/ipc/procarray.c
@@ -271,6 +271,7 @@ static TransactionId cachedXidIsNotInProgress = InvalidTransactionId;
  */
 static TransactionId *KnownAssignedXids;
 static bool *KnownAssignedXidsValid;
+static int32 *KnownAssignedXidsNextOffset;
 static TransactionId latestObservedXid = InvalidTransactionId;
 
 /*
@@ -450,6 +451,12 @@ CreateSharedProcArray(void)
 			ShmemInitStruct("KnownAssignedXidsValid",
 							mul_size(sizeof(bool), TOTAL_MAX_CACHED_SUBXIDS),
 							&found);
+		KnownAssignedXidsNextOffset = (int32 *)
+				ShmemInitStruct("KnownAssignedXidsNextOffset",
+								mul_size(sizeof(int32), TOTAL_MAX_CACHED_SUBXIDS),
+								&found);
+		for (int i = 0; i < TOTAL_MAX_CACHED_SUBXIDS; i++)
+			KnownAssignedXidsNextOffset[i] = 1;
 	}
 }
 
@@ -4539,7 +4546,15 @@ ExpireOldKnownAssignedTransactionIds(TransactionId xid)
  * XID entry itself.  This preserves the property that the XID entries are
  * sorted, so we can do binary searches easily.  Periodically we compress
  * out the unused entries; that's much cheaper than having to compress the
- * array immediately on every deletion.
+ * array immediately on every deletion. Also, we lazily maintain an offset
+ * in KnownAssignedXidsNextOffset[] array to skip known to be invalid xids.
+ * It helps to skip the gaps; it could significantly increase performance in
+ * the case of long transactions on the primary. KnownAssignedXidsNextOffset
+ * is s updated during taking the snapshot. The KnownAssignedXidsNextOffset
+ * contains not an offset to the next valid xid but a number which tends to
+ * the offset to next valid xid. KnownAssignedXidsNextOffset[] values read
+ * and updated without additional locking because four-bytes read-writes are
+ * assumed to be atomic.
  *
  * The actually valid items in KnownAssignedXids[] and KnownAssignedXidsValid[]
  * are those with indexes tail <= i < head; items outside this subscript range
@@ -4577,7 +4592,7 @@ ExpireOldKnownAssignedTransactionIds(TransactionId xid)
  *		must happen)
  *	* Compressing the array is O(S) and requires exclusive lock
  *	* Removing an XID is O(logS) and requires exclusive lock
- *	* Taking a snapshot is O(S) and requires shared lock
+ *	* Taking a snapshot is O(S), amortized O(N) next call; requires shared lock
  *	* Checking for an XID is O(logS) and requires shared lock
  *
  * In comparison, using a hash table for KnownAssignedXids would mean that
@@ -4637,12 +4652,13 @@ KnownAssignedXidsCompress(bool force)
 	 * re-aligning data to 0th element.
 	 */
 	compress_index = 0;
-	for (i = tail; i < head; i++)
+	for (i = tail; i < head; i += KnownAssignedXidsNextOffset[i])
 	{
 		if (KnownAssignedXidsValid[i])
 		{
 			KnownAssignedXids[compress_index] = KnownAssignedXids[i];
 			KnownAssignedXidsValid[compress_index] = true;
+			KnownAssignedXidsNextOffset[compress_index] = 1;
 			compress_index++;
 		}
 	}
@@ -4745,6 +4761,7 @@ KnownAssignedXidsAdd(TransactionId from_xid, TransactionId to_xid,
 	{
 		KnownAssignedXids[head] = next_xid;
 		KnownAssignedXidsValid[head] = true;
+		KnownAssignedXidsNextOffset[head] = 1;
 		TransactionIdAdvance(next_xid);
 		head++;
 	}
@@ -4960,7 +4977,7 @@ KnownAssignedXidsRemovePreceding(TransactionId removeXid)
 	tail = pArray->tailKnownAssignedXids;
 	head = pArray->headKnownAssignedXids;
 
-	for (i = tail; i < head; i++)
+	for (i = tail; i < head; i += KnownAssignedXidsNextOffset[i])
 	{
 		if (KnownAssignedXidsValid[i])
 		{
@@ -4983,7 +5000,7 @@ KnownAssignedXidsRemovePreceding(TransactionId removeXid)
 	/*
 	 * Advance the tail pointer if we've marked the tail item invalid.
 	 */
-	for (i = tail; i < head; i++)
+	for (i = tail; i < head; i += KnownAssignedXidsNextOffset[i])
 	{
 		if (KnownAssignedXidsValid[i])
 			break;
@@ -5033,7 +5050,9 @@ KnownAssignedXidsGetAndSetXmin(TransactionId *xarray, TransactionId *xmin,
 	int			count = 0;
 	int			head,
 				tail;
-	int			i;
+	int			i,
+				prev,
+				prevOffset;
 
 	/*
 	 * Fetch head just once, since it may change while we loop. We can stop
@@ -5047,9 +5066,11 @@ KnownAssignedXidsGetAndSetXmin(TransactionId *xarray, TransactionId *xmin,
 	SpinLockAcquire(&procArray->known_assigned_xids_lck);
 	tail = procArray->tailKnownAssignedXids;
 	head = procArray->headKnownAssignedXids;
+	prev = tail;
+	prevOffset = KnownAssignedXidsNextOffset[prev];
 	SpinLockRelease(&procArray->known_assigned_xids_lck);
 
-	for (i = tail; i < head; i++)
+	for (i = tail; i < head; i += KnownAssignedXidsNextOffset[i])
 	{
 		/* Skip any gaps in the array */
 		if (KnownAssignedXidsValid[i])
@@ -5074,6 +5095,24 @@ KnownAssignedXidsGetAndSetXmin(TransactionId *xarray, TransactionId *xmin,
 
 			/* Add knownXid into output array */
 			xarray[count++] = knownXid;
+
+			if (prev != i)
+			{
+				int32 n = i - prev;
+				/*
+				 * Do not touch the cache if value is unchanged. This way we
+				 * can avoid additional cache miss.
+				 */
+				if (n != prevOffset)
+					KnownAssignedXidsNextOffset[prev] = n;
+				/*
+				 * Remember this xid as previous valid. Also, manually store
+				 * prevOffset from current fetched value to avoid additional
+				 * atomic read.
+				 */
+				prev = i;
+				prevOffset = KnownAssignedXidsNextOffset[i];
+			}
 		}
 	}
 
@@ -5099,7 +5138,7 @@ KnownAssignedXidsGetOldestXmin(void)
 	head = procArray->headKnownAssignedXids;
 	SpinLockRelease(&procArray->known_assigned_xids_lck);
 
-	for (i = tail; i < head; i++)
+	for (i = tail; i < head; i += KnownAssignedXidsNextOffset[i])
 	{
 		/* Skip any gaps in the array */
 		if (KnownAssignedXidsValid[i])
@@ -5134,7 +5173,7 @@ KnownAssignedXidsDisplay(int trace_level)
 
 	initStringInfo(&buf);
 
-	for (i = tail; i < head; i++)
+	for (i = tail; i < head; i += KnownAssignedXidsNextOffset[i])
 	{
 		if (KnownAssignedXidsValid[i])
 		{
-- 
2.25.1

---

From: Andrey Borodin <[email-masked]>
Date: Tue, 26 Jul 2022 23:09:16 +0500

> On 20 Jul 2022, at 02:12, Michail Nikolaev <[email-masked]> wrote:
> 
>> I've looked into v5.
> Thanks!
> 

The patch seems Ready for Committer from my POV.

Thanks!

Best regards, Andrey Borodin.

---

From: Kyotaro Horiguchi <[email-masked]>
Date: Wed, 27 Jul 2022 16:08:07 +0900 (JST)

At Tue, 26 Jul 2022 23:09:16 +0500, Andrey Borodin <[email-masked]> wrote in 

Is there still a reason why the array stores the distnace to the next
valid element instead of the index number of the next valid index?  It
seems to me that that was in an intention to reduce the size of the
offset array but it is int32[] which is far wider than
TOTAL_MAX_CACHED_SUBXIDS.

It seems to me storing the index itself is simpler and maybe faster by
the cycles to perform addition.

regards.

-- 
Kyotaro Horiguchi
NTT Open Source Software Center

---

From: Simon Riggs <[email-masked]>
Date: Fri, 29 Jul 2022 16:08:38 +0100

> the cycles to perform addition.

I'm inclined to think this is all too much. All of this optimization
makes sense when the array spreads out horribly, but we should be just
avoiding that in the first place by compressing more often.

The original coded frequency of compression was just a guess and was
never tuned later.

A simple patch like this seems to hit the main concern, aiming to keep
the array from spreading out and impacting snapshot performance for
SELECTs, yet not doing it so often that the startup process has a
higher burden of work.

-- 
Simon Riggs                http://www.EnterpriseDB.com/

---

From: Michail Nikolaev <[email-masked]>
Date: Fri, 29 Jul 2022 20:24:30 +0300

Hello.

Thanks to everyone for the review.

> the cycles to perform addition.

Yes, first version used 1-byte for offset with maximum value of 255.
Agreed, looks like there is no sense to store offsets now.

> SELECTs, yet not doing it so often that the startup process has a

Nice, I'll do performance testing for both versions and master branch
as baseline.

Thanks,
Michail.