Thread: Not your father's question about deadlocks

Once upon a time, I put a question regarding deadlocks to the group,
and Tom Lane immediately answered with this:

>The guy waiting on the tuple-specific lock is second in
>line to actually mung the tuple.  Whoever is first in line behind the
>current tenant will be blocked trying to acquire ShareLock on the
>current tenant's transaction ID.
>
>What you appear to have is a situation where two transactions are trying
>to lock or update the same two rows in different orders.  Without a lot
>more info about your application logic, I couldn't guess why this seems
>to be associated with having more than two transaction interested in the
>same tuple.
>
>Note that the guy looking for ShareLock on the tuple is evidently either
>doing SELECT FOR SHARE on this tuple, or trying to install a new tuple
>referencing this one as a foreign key (which does SELECT FOR SHARE under
>the hood).  But he's blocked by someone who's done either SELECT FOR
>UPDATE or an actual UPDATE on that tuple.

I'm still creeping up on the problem. I configured postgres to resolve
a deadlock only after a month, and now I seem to have a complete
snapshot of one of them. The details are below. The part that doesn't
fit with what Tom says is that there are only two transactions involved.
The first and third "guys" are the same guy!

The first one, I'll call it X71, is the one doing the insert. The
LedgerDetail table references various other tables; the one of interest
is the buys table, and it is inserting a record referencing buy #955. It
had done several other inserts before this, some of them also referencing
buy #955. (In fact, the immediately preceding statement was one such.)
This is evidenced by the RowShareLock that it holds on the buys table.

The other one, X78, is executing a stored procedure which has only one
reference to buys, this statement:
    update buys set budget=budget+remainder where id=buynum;

So the timeline is this
   X71                          X78
   -----------------------      ----------------------
   insert buy955 reference
   insert buy955 reference
   insert buy955 reference
                                update buy955 (blocks)
   insert buy955 reference (blocks)

Here is the state of the system. I have edited it somewhat. The pg_locks
table actually shows five waiters; the three that I've deleted started
much later than when the deadlock happened, so I've deleted all the pg_locks
rows that belonged to their transactions. I've also deleted all pg_locks
rows for X71 and X78 that referred to relations that the other transaction
had no lock on. And I've deleted empty or constant columns, and the relation
oid column.
======================================================================
   27478 |  insert into LedgerDetail

(ledger,strategy,advId,campaignId,buyId,creativeId,siteId,providerType,adspotId,checkbookId,count,dr,cr,dr_usd,cr_usd,time)
         values('imp',',61144,',533,676,955,4076,2,5,656,31275,14,0,110936,0,142142,1163530800)
         | 2006-11-14 19:22:43.760703+00 | 2006-11-14 19:22:29.342683+00
   99056 |  FETCH 1 FROM "PgSQL_0CDD618C"
         | 2006-11-14 19:22:43.748025+00 | 2006-11-13 19:21:40.038948+00

2006-11-14 11:22:43 PST[99056]LOG:  statement: DECLARE "PgSQL_0CDD618C" CURSOR FOR
               select repayBuyBudget(955, 31275, fromusd(ecc2usd(7790), 'EUR'))

         relation          |   locktype    |  page | tuple | transactionid |  transaction |  pid  |       mode       |
granted

---------------------------+---------------+-------+-------+---------------+--------------+-------+------------------+---------
 buys                      | relation      |       |       |               |    101953371 | 27478 | AccessShareLock  |
t
 buys                      | relation      |       |       |               |    101953371 | 27478 | RowShareLock     |
t
 buys                      | tuple         |    38 |    11 |               |    101953371 | 27478 | ShareLock        |
f
 buys_pkey                 | relation      |       |       |               |    101953371 | 27478 | AccessShareLock  |
t

                           | transactionid |       |       |     101953371 |    101954678 | 99056 | ShareLock        |
f
 buys                      | relation      |       |       |               |    101954678 | 99056 | AccessShareLock  |
t
 buys                      | relation      |       |       |               |    101954678 | 99056 | RowExclusiveLock |
