Re: Deterministic locking in PostgreSQL

Hi Tom,

First of all thanks for the quick response. No, the arrival order will not
be deterministic. Here is how we ensure determinism.

1.) SQL requests are delivered to the replication agent in a specific total
order. This could occur either because they were already serialized by a
database (master/slave case) or delivery through group communications
(master/master case).

2.) Within replication we use advisory table locks at the middleware level
to guide scheduling of request execution. This allows non-conflicting SQL
statements to proceed in parallel but blocks those that might conflict.

The reason I asked about determinism in locking is that this algorithm has a
problem with distributed deadlock. If you look back at the example in the
original post, you get the following:

1: T1, T2, T3: begin
2: T1: update foo set value='x' where id=25; <-- Grabs row lock,
grabs and releases middleware table lock
3: T2: update foo set value='y' where id=25; <-- Grabs middleware
table lock, blocks on row lock
4: T3: update foo set value='z' where id=25; <-- DEADLOCKED
5: T1: update foo set value='x1' where id=25;
6: T1: commit
7: T2: commit
8: T3: commit

At step 3 we deadlock since the request blocks in the database while holding
the middleware table lock.

Our plan to alleviate this problem is to look for requests that block (i.e.,
show up in pg_locks) and release their middleware table lock. As long as
locks are granted deterministically this allows the next request to
proceed--the ordering is now enforced by the database itself.

There are some other possible race conditions, such as results of
sub-selects on UPDATE statements, but this optimization will help us avoid a
number of unnecessary failures in master/master replication. If anything
else about this raises hackles on your neck (or anyone else's for that
matter) please let me know. It's better to know now. :)

Cheers, Robert

On 5/9/08 4:53 PM, "Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Robert Hodges <robert(dot)hodges(at)continuent(dot)com> writes:
>> This question may have an obvious answer I have somehow missed, but to what
>> extent is locking order deterministic in PostgreSQL? For example, if
>> requests from multiple transactions arrive in some deterministic order and
>> acquire locks, can one assume that locks will be granted in the same order
>> if the requests are repeated at different times or on different servers?
>
> Yeah, it should be deterministic given consistent arrival order.
>
>> Lock determinism is an important issue for replication algorithms that
>> depend on database instances to behave as state machines.
>
> However, the idea of depending on a replication algorithm that has race
> conditions gives me the willies ... and that sure sounds like what you
> are describing. Do not trust your data to the assumption that arrival
> order will be deterministic.
>
> regards, tom lane
>

--
Robert Hodges, CTO, Continuent, Inc.
Email: robert(dot)hodges(at)continuent(dot)com
Mobile: +1-510-501-3728 Skype: hodgesrm