[PATCH] Improve performance of NOTIFY over many databases (issue blocking on AccessExclusiveLock on object 0 of class 1262 of database 0)

Hoi hackers,

Please find attached updated versions of the patches, I've now tested
them. Also attached is a reproduction script to verify that they
actually work.

To test you need to create 150 databases as described in the script,
then simply execute it. Before patching you get the following results
(last figure is the CPU usage of Postgres):

1559749330 Sent: 500, Recv: 1000, Delays: Min: 0.01, Max: 0.01, Avg:
0.01 [0.01/0.01/0.01/0.01/0.01], 269.07%
1559749335 Sent: 500, Recv: 1000, Delays: Min: 0.01, Max: 0.01, Avg:
0.01 [0.01/0.01/0.01/0.01/0.01], 268.07%
1559749340 Sent: 500, Recv: 1000, Delays: Min: 0.01, Max: 0.01, Avg:
0.01 [0.01/0.01/0.01/0.01/0.01], 270.94%

After patching you get the following:

1559749840 Sent: 500, Recv: 1000, Delays: Min: 0.01, Max: 0.02, Avg:
0.01 [0.01/0.01/0.01/0.01/0.01], 5.09%
1559749845 Sent: 500, Recv: 1000, Delays: Min: 0.01, Max: 0.01, Avg:
0.01 [0.01/0.01/0.01/0.01/0.01], 5.06%
1559749850 Sent: 500, Recv: 1000, Delays: Min: 0.01, Max: 0.01, Avg:
0.01 [0.01/0.01/0.01/0.01/0.01], 4.75%

The async queue functions in postgres also no longer appear in the
perf output (below measuring threshold).

As for general method, it seems like the actual optimisation here is
that the async queue tail pointer is only updated once per SLRU page
instead of every message. This would require a significantly larger
patch, but shouldn't be too difficult. Thoughts?

Have a nice day,
Martijn

On Tue, 4 Jun 2019 at 09:08, Martijn van Oosterhout <kleptog@gmail.com> wrote:

Hoi hackers,

We've been having issues with NOTIFYs blocking over multiple databases
(see [1] for more details). That was 9.4 but we've updated the
database to 11.3 and still have the same issue. Now however we could
use perf to do profiling and got the following profile (useless
details elided):

--32.83%--ProcessClientReadInterrupt
--32.68%--ProcessNotifyInterrupt
--32.16%--asyncQueueReadAllNotifications
--23.37%--asyncQueueAdvanceTail
--20.49%--LWLockAcquire
--18.93%--LWLockQueueSelf
--12.99%--LWLockWaitListLock

(from: perf record -F 99 -ag -- sleep 600)

That shows that more than 20% of the time is spent in that single
function, waiting for an exclusive lock on the AsyncQueueLock. This
will block any concurrent session doing a NOTIFY in any database on
the system. This would certainly explain the symptoms we're seeing
(process xxx still waiting for AccessExclusiveLock on object 0 of
class 1262 of database 0).

Analysis of the code leads me to the following hypothesis (and hence
to the attached patches):

We have ~150 databases, each of which has 2 active backends with an
active LISTEN. When a NOTIFY happens anywhere on any database it
(under an exclusive lock) makes a list of 300 backends to send a
signal to. It then wakes up all of those backends. Each backend then
examines the message and all but one discards it as being for the
wrong database. Each backend then calls asyncQueueAdvanceTail (because
the current position of the each backend was the tail) which then
takes an exclusive lock and checks all the other backends to see if
the tail can be advanced. All of these will conclude 'no', except the
very last one which concludes the tail can be advanced by about 50
bytes or so.

So the inner loop of asyncQueueAdvanceTail will, while holding a
global exclusive lock, execute 2*150*4000 (max backends) = 1.2 million
times for basically no benefit. During this time, no other transaction
anywhere in the system that does a NOTIFY will be able to commit.

The attached patches attempt reduce the overhead in two ways:

