[PATCH] Improve performance of NOTIFY over many databases (v2)

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

The original three patches have been collapsed into one as given the
changes discussed it didn't make sense to keep them separate. There
are now two patches (the third is just to help with testing):

Patch 1: Tracks the listening backends in a list so non-listening
backends can be quickly skipped over. This is separate because it's
orthogonal to the rest of the changes and there are other ways to do
this.

Patch 2: This is the meat of the change. It implements all the
suggestions discussed:

I pushed 0001 after doing some hacking on it --- it was sloppy about
datatypes, and about whether the invalid-entry value is 0 or -1,
and it was just wrong about keeping the list in backendid order.
(You can't conditionally skip looking for where to put the new
entry, if you want to maintain the order. I thought about just
defining the list as unordered, which would simplify joining the
list initially, but that could get pretty cache-unfriendly when
there are lots of entries.)

0002 is now going to need a rebase, so please do that.

regards, tom lane

Hoi Tom,

On Wed, 11 Sep 2019 at 00:18, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I pushed 0001 after doing some hacking on it --- it was sloppy about
datatypes, and about whether the invalid-entry value is 0 or -1,
and it was just wrong about keeping the list in backendid order.
(You can't conditionally skip looking for where to put the new
entry, if you want to maintain the order. I thought about just
defining the list as unordered, which would simplify joining the
list initially, but that could get pretty cache-unfriendly when
there are lots of entries.)

0002 is now going to need a rebase, so please do that.

Thanks for this, and good catch. Looks like I didn't test the first patch
by itself very well.

Here is the rebased second patch.

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

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

Here is the rebased second patch.

This throws multiple compiler warnings for me:

async.c: In function 'asyncQueueUnregister':
async.c:1293: warning: unused variable 'advanceTail'
async.c: In function 'asyncQueueAdvanceTail':
async.c:2153: warning: 'slowbackendpid' may be used uninitialized in this function

Also, I don't exactly believe this bit:

+            /* If we are advancing to a new page, remember this so after the
+             * transaction commits we can attempt to advance the tail
+             * pointer, see ProcessCompletedNotifies() */
+            if (QUEUE_POS_OFFSET(QUEUE_HEAD) == 0)
+                backendTryAdvanceTail = true;

It seems unlikely that insertion would stop exactly at a page boundary,
but that seems to be what this is looking for.

But, really ... do we need the backendTryAdvanceTail flag at all?
I'm dubious, because it seems like asyncQueueReadAllNotifications
would have already covered the case if we're listening. If we're
not listening, but we signalled some other listeners, it falls
to them to kick us if we're the slowest backend. If we're not the
slowest backend then doing asyncQueueAdvanceTail isn't useful.

I agree with getting rid of the asyncQueueAdvanceTail call in
asyncQueueUnregister; on reflection doing that there seems pretty unsafe,
because we're not necessarily in a transaction and hence anything that
could possibly error is a bad idea. However, it'd be good to add a
comment explaining that we're not doing that and why it's ok not to.

I'm fairly unimpressed with the "kick a random slow backend" logic.
There can be no point in kicking any but the slowest backend, ie
one whose pointer is exactly the oldest. Since we're already computing
the min pointer in that loop, it would actually take *less* logic inside
the loop to remember the/a backend that had that pointer value, and then
decide afterwards whether it's slow enough to merit a kick.

regards, tom lane

Hoi Tom,

On Fri, 13 Sep 2019 at 22:04, Tom Lane <tgl@sss.pgh.pa.us> wrote:

This throws multiple compiler warnings for me:

Fixed.

Also, I don't exactly believe this bit:

[snip]

It seems unlikely that insertion would stop exactly at a page boundary,
but that seems to be what this is looking for.

