Use the pairing heap instead of a flat array for LSN replay waiters
authorAlexander Korotkov <akorotkov@postgresql.org>
Wed, 3 Apr 2024 15:15:17 +0000 (18:15 +0300)
committerAlexander Korotkov <akorotkov@postgresql.org>
Wed, 3 Apr 2024 15:15:41 +0000 (18:15 +0300)
commitbf1e65080629e2b0ac47ffe245576da96eff8420
treed6eae6fbb978d03d72388d54a2ec86848a8979dd
parent936e3fa3787a51397280c1081587586e83c20399
Use the pairing heap instead of a flat array for LSN replay waiters

06c418e163 introduced pg_wal_replay_wait() procedure allowing to wait for
the particular LSN to be replayed on standby.  The waiters were stored in
the flat array.  Even though scanning small arrays is fast, that might be a
problem at scale (a lot of waiting processes).

This commit replaces the flat shared memory array with the pairing heap,
which holds the waiter with the least LSN at the top.  This gives us O(log N)
complexity for both inserting and removing waiters.

Reported-by: Alvaro Herrera
Discussion: https://postgr.es/m/202404030658.hhj3vfxeyhft%40alvherre.pgsql
src/backend/access/transam/xlogrecovery.c
src/backend/commands/waitlsn.c
src/backend/lib/pairingheap.c
src/include/commands/waitlsn.h
src/include/lib/pairingheap.h