Patch 1: Changes asyncQueueAdvanceTail to do nothing unless the
QUEUE_HEAD is on a different page than the QUEUE_TAIL. The idea is
that there's no point trying to advance the tail unless we can
actually usefully truncate the SLRU. This does however mean that
asyncQueueReadAllNotifications always has to call
asyncQueueAdvanceTail since it can no longer be guaranteed that any
backend is still at the tail, which is one of the assumptions of the
current code. Not sure if this is a problem or if it can be improved
without tracking much more state.

Patch 2: Changes SignalBackends to only notify other backends when (a)
they're the same database as me or (b) the notify queue has advanced
to a new SLRU page. This avoids backends being woken up for messages
which they are not interested in.

As a consequence of these changes, we can reduce the number of
exclusive locks and backend wake ups in our case by a factor of 300.
You still however get a thundering herd at the end of each SLRU page.

Note: these patches have not yet been extensively tested, and so
should only be used as basis for discussion.

Comments? Suggestions?

[1] /messages/by-id/CADWG95t0j9zF0uwdcMH81KMnDsiTAVHxmBvgYqrRJcD-iLwQhw@mail.gmail.com

--
Martijn van Oosterhout <kleptog@gmail.com> http://svana.org/kleptog/

--
Martijn van Oosterhout <kleptog@gmail.com> http://svana.org/kleptog/

Martijn van Oosterhout <kleptog@gmail.com> writes:

Please find attached updated versions of the patches, I've now tested
them. Also attached is a reproduction script to verify that they
actually work.

I looked through these (a bit cursorily).

I'm generally on board with the idea of 0001, but not with the patch
details. As coded, asyncQueueAdvanceTail is supposing that it can
examine the shared QUEUE_HEAD and QUEUE_TAIL pointers without any
lock whatsoever. That's probably unsafe, and if it is safe for some
reason, you haven't made the argument why. Moreover, it seems
unnecessary to make any such assumption. Why not put back the
advanceTail tests you removed, but adjust them so that advanceTail
isn't set true unless QUEUE_HEAD and QUEUE_TAIL point to different
pages? (Note that in the existing coding, those tests are made
while holding an appropriate lock, so it's safe to look at those
pointers there.)

It might be a good idea to make a macro encapsulating this new,
more complicated rule for setting advanceTail, instead of relying
on keeping the various call sites in sync.

More attention to comments is also needed. For instance, you've
made a lie out of the documentation of the tail pointer:

QueuePosition tail; /* the global tail is equivalent to the pos of
* the "slowest" backend */

It needs to say something like "is <= the pos of the slowest backend",
instead. I think the explanation of why this algorithm is good could
use more effort, too.

Comments for 0002 are about the same: for no explained reason, and
certainly no savings, you've put the notify_all test in an unsafe
place rather than a safe one (viz, two lines down, *after* taking
the relevant lock). And 0002 needs more commentary about why
its optimization is safe and useful, too. In particular it's
not obvious why QUEUE_HEAD being on a different page from QUEUE_TAIL
has anything to do with whether we should wake up other backends.

I'm not very persuaded by 0003, mainly because it seems likely to
me that 0001 and 0002 will greatly reduce the possibility that
the early-exit can happen. So it seems like it's adding cycles
(in a spot where we hold exclusive lock) without a good chance of
saving any cycles.

Taking a step back in hopes of seeing the bigger picture ...
as you already noted, these changes don't really fix the "thundering
herd of wakeups" problem, they just arrange for it to happen
once per SLRU page rather than once per message. I wonder if we
could improve matters by stealing an idea from the sinval code:
when we're trying to cause advance of the global QUEUE_TAIL, waken
only the slowest backend, and have it waken the next-slowest after
it's done. In sinval there are some additional provisions to prevent
a nonresponsive backend from delaying matters for other backends,
but I think maybe we don't need that here. async.c doesn't have
anything equivalent to sinval reset, so there's no chance of
overruling a slow backend's failure to advance its pos pointer,
so there's not much reason not to just wait till it does do so.

