[Bossart, Nathan <bossartn@amazon.com>]

On 5/4/21, 7:07 AM, "Robert Haas" <robertmhaas@gmail.com> wrote:
> On Tue, May 4, 2021 at 12:27 AM Andres Freund <andres@anarazel.de> wrote:
>> On 2021-05-03 16:49:16 -0400, Robert Haas wrote:
>> > I have two possible ideas for addressing this; perhaps other people
>> > will have further suggestions. A relatively non-invasive fix would be
>> > to teach pgarch.c how to increment a WAL file name. After archiving
>> > segment N, check using stat() whether there's an .ready file for
>> > segment N+1. If so, do that one next. If not, then fall back to
>> > performing a full directory scan.
>>
>> Hm. I wonder if it'd not be better to determine multiple files to be
>> archived in one readdir() pass?
>
> I think both methods have some merit. If we had a way to pass a range
> of files to archive_command instead of just one, then your way is
> distinctly better, and perhaps we should just go ahead and invent such
> a thing. If not, your way doesn't entirely solve the O(n^2) problem,
> since you have to choose some upper bound on the number of file names
> you're willing to buffer in memory, but it may lower it enough that it
> makes no practical difference. I am somewhat inclined to think that it
> would be good to start with the method I'm proposing, since it is a
> clear-cut improvement over what we have today and can be done with a
> relatively limited amount of code change and no redesign, and then
> perhaps do something more ambitious afterward.

I was curious about this, so I wrote a patch (attached) to store
multiple files per directory scan and tested it against the latest
patch in this thread (v9) [0].  Specifically, I set archive_command to
'false', created ~20K WAL segments, then restarted the server with
archive_command set to 'true'.  Both the v9 patch and the attached
patch completed archiving all segments in just under a minute.  (I
tested the attached patch with NUM_FILES_PER_DIRECTORY_SCAN set to 64,
128, and 256 and didn't observe any significant difference.)  The
existing logic took over 4 minutes to complete.

I'm hoping to do this test again with many more (100K+) status files,
as I believe that the v9 patch will be faster at that scale, but I'm
not sure how much faster it will be.

Nathan

[0] https://www.postgresql.org/message-id/attachment/125543/v9-0001-mitigate-directory-scan-for-WAL-arch...



Attachments:

  [application/octet-stream] v1-0001-Improve-performance-of-pgarch_readyXlog-with-many.patch (10.3K, ../620F3CE1-0255-4D66-9D87-0EADE866985A@amazon.com/2-v1-0001-Improve-performance-of-pgarch_readyXlog-with-many.patch)
  download | inline diff:
From 0fe199f920189a248d6e96c9501a11fe21559e68 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <bossartn@amazon.com>
Date: Sun, 22 Aug 2021 04:19:18 +0000
Subject: [PATCH v1 1/1] Improve performance of pgarch_readyXlog() with many
 status files.

Presently, the archive_status directory is scanned for each file to
archive.  When there are many status files (e.g., archive_command
has been failing for a long time), these directory scans can take
much longer, which significantly slows the rate of archival.  With
this change, the archiver stores several files to archive in each
directory scan, which improves the rate of archival when there are
many files in archive_status.  To ensure timeline history files are
archived as quickly as possible, XLogArchiveNotify() forces the
archiver to do a new directory scan as soon as the .ready file for
one is created.
---
 src/backend/access/transam/xlogarchive.c |   4 +
 src/backend/postmaster/pgarch.c          | 177 +++++++++++++++++++++++++++----
 src/include/postmaster/pgarch.h          |   1 +
 3 files changed, 162 insertions(+), 20 deletions(-)

diff --git a/src/backend/access/transam/xlogarchive.c b/src/backend/access/transam/xlogarchive.c
index 26b023e754..3809796709 100644
--- a/src/backend/access/transam/xlogarchive.c
+++ b/src/backend/access/transam/xlogarchive.c
@@ -489,6 +489,10 @@ XLogArchiveNotify(const char *xlog)
 		return;
 	}
 
+	/* Archive timeline history files as soon as possible. */
+	if (IsTLHistoryFileName(xlog))
+		PgArchForceDirScan();
+
 	/* Notify archiver that it's got something to do */
 	if (IsUnderPostmaster)
 		PgArchWakeup();
diff --git a/src/backend/postmaster/pgarch.c b/src/backend/postmaster/pgarch.c
index 74a7d7c4d0..4121d05a6e 100644
--- a/src/backend/postmaster/pgarch.c
+++ b/src/backend/postmaster/pgarch.c
@@ -35,6 +35,7 @@
 
 #include "access/xlog.h"
 #include "access/xlog_internal.h"
+#include "lib/binaryheap.h"
 #include "libpq/pqsignal.h"
 #include "miscadmin.h"
 #include "pgstat.h"
@@ -47,6 +48,7 @@
 #include "storage/proc.h"
 #include "storage/procsignal.h"
 #include "storage/shmem.h"
+#include "storage/spin.h"
 #include "utils/guc.h"
 #include "utils/ps_status.h"
 
