Thread: Avoiding deadlocks ...
Kevin,
This one is for you:
Two sessions, in transaction:
Process A Process B
update session where id = X; update order where orderid = 5;
update order where orderid = 5; update order where orderid = 5;
... deadlock error.
It seems like we ought to be able to avoid a deadlock in this case;
there's a clear precedence of who grabbed the order row first. Does
your serializability patch address the above situation at all?
-- -- Josh Berkus PostgreSQL Experts Inc.
http://www.pgexperts.com
On 8/19/10 3:51 PM, Josh Berkus wrote:
> Kevin,
>
> This one is for you:
>
> Two sessions, in transaction:
>
> Process A Process B
>
> update session where id = X;
> update order where orderid = 5;
> update order where orderid = 5;
> update order where orderid = 5;
> ... deadlock error.
Johto on IRC pointed out I left something out of the above: "session" is
referenced in an FK by "orders", and session = X is related to orderid = 5.
>
> It seems like we ought to be able to avoid a deadlock in this case;
> there's a clear precedence of who grabbed the order row first. Does
> your serializability patch address the above situation at all?
>
-- -- Josh Berkus PostgreSQL Experts Inc.
http://www.pgexperts.com
On 20 August 2010 09:39, Josh Berkus <josh@agliodbs.com> wrote: > On 8/19/10 3:51 PM, Josh Berkus wrote: >> Kevin, >> >> This one is for you: >> >> Two sessions, in transaction: >> >> Process A Process B >> >> update session where id = X; >> update order where orderid = 5; >> update order where orderid = 5; >> update order where orderid = 5; >> ... deadlock error. > > Johto on IRC pointed out I left something out of the above: "session" is > referenced in an FK by "orders", and session = X is related to orderid = 5. > I was wondering what that had to do with anything. -- Thom Brown Registered Linux user: #516935
On 2010-08-20 11:39 AM +0300, Josh Berkus wrote: > On 8/19/10 3:51 PM, Josh Berkus wrote: >> Two sessions, in transaction: >> >> Process A Process B >> >> update session where id = X; >> update order where orderid = 5; >> update order where orderid = 5; >> update order where orderid = 5; >> ... deadlock error. > > Johto on IRC pointed out I left something out of the above: "session" is > referenced in an FK by "orders", and session = X is related to orderid = 5. Right, that would result in a deadlock. I think truly serializable transactions still need to SELECT FOR SHARE here for foreign keys to work, no? Regards, Marko Tiikkaja
Josh Berkus wrote: >> Two sessions, in transaction: >> >> Process A Process B >> >> update session where id = X; >> update order where orderid = 5; >> update order where orderid = 5; >> update order where orderid = 5; >> ... deadlock error. > > Johto on IRC pointed out I left something out of the above: > "session" is referenced in an FK by "orders", and session = X is > related to orderid = 5. The patch I'm offering implements the SSI techniques published by Michael Cahill, et al. Those techniques basically allow the current snapshot isolation to run as it currently does, but monitors for read/write conflicts to generate a new type of serialization failure when a cycle becomes possible which could create an anomaly. There are no read/write conflict cycles in your example, so it would behave just as REPEATABLE READ and SERIALIZABLE now behave -- you get a deadlock which rolls back one of the transactions. I don't see how SSI can be modified to generate some other form of serialization failure here, but I'm always open to suggestions. -Kevin
I wrote: > I don't see how SSI can be modified to generate some other form of > serialization failure here, but I'm always open to suggestions. Actually, after thinking about it a bit more, the UPDATE statements *do* read the rows before writing, so a naive implementation would see write skew in Josh's example and generate a rollback before things got far enough to cause a deadlock. In fact, a few months ago the implementation probably would have done so, before we implemented the optimization mentioned in section 3.7.3 of Cahill's doctoral thesis[1]. The reasons for implementing that change were: (1) It avoids getting an SIREAD lock on a row if that row has been updated by the transaction. I believe that in the PostgreSQL implementation we even avoid taking the SIREAD lock when we're in a scan from an UPDATE or DELETE statement, but I'd have to dig into the code to confirm. (2) Because of (1) and the removal of an SIREAD lock on a row is later updated, the shared memory structures used for tracking SIREAD locks can be somewhat smaller and access to them will be a bit faster. (3) I *think* that having the additional SIREAD locks would tend to increase the false positive rate, although I'd need to spend some time working through that to be sure. So, the question would be: does this "optimization" from the paper actually improve performance because of the above points more than the savings which would accrue from catching the conflict in Josh's example before it gets to the point of deadlock? I can add that to the list of things to check once we have a good set of benchmarks. -Kevin [1] http://hdl.handle.net/2123/5353
Marko Tiikkaja <marko.tiikkaja@cs.helsinki.fi> wrote: > I think truly serializable transactions still need to SELECT FOR > SHARE here for foreign keys to work, no? That depends on how you look at it. The SSI patch that Dan and I have been working on doesn't attempt to change the implementation techniques for foreign keys, because SSI only enforces integrity among serializable transactions -- and we want foreign keys to be enforced regardless of the transaction isolation levels used. When writing queries which will be run at the serializable isolation level, if you are only concerned with anomalies from interaction with other serializable transactions, you *never* have to explicitly code SELECT FOR SHARE or SELECT FOR UPDATE, nor do you ever need to explicitly request a lock; so from that perspective the answer to the question is "No." Under the covers, PostgreSQL will continue to use existing techniques for enforcing referential integrity defined by foreign keys; so from that perspective the answer to the question is "Yes." Hopefully that made sense.... -Kevin
On 2010-08-20 6:19 PM, Kevin Grittner wrote: > Marko Tiikkaja<marko.tiikkaja@cs.helsinki.fi> wrote: > >> I think truly serializable transactions still need to SELECT FOR >> SHARE here for foreign keys to work, no? > > That depends on how you look at it. The SSI patch that Dan and I > have been working on doesn't attempt to change the implementation > techniques for foreign keys, because SSI only enforces integrity > among serializable transactions -- and we want foreign keys to be > enforced regardless of the transaction isolation levels used. Exactly. Regards, Marko Tiikkaja
On Thu, Aug 19, 2010 at 11:51 PM, Josh Berkus <josh@agliodbs.com> wrote: > update session where id = X; > update order where orderid = 5; > update order where orderid = 5; So i think this will already deadlock. A has a exclusive-lock on session<X> and is waiting on order<5>. B has an exclusive lock on order<5> and is waiting on a share-lock on session<x> > update order where orderid = 5; > ... deadlock error. > Do you actually get a prompt here to type this command? -- greg
Greg Stark <gsstark@mit.edu> wrote: > Josh Berkus <josh@agliodbs.com> wrote: >> update session where id = X; >> update order where orderid = 5; >> update order where orderid = 5; > > So i think this will already deadlock. > > A has a exclusive-lock on session<X> and is waiting on order<5>. B > has an exclusive lock on order<5> and is waiting on a share-lock > on session<x> No, see Tom's explanation on the related "Deadlock bug" thread: http://archives.postgresql.org/pgsql-hackers/2010-08/msg01464.php >> update order where orderid = 5; >> ... deadlock error. > > Do you actually get a prompt here to type this command? Yes. The attachment at the start of the other thread makes it easy to confirm: http://archives.postgresql.org/pgsql-hackers/2010-08/msg01447.php -Kevin
On 8/20/10 8:23 AM, Marko Tiikkaja wrote:
> On 2010-08-20 6:19 PM, Kevin Grittner wrote:
>> Marko Tiikkaja<marko.tiikkaja@cs.helsinki.fi> wrote:
>>
>>> I think truly serializable transactions still need to SELECT FOR
>>> SHARE here for foreign keys to work, no?
>>
>> That depends on how you look at it. The SSI patch that Dan and I
>> have been working on doesn't attempt to change the implementation
>> techniques for foreign keys, because SSI only enforces integrity
>> among serializable transactions -- and we want foreign keys to be
>> enforced regardless of the transaction isolation levels used.
Ok, then that's not a fix for this particular problem. This case is a
good example, though, of showing how deadlocks are the most expensive
type of serialization failure, and thus models which avoid deadlocks (in
favor of other kinds of blocking and/or serialization errors) are desirable.
-- -- Josh Berkus PostgreSQL Experts Inc.
http://www.pgexperts.com