A related idea is to awaken only one backend at a time when we
send a new message (i.e., advance QUEUE_HEAD) but I think that
would likely be bad. The hazard with the chained-wakeups method
is that a slow backend blocks wakeup of everything else. We don't
care about that hugely for QUEUE_TAIL advance, because we're just
hoping to free some SLRU space. But for QUEUE_HEAD advance it'd
mean failing to deliver notifies in a timely way, which we do care
about. (Also, if I remember correctly, the processing on that side
only requires shared lock so it's less of a problem if many backends
do it at once.)

regards, tom lane

Hoi Tom,

Thank you for the detailed response. Sorry the delay, I was on holiday.

You are absolutely correct when you point out that the queue pointers
were accessed without the lock and this is probably unsafe. For the
first two patches this is can be remedied, though I find it makes the
logic a bit harder to follow. The comments will need to be updated to
reflect the new logic. I hope to post something soon.

As for your point about the third patch, you are right that it's
probably not saving many cycles. However I do think it's worthwhile
actually optimising this loop, because the number of backends that are
listening is likely to be much smaller than the total number of
backends, so there's a lot of cycles being wasted here already. Fixing
the thundering herd issue (like in sinval as you point out) doesn't
actually reduce the amount of work being done, just spreads it out.
Since readers and writers block each other, blocking a writer means
blocking commits across the whole cluster.

There are a number of possible improvements here:

1. Do what sinval does and separate the reader and writer locks so
they can't block each other. This is the ultimate solution, but it's a
significant refactor and it's not clear that's actually worthwhile
here. This would almost be adopting the sinvaladt structure wholesale.

2. Add a field to AsyncQueueEntry which points to the next listening
backend. This would allow the loops over all listening backends to
complete much faster, especially in the normal case where there are
not many listeners relative to the number of backends. The downside is
this requires an exclusive lock to remove listeners, but that doesn't
seem a big problem.

3. The other idea from sinval where you only wake up one worker at a
time is a good one as you point out. This seems quite doable, however,
it seems wasteful to try and wake everyone up the moment we switch to
a new page. The longer you delay the lower the chance you need to wake
anyone at all because they've because they'll have caught up by
themselves. A single SLRU page can hold hundreds, or even thousands of
messages.

Do 2 & 3 seem like a good direction to go? I can probably work something up.

Thanks in advance,
Martijn

Martijn van Oosterhout <kleptog@gmail.com> writes:

Please find attached updated versions of the patches, I've now tested
them. Also attached is a reproduction script to verify that they
actually work.

I looked through these (a bit cursorily).

I'm generally on board with the idea of 0001, but not with the patch
details. As coded, asyncQueueAdvanceTail is supposing that it can
examine the shared QUEUE_HEAD and QUEUE_TAIL pointers without any
lock whatsoever. That's probably unsafe, and if it is safe for some
reason, you haven't made the argument why. Moreover, it seems
unnecessary to make any such assumption. Why not put back the
advanceTail tests you removed, but adjust them so that advanceTail
isn't set true unless QUEUE_HEAD and QUEUE_TAIL point to different
pages? (Note that in the existing coding, those tests are made
while holding an appropriate lock, so it's safe to look at those
pointers there.)

It might be a good idea to make a macro encapsulating this new,
more complicated rule for setting advanceTail, instead of relying
on keeping the various call sites in sync.

More attention to comments is also needed. For instance, you've
made a lie out of the documentation of the tail pointer:

QueuePosition tail; /* the global tail is equivalent to the pos of
* the "slowest" backend */

It needs to say something like "is <= the pos of the slowest backend",
instead. I think the explanation of why this algorithm is good could
use more effort, too.

Comments for 0002 are about the same: for no explained reason, and
certainly no savings, you've put the notify_all test in an unsafe
place rather than a safe one (viz, two lines down, *after* taking
the relevant lock). And 0002 needs more commentary about why
its optimization is safe and useful, too. In particular it's
not obvious why QUEUE_HEAD being on a different page from QUEUE_TAIL
has anything to do with whether we should wake up other backends.