@@ -72,10 +74,23 @@
  */
 #define NUM_ORPHAN_CLEANUP_RETRIES 3
 
+/*
+ * Maximum number of .ready files to gather per directory scan.
+ */
+#define NUM_FILES_PER_DIRECTORY_SCAN 64
+
 /* Shared memory area for archiver process */
 typedef struct PgArchData
 {
 	int			pgprocno;		/* pgprocno of archiver process */
+
+	/*
+	 * Forces a directory scan in pgarch_readyXlog().  Protected by
+	 * arch_lck.
+	 */
+	bool		force_dir_scan;
+
+	slock_t		arch_lck;
 } PgArchData;
 
 
@@ -86,6 +101,22 @@ typedef struct PgArchData
 static time_t last_sigterm_time = 0;
 static PgArchData *PgArch = NULL;
 
+/*
+ * Stuff for tracking multiple files to archive for each directory scan.
+ * Minimizing the number of directory scans when there are many files to
+ * archive can significantly improve archival rate.
+ *
+ * arch_heap is a max-heap that is used during the directory scan to track
+ * the highest-priority files to archive.  After the directory scan
+ * completes, the file names are stored in ascending order of priority in
+ * arch_files.  pgarch_readyXlog() returns files from arch_files until it
+ * is empty, at which point another directory scan must be performed.
+ */
+static binaryheap *arch_heap = NULL;
+static char arch_filenames[NUM_FILES_PER_DIRECTORY_SCAN][MAX_XFN_CHARS];
+static char *arch_files[NUM_FILES_PER_DIRECTORY_SCAN];
+static int arch_files_size = 0;
+
 /*
  * Flags set by interrupt handlers for later service in the main loop.
  */
@@ -103,6 +134,7 @@ static bool pgarch_readyXlog(char *xlog);
 static void pgarch_archiveDone(char *xlog);
 static void pgarch_die(int code, Datum arg);
 static void HandlePgArchInterrupts(void);
+static int ready_file_comparator(Datum a, Datum b, void *arg);
 
 /* Report shared memory space needed by PgArchShmemInit */
 Size
@@ -129,6 +161,7 @@ PgArchShmemInit(void)
 		/* First time through, so initialize */
 		MemSet(PgArch, 0, PgArchShmemSize());
 		PgArch->pgprocno = INVALID_PGPROCNO;
+		SpinLockInit(&PgArch->arch_lck);
 	}
 }
 
@@ -198,6 +231,10 @@ PgArchiverMain(void)
 	 */
 	PgArch->pgprocno = MyProc->pgprocno;
 
+	/* Initialize our max-heap for prioritizing files to archive. */
+	arch_heap = binaryheap_allocate(NUM_FILES_PER_DIRECTORY_SCAN,
+									ready_file_comparator, NULL);
+
 	pgarch_MainLoop();
 
 	proc_exit(0);
@@ -363,6 +400,10 @@ pgarch_ArchiverCopyLoop(void)
 			{
 				ereport(WARNING,
 						(errmsg("archive_mode enabled, yet archive_command is not set")));
+
+				/* force directory scan during next call */
+				arch_files_size = 0;
+
 				return;
 			}
 
@@ -397,6 +438,9 @@ pgarch_ArchiverCopyLoop(void)
 							(errmsg("removal of orphan archive status file \"%s\" failed too many times, will try again later",
 									xlogready)));
 
+					/* force directory scan during next call */
+					arch_files_size = 0;
+
 					/* give up cleanup of orphan status files */
 					return;
 				}
@@ -432,6 +476,10 @@ pgarch_ArchiverCopyLoop(void)
 					ereport(WARNING,
 							(errmsg("archiving write-ahead log file \"%s\" failed too many times, will try again later",
 									xlog)));
+
+					/* force directory scan during next call */
+					arch_files_size = 0;
+
 					return;		/* give up archiving for now */
 				}
 				pg_usleep(1000000L);	/* wait a bit before retrying */
@@ -609,8 +657,35 @@ pgarch_readyXlog(char *xlog)
 	char		XLogArchiveStatusDir[MAXPGPATH];
 	DIR		   *rldir;
 	struct dirent *rlde;
-	bool		found = false;
-	bool		historyFound = false;
+
+	/*
+	 * If we still have files from the last directory scan to process, return
+	 * those.
+	 */
+	if (arch_files_size > 0)
+	{
+		bool force_dir_scan;
+
+		SpinLockAcquire(&PgArch->arch_lck);
+		force_dir_scan = PgArch->force_dir_scan;
+		PgArch->force_dir_scan = false;
+		SpinLockRelease(&PgArch->arch_lck);
+
+		/*
+		 * If a directory scan was requested, clear the stored file names and
+		 * proceed.  Otherwise, return the highest priority file from the array,
+		 * which will be the last element.
+		 */
+		if (force_dir_scan)
+			arch_files_size = 0;
+		else
+		{
+			arch_files_size--;
+			strcpy(xlog, arch_files[arch_files_size]);
+
+			return true;
+		}
+	}
 
 	snprintf(XLogArchiveStatusDir, MAXPGPATH, XLOGDIR "/archive_status");
 	rldir = AllocateDir(XLogArchiveStatusDir);
