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

On 01/03/2015 12:00 PM, Peter Geoghegan wrote:
> Two concurrent exclusion constraints inserters can easily insert at
> exactly the same time, and then wait on each other's xact, and then
> deadlock. That can't happen with B-Tree inserts because the checking
> and insertion happen at the same time, when that exclusive buffer lock
> is held. Some inserter establishes the right to insert, and then
> actually inserts atomically, and when it releases the buffer lock
> every other inserter will see for itself that it has inserted (and
> established the right to do so).

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.

> 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.

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.

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

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).

- Heikki