t
 buys                      | tuple         |    38 |    11 |               |    101954678 | 99056 | ExclusiveLock    |
t
 buys_pkey                 | relation      |       |       |               |    101954678 | 99056 | AccessShareLock  |
t
 buys_pkey                 | relation      |       |       |               |    101954678 | 99056 | RowExclusiveLock |
t
======================================================================

That scenario seems quite simple, but I can't reproduce the deadlock with
this seemingly-identical sequence. The "Sn" prompts show the sequence of
statements done from psql in two terminal sessions.
    S1 => create table t1(f1 int primary key);
    NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "t1_pkey" for table "t1"
    CREATE TABLE
    S2 => create table t2(f1 int references t1);
    CREATE TABLE
    S3 => insert into t1 values(1);
    INSERT 0 1
    S4 => begin;
    BEGIN
    S7 => update t1 set f1=1;   (blocks)

    S5 => begin;
    BEGIN
    S6 => insert into t2 values(1);
    INSERT 0 1
    S8 => insert into t2 values(1);
    INSERT 0 1

S8 is the statement that seems analagous to the one that blocks in the
real system, but it doesn't here.

Apart from that test being different somehow that I can't figure out,
situation on the real system seems to suggest that I need to either
lock all the reference tables at the beginning of X71 (uncomfortable),
or have it commit after each insert (unacceptable).

Thanks in advance for your help.

Clarence Gardner <clarence@silcom.com> writes:
> That scenario seems quite simple, but I can't reproduce the deadlock with
> this seemingly-identical sequence.

This is a bug in 8.1 and up.  The reason you couldn't reproduce it is
that it requires a minimum of three transactions involved, two of which
concurrently grab ShareLock on a tuple --- resulting in a MultiXact
being created to represent the concurrent lock holder.  The third xact
then comes along and tries to update the same tuple, so it naturally
blocks waiting for the existing ShareLocks to go away.  Then one of the
original xacts tries to grab share lock again.  It should fall through
because it "already has" the lock, but it fails to recognize this and
queues up behind the exclusive locker ... deadlock!

Reproducer:

Session 1:
create table foo (f1 int primary key, f2 text);
insert into foo values(1, 'z');
create table bar (f1 int references foo);
begin;
insert into bar values(1);

Session 2:
begin;
insert into bar values(1);

Session 3:
update foo set f2='q';

Back to session 1:
insert into bar values(1);
ERROR:  deadlock detected

Note that session 2 might actually have exited before the deadlock
occurs.

I think the problem is that HeapTupleSatisfiesUpdate() always returns
HeapTupleBeingUpdated when XMAX is a running MultiXact, even if the
MultiXact includes our own transaction.  This seems correct for the
usages in heap_update and heap_delete --- we have to wait for the
multixact's other members to terminate.  But in heap_lock_tuple
we need a special case when we are already a member of the MultiXact:
fall through without trying to reacquire the tuple lock.

Comments?  Should we change HeapTupleSatisfiesUpdate's API to
distinguish this case, or is it better to have a localized change
in heap_lock_tuple?

            regards, tom lane

On 11/17/06, Tom Lane <tgl@sss.pgh.pa.us> wrote:


--
gurjeet[.singh]@EnterpriseDB.com
singh.gurjeet@{ gmail | hotmail | yahoo }.com

"Gurjeet Singh" <singh.gurjeet@gmail.com> writes:
> On 11/17/06, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> we need a special case when we are already a member of the MultiXact:
>> fall through without trying to reacquire the tuple lock.

> Small implementation detail: Also keep a count of how many times the same
> session requested the same lock, and do not release the lock until he
> requests same number of releases.

No need for that, because there isn't any heap_unlock_tuple.

            regards, tom lane

On 11/17/06, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Cool... I didn't know we could get away with that in PG land!!

I assume unlocking is done by a COMMIT/ROLLBACK.

--
gurjeet[.singh]@EnterpriseDB.com
singh.gurjeet@{ gmail | hotmail | yahoo }.com