From a4adc31f6902f6fc29d74868e8969412fc590da9 Mon Sep 17 00:00:00 2001 From: Andres Freund Date: Sun, 20 Nov 2022 11:56:32 -0800 Subject: lwlock: Fix quadratic behavior with very long wait lists Until now LWLockDequeueSelf() sequentially searched the list of waiters to see if the current proc is still is on the list of waiters, or has already been removed. In extreme workloads, where the wait lists are very long, this leads to a quadratic behavior. #backends iterating over a list #backends long. Additionally, the likelihood of needing to call LWLockDequeueSelf() in the first place also increases with the increased length of the wait queue, as it becomes more likely that a lock is released while waiting for the wait list lock, which is held for longer during lock release. Due to the exponential back-off in perform_spin_delay() this is surprisingly hard to detect. We should make that easier, e.g. by adding a wait event around the pg_usleep() - but that's a separate patch. The fix is simple - track whether a proc is currently waiting in the wait list or already removed but waiting to be woken up in PGPROC->lwWaiting. In some workloads with a lot of clients contending for a small number of lwlocks (e.g. WALWriteLock), the fix can substantially increase throughput. As the quadratic behavior arguably is a bug, we might want to decide to backpatch this fix in the future. Author: Andres Freund Reviewed-by: Bharath Rupireddy Discussion: https://postgr.es/m/20221027165914.2hofzp4cvutj6gin@awork3.anarazel.de Discussion: https://postgr.es/m/CALj2ACXktNbG=K8Xi7PSqbofTZozavhaxjatVc14iYaLu4Maag@mail.gmail.com --- src/include/storage/lwlock.h | 8 ++++++++ src/include/storage/proc.h | 2 +- 2 files changed, 9 insertions(+), 1 deletion(-) (limited to 'src/include') diff --git a/src/include/storage/lwlock.h b/src/include/storage/lwlock.h index ca4eca76f4..a494cb598f 100644 --- a/src/include/storage/lwlock.h +++ b/src/include/storage/lwlock.h @@ -23,6 +23,14 @@ struct PGPROC; +/* what state of the wait process is a backend in */ +typedef enum LWLockWaitState +{ + LW_WS_NOT_WAITING, /* not currently waiting / woken up */ + LW_WS_WAITING, /* currently waiting */ + LW_WS_PENDING_WAKEUP, /* removed from waitlist, but not yet signalled */ +} LWLockWaitState; + /* * Code outside of lwlock.c should not manipulate the contents of this * structure directly, but we have to declare it here to allow LWLocks to be diff --git a/src/include/storage/proc.h b/src/include/storage/proc.h index 8d096fdeeb..aa13e1d66e 100644 --- a/src/include/storage/proc.h +++ b/src/include/storage/proc.h @@ -217,7 +217,7 @@ struct PGPROC bool recoveryConflictPending; /* Info about LWLock the process is currently waiting for, if any. */ - bool lwWaiting; /* true if waiting for an LW lock */ + uint8 lwWaiting; /* see LWLockWaitState */ uint8 lwWaitMode; /* lwlock mode being waited for */ proclist_node lwWaitLink; /* position in LW lock wait list */ -- cgit v1.2.1