alternative model for handling locking in parallel groups

Discussion of my incomplete group locking patch seems to have
converged around two points: (1) Everybody agrees that undetected
deadlocks are unacceptable. (2) Nobody agrees with my proposal to
treat locks held by group members as mutually non-conflicting. As was
probably evident from the emails on the other thread, it was not
initially clear to me why you'd EVER want heavyweight locks held by
different group members to mutually conflict, but after thinking it
over for a while, I started to think of cases where you would
definitely want that:

1. Suppose two or more parallel workers are doing a parallel COPY.
Each time the relation needs to be extended, one backend or the other
will need to take the relation extension lock in Exclusive mode.
Clearly, taking this lock needs to exclude both workers in the same
group and also unrelated processes.

2. Suppose two or more parallel workers are doing a parallel
sequential scan, with a filter condition of myfunc(a.somecol), and
that myfunc(a.somecal) updates a tuple in some other table. Access to
update that tuple will be serialized using tuple locks, and it's no
safer for two parallel workers to do this at the same time than it
would be for two unrelated processes to do it at the same time.

On the other hand, I think there are also some cases where you pretty
clearly DO want the locks among group members to be mutually
non-conflicting, such as:

3. Parallel VACUUM. VACUUM takes ShareUpdateExclusiveLock, so that
only one process can be vacuuming a relation at the same time. Now,
if you've got several processes in a group that are collaborating to
vacuum that relation, they clearly need to avoid excluding each other,
but they still need to exclude other people. And in particular,
nobody else should get to start vacuuming that relation until the last
member of the group exits. So what you want is a
ShareUpdateExclusiveLock that is, in effect, shared across the whole
group, so that it's only released when the last process exits.

4. Parallel query on a locked relation. Parallel query should work on
a table created in the current transaction, or one explicitly locked
by user action. It's not acceptable for that to just randomly
deadlock, and skipping parallelism altogether, while it'd probably be
acceptable for a first version, is not going a good long-term
solution. It also sounds buggy and fragile for the query planner to
try to guess whether the lock requests in the parallel workers will
succeed or fail when issued. Figuring such details out is the job of
the lock manager or the parallelism infrastructure, not the query
planner.

After thinking about these cases for a bit, I came up with a new
possible approach to this problem. Suppose that, at the beginning of
parallelism, when we decide to start up workers, we grant all of the
locks already held by the master to each worker (ignoring the normal
rules for lock conflicts). Thereafter, we do everything the same as
now, with no changes to the deadlock detector. That allows the lock
conflicts to happen normally in the first two cases above, while
preventing the unwanted lock conflicts in the second two cases.

I believe that it can also be made safe against undetected deadlocks.
Suppose A1 and A2 are members of the same parallel group. If A1 waits
for some unrelated process B which waits for A2, then there are two
possibilities. One is that the blocking lock held by A2 was acquired
before the beginning of parallelism. In that case, both A1 and A2
will hold the problematic lock, so the deadlock detector will notice
that A1 waits for B waits for A1 and report the deadlock. Woohoo!
The other option is that the blocking lock was acquired after the
start of parallelism. But if that's the case, it probably *isn't* a
deadlock, because the lock in question is likely one we intend to hold
only briefly, like a relation extension lock, tuple lock, or a
relation lock on a system catalog that we're scanning for a system
cache lookup. So it's fine to let A1 wait, in this case. In due
time, A2 will release the lock, and everyone will be happy.