This is how asyncQueueAddEntries() works. Entries are never split over
pages. If there is not enough room, then it advances to the beginning
of the next page and returns. Hence here the offset is zero. I could
set the global inside asyncQueueAddEntries() but that seems icky.
Another alternative is to have asyncQueueAddEntries() return a boolean
"moved to new page", but that's just a long-winded way of doing what
it is now.

But, really ... do we need the backendTryAdvanceTail flag at all?
I'm dubious, because it seems like asyncQueueReadAllNotifications
would have already covered the case if we're listening. If we're
not listening, but we signalled some other listeners, it falls
to them to kick us if we're the slowest backend. If we're not the
slowest backend then doing asyncQueueAdvanceTail isn't useful.

There are multiple issues here. asyncQueueReadAllNotifications() is
going to be called by each listener simultaneously, so each listener
is going to come to the same conclusion. On the other side, there is
no guarantee we wake up anyone as a result of the NOTIFY, e.g. if
there are no listeners in the current database. To be sure you try to
advance the tail, you have to trigger on the sending side. The global
is there because at the point we are inserting entries we are still in
a user transaction, potentially holding many table locks (the issue we
were running into in the first place). By setting
backendTryAdvanceTail we can move the work to
ProcessCompletedNotifies() which is after the transaction has
committed and the locks released.

I agree with getting rid of the asyncQueueAdvanceTail call in
asyncQueueUnregister; on reflection doing that there seems pretty unsafe,
because we're not necessarily in a transaction and hence anything that
could possibly error is a bad idea. However, it'd be good to add a
comment explaining that we're not doing that and why it's ok not to.

Comment added.

I'm fairly unimpressed with the "kick a random slow backend" logic.
There can be no point in kicking any but the slowest backend, ie
one whose pointer is exactly the oldest. Since we're already computing
the min pointer in that loop, it would actually take *less* logic inside
the loop to remember the/a backend that had that pointer value, and then
decide afterwards whether it's slow enough to merit a kick.

Adjusted this. I'm not sure it's actually clearer this way, but it is
less work inside the loop. A small change is that now it won't signal
anyone if this backend is the slowest, which more correct.

Thanks for the feedback. Attached is version 3.

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

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

On Fri, 13 Sep 2019 at 22:04, Tom Lane <tgl@sss.pgh.pa.us> wrote:

But, really ... do we need the backendTryAdvanceTail flag at all?

There are multiple issues here. asyncQueueReadAllNotifications() is
going to be called by each listener simultaneously, so each listener
is going to come to the same conclusion. On the other side, there is
no guarantee we wake up anyone as a result of the NOTIFY, e.g. if
there are no listeners in the current database. To be sure you try to
advance the tail, you have to trigger on the sending side. The global
is there because at the point we are inserting entries we are still in
a user transaction, potentially holding many table locks (the issue we
were running into in the first place). By setting
backendTryAdvanceTail we can move the work to
ProcessCompletedNotifies() which is after the transaction has
committed and the locks released.

None of this seems to respond to my point: it looks to me like it would
work fine if you simply dropped the patch's additions in PreCommit_Notify
and ProcessCompletedNotifies, because there is already enough logic to
decide when to call asyncQueueAdvanceTail. In particular, the result from
Signal[MyDB]Backends tells us whether anyone else was awakened, and
ProcessCompletedNotifies already does asyncQueueAdvanceTail if not.
As long as we did awaken someone, the ball's now in their court to
make sure asyncQueueAdvanceTail happens eventually.

There are corner cases where someone else might get signaled but never
do asyncQueueAdvanceTail -- for example, if they're in process of exiting
--- but I think the whole point of this patch is that we don't care too
much if that occasionally fails to happen.  If there's a continuing
stream of NOTIFY activity, asyncQueueAdvanceTail will happen often
enough to ensure that the queue storage doesn't bloat unreasonably.

regards, tom lane

On Sat, 14 Sep 2019 at 17:08, Tom Lane <tgl@sss.pgh.pa.us> wrote:

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

