Re: Problems with approach #2 to value locking (INSERT ... ON CONFLICT UPDATE/IGNORE patch)

On Sat, Jan 3, 2015 at 2:41 AM, Heikki Linnakangas
<hlinnakangas@vmware.com> wrote:
> A-ha, I see. And this can happen without INSERT ON CONFLICT, too? In that
> case, one of the transactions is bound to error and roll back anyway, but
> you get a deadlock error instead of the constraint violation error, which is
> not as nice.

Agreed.

I haven't experimentally verified that this can happen with exclusion
constraints without the ON CONFLICT patch being involved, but I would
be very surprised if it didn't. How could it possibly not happen? It's
not all that bad since, as you say, one or the other xact was going to
be aborted anyway. Since the insertions would have to occur at exactly
the same time, even if one backend were to get an exclusion violation
rather than being killed by the deadlock detector, the choice of which
backend to raise an error within would be essentially random anyway.

There are probably additional factors that make the situation more
complicated than it is for the ON CONFLICT patch, but it's clear to me
that the mutual dependency that can be involved with two ordinary
exclusion constraint inserters is reason enough for those to deadlock.

>> I'm sorry, but I honestly don't see a way to fix this one. It would
>> take a very novel approach, since exclusion constraints can work with
>> any amgettuple AM. I briefly though about doing something crazy with
>> the deadlock detector, but apart from anything else I think that might
>> introduce livelock risks.
>
> Some ideas off the top of my head:
>
> 1. On conflict, mark the inserted tuple as killed, and retry. But before
> retrying, acquire a new kind of lock on the table, let's call it
> SpeculativeInsertionLock. This fixes the deadlock, by retrying instead of
> sleeping, and avoids the livelock because the new lock ensures that only one
> backend retries at a time.

We "super delete" the tuple on retry already. However, we wait for the
other xact with our broken promise tuple still physically inserted
into the heap. We can't super delete the tuple before
XactLockTableWait()/SpeculativeInsertionWait() lock acquisition,
because doing so risks livelock. I think you already agree with me up
to here.

However, if we're not sleep waiting on the other xact (rather, we're
"retrying [with a new class of exclusive table-level lock] instead of
sleeping"), why should our xact be able to do useful work on retry?
Why won't it just spin/busy wait? More to the point, why wouldn't it
deadlock when it is obliged to wait on a third inserter's tuple?
AFAICT, you've just moved the problem around, because now we're
obliged to get a shared lock on the xid or speculative token
(XactLockTableWait()/SpeculativeInsertionWait()) of a session that
itself wants this new table level lock that only we have.

> 2. Use e.g. the XID (or backend id or something) to resolve the tie. When
> you have inserted a tuple and find that it conflicts with another
> in-progress insertion, check the conflicting tuple's xmin. If it's < current
> XID, wajt for the other inserter to finish. Otherwise kill the
> already-inserted tuple first, and wait only after that.

That sounds scary. I think it might introduce livelock hazards. What
about some third xact, that's waiting on our XID, when we ourselves
super delete the already-inserted tuple in deference to the first
xact/inserter? I also worry about the bloating this could cause.

> 3. Don't allow the deadlock checker to kick in. Instead, use timeout with
> exponential backoff to avoid getting stuck in the livelock indefinitely.

I don't know if that would work, but it seems very undesirable...to
add a new behavior to the deadlock detector just to make ON CONFLICT
IGNORE work with exclusion constraints. It seems to me like the best
suggestion, though.

> Can there be other lock types involved in the deadlock? AFAICS it's always
> going to be between two or more backends that wait on each with
> XactLockTableWait (or some variant of that specific to speculative
> insertions).

I believe you're right about that. But don't forget that at least with
the current implementation, we also get spurious exclusion violations.
I think that's because we super-delete, as we must for other reasons
(so they're not a concern for regular inserters today, as I said). So
solving the problem for regular inserters is probably easier than
solving it for the ON CONFLICT patch.

-- 
Peter Geoghegan