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. This has been originally fixed for 16~ with a4adc31f6902 without a backpatch, and we have heard complaints from users impacted by this quadratic behavior in older versions as well. Author: Andres Freund <and...@anarazel.de> Reviewed-by: Bharath Rupireddy <bharath.rupireddyforpostg...@gmail.com> Discussion: https://postgr.es/m/20221027165914.2hofzp4cvutj6...@awork3.anarazel.de Discussion: https://postgr.es/m/CALj2ACXktNbG=k8xi7psqboftzozavhaxjatvc14iyalu4m...@mail.gmail.com Backpatch-through: 12 Branch ------ REL_13_STABLE Details ------- https://git.postgresql.org/pg/commitdiff/dc9d424cf0cdac4971b89e426554d9562c4b9349 Author: Andres Freund <and...@anarazel.de> Modified Files -------------- src/backend/access/transam/twophase.c | 2 +- src/backend/storage/lmgr/lwlock.c | 53 ++++++++++++++++++++--------------- src/backend/storage/lmgr/proc.c | 4 +-- src/include/storage/lwlock.h | 8 ++++++ src/include/storage/proc.h | 2 +- 5 files changed, 42 insertions(+), 27 deletions(-)