I'm not very persuaded by 0003, mainly because it seems likely to
me that 0001 and 0002 will greatly reduce the possibility that
the early-exit can happen. So it seems like it's adding cycles
(in a spot where we hold exclusive lock) without a good chance of
saving any cycles.

Taking a step back in hopes of seeing the bigger picture ...
as you already noted, these changes don't really fix the "thundering
herd of wakeups" problem, they just arrange for it to happen
once per SLRU page rather than once per message. I wonder if we
could improve matters by stealing an idea from the sinval code:
when we're trying to cause advance of the global QUEUE_TAIL, waken
only the slowest backend, and have it waken the next-slowest after
it's done. In sinval there are some additional provisions to prevent
a nonresponsive backend from delaying matters for other backends,
but I think maybe we don't need that here. async.c doesn't have
anything equivalent to sinval reset, so there's no chance of
overruling a slow backend's failure to advance its pos pointer,
so there's not much reason not to just wait till it does do so.

A related idea is to awaken only one backend at a time when we
send a new message (i.e., advance QUEUE_HEAD) but I think that
would likely be bad. The hazard with the chained-wakeups method
is that a slow backend blocks wakeup of everything else. We don't
care about that hugely for QUEUE_TAIL advance, because we're just
hoping to free some SLRU space. But for QUEUE_HEAD advance it'd
mean failing to deliver notifies in a timely way, which we do care
about. (Also, if I remember correctly, the processing on that side
only requires shared lock so it's less of a problem if many backends
do it at once.)

regards, tom lane

--
Martijn van Oosterhout <kleptog@gmail.com> http://svana.org/kleptog/

Martijn van Oosterhout <kleptog@gmail.com> writes:

There are a number of possible improvements here:

1. Do what sinval does and separate the reader and writer locks so
they can't block each other. This is the ultimate solution, but it's a
significant refactor and it's not clear that's actually worthwhile
here. This would almost be adopting the sinvaladt structure wholesale.

I agree that that's probably more ambitious than is warranted.

2. Add a field to AsyncQueueEntry which points to the next listening
backend. This would allow the loops over all listening backends to
complete much faster, especially in the normal case where there are
not many listeners relative to the number of backends. The downside is
this requires an exclusive lock to remove listeners, but that doesn't
seem a big problem.

I don't understand how that would work? The sending backend doesn't
know what the "next listening backend" is. Having to scan the whole
queue when a listener unlistens seems pretty awful too, especially
if you need exclusive lock while doing so.

3. The other idea from sinval where you only wake up one worker at a
time is a good one as you point out. This seems quite doable, however,
it seems wasteful to try and wake everyone up the moment we switch to
a new page. The longer you delay the lower the chance you need to wake
anyone at all because they've because they'll have caught up by
themselves. A single SLRU page can hold hundreds, or even thousands of
messages.

Not entirely following your comment here either. The point of the change
is exactly that we'd wake up only one backend at a time (and only the
furthest-behind one, so that anyone who catches up of their own accord
stops being a factor). Also, "hundreds or thousands" seems
over-optimistic given that the minimum size of AsyncQueueEntry is 20
bytes --- in practice it'll be more because people don't use empty
strings as notify channel names. I think a few hundred messages per
page is the upper limit, and it could be a lot less.

Do 2 & 3 seem like a good direction to go? I can probably work something up.

I'm on board with 3, obviously. Not following what you have in mind
for 2.

regards, tom lane

On Tue, 23 Jul 2019 at 19:21, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Martijn van Oosterhout <kleptog@gmail.com> writes:

2. Add a field to AsyncQueueEntry which points to the next listening
backend. This would allow the loops over all listening backends to
complete much faster, especially in the normal case where there are
not many listeners relative to the number of backends. The downside is
this requires an exclusive lock to remove listeners, but that doesn't
seem a big problem.