On Fri, 13 Sep 2019 at 22:04, Tom Lane <tgl@sss.pgh.pa.us> wrote:

But, really ... do we need the backendTryAdvanceTail flag at all?

None of this seems to respond to my point: it looks to me like it would
work fine if you simply dropped the patch's additions in PreCommit_Notify
and ProcessCompletedNotifies, because there is already enough logic to
decide when to call asyncQueueAdvanceTail. In particular, the result from
Signal[MyDB]Backends tells us whether anyone else was awakened, and
ProcessCompletedNotifies already does asyncQueueAdvanceTail if not.
As long as we did awaken someone, the ball's now in their court to
make sure asyncQueueAdvanceTail happens eventually.

Ah, I think I see what you're getting at. As written,
asyncQueueReadAllNotifications() only calls asyncQueueAdvanceTail() if
*it* was a slow backend (advanceTail =
QUEUE_SLOW_BACKEND(MyBackendId)). In a situation where some databases
are regularly using NOTIFY and a few others never (but still
listening) it will lead to the situation where the tail never gets
advanced.

However, I guess you're thinking of asyncQueueReadAllNotifications()
triggering if the queue as a whole was too long. This could in
principle work but it does mean that at some point all backends
sending NOTIFY are going to start calling asyncQueueAdvanceTail()
every time, until the tail gets advanced, and if there are many idle
listening backends behind this could take a while. The slowest backend
might receive more signals while it is processing and so end up
running asyncQueueAdvanceTail() twice. The fact that signals coalesce
stops the process getting completely out of hand but it does feel a
little uncontrolled.

The whole point of this patch is to ensure that at any time only one
backend is being woken up and calling asyncQueueAdvanceTail() at a
time.

But you do point out that the use of the return value of
SignalMyDBBackends() is used wrongly. The fact that no-one got
signalled only meant there were no other listeners on this database
which means nothing in terms of global queue cleanup. What you want to
know is if you're the only listener in the whole system and you can
test for that directly (QUEUE_FIRST_BACKEND == MyBackendId &&
QUEUE_NEXT_BACKEND(MyBackendId) == InvalidBackendId). I can adjust
this in the next version if necessary, it's fairly harmless as is as
it only triggers in the case where a database is only notifying
itself, which probably isn't that common.

I hope I have correctly understood this time.

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

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

On Sat, 14 Sep 2019 at 17:08, Tom Lane <tgl@sss.pgh.pa.us> wrote:

None of this seems to respond to my point: it looks to me like it would
work fine if you simply dropped the patch's additions in PreCommit_Notify
and ProcessCompletedNotifies, because there is already enough logic to
decide when to call asyncQueueAdvanceTail.

...
However, I guess you're thinking of asyncQueueReadAllNotifications()
triggering if the queue as a whole was too long. This could in
principle work but it does mean that at some point all backends
sending NOTIFY are going to start calling asyncQueueAdvanceTail()
every time, until the tail gets advanced, and if there are many idle
listening backends behind this could take a while. The slowest backend
might receive more signals while it is processing and so end up
running asyncQueueAdvanceTail() twice. The fact that signals coalesce
stops the process getting completely out of hand but it does feel a
little uncontrolled.
The whole point of this patch is to ensure that at any time only one
backend is being woken up and calling asyncQueueAdvanceTail() at a
time.

I spent some more time thinking about this, and I'm still not too
satisfied with this patch's approach. It seems to me the key insights
we're trying to make use of are:

1. We don't really need to keep the global tail pointer exactly
up to date. It's bad if it falls way behind, but a few pages back
is fine.

2. When sending notifies, only listening backends connected to our
own database need be awakened immediately. Backends connected to
other DBs will need to advance their queue pointer sometime, but
again it doesn't need to be right away.

3. It's bad for multiple processes to all be trying to do
asyncQueueAdvanceTail concurrently: they'll contend for exclusive
access to the AsyncQueueLock. Therefore, having the listeners
do it is really the wrong thing, and instead we should do it on
the sending side.