@@ -619,7 +694,7 @@ pgarch_readyXlog(char *xlog)
 	{
 		int			basenamelen = (int) strlen(rlde->d_name) - 6;
 		char		basename[MAX_XFN_CHARS + 1];
-		bool		ishistory;
+		char	   *arch_file;
 
 		/* Ignore entries with unexpected number of characters */
 		if (basenamelen < MIN_XFN_CHARS ||
@@ -638,32 +713,94 @@ pgarch_readyXlog(char *xlog)
 		memcpy(basename, rlde->d_name, basenamelen);
 		basename[basenamelen] = '\0';
 
-		/* Is this a history file? */
-		ishistory = IsTLHistoryFileName(basename);
-
 		/*
-		 * Consume the file to archive.  History files have the highest
-		 * priority.  If this is the first file or the first history file
-		 * ever, copy it.  In the presence of a history file already chosen as
-		 * target, ignore all other files except history files which have been
-		 * generated for an older timeline than what is already chosen as
-		 * target to archive.
+		 * Store the file in our max-heap if it has a high enough priority.
 		 */
-		if (!found || (ishistory && !historyFound))
+		if (arch_heap->bh_size < NUM_FILES_PER_DIRECTORY_SCAN)
 		{
-			strcpy(xlog, basename);
-			found = true;
-			historyFound = ishistory;
+			/* If the heap isn't full yet, quickly add it. */
+			arch_file = arch_filenames[arch_heap->bh_size];
+			strcpy(arch_file, basename);
+			binaryheap_add_unordered(arch_heap, CStringGetDatum(arch_file));
+
+			/* If we just filled the heap, make it a valid one. */
+			if (arch_heap->bh_size == NUM_FILES_PER_DIRECTORY_SCAN)
+				binaryheap_build(arch_heap);
 		}
-		else if (ishistory || !historyFound)
+		else if (ready_file_comparator(binaryheap_first(arch_heap),
+									   CStringGetDatum(basename), NULL) > 0)
 		{
-			if (strcmp(basename, xlog) < 0)
-				strcpy(xlog, basename);
+			/*
+			 * Remove the lowest priority file and add the current one to
+			 * the heap.
+			 */
+			arch_file = DatumGetCString(binaryheap_remove_first(arch_heap));
+			strcpy(arch_file, basename);
+			binaryheap_add(arch_heap, CStringGetDatum(arch_file));
 		}
 	}
 	FreeDir(rldir);
 
-	return found;
+	/* If no files were found, simply return. */
+	if (arch_heap->bh_size == 0)
+		return false;
+
+	/*
+	 * If we didn't fill the heap, we didn't make it a valid one.  Do that
+	 * now.
+	 */
+	if (arch_heap->bh_size < NUM_FILES_PER_DIRECTORY_SCAN)
+		binaryheap_build(arch_heap);
+
+	/*
+	 * Fill arch_files array with the files to archive in ascending order
+	 * of priority.
+	 */
+	arch_files_size = arch_heap->bh_size;
+	for (int i = 0; i < arch_files_size; i++)
+		arch_files[i] = DatumGetCString(binaryheap_remove_first(arch_heap));
+
+	/* Return the highest priority file. */
+	arch_files_size--;
+	strcpy(xlog, arch_files[arch_files_size]);
+
+	return true;
+}
+
+/*
+ * ready_file_comparator
+ *
+ * Compares the archival priority of the given files to archive.
+ */
+static int
+ready_file_comparator(Datum a, Datum b, void *arg)
+{
+	char *a_str = DatumGetCString(a);
+	char *b_str = DatumGetCString(b);
+	bool a_history = IsTLHistoryFileName(a_str);
+	bool b_history = IsTLHistoryFileName(b_str);
+
+	/* Timeline history files always have the highest priority. */
+	if (a_history != b_history)
+		return a_history ? -1 : 1;
+
+	/* Priority is given to older files. */
+	return strcmp(a_str, b_str);
+}
+
+/*
+ * PgArchForceDirScan
+ *
+ * When called, the next call to pgarch_readyXlog() will perform a
+ * directory scan.  This is useful for ensuring that important files such
+ * as timeline history files are archived as quickly as possible.
+ */
+void
+PgArchForceDirScan(void)
+{
+	SpinLockAcquire(&PgArch->arch_lck);
+	PgArch->force_dir_scan = true;
+	SpinLockRelease(&PgArch->arch_lck);
 }
 
 /*
diff --git a/src/include/postmaster/pgarch.h b/src/include/postmaster/pgarch.h
index 1e47a143e1..732615be57 100644
--- a/src/include/postmaster/pgarch.h
+++ b/src/include/postmaster/pgarch.h
@@ -31,5 +31,6 @@ extern void PgArchShmemInit(void);
 extern bool PgArchCanRestart(void);
 extern void PgArchiverMain(void) pg_attribute_noreturn();
 extern void PgArchWakeup(void);
+extern void PgArchForceDirScan(void);
 
 #endif							/* _PGARCH_H */
-- 
2.16.6