Re: [HACKERS] Reducing likelihood of deadlocks (was referential Integrity and SHARE locks)
On Tue, 13 Feb 2007, Marc Munro wrote: > On Mon, 2007-12-02 at 00:10 -0500, Tom Lane wrote: > > Marc Munro <[EMAIL PROTECTED]> writes: > > > Consider a table C containing 2 child records C1 and C2, of parent P. > > > If transaction T1 updates C1 and C2, the locking order of the the > > > records will be C1, P, C2. Another transaction, T2, that attempts to > > > update only C2, will lock the records in order C2, P. > > > > > The locks on C2 and P are taken in different orders by the two > > > transactions, leading to the possibility of deadlock. > > > > But the lock on P is shared, hence no deadlock. > > Doh! Yes, you are right. It is not that simple. > > For deadlock to occur, we need a transaction that takes an exclusive > lock on P as well as on one of the children. Let us replace T2 with a > new transaction, T3, which is going to update P and only one of its > children. > > If T3 is going to update P and C1 without the possibility of deadlock > against T1, then it must take out the locks in the order C1, P. If, on > the other hand, it is going to update P and C2, then the locks must be > taken in the order P, C2. > > This means that there is no single strategy we can apply to T3 that will > guarantee to avoid deadlocks with transactions that update only C (ie > transactions, which to a developers point of view do nothing to P, and > so should be unable to deadlock with T3). This scenario would do it, too: Table X has rows representing an object of some kind. These objects contain other objects, which are represented by rows in table Y. Suppose X stores a count of the Y objects it contains in a particular status (because your application needs to get this quickly) and suppose the count is updated by a trigger. The Y objects hold references to the containing X, checked by FK constraints. A query which updates the status of one or more Ys can deadlock with another instance of itself. It first locks a Y row, then shared-locks an X row, then updates the X row (when the trigger runs). Two transactions could get to the shared-lock stage simultaneously, then deadlock. I've come across some a bit like this in my own applications. I'm sure there are many, many, others. > From an application developer's standpoint there are few options, none > of them ideal: > > 1) Insist on a locking policy that requires updates to first lock their > parent records. > > This is horrible for so many reasons. It should be unnecessary; it > causes exclusive locking on parent records, thereby eliminating the > gains made by introducing row share locks in 8.1; it is onerous on the > developers; it is error-prone; etc I once tried to define a locking order for rows in a database. It doesn't work (though this was at a time when FK constraint checking used FOR UPDATE locks, which, of course, made things much worse). This wasn't specifically for FK checks, but they were an important cause of deadlocks. Firstly, you have no idea of the order in which rows locked by a statement will be locked. UPDATE d SET counter=counter+1 WHERE d.a=1 could deadlock with UPDATE d SET counter=counter+1 WHERE d.b=1. Secondly, even if you could defining a usable locking order across all of the rows in your database (not just the tables) is nearly impossible. I suppose you could base it on, say, the order (tablename, id) but you'd have to go to extreme lengths to follow this. Imagine having to determine the id of every row you want to update and the ID and table name of every row they'll lock because of FK constraints and then sort a big set of 'SELECT .. FOR SHARE' and 'UPDATE' statements. That's a lot of queries - and huge variety of useful queries you can't use any more. And once you've done all that you might find your application has race conditions - there are sometimes other reasons for performing queries in a certain order. > 2) Remove FK constraints to eliminate the possibility of RI-triggered > deadlocks. > > Ugh. Deadlocks aren't the only problem FK constraints' locks are going to cause you. It's quite possible you have, somewhere, a small number of rows referenced via FKs by a huge number of rows. Think about the amount of locking (not just locks on rows, but internal locks on bits of cache) and cache coherency logic going on in a production SMP machine. It'll depend on your load and schema, of course, but I've found the constraints to be mostly impractical in my production systems. Some I can keep, but only if I know that the checks aren't going to be triggered too often. > 3) Encapsulate all transactions in some form of retry mechanism that > traps deadlocks and retries those transactions. > > This may not be practicable, and incurs all of the overhead of > encountering and trapping deadlocks in the first place. Also, as each > deadlock occurs, a number of locks will be left active before deadlock > detection kicks in, increasing the window for further deadlocks. On a > busy system, the first deadlock m
Re: [HACKERS] Reducing likelihood of deadlocks (was referential Integrity and SHARE locks)
On Tue, 2007-13-02 at 11:38 -0500, Tom Lane wrote: > Marc Munro <[EMAIL PROTECTED]> writes: > > From an application developer's standpoint there are few options, none > > of them ideal: > > How about > > 4) Make all the FK constraints deferred, so that they are only checked > at end of transaction. Then the locking order of transactions that only > modify C is always C1, C2, ..., P. Excellent suggestion. Thank you. __ Marc signature.asc Description: This is a digitally signed message part
Re: [HACKERS] Reducing likelihood of deadlocks (was referential Integrity and SHARE locks)
Marc Munro <[EMAIL PROTECTED]> writes: > From an application developer's standpoint there are few options, none > of them ideal: How about 4) Make all the FK constraints deferred, so that they are only checked at end of transaction. Then the locking order of transactions that only modify C is always C1, C2, ..., P. regards, tom lane ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] Reducing likelihood of deadlocks (was referential Integrity and SHARE locks)
On Mon, 2007-12-02 at 00:10 -0500, Tom Lane wrote: > Marc Munro <[EMAIL PROTECTED]> writes: > > Consider a table C containing 2 child records C1 and C2, of parent P. > > If transaction T1 updates C1 and C2, the locking order of the the > > records will be C1, P, C2. Another transaction, T2, that attempts to > > update only C2, will lock the records in order C2, P. > > > The locks on C2 and P are taken in different orders by the two > > transactions, leading to the possibility of deadlock. > > But the lock on P is shared, hence no deadlock. Doh! Yes, you are right. It is not that simple. For deadlock to occur, we need a transaction that takes an exclusive lock on P as well as on one of the children. Let us replace T2 with a new transaction, T3, which is going to update P and only one of its children. If T3 is going to update P and C1 without the possibility of deadlock against T1, then it must take out the locks in the order C1, P. If, on the other hand, it is going to update P and C2, then the locks must be taken in the order P, C2. This means that there is no single strategy we can apply to T3 that will guarantee to avoid deadlocks with transactions that update only C (ie transactions, which to a developers point of view do nothing to P, and so should be unable to deadlock with T3). From an application developer's standpoint there are few options, none of them ideal: 1) Insist on a locking policy that requires updates to first lock their parent records. This is horrible for so many reasons. It should be unnecessary; it causes exclusive locking on parent records, thereby eliminating the gains made by introducing row share locks in 8.1; it is onerous on the developers; it is error-prone; etc 2) Remove FK constraints to eliminate the possibility of RI-triggered deadlocks. Ugh. 3) Encapsulate all transactions in some form of retry mechanism that traps deadlocks and retries those transactions. This may not be practicable, and incurs all of the overhead of encountering and trapping deadlocks in the first place. Also, as each deadlock occurs, a number of locks will be left active before deadlock detection kicks in, increasing the window for further deadlocks. On a busy system, the first deadlock may well trigger a cascade of further deadlocks. __ Marc signature.asc Description: This is a digitally signed message part
Re: [HACKERS] Reducing likelihood of deadlocks (was referential Integrity and SHARE locks)
Marc Munro <[EMAIL PROTECTED]> writes: > Consider a table C containing 2 child records C1 and C2, of parent P. > If transaction T1 updates C1 and C2, the locking order of the the > records will be C1, P, C2. Another transaction, T2, that attempts to > update only C2, will lock the records in order C2, P. > The locks on C2 and P are taken in different orders by the two > transactions, leading to the possibility of deadlock. But the lock on P is shared, hence no deadlock. regards, tom lane ---(end of broadcast)--- TIP 1: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] Reducing likelihood of deadlocks (was referential Integrity and SHARE locks)
On Sun, 2007-11-02 at 12:21 -0600, Jim C. Nasby wrote: > On Thu, Feb 08, 2007 at 08:47:42AM -0800, Marc Munro wrote: > > One of the causes of deadlocks in Postgres is that its referential > > integrity triggers can take locks in inconsistent orders. Generally a > > child record will be locked before its parent, but not in all cases. > > Where would PostgreSQL lock the parent before the child? AFAIK the > behavior should be consistent... Consider a table C containing 2 child records C1 and C2, of parent P. If transaction T1 updates C1 and C2, the locking order of the the records will be C1, P, C2. Another transaction, T2, that attempts to update only C2, will lock the records in order C2, P. The locks on C2 and P are taken in different orders by the two transactions, leading to the possibility of deadlock. __ Marc signature.asc Description: This is a digitally signed message part
Re: [HACKERS] Reducing likelihood of deadlocks (was referential Integrity and SHARE locks)
On Thu, Feb 08, 2007 at 08:47:42AM -0800, Marc Munro wrote: > One of the causes of deadlocks in Postgres is that its referential > integrity triggers can take locks in inconsistent orders. Generally a > child record will be locked before its parent, but not in all cases. Where would PostgreSQL lock the parent before the child? AFAIK the behavior should be consistent... -- Jim Nasby[EMAIL PROTECTED] EnterpriseDB http://enterprisedb.com 512.569.9461 (cell) ---(end of broadcast)--- TIP 7: You can help support the PostgreSQL project by donating at http://www.postgresql.org/about/donate
Re: [HACKERS] Reducing likelihood of deadlocks (was referential Integrity and SHARE locks)
On Thu, 2007-08-02 at 18:06 +0100, Csaba Nagy wrote: > The problem is that eliminating the deadlock is still not the complete > cake... the interlocking still remains, possibly leading to degraded > performance on high contention on very common parent rows. The real > solution would be when an update on the parent table's non-referenced > fields is not interlocking at all with updates of the child rows... and > I think there were some proposals to do that. Agreed. There are two issues here, unnecessary blocking and deadlock. These can be tackled separately. My proposal deals only with the deadlock issue. Even if if contention is reduced, for instance by implementing column-level locking, there will still be the potential for deadlock arising from inconsistent ordering of locks. I continue to stand by my proposal. __ Marc signature.asc Description: This is a digitally signed message part
Re: [HACKERS] Reducing likelihood of deadlocks (was referential Integrity and SHARE locks)
On Thu, 2007-02-08 at 17:47, Marc Munro wrote: > [snip] One of the causes of deadlocks in Postgres is that its referential > integrity triggers can take locks in inconsistent orders. Generally a > child record will be locked before its parent, but not in all cases. [snip] The problem is that eliminating the deadlock is still not the complete cake... the interlocking still remains, possibly leading to degraded performance on high contention on very common parent rows. The real solution would be when an update on the parent table's non-referenced fields is not interlocking at all with updates of the child rows... and I think there were some proposals to do that. In fact one possibility to avoid this problem is vertical partitioning, i.e. separating the non-key columns in a parallel table and updating them there. However this is a choice only when you know it beforehand and you're not inheriting the schema from other DBs... Cheers, Csaba. ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
[HACKERS] Reducing likelihood of deadlocks (was referential Integrity and SHARE locks)
I am going to restate my earlier proposal, to clarify it and in the hope of stimulating more discussion. One of the causes of deadlocks in Postgres is that its referential integrity triggers can take locks in inconsistent orders. Generally a child record will be locked before its parent, but not in all cases. My proposal modifies the order in which locks are taken by referential integrity triggers, so that parents are always locked before their children. The proposal is, that referential integrity triggers should fire before locking the tuple from which they are triggered. I guess a new sort of trigger is required for this, a before-lock trigger. If this is a dumb idea, please tell me why. If it would cause more problems than it solves, ditto. If it would be difficult to implement, let's discuss and try to find solutions. __ Marc signature.asc Description: This is a digitally signed message part
