From 6b22d2e63d061be465e9e9f5ce2fefdaae6ebf0e Mon Sep 17 00:00:00 2001
From: Yura Sokolov <y.sokolov@postgrespro.ru>
Date: Thu, 16 Jan 2025 15:30:57 +0300
Subject: [PATCH v10 2/2] Several attempts to lock WALInsertLocks.

Birthday paradox tells we could get collision with 34% probability with
just 3, 58% with 4 and 79% with 5 concurrent processes
(when NUM_XLOGINSERT_LOCKS == 8).

Trying several times to lock conditionally with just linear increase by
random delta, will reduce probability of blocking greatly:
- with 1 conditional attempt - 4%, 14% and 33% respectively
- with 2 conditional attempts - 0%, 2.1% and 9.7%
- with 3 conditional attempts - 0%, 0% and 1.85%

Probabilities are calculated with simple Ruby program:
  def try_add(arr, n)
    a, b = rand(8), rand(8)|1
    n.times {
      (arr << a; break) unless arr.include?(a)
      a = (a + b) % 8
    }
  end
  def calc_prob(n, k)
    300000.times.
       map{ ar=[]; n.times{ try_add(ar, k) }; ar}.
       count{|a| a.length < n} / 300000.0 * 100
  end
  (3..5).each{|n| (1..5).each{|k| p [n,k,calc_prob(n, k).round(2)]}}

Given every attempt is a cache miss, 2 attempts following non-conditional
lock looks to be good compromise.
---
 src/backend/access/transam/xlog.c | 44 ++++++++++++++++++++-----------
 1 file changed, 28 insertions(+), 16 deletions(-)

diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index c232ba2d599..13fb1c35ad8 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -68,6 +68,7 @@
 #include "catalog/pg_database.h"
 #include "common/controldata_utils.h"
 #include "common/file_utils.h"
+#include "common/pg_prng.h"
 #include "executor/instrument.h"
 #include "miscadmin.h"
 #include "pg_trace.h"
@@ -1376,7 +1377,11 @@ CopyXLogRecordToWAL(int write_len, bool isLogSwitch, XLogRecData *rdata,
 static void
 WALInsertLockAcquire(void)
 {
-	bool		immed;
+	/*
+	 * Two conditional attempts looks to be good compromise between good
+	 * probability to acquire lock and cache misses on every attempt.
+	 */
+	int			attempts = 2;
 
 	/*
 	 * It doesn't matter which of the WAL insertion locks we acquire, so try
@@ -1389,29 +1394,36 @@ WALInsertLockAcquire(void)
 	 * (semi-)randomly.  This allows the locks to be used evenly if you have a
 	 * lot of very short connections.
 	 */
-	static int	lockToTry = -1;
+	static uint32 lockToTry = 0;
+	static uint32 lockDelta = 0;
 
-	if (lockToTry == -1)
+	if (lockDelta == 0)
+	{
 		lockToTry = MyProcNumber % NUM_XLOGINSERT_LOCKS;
+		lockDelta = pg_prng_uint32(&pg_global_prng_state) % NUM_XLOGINSERT_LOCKS;
+		lockDelta |= 1;			/* must be odd */
+		StaticAssertStmt((NUM_XLOGINSERT_LOCKS & (NUM_XLOGINSERT_LOCKS - 1)) == 0,
+						 "NUM_XLOGINSERT_LOCKS must be power of 2");
+	}
+
 	MyLockNo = lockToTry;
 
-	/*
-	 * The insertingAt value is initially set to 0, as we don't know our
-	 * insert location yet.
-	 */
-	immed = LWLockAcquire(&WALInsertLocks[MyLockNo].l.lock, LW_EXCLUSIVE);
-	if (!immed)
+	while (attempts-- > 0)
 	{
+		if (LWLockConditionalAcquire(&WALInsertLocks[MyLockNo].l.lock, LW_EXCLUSIVE))
+			return;
+
 		/*
-		 * If we couldn't get the lock immediately, try another lock next
-		 * time.  On a system with more insertion locks than concurrent
-		 * inserters, this causes all the inserters to eventually migrate to a
-		 * lock that no-one else is using.  On a system with more inserters
-		 * than locks, it still helps to distribute the inserters evenly
-		 * across the locks.
+		 * If we couldn't get the lock immediately, try another lock. On a
+		 * system with more insertion locks than concurrent inserters, this
+		 * causes all the inserters to eventually migrate to a lock that
+		 * no-one else is using.  On a system with more inserters than locks,
+		 * it still helps to distribute the inserters evenly across the locks.
 		 */
-		lockToTry = (lockToTry + 1) % NUM_XLOGINSERT_LOCKS;
+		lockToTry = (lockToTry + lockDelta) % NUM_XLOGINSERT_LOCKS;
+		MyLockNo = lockToTry;
 	}
+	LWLockAcquire(&WALInsertLocks[MyLockNo].l.lock, LW_EXCLUSIVE);
 }
 
 /*
-- 
2.43.0