However, the patch as presented doesn't go all the way on point 3,
instead having listeners maybe-or-maybe-not do asyncQueueAdvanceTail
in asyncQueueReadAllNotifications. I propose that we should go all
the way and just define tail-advancing as something that happens on
the sending side, and only once every few pages. I also think we
can simplify the handling of other-database listeners by including
them in the set signaled by SignalBackends, but only if they're
several pages behind. So that leads me to the attached patch;
what do you think?

BTW, in my hands it seems like point 2 (skip wakening other-database
listeners) is the only really significant win here, and of course
that only wins when the notify traffic is spread across a fair number
of databases. Which I fear is not the typical use-case. In single-DB
use-cases, point 2 helps not at all. I had a really hard time measuring
any benefit from point 3 --- I eventually saw a noticeable savings
when I tried having one notifier and 100 listen-only backends, but
again that doesn't seem like a typical use-case. I could not replicate
your report of lots of time spent in asyncQueueAdvanceTail's lock
acquisition. I wonder whether you're using a very large max_connections
setting and we already fixed most of the problem with that in bca6e6435.
Still, this patch doesn't seem to make any cases worse, so I don't mind
if it's just improving unusual use-cases.

regards, tom lane

Hoi Tom,

On Mon, 16 Sep 2019 at 00:14, Tom Lane <tgl@sss.pgh.pa.us> wrote:

I spent some more time thinking about this, and I'm still not too
satisfied with this patch's approach. It seems to me the key insights
we're trying to make use of are:

1. We don't really need to keep the global tail pointer exactly
up to date. It's bad if it falls way behind, but a few pages back
is fine.

Agreed.

2. When sending notifies, only listening backends connected to our
own database need be awakened immediately. Backends connected to
other DBs will need to advance their queue pointer sometime, but
again it doesn't need to be right away.

Agreed.

3. It's bad for multiple processes to all be trying to do
asyncQueueAdvanceTail concurrently: they'll contend for exclusive
access to the AsyncQueueLock. Therefore, having the listeners
do it is really the wrong thing, and instead we should do it on
the sending side.

Agreed, but I'd add that listeners in databases that are largely idle
there may never be a sender, and thus need to be advanced up some
other way.

However, the patch as presented doesn't go all the way on point 3,
instead having listeners maybe-or-maybe-not do asyncQueueAdvanceTail
in asyncQueueReadAllNotifications. I propose that we should go all
the way and just define tail-advancing as something that happens on
the sending side, and only once every few pages. I also think we
can simplify the handling of other-database listeners by including
them in the set signaled by SignalBackends, but only if they're
several pages behind. So that leads me to the attached patch;
what do you think?

I think I like the idea of having SignalBackend do the waking up a
slow backend but I'm not enthused by the "lets wake up (at once)
everyone that is behind". That's one of the issues I was explicitly
trying to solve. If there are any significant number of "slow"
backends then we get the "thundering herd" again. If the number of
slow backends exceeds the number of cores then commits across the
system could be held up quite a while (which is what caused me to make
this patch, multiple seconds was not unusual).

The maybe/maybe not in asyncQueueReadAllNotifications is that "if I
was behind, then I probably got woken up, hence I need to wake up
someone else", thus ensuring the cleanup proceeds in an orderly
fashion, leaving gaps where the lock isn't held allowing COMMITs to
proceed.

BTW, in my hands it seems like point 2 (skip wakening other-database
listeners) is the only really significant win here, and of course
that only wins when the notify traffic is spread across a fair number
of databases. Which I fear is not the typical use-case. In single-DB
use-cases, point 2 helps not at all. I had a really hard time measuring
any benefit from point 3 --- I eventually saw a noticeable savings
when I tried having one notifier and 100 listen-only backends, but
again that doesn't seem like a typical use-case. I could not replicate
your report of lots of time spent in asyncQueueAdvanceTail's lock
acquisition. I wonder whether you're using a very large max_connections
setting and we already fixed most of the problem with that in bca6e6435.
Still, this patch doesn't seem to make any cases worse, so I don't mind
if it's just improving unusual use-cases.