I don't understand how that would work? The sending backend doesn't
know what the "next listening backend" is. Having to scan the whole
queue when a listener unlistens seems pretty awful too, especially
if you need exclusive lock while doing so.

I mean tracking the listening backends specifically, so you can
replace the loops:

for (i=0; i < MaxBackends; i++)

with

for (i=QUEUE_FIRST_LISTENING_BACKEND; i; i = QUEUE_NEXT_LISTENING_BACKEND(i))

Such loops occur often when trying to advance the tail, when adding a
new listener,
when sending a notify, etc, all while holding a (exclusive) lock.
Seems like such an easy win
to only loop over the listening backends rather than all of them.

Do 2 & 3 seem like a good direction to go? I can probably work something up.

I'm on board with 3, obviously. Not following what you have in mind
for 2.

Hope this clears it up a bit. Only waking up one at a time is a good
idea, but needs to some
careful thinking to prove it actually works.

Have a nice day,
--
Martijn van Oosterhout <kleptog@gmail.com> http://svana.org/kleptog/

Martijn van Oosterhout <kleptog@gmail.com> writes:

On Tue, 23 Jul 2019 at 19:21, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Martijn van Oosterhout <kleptog@gmail.com> writes:

2. Add a field to AsyncQueueEntry which points to the next listening
backend. This would allow the loops over all listening backends to
complete much faster, especially in the normal case where there are
not many listeners relative to the number of backends. The downside is
this requires an exclusive lock to remove listeners, but that doesn't
seem a big problem.

I don't understand how that would work? The sending backend doesn't
know what the "next listening backend" is. Having to scan the whole
queue when a listener unlistens seems pretty awful too, especially
if you need exclusive lock while doing so.

I mean tracking the listening backends specifically, so you can
replace the loops:
for (i=0; i < MaxBackends; i++)
with
for (i=QUEUE_FIRST_LISTENING_BACKEND; i; i = QUEUE_NEXT_LISTENING_BACKEND(i))

Ah ... but surely you would not put such info in AsyncQueueEntry,
where there'd be a separate copy for each message. I think you
meant to add the info to AsyncQueueControl.

It might be better to redefine the backends[] array as being mostly
contiguous (ie, a new backend takes the first free slot not the one
indexed by its own BackendId), at the price of needing to store
BackendId in each slot explicitly instead of assuming it's equal to
the array index. I suspect the existing data structure is putting too
much of a premium on making sizeof(QueueBackendStatus) a power of 2.

regards, tom lane

On Tue, 23 Jul 2019 at 23:32, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Martijn van Oosterhout <kleptog@gmail.com> writes:

I mean tracking the listening backends specifically, so you can
replace the loops:
for (i=0; i < MaxBackends; i++)
with
for (i=QUEUE_FIRST_LISTENING_BACKEND; i; i = QUEUE_NEXT_LISTENING_BACKEND(i))

Ah ... but surely you would not put such info in AsyncQueueEntry,
where there'd be a separate copy for each message. I think you
meant to add the info to AsyncQueueControl.

Umm, yeah. Got that mixed up.

It might be better to redefine the backends[] array as being mostly
contiguous (ie, a new backend takes the first free slot not the one
indexed by its own BackendId), at the price of needing to store
BackendId in each slot explicitly instead of assuming it's equal to
the array index. I suspect the existing data structure is putting too
much of a premium on making sizeof(QueueBackendStatus) a power of 2.

This would require adding a "MyListenerId" to each backend which I'm not sure
helps the readability. And there's a chance of mixing the id up. The
power-of-2-ness
is I think indeed overrated.

I'll give it a shot a see how it looks.

Have a nice day,

--
Martijn van Oosterhout <kleptog@gmail.com> http://svana.org/kleptog/

On Wed, Jul 24, 2019 at 8:30 PM Martijn van Oosterhout
<kleptog@gmail.com> wrote:

I'll give it a shot a see how it looks.

Moved to September CF, "Waiting on Author".

--
Thomas Munro
https://enterprisedb.com