But wait, I hear you cry! What if (as in case #2 above) the lock in
question is long-lived, one which we intend to retain until
transaction commit? I think we can just decide not to support this
case for right now. Impose a coding rule that nothing done in
parallel-mode can acquire such a lock; verify when finishing the
parallel section of a computation, before waiting for other members of
the parallel group, or terminating, that we have not accumulated any
such locks, and throw an error if we have. We could make this case
work, but it's tricky. Aside from needing to work out how to make
deadlock detection work, we'd need to transfer the lock in the
opposite direction, from child to parent. Otherwise, we'd have a
behavior difference vs. the non-parallel case: instead of being
retained until transaction commit, the lock would only be retained
until the current parallel phase ended. For now, it seems fine not to
allow this: lots of useful things will be parallel-safe even without
support for this case.

We might have problems if the following sequence of events occurs: (1)
the user backend acquires AccessExclusiveLock on a relation; (2) it
spawns a parallel worker; (3) either of the two processes now attempts
to get AccessShareLock on that relation. LockCheckConflicts() will
(correctly) realize that the processes' own AccessExclusiveLock
doesn't conflict with its desire for AccessShareLock, but it will
still think that the other one does. To fix that, we can teach
LockCheckConflicts() that it's always OK to get a lock if your
existing locks conflict with all modes with which the new lock would
also conflict. I'm not absolutely positive that's a big enough
band-aid, but it's certainly simple to implement, and I can't think of
a problem with it off-hand.

Thoughts?

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Hi,

On 2014-11-13 15:59:11 -0500, Robert Haas wrote:
> Discussion of my incomplete group locking patch seems to have
> converged around two points: (1) Everybody agrees that undetected
> deadlocks are unacceptable. (2) Nobody agrees with my proposal to
> treat locks held by group members as mutually non-conflicting. As was
> probably evident from the emails on the other thread, it was not
> initially clear to me why you'd EVER want heavyweight locks held by
> different group members to mutually conflict, but after thinking it
> over for a while, I started to think of cases where you would
> definitely want that:

> 1. Suppose two or more parallel workers are doing a parallel COPY.
> Each time the relation needs to be extended, one backend or the other
> will need to take the relation extension lock in Exclusive mode.
> Clearly, taking this lock needs to exclude both workers in the same
> group and also unrelated processes.
>
> 2. Suppose two or more parallel workers are doing a parallel
> sequential scan, with a filter condition of myfunc(a.somecol), and
> that myfunc(a.somecal) updates a tuple in some other table. Access to
> update that tuple will be serialized using tuple locks, and it's no
> safer for two parallel workers to do this at the same time than it
> would be for two unrelated processes to do it at the same time.
>
> On the other hand, I think there are also some cases where you pretty
> clearly DO want the locks among group members to be mutually
> non-conflicting, such as:
>
> 3. Parallel VACUUM. VACUUM takes ShareUpdateExclusiveLock, so that
> only one process can be vacuuming a relation at the same time. Now,
> if you've got several processes in a group that are collaborating to
> vacuum that relation, they clearly need to avoid excluding each other,
> but they still need to exclude other people. And in particular,
> nobody else should get to start vacuuming that relation until the last
> member of the group exits. So what you want is a
> ShareUpdateExclusiveLock that is, in effect, shared across the whole
> group, so that it's only released when the last process exits.

Note that you'd definitely not want to do this naively - currently
there's baked in assumptions into the vaccum code that only one backend
is doing parts of it.

I think there's

> 4. Parallel query on a locked relation. Parallel query should work on
> a table created in the current transaction, or one explicitly locked
> by user action. It's not acceptable for that to just randomly
> deadlock, and skipping parallelism altogether, while it'd probably be
> acceptable for a first version, is not going a good long-term
> solution.

FWIW, I think it's perfectly acceptable to refuse to work in parallel in
that scenario. And not just for now.

The biggest argument I can see to that is parallel index creation.

> It also sounds buggy and fragile for the query planner to
> try to guess whether the lock requests in the parallel workers will
> succeed or fail when issued.

I don't know. Checking whether we hold a self exclusive lock on that
relation doesn't sound very problematic to me.

> Figuring such details out is the job of
> the lock manager or the parallelism infrastructure, not the query
> planner.

I don't think you can sensibly separate the parallelism infrastructure
and the query planner.

> After thinking about these cases for a bit, I came up with a new
> possible approach to this problem. Suppose that, at the beginning of
> parallelism, when we decide to start up workers, we grant all of the
> locks already held by the master to each worker (ignoring the normal
> rules for lock conflicts). Thereafter, we do everything the same as
> now, with no changes to the deadlock detector. That allows the lock
> conflicts to happen normally in the first two cases above, while
> preventing the unwanted lock conflicts in the second two cases.

I don't think that's safe enough. There's e.g. a reason why ANALYZE
requires SUE lock. It'd definitely not be safe to simply grant the
worker a SUE lock, just because the master backend already analyzed it
or something like that. You could end up with the master and worker
backends ANALYZEing the same relation.

That said, I can definitely see use for a infrastructure where we
explicitly can grant another backend a lock that'd conflict with one
we're already holding. But I think it'll need to be more explicit than
just granting all currently held locks at the "highest" current
level. And I think it's not necessarily going to be granting them all
the locks at their current levels.

What I'm thinking of is basically add a step to execMain.c:InitPlan()
that goes through the locks and grants the child process all the locks
that are required for the statement to run. But not possibly preexisting
higher locks.

Greetings,

Andres Freund

On Fri, Nov 14, 2014 at 12:03 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> Note that you'd definitely not want to do this naively - currently
> there's baked in assumptions into the vaccum code that only one backend
> is doing parts of it.
>
> I think there's

Did something you intended get left out here?

>> 4. Parallel query on a locked relation. Parallel query should work on
>> a table created in the current transaction, or one explicitly locked
>> by user action. It's not acceptable for that to just randomly
>> deadlock, and skipping parallelism altogether, while it'd probably be
>> acceptable for a first version, is not going a good long-term
>> solution.
>
> FWIW, I think it's perfectly acceptable to refuse to work in parallel in
> that scenario. And not just for now.

I don't agree with that, but my point is that I think that fixing it
so it works is probably no more work than detecting that it isn't
going to work, whether the specific proposal in this email pans out or
not.

> The biggest argument I can see to that is parallel index creation.
>
>> It also sounds buggy and fragile for the query planner to
>> try to guess whether the lock requests in the parallel workers will
>> succeed or fail when issued.
>
> I don't know. Checking whether we hold a self exclusive lock on that
> relation doesn't sound very problematic to me.

That seems like gross oversimplification of what we need to check.
For example, suppose we want to do a parallel scan. We grab
AccessShareLock. Now, another backends waits for AccessExcusiveLock.
We start workers, who all try to get AccessShareLock. They wait
behind the AccessExclusiveLock, while, outside the view of the current
lock manager, we wait for them. No process in our group acquired more
than AccesShareLock, yet we've got problems. We need a simple and
elegant way to avoid this kind of situation.

>> After thinking about these cases for a bit, I came up with a new
>> possible approach to this problem. Suppose that, at the beginning of
>> parallelism, when we decide to start up workers, we grant all of the
>> locks already held by the master to each worker (ignoring the normal
>> rules for lock conflicts). Thereafter, we do everything the same as
>> now, with no changes to the deadlock detector. That allows the lock
>> conflicts to happen normally in the first two cases above, while
>> preventing the unwanted lock conflicts in the second two cases.
>
> I don't think that's safe enough. There's e.g. a reason why ANALYZE
> requires SUE lock. It'd definitely not be safe to simply grant the
> worker a SUE lock, just because the master backend already analyzed it
> or something like that. You could end up with the master and worker
> backends ANALYZEing the same relation.

Well, in the first version of this, I expect to prohibit parallel
workers from doing any DML or DDL whatsoever - they will be strictly
read-only. So you won't have that problem. Now, eventually, we might
relax that, but I would expect that a prohibition on the workers
starting new utility commands while in parallel mode wouldn't be very
high on anyone's list of restrictions to relax.

> That said, I can definitely see use for a infrastructure where we
> explicitly can grant another backend a lock that'd conflict with one
> we're already holding. But I think it'll need to be more explicit than
> just granting all currently held locks at the "highest" current
> level. And I think it's not necessarily going to be granting them all
> the locks at their current levels.
>
> What I'm thinking of is basically add a step to execMain.c:InitPlan()
> that goes through the locks and grants the child process all the locks
> that are required for the statement to run. But not possibly preexisting
> higher locks.

This doesn't actually solve the problem, because we can be
incidentally holding locks on other relations - system catalogs, in
particular - that will cause the child processes to fail.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Fri, Nov 14, 2014 at 2:29 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>
> Discussion of my incomplete group locking patch seems to have
> converged around two points: (1) Everybody agrees that undetected
> deadlocks are unacceptable. (2) Nobody agrees with my proposal to
> treat locks held by group members as mutually non-conflicting. As was
> probably evident from the emails on the other thread, it was not
> initially clear to me why you'd EVER want heavyweight locks held by
> different group members to mutually conflict, but after thinking it
> over for a while, I started to think of cases where you would
> definitely want that:
>
> 1. Suppose two or more parallel workers are doing a parallel COPY.
> Each time the relation needs to be extended, one backend or the other
> will need to take the relation extension lock in Exclusive mode.
> Clearly, taking this lock needs to exclude both workers in the same
> group and also unrelated processes.
>
> 2. Suppose two or more parallel workers are doing a parallel
> sequential scan, with a filter condition of myfunc(a.somecol), and
> that myfunc(a.somecal) updates a tuple in some other table. Access to
> update that tuple will be serialized using tuple locks, and it's no
> safer for two parallel workers to do this at the same time than it
> would be for two unrelated processes to do it at the same time.
>

Won't this be addressed because both updates issued from myfunc()
are considered as separate commands, so w.r.t lock it should behave
as 2 different updates in same transaction. I think there may be more
things to make updates possible via parallel workers apart from tuple lock.

> On the other hand, I think there are also some cases where you pretty
> clearly DO want the locks among group members to be mutually
> non-conflicting, such as:
>
> 3. Parallel VACUUM. VACUUM takes ShareUpdateExclusiveLock, so that
> only one process can be vacuuming a relation at the same time. Now,
> if you've got several processes in a group that are collaborating to
> vacuum that relation, they clearly need to avoid excluding each other,
> but they still need to exclude other people. And in particular,
> nobody else should get to start vacuuming that relation until the last
> member of the group exits. So what you want is a
> ShareUpdateExclusiveLock that is, in effect, shared across the whole
> group, so that it's only released when the last process exits.
>
> 4. Parallel query on a locked relation. Parallel query should work on
> a table created in the current transaction, or one explicitly locked
> by user action. It's not acceptable for that to just randomly
> deadlock, and skipping parallelism altogether, while it'd probably be
> acceptable for a first version, is not going a good long-term
> solution. It also sounds buggy and fragile for the query planner to
> try to guess whether the lock requests in the parallel workers will
> succeed or fail when issued. Figuring such details out is the job of
> the lock manager or the parallelism infrastructure, not the query
> planner.
>
> After thinking about these cases for a bit, I came up with a new
> possible approach to this problem. Suppose that, at the beginning of
> parallelism, when we decide to start up workers, we grant all of the
> locks already held by the master to each worker (ignoring the normal
> rules for lock conflicts). Thereafter, we do everything the same as
> now, with no changes to the deadlock detector. That allows the lock
> conflicts to happen normally in the first two cases above, while
> preventing the unwanted lock conflicts in the second two cases.
>

Here I think we have to consider how to pass the information about
all the locks held by master to worker backends. Also I think assuming
we have such an information available, still it will be considerable work
to grant locks considering the number of locks we acquire [1] (based
on Simon's analysis) and the additional memory they require. Finally
I think deadlock detector work might also be increased as there will be
now more procs to visit.

In general, I think this scheme will work, but I am not sure it is worth
at this stage (considering initial goal to make parallel workers will be
used for read operations).

[1] :
http://www.postgresql.org/message-id/CA+U5nMJLuBGduWjqikt6UmQRFMrmRQdhpNDb6Z5Xzdtb0pH2vQ@mail.gmail.com

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Tue, Nov 18, 2014 at 8:53 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> Won't this be addressed because both updates issued from myfunc()
> are considered as separate commands, so w.r.t lock it should behave
> as 2 different updates in same transaction. I think there may be more
> things to make updates possible via parallel workers apart from tuple lock.

Hmm. It won't work to have different backends with different command
counters anyway. If backend 1 is using command counter 5 and backend
2 is using command counter 6, then backend 2 will see its snapshot
changing under it as backend 1 makes changes. That's not OK.

But that's not really the point. Heavyweight locks are sometimes used
to protect pretty low-level things, like the right to update a tuple,
or physically extend a relation by a block on disk, or split a bucket
in a hash index. It won't be OK to just ignore the requirement of
mutual exclusion in those cases, I think. We could of course decide
that the parallel processes must have their own mechanism to prevent
such conflicts apart from the lock manager, but they've got to be
prevented somehow.

>> After thinking about these cases for a bit, I came up with a new
>> possible approach to this problem. Suppose that, at the beginning of
>> parallelism, when we decide to start up workers, we grant all of the
>> locks already held by the master to each worker (ignoring the normal
>> rules for lock conflicts). Thereafter, we do everything the same as
>> now, with no changes to the deadlock detector. That allows the lock
>> conflicts to happen normally in the first two cases above, while
>> preventing the unwanted lock conflicts in the second two cases.
>
> Here I think we have to consider how to pass the information about
> all the locks held by master to worker backends. Also I think assuming
> we have such an information available, still it will be considerable work
> to grant locks considering the number of locks we acquire [1] (based
> on Simon's analysis) and the additional memory they require. Finally
> I think deadlock detector work might also be increased as there will be
> now more procs to visit.
>
> In general, I think this scheme will work, but I am not sure it is worth
> at this stage (considering initial goal to make parallel workers will be
> used for read operations).

I think this scheme might be quite easy to implement - we just need
the user backend to iterate over the locks it holds and serialize them
(similar to what pg_background does for GUCs) and store that in the
DSM; the parallel worker calls some function on that serialized
representation to put all those locks back in place. The actual
deadlock detector should need few or no changes, which seems like a
major advantage in comparison with the approach dicussed on the other
thread.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Wed, Nov 19, 2014 at 8:56 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>
> On Tue, Nov 18, 2014 at 8:53 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com>
wrote:
> > Won't this be addressed because both updates issued from myfunc()
> > are considered as separate commands, so w.r.t lock it should behave
> > as 2 different updates in same transaction. I think there may be more
> > things to make updates possible via parallel workers apart from tuple
lock.
>
> Hmm. It won't work to have different backends with different command
> counters anyway. If backend 1 is using command counter 5 and backend
> 2 is using command counter 6, then backend 2 will see its snapshot
> changing under it as backend 1 makes changes. That's not OK.
>

Right, so which means that we need to do much more than just make
lock manager changes to handle parallel WRITE operations.

> But that's not really the point. Heavyweight locks are sometimes used
> to protect pretty low-level things, like the right to update a tuple,
> or physically extend a relation by a block on disk, or split a bucket
> in a hash index. It won't be OK to just ignore the requirement of
> mutual exclusion in those cases, I think. We could of course decide
> that the parallel processes must have their own mechanism to prevent
> such conflicts apart from the lock manager, but they've got to be
> prevented somehow.
>

Agreed and I would vote for going by simple mechanism in this case
which is to prohibit any *write* operation in parallel worker.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Wed, Nov 19, 2014 at 8:56 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>
> On Tue, Nov 18, 2014 at 8:53 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com>
wrote:
> >> After thinking about these cases for a bit, I came up with a new
> >> possible approach to this problem. Suppose that, at the beginning of
> >> parallelism, when we decide to start up workers, we grant all of the
> >> locks already held by the master to each worker (ignoring the normal
> >> rules for lock conflicts). Thereafter, we do everything the same as
> >> now, with no changes to the deadlock detector. That allows the lock
> >> conflicts to happen normally in the first two cases above, while
> >> preventing the unwanted lock conflicts in the second two cases.
> >
> > Here I think we have to consider how to pass the information about
> > all the locks held by master to worker backends. Also I think assuming
> > we have such an information available, still it will be considerable
work
> > to grant locks considering the number of locks we acquire [1] (based
> > on Simon's analysis) and the additional memory they require. Finally
> > I think deadlock detector work might also be increased as there will be
> > now more procs to visit.
> >
> > In general, I think this scheme will work, but I am not sure it is worth
> > at this stage (considering initial goal to make parallel workers will be
> > used for read operations).
>
> I think this scheme might be quite easy to implement - we just need
> the user backend to iterate over the locks it holds and serialize them
> (similar to what pg_background does for GUCs) and store that in the
> DSM; the parallel worker calls some function on that serialized
> representation to put all those locks back in place.

Today, I have thought about this scheme a bit more and it seems that
we can go through the local lock hash table (LockMethodLocalHash) to
get the locks which user backend holds and then using Local lock tag
we can form the similar hash table in worker. Apart from that, I think
we need to get the information for fastpath locks from PGPROC and
restore the same information for worker (here before restore we need
to ensure that nobody else has moved that fast path lock to shared
table, we can do that by checking the available fast path information
against the user backend fast path lock information). For non-fastpath
locks, I think we can search shared hash table (LockMethodLockHash) to
obtain the lock information and assign the same to local lock and finally
establish the proclock entry for parallel worker in LockMethodProcLockHash.

In the above analysis, one point which slightly worries me is that for
non-fastpath locks we need to obtain partitionLock which can be
bottleneck as all parallel worker's needs to obtain the same and it can
very well contend with any unrelated backend as well.

> The actual
> deadlock detector should need few or no changes, which seems like a
> major advantage in comparison with the approach dicussed on the other
> thread.
>

Okay, but there is one downside to this approach as well which is
additional overhead of acquiring more number of locks which will
be more severe as it has to be taken care every time for a parallel
operation for each worker whereas in other approach there will be
no such overhead.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com