From d67278a64983b5f2eb5e408a51e9516aa8fd2264 Mon Sep 17 00:00:00 2001 From: Tomas Vondra Date: Thu, 22 May 2025 18:38:41 +0200 Subject: [PATCH v2 4/7] NUMA: partition buffer freelist Instead of a single buffer freelist, partition into multiple smaller lists, to reduce lock contention, and to spread the buffers over all NUMA nodes more evenly. There are four strategies, specified by GUC numa_partition_freelist * none - single long freelist, should work just like now * node - one freelist per NUMA node, with only buffers from that node * cpu - one freelist per CPU * pid - freelist determined by PID (same number of freelists as 'cpu') When allocating a buffer, it's taken from the correct freelist (e.g. same NUMA node). Note: This is (probably) more important than partitioning ProcArray. --- src/backend/storage/buffer/buf_init.c | 4 +- src/backend/storage/buffer/freelist.c | 372 ++++++++++++++++++++++++-- src/backend/utils/init/globals.c | 1 + src/backend/utils/misc/guc_tables.c | 10 + src/include/miscadmin.h | 1 + src/include/storage/bufmgr.h | 8 + 6 files changed, 367 insertions(+), 29 deletions(-) diff --git a/src/backend/storage/buffer/buf_init.c b/src/backend/storage/buffer/buf_init.c index 2ad34624c49..920f1a32a8f 100644 --- a/src/backend/storage/buffer/buf_init.c +++ b/src/backend/storage/buffer/buf_init.c @@ -543,8 +543,8 @@ pg_numa_interleave_memory(char *startptr, char *endptr, * XXX no return value, to make this fail on error, has to use * numa_set_strict * - * XXX Should we still touch the memory first, like with numa_move_pages, - * or is that not necessary? + * XXX Should we still touch the memory first, like with + * numa_move_pages, or is that not necessary? */ numa_tonode_memory(ptr, sz, node); diff --git a/src/backend/storage/buffer/freelist.c b/src/backend/storage/buffer/freelist.c index e046526c149..e38e5c7ec3d 100644 --- a/src/backend/storage/buffer/freelist.c +++ b/src/backend/storage/buffer/freelist.c @@ -15,14 +15,52 @@ */ #include "postgres.h" +#include +#include + +#ifdef USE_LIBNUMA +#include +#include +#endif + #include "pgstat.h" #include "port/atomics.h" #include "storage/buf_internals.h" #include "storage/bufmgr.h" +#include "storage/ipc.h" #include "storage/proc.h" #define INT_ACCESS_ONCE(var) ((int)(*((volatile int *)&(var)))) +/* + * Represents one freelist partition. + */ +typedef struct BufferStrategyFreelist +{ + /* Spinlock: protects the values below */ + slock_t freelist_lock; + + /* + * XXX Not sure why this needs to be aligned like this. Need to ask + * Andres. + */ + int firstFreeBuffer __attribute__((aligned(64))); /* Head of list of + * unused buffers */ + + /* Number of buffers consumed from this list. */ + uint64 consumed; +} BufferStrategyFreelist; + +/* + * The minimum number of partitions we want to have. We want at least this + * number of partitions, even on non-NUMA system, as it helps with contention + * for buffers. But with multiple NUMA nodes, we want a separate partition per + * node. But we may get multiple partitions per node, for low node count. + * + * With multiple partitions per NUMA node, we pick the partition based on CPU + * (or some other parameter). + */ +#define MIN_FREELIST_PARTITIONS 4 /* * The shared freelist control information. @@ -39,8 +77,6 @@ typedef struct */ pg_atomic_uint32 nextVictimBuffer; - int firstFreeBuffer; /* Head of list of unused buffers */ - /* * Statistics. These counters should be wide enough that they can't * overflow during a single bgwriter cycle. @@ -51,13 +87,38 @@ typedef struct /* * Bgworker process to be notified upon activity or -1 if none. See * StrategyNotifyBgWriter. + * + * XXX Not sure why this needs to be aligned like this. Need to ask + * Andres. Also, shouldn't the alignment be specified after, like for + * "consumed"? */ - int bgwprocno; + int __attribute__((aligned(64))) bgwprocno; + + /* info about freelist partitioning */ + int num_partitions; + int num_partitions_groups; /* effectively num of NUMA nodes */ + int num_partitions_per_group; + + BufferStrategyFreelist freelists[FLEXIBLE_ARRAY_MEMBER]; } BufferStrategyControl; /* Pointers to shared state */ static BufferStrategyControl *StrategyControl = NULL; +/* + * XXX shouldn't this be in BufferStrategyControl? Probably not, we need to + * calculate it during sizing, and perhaps it could change before the memory + * gets allocated (so we need to remember the values). + * + * XXX We should probably have a fixed number of partitions, and map the + * NUMA nodes to them, somehow (i.e. each node would get some subset of + * partitions). Similar to NUM_LOCK_PARTITIONS. + * + * XXX We don't use the ncpus, really. + */ +static int strategy_ncpus; +static int strategy_nnodes; + /* * Private (non-shared) state for managing a ring of shared buffers to re-use. * This is currently the only kind of BufferAccessStrategy object, but someday @@ -157,6 +218,104 @@ ClockSweepTick(void) return victim; } +/* + * Size the clocksweep partitions. At least one partition per NUMA node, + * but at least MIN_FREELIST_PARTITIONS partitions in total. +*/ +static int +calculate_partition_count(int num_nodes) +{ + int num_per_node = 1; + + while (num_per_node * num_nodes < MIN_FREELIST_PARTITIONS) + num_per_node++; + + return (num_nodes * num_per_node); +} + +static int +calculate_partition_index() +{ + int rc; + unsigned cpu; + unsigned node; + int index; + + Assert(StrategyControl->num_partitions_groups == strategy_nnodes); + + Assert(StrategyControl->num_partitions == + (strategy_nnodes * StrategyControl->num_partitions_per_group)); + + /* + * freelist is partitioned, so determine the CPU/NUMA node, and pick a + * list based on that. + */ + rc = getcpu(&cpu, &node); + if (rc != 0) + elog(ERROR, "getcpu failed: %m"); + + /* + * XXX We should't get nodes that we haven't considered while building + * the partitions. Maybe if we allow this (e.g. due to support adjusting + * the NUMA stuff at runtime), we should just do our best to minimize + * the conflicts somehow. But it'll make the mapping harder, so for now + * we ignore it. + */ + if (node > strategy_nnodes) + elog(ERROR, "node out of range: %d > %u", cpu, strategy_nnodes); + + /* + * Find the partition. If we have a single partition per node, we can + * calculate the index directly from node. Otherwise we need to do two + * steps, using node and then cpu. + */ + if (StrategyControl->num_partitions_per_group == 1) + { + index = (node % StrategyControl->num_partitions); + } + else + { + int index_group, + index_part; + + /* two steps - calculate group from node, partition from cpu */ + index_group = (node % StrategyControl->num_partitions_groups); + index_part = (cpu % StrategyControl->num_partitions_per_group); + + index = (index_group * StrategyControl->num_partitions_per_group) + + index_part; + } + + return index; +} + +/* + * ChooseFreeList + * Pick the buffer freelist to use, depending on the CPU and NUMA node. + * + * Without partitioned freelists (numa_partition_freelist=false), there's only + * a single freelist, so use that. + * + * With partitioned freelists, we have multiple ways how to pick the freelist + * for the backend: + * + * - one freelist per CPU, use the freelist for CPU the task executes on + * + * - one freelist per NUMA node, use the freelist for node task executes on + * + * - use fixed number of freelists, map processes to lists based on PID + * + * There may be some other strategies, not sure. The important thing is this + * needs to be refrecled during initialization, i.e. we need to create the + * right number of lists. + */ +static BufferStrategyFreelist * +ChooseFreeList(void) +{ + int index = calculate_partition_index(); + return &StrategyControl->freelists[index]; +} + /* * have_free_buffer -- a lockless check to see if there is a free buffer in * buffer pool. @@ -168,10 +327,13 @@ ClockSweepTick(void) bool have_free_buffer(void) { - if (StrategyControl->firstFreeBuffer >= 0) - return true; - else - return false; + for (int i = 0; i < strategy_nnodes; i++) + { + if (StrategyControl->freelists[i].firstFreeBuffer >= 0) + return true; + } + + return false; } /* @@ -193,6 +355,7 @@ StrategyGetBuffer(BufferAccessStrategy strategy, uint32 *buf_state, bool *from_r int bgwprocno; int trycounter; uint32 local_buf_state; /* to avoid repeated (de-)referencing */ + BufferStrategyFreelist *freelist; *from_ring = false; @@ -259,31 +422,35 @@ StrategyGetBuffer(BufferAccessStrategy strategy, uint32 *buf_state, bool *from_r * buffer_strategy_lock not the individual buffer spinlocks, so it's OK to * manipulate them without holding the spinlock. */ - if (StrategyControl->firstFreeBuffer >= 0) + freelist = ChooseFreeList(); + if (freelist->firstFreeBuffer >= 0) { while (true) { /* Acquire the spinlock to remove element from the freelist */ - SpinLockAcquire(&StrategyControl->buffer_strategy_lock); + SpinLockAcquire(&freelist->freelist_lock); - if (StrategyControl->firstFreeBuffer < 0) + if (freelist->firstFreeBuffer < 0) { - SpinLockRelease(&StrategyControl->buffer_strategy_lock); + SpinLockRelease(&freelist->freelist_lock); break; } - buf = GetBufferDescriptor(StrategyControl->firstFreeBuffer); + buf = GetBufferDescriptor(freelist->firstFreeBuffer); Assert(buf->freeNext != FREENEXT_NOT_IN_LIST); /* Unconditionally remove buffer from freelist */ - StrategyControl->firstFreeBuffer = buf->freeNext; + freelist->firstFreeBuffer = buf->freeNext; buf->freeNext = FREENEXT_NOT_IN_LIST; + /* increment number of buffers we consumed from this list */ + freelist->consumed++; + /* * Release the lock so someone else can access the freelist while * we check out this buffer. */ - SpinLockRelease(&StrategyControl->buffer_strategy_lock); + SpinLockRelease(&freelist->freelist_lock); /* * If the buffer is pinned or has a nonzero usage_count, we cannot @@ -305,7 +472,17 @@ StrategyGetBuffer(BufferAccessStrategy strategy, uint32 *buf_state, bool *from_r } } - /* Nothing on the freelist, so run the "clock sweep" algorithm */ + /* + * Nothing on the freelist, so run the "clock sweep" algorithm + * + * XXX Should we also make this NUMA-aware, to only access buffers from + * the same NUMA node? That'd probably mean we need to make the clock + * sweep NUMA-aware, perhaps by having multiple clock sweeps, each for a + * subset of buffers. But that also means each process could "sweep" only + * a fraction of buffers, even if the other buffers are better candidates + * for eviction. Would that also mean we'd have multiple bgwriters, one + * for each node, or would one bgwriter handle all of that? + */ trycounter = NBuffers; for (;;) { @@ -356,7 +533,22 @@ StrategyGetBuffer(BufferAccessStrategy strategy, uint32 *buf_state, bool *from_r void StrategyFreeBuffer(BufferDesc *buf) { - SpinLockAcquire(&StrategyControl->buffer_strategy_lock); + BufferStrategyFreelist *freelist; + + /* + * We don't want to call ChooseFreeList() again, because we might get a + * completely different freelist - either a different partition in the + * same group, or even a different group if the NUMA node changed. But + * we can calculate the proper freelist from the buffer id. + */ + int index = (BufferGetNode(buf->buf_id) * StrategyControl->num_partitions_per_group) + + (buf->buf_id % StrategyControl->num_partitions_per_group); + + Assert((index >= 0) && (index < StrategyControl->num_partitions)); + + freelist = &StrategyControl->freelists[index]; + + SpinLockAcquire(&freelist->freelist_lock); /* * It is possible that we are told to put something in the freelist that @@ -364,11 +556,11 @@ StrategyFreeBuffer(BufferDesc *buf) */ if (buf->freeNext == FREENEXT_NOT_IN_LIST) { - buf->freeNext = StrategyControl->firstFreeBuffer; - StrategyControl->firstFreeBuffer = buf->buf_id; + buf->freeNext = freelist->firstFreeBuffer; + freelist->firstFreeBuffer = buf->buf_id; } - SpinLockRelease(&StrategyControl->buffer_strategy_lock); + SpinLockRelease(&freelist->freelist_lock); } /* @@ -432,6 +624,42 @@ StrategyNotifyBgWriter(int bgwprocno) SpinLockRelease(&StrategyControl->buffer_strategy_lock); } +/* prints some debug info / stats about freelists at shutdown */ +static void +freelist_before_shmem_exit(int code, Datum arg) +{ + for (int node = 0; node < strategy_nnodes; node++) + { + BufferStrategyFreelist *freelist = &StrategyControl->freelists[node]; + uint64 remain = 0; + uint64 actually_free = 0; + int cur = freelist->firstFreeBuffer; + + while (cur >= 0) + { + uint32 local_buf_state; + BufferDesc *buf; + + buf = GetBufferDescriptor(cur); + + remain++; + + local_buf_state = LockBufHdr(buf); + + if (!(local_buf_state & BM_TAG_VALID)) + actually_free++; + + UnlockBufHdr(buf, local_buf_state); + + cur = buf->freeNext; + } + elog(LOG, "freelist %d, firstF: %d: consumed: %lu, remain: %lu, actually free: %lu", + node, + freelist->firstFreeBuffer, + freelist->consumed, + remain, actually_free); + } +} /* * StrategyShmemSize @@ -445,12 +673,28 @@ Size StrategyShmemSize(void) { Size size = 0; + int num_partitions; + + /* FIXME */ +#ifdef USE_LIBNUMA + strategy_ncpus = numa_num_task_cpus(); + strategy_nnodes = numa_num_task_nodes(); +#else + strategy_ncpus = 1; + strategy_nnodes = 1; +#endif + + num_partitions = calculate_partition_count(strategy_nnodes); /* size of lookup hash table ... see comment in StrategyInitialize */ size = add_size(size, BufTableShmemSize(NBuffers + NUM_BUFFER_PARTITIONS)); /* size of the shared replacement strategy control block */ - size = add_size(size, MAXALIGN(sizeof(BufferStrategyControl))); + size = add_size(size, MAXALIGN(offsetof(BufferStrategyControl, freelists))); + + /* size of freelist partitions (at least one per NUMA node) */ + size = add_size(size, MAXALIGN(mul_size(sizeof(BufferStrategyFreelist), + num_partitions))); return size; } @@ -466,6 +710,13 @@ void StrategyInitialize(bool init) { bool found; + int buffers_per_partition; + + int num_partitions; + int num_partitions_per_group; + + /* */ + num_partitions = calculate_partition_count(strategy_nnodes); /* * Initialize the shared buffer lookup hashtable. @@ -484,23 +735,28 @@ StrategyInitialize(bool init) */ StrategyControl = (BufferStrategyControl *) ShmemInitStruct("Buffer Strategy Status", - sizeof(BufferStrategyControl), + MAXALIGN(offsetof(BufferStrategyControl, freelists)) + + MAXALIGN(sizeof(BufferStrategyFreelist) * num_partitions), &found); if (!found) { + int32 numBuffers = NBuffers / num_partitions; + + while (numBuffers * num_partitions < NBuffers) + numBuffers++; + + Assert(numBuffers * num_partitions == NBuffers); + /* * Only done once, usually in postmaster */ Assert(init); - SpinLockInit(&StrategyControl->buffer_strategy_lock); + /* register callback to dump some stats on exit */ + before_shmem_exit(freelist_before_shmem_exit, 0); - /* - * Grab the whole linked list of free buffers for our strategy. We - * assume it was previously set up by BufferManagerShmemInit(). - */ - StrategyControl->firstFreeBuffer = 0; + SpinLockInit(&StrategyControl->buffer_strategy_lock); /* Initialize the clock sweep pointer */ pg_atomic_init_u32(&StrategyControl->nextVictimBuffer, 0); @@ -511,6 +767,68 @@ StrategyInitialize(bool init) /* No pending notification */ StrategyControl->bgwprocno = -1; + + /* always a multiple of NUMA nodes */ + Assert(num_partitions % strategy_nnodes == 0); + + num_partitions_per_group = (num_partitions / strategy_nnodes); + + /* initialize the partitioned clocksweep */ + StrategyControl->num_partitions = num_partitions; + StrategyControl->num_partitions_groups = strategy_nnodes; + StrategyControl->num_partitions_per_group = num_partitions_per_group; + + /* + * Rebuild the freelist - right now all buffers are in one huge list, + * we want to rework that into multiple lists. Start by initializing + * the strategy to have empty lists. + */ + for (int nfreelist = 0; nfreelist < num_partitions; nfreelist++) + { + BufferStrategyFreelist *freelist; + + freelist = &StrategyControl->freelists[nfreelist]; + + freelist->firstFreeBuffer = FREENEXT_END_OF_LIST; + + SpinLockInit(&freelist->freelist_lock); + } + + /* buffers per partition */ + buffers_per_partition = (NBuffers / num_partitions); + + elog(LOG, "NBuffers: %d, nodes %d, ncpus: %d, divide: %d, remain: %d", + NBuffers, strategy_nnodes, strategy_ncpus, + buffers_per_partition, NBuffers - (num_partitions * buffers_per_partition)); + + /* + * Walk through the buffers, add them to the correct list. Walk from + * the end, because we're adding the buffers to the beginning. + */ + for (int i = NBuffers - 1; i >= 0; i--) + { + BufferDesc *buf = GetBufferDescriptor(i); + BufferStrategyFreelist *freelist; + int node; + int index; + + /* + * Split the freelist into partitions, if needed (or just keep the + * freelist we already built in BufferManagerShmemInit(). + */ + + /* determine NUMA node for buffer, this determines the group */ + node = BufferGetNode(i); + + /* now calculate the actual freelist index */ + index = node * num_partitions_per_group + (i % num_partitions_per_group); + + /* add to the right freelist */ + freelist = &StrategyControl->freelists[index]; + + buf->freeNext = freelist->firstFreeBuffer; + freelist->firstFreeBuffer = i; + } } else Assert(!init); diff --git a/src/backend/utils/init/globals.c b/src/backend/utils/init/globals.c index f5359db3656..a11bc71a386 100644 --- a/src/backend/utils/init/globals.c +++ b/src/backend/utils/init/globals.c @@ -148,6 +148,7 @@ int MaxBackends = 0; /* NUMA stuff */ bool numa_buffers_interleave = false; bool numa_localalloc = false; +bool numa_partition_freelist = false; /* GUC parameters for vacuum */ int VacuumBufferUsageLimit = 2048; diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c index a21f20800fb..0552ed62cc7 100644 --- a/src/backend/utils/misc/guc_tables.c +++ b/src/backend/utils/misc/guc_tables.c @@ -2136,6 +2136,16 @@ struct config_bool ConfigureNamesBool[] = NULL, NULL, NULL }, + { + {"numa_partition_freelist", PGC_POSTMASTER, DEVELOPER_OPTIONS, + gettext_noop("Enables buffer freelists to be partitioned per NUMA node."), + gettext_noop("When enabled, we create a separate freelist per NUMA node."), + }, + &numa_partition_freelist, + false, + NULL, NULL, NULL + }, + { {"sync_replication_slots", PGC_SIGHUP, REPLICATION_STANDBY, gettext_noop("Enables a physical standby to synchronize logical failover replication slots from the primary server."), diff --git a/src/include/miscadmin.h b/src/include/miscadmin.h index 692871a401f..66baf2bf33e 100644 --- a/src/include/miscadmin.h +++ b/src/include/miscadmin.h @@ -180,6 +180,7 @@ extern PGDLLIMPORT int max_parallel_workers; extern PGDLLIMPORT bool numa_buffers_interleave; extern PGDLLIMPORT bool numa_localalloc; +extern PGDLLIMPORT bool numa_partition_freelist; extern PGDLLIMPORT int commit_timestamp_buffers; extern PGDLLIMPORT int multixact_member_buffers; diff --git a/src/include/storage/bufmgr.h b/src/include/storage/bufmgr.h index c257c8a1c20..efb7e28c10f 100644 --- a/src/include/storage/bufmgr.h +++ b/src/include/storage/bufmgr.h @@ -93,6 +93,14 @@ typedef enum ExtendBufferedFlags EB_LOCK_TARGET = (1 << 5), } ExtendBufferedFlags; +typedef enum FreelistPartitionMode +{ + FREELIST_PARTITION_NONE, + FREELIST_PARTITION_NODE, + FREELIST_PARTITION_CPU, + FREELIST_PARTITION_PID, +} FreelistPartitionMode; + /* * Some functions identify relations either by relation or smgr + * relpersistence. Used via the BMR_REL()/BMR_SMGR() macros below. This -- 2.49.0