pg.ddx.io pgsql-committers@postgresql.org mailing list archivehelp / color / mirror / Atom feed
pgsql: lwlock: Fix quadratic behavior with very long wait lists 5+ messages / 2 participants [nested] [flat]
* pgsql: lwlock: Fix quadratic behavior with very long wait lists @ 2022-11-20 19:57 Andres Freund <andres@anarazel.de> 0 siblings, 0 replies; 5+ messages in thread From: Andres Freund @ 2022-11-20 19:57 UTC (permalink / raw) To: pgsql-committers@lists.postgresql.org 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 <andres@anarazel.de> Reviewed-by: Bharath Rupireddy <bharath.rupireddyforpostgres@gmail.com> Discussion: https://postgr.es/m/20221027165914.2hofzp4cvutj6gin@awork3.anarazel.de Discussion: https://postgr.es/m/CALj2ACXktNbG=K8Xi7PSqbofTZozavhaxjatVc14iYaLu4Maag@mail.gmail.com Branch ------ master Details ------- https://git.postgresql.org/pg/commitdiff/a4adc31f6902f6fc29d74868e8969412fc590da9 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(-) ^ permalink raw reply [nested|flat] 5+ messages in thread
* pgsql: lwlock: Fix quadratic behavior with very long wait lists @ 2024-01-18 02:13 Michael Paquier <michael@paquier.xyz> 0 siblings, 0 replies; 5+ messages in thread From: Michael Paquier @ 2024-01-18 02:13 UTC (permalink / raw) To: pgsql-committers@lists.postgresql.org 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 <andres@anarazel.de> Reviewed-by: Bharath Rupireddy <bharath.rupireddyforpostgres@gmail.com> Discussion: https://postgr.es/m/20221027165914.2hofzp4cvutj6gin@awork3.anarazel.de Discussion: https://postgr.es/m/CALj2ACXktNbG=K8Xi7PSqbofTZozavhaxjatVc14iYaLu4Maag@mail.gmail.com Backpatch-through: 12 Branch ------ REL_13_STABLE Details ------- https://git.postgresql.org/pg/commitdiff/dc9d424cf0cdac4971b89e426554d9562c4b9349 Author: Andres Freund <andres@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(-) ^ permalink raw reply [nested|flat] 5+ messages in thread
* pgsql: lwlock: Fix quadratic behavior with very long wait lists @ 2024-01-18 02:13 Michael Paquier <michael@paquier.xyz> 0 siblings, 0 replies; 5+ messages in thread From: Michael Paquier @ 2024-01-18 02:13 UTC (permalink / raw) To: pgsql-committers@lists.postgresql.org 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 <andres@anarazel.de> Reviewed-by: Bharath Rupireddy <bharath.rupireddyforpostgres@gmail.com> Discussion: https://postgr.es/m/20221027165914.2hofzp4cvutj6gin@awork3.anarazel.de Discussion: https://postgr.es/m/CALj2ACXktNbG=K8Xi7PSqbofTZozavhaxjatVc14iYaLu4Maag@mail.gmail.com Backpatch-through: 12 Branch ------ REL_15_STABLE Details ------- https://git.postgresql.org/pg/commitdiff/f374fb4aab3efd37c4c522bce68ca96c7550e8af Author: Andres Freund <andres@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(-) ^ permalink raw reply [nested|flat] 5+ messages in thread
* pgsql: lwlock: Fix quadratic behavior with very long wait lists @ 2024-01-18 02:13 Michael Paquier <michael@paquier.xyz> 0 siblings, 0 replies; 5+ messages in thread From: Michael Paquier @ 2024-01-18 02:13 UTC (permalink / raw) To: pgsql-committers@lists.postgresql.org 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 <andres@anarazel.de> Reviewed-by: Bharath Rupireddy <bharath.rupireddyforpostgres@gmail.com> Discussion: https://postgr.es/m/20221027165914.2hofzp4cvutj6gin@awork3.anarazel.de Discussion: https://postgr.es/m/CALj2ACXktNbG=K8Xi7PSqbofTZozavhaxjatVc14iYaLu4Maag@mail.gmail.com Backpatch-through: 12 Branch ------ REL_14_STABLE Details ------- https://git.postgresql.org/pg/commitdiff/5f6ec27a64774b10ff8522bc745e5e993503011d Author: Andres Freund <andres@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(-) ^ permalink raw reply [nested|flat] 5+ messages in thread
* pgsql: lwlock: Fix quadratic behavior with very long wait lists @ 2024-01-18 02:13 Michael Paquier <michael@paquier.xyz> 0 siblings, 0 replies; 5+ messages in thread From: Michael Paquier @ 2024-01-18 02:13 UTC (permalink / raw) To: pgsql-committers@lists.postgresql.org 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 <andres@anarazel.de> Reviewed-by: Bharath Rupireddy <bharath.rupireddyforpostgres@gmail.com> Discussion: https://postgr.es/m/20221027165914.2hofzp4cvutj6gin@awork3.anarazel.de Discussion: https://postgr.es/m/CALj2ACXktNbG=K8Xi7PSqbofTZozavhaxjatVc14iYaLu4Maag@mail.gmail.com Backpatch-through: 12 Branch ------ REL_12_STABLE Details ------- https://git.postgresql.org/pg/commitdiff/81038228582aa92718be2afcb7ddb67a5a19fa43 Author: Andres Freund <andres@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(-) ^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2024-01-18 02:13 UTC | newest] Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2022-11-20 19:57 pgsql: lwlock: Fix quadratic behavior with very long wait lists Andres Freund <andres@anarazel.de> 2024-01-18 02:13 pgsql: lwlock: Fix quadratic behavior with very long wait lists Michael Paquier <michael@paquier.xyz> 2024-01-18 02:13 pgsql: lwlock: Fix quadratic behavior with very long wait lists Michael Paquier <michael@paquier.xyz> 2024-01-18 02:13 pgsql: lwlock: Fix quadratic behavior with very long wait lists Michael Paquier <michael@paquier.xyz> 2024-01-18 02:13 pgsql: lwlock: Fix quadratic behavior with very long wait lists Michael Paquier <michael@paquier.xyz>
This inbox is served by DDX for PostgreSQL; see mirroring instructions for how to clone and mirror all data and code used for this inbox