I'm not sure if it's an unusual use-case, but it is my use-case :).
Specifically, there are 100+ instances of the same application running
on the same cluster with wildly different usage patterns. Some will be
idle because no-one is logged in, some will be quite busy. Although
there are only 2 listeners per database, that's still a lot of
listeners that can be behind. Though I agree that bca6e6435 will have
mitigated quite a lot (yes, max_connections is quite high). Another
mitigation would be to spread across more smaller database clusters,
which we need to do anyway.

That said, your approach is conceptually simpler which is also worth
something and it gets essentially all the same benefits for more
normal use cases. If the QUEUE_CLEANUP_DELAY were raised a bit then we
could do mitigation of the rest on the client side by having idle
databases send dummy notifies every now and then to trigger clean up
for their database. The flip-side is that slow backends will then have
further to catch up, thus holding the lock longer. It's not worth
making it configurable so we have to guess, but 16 is perhaps a good
compromise.

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

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

On Mon, 16 Sep 2019 at 00:14, Tom Lane <tgl@sss.pgh.pa.us> wrote:

... I also think we
can simplify the handling of other-database listeners by including
them in the set signaled by SignalBackends, but only if they're
several pages behind. So that leads me to the attached patch;
what do you think?

I think I like the idea of having SignalBackend do the waking up a
slow backend but I'm not enthused by the "lets wake up (at once)
everyone that is behind". That's one of the issues I was explicitly
trying to solve. If there are any significant number of "slow"
backends then we get the "thundering herd" again.

But do we care? With asyncQueueAdvanceTail gone from the listeners,
there's no longer an exclusive lock for them to contend on. And,
again, I failed to see any significant contention even in HEAD as it
stands; so I'm unconvinced that you're solving a live problem.

regards, tom lane

Hoi Tom,

On Mon, 16 Sep 2019 at 15:33, Tom Lane <tgl@sss.pgh.pa.us> wrote:

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

I think I like the idea of having SignalBackend do the waking up a
slow backend but I'm not enthused by the "lets wake up (at once)
everyone that is behind". That's one of the issues I was explicitly
trying to solve. If there are any significant number of "slow"
backends then we get the "thundering herd" again.

But do we care? With asyncQueueAdvanceTail gone from the listeners,
there's no longer an exclusive lock for them to contend on. And,
again, I failed to see any significant contention even in HEAD as it
stands; so I'm unconvinced that you're solving a live problem.

You're right, they only acquire a shared lock which is much less of a
problem. And I forgot that we're still reducing the load from a few
hundred signals and exclusive locks per NOTIFY to perhaps a dozen
shared locks every thousand messages. You'd be hard pressed to
demonstrate there's a real problem here.

So I think your patch is fine as is.

Looking at the release cycle it looks like the earliest either of
these patches will appear in a release is PG13, right?

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

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

On Mon, 16 Sep 2019 at 15:33, Tom Lane <tgl@sss.pgh.pa.us> wrote:

But do we care? With asyncQueueAdvanceTail gone from the listeners,
there's no longer an exclusive lock for them to contend on. And,
again, I failed to see any significant contention even in HEAD as it
stands; so I'm unconvinced that you're solving a live problem.

You're right, they only acquire a shared lock which is much less of a
problem. And I forgot that we're still reducing the load from a few
hundred signals and exclusive locks per NOTIFY to perhaps a dozen
shared locks every thousand messages. You'd be hard pressed to
demonstrate there's a real problem here.

So I think your patch is fine as is.

OK, pushed.

Looking at the release cycle it looks like the earliest either of
these patches will appear in a release is PG13, right?

Right.

regards, tom lane