Fix FK deadlock, but no magic please 
Author Message
 Fix FK deadlock, but no magic please

Quote:

> The terms "dirty read" and "magic" came up during the description of the fix.
> The term "dirty read" is a dirty phrase when your using proper
> transactioning.   The term "magic" is not what you want to hear when the
> database is supposed to be the rock that everything else depends on.

Well, I used magic flippently as short for, I haven't worked out the
details yet because I'm in the sit down design and try things out stage.
I'll apologize for using the term then.

As for dirty reads, given that part of the part that was referred to as
magic involves doing waits on transactions so that it's very much like
the current row locks except with foreign key based knowledge embedded
so as to help avoid deadlocks.  Yes, it's seeing rows that haven't
been committed, but it's mostly seeing them to find out what transactions
it needs to wait on.

Quote:
> Other databases have tackled this issue without the above terms.  From what I
> can tell, there is a standard and non-standard way this can be fixed in
> PostgreSQL.  The standard way would be to implement FK as a part of the
> schema and create the hooks to allow read locks on records by FK only.  The
> non-standard way would be to expand the SQL interface with a non standard FOR
> READ statement (or something similar) and then continue to use triggers.
> Only the developers can decide which method will be easier, work better, or
> is more in line with the overall goals of PostgreSQL.

Record read locks are not quite as good a solution as dirty reads from a
performance standpoint, which is why we've been aiming that direction
first. You'd need column locks pretty much to get equivalent behavior
afaict.  The issue is that with record read locks, you prevent updates to
rows that do not affect the key values.

Quote:
> I've even tried to get an estimate from pgsql.com for this issue, but they
> just ignored me.  I figure that the alternative is to get Oracle which has a
> price tag equivalent to at least 20 man weeks of effort (minimum).  I'd much
> rather see this kind of money go toward making PostgreSQL better.  I don't
> know if I can actually get the money, but I would at least like to know what
> to shoot for.  Maybe I can get multiple customers to split the fee.

I personally can't (I have a full time job that has nothing to do with
PostgreSQL which is part of why this hasn't gotten done yet), but I
certainly wouldn't want that to stop someone who does have the time and
could take the money from doing it instead. :)

---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster



Tue, 05 Jul 2005 03:10:05 GMT
 Fix FK deadlock, but no magic please

Thanks Stephan for you quick response.


Quote:

> > The terms "dirty read" and "magic" came up during the description of the
> > fix. The term "dirty read" is a dirty phrase when your using proper
> > transactioning.   The term "magic" is not what you want to hear when the
> > database is supposed to be the rock that everything else depends on.

> Well, I used magic flippently as short for, I haven't worked out the
> details yet because I'm in the sit down design and try things out stage.
> I'll apologize for using the term then.

> As for dirty reads, given that part of the part that was referred to as
> magic involves doing waits on transactions so that it's very much like
> the current row locks except with foreign key based knowledge embedded
> so as to help avoid deadlocks.  Yes, it's seeing rows that haven't
> been committed, but it's mostly seeing them to find out what transactions
> it needs to wait on.

Fair enough.

- Show quoted text -

Quote:
> > Other databases have tackled this issue without the above terms.  From
> > what I can tell, there is a standard and non-standard way this can be
> > fixed in PostgreSQL.  The standard way would be to implement FK as a part
> > of the schema and create the hooks to allow read locks on records by FK
> > only.  The non-standard way would be to expand the SQL interface with a
> > non standard FOR READ statement (or something similar) and then continue
> > to use triggers. Only the developers can decide which method will be
> > easier, work better, or is more in line with the overall goals of
> > PostgreSQL.

> Record read locks are not quite as good a solution as dirty reads from a
> performance standpoint, which is why we've been aiming that direction
> first. You'd need column locks pretty much to get equivalent behavior
> afaict.  The issue is that with record read locks, you prevent updates to
> rows that do not affect the key values.

From the standpoint of expected behaviour, I don't think you have any choice
but to use record read locks.  When someone does a write lock on a FK table
record they have the expectation that they can do anything they want with the
record including changing the PK or deleting the record.  That is as long as
there were no referencing records before the write lock was obtained.  This
means that someone else shouldn't be able to insert a record referencing
while the FK table record has a write lock.

Not being able to get a read lock when someone else has a write lock is
expected behaviour.  A single record should be able to have one write lock or
multiple read locks, but not both.  If I have a program that checks for
referencing records, deletes them if found, and obtains a write lock on the
FK record then I should reasonably assume that I can change anything about
that record including delete it.  If you don't prevent the write lock when a
read lock is there then the person obtaining the write lock to very well get
errors that they wouldn't normally expect.

Quote:
> > I've even tried to get an estimate from pgsql.com for this issue, but
> > they just ignored me.  I figure that the alternative is to get Oracle
> > which has a price tag equivalent to at least 20 man weeks of effort
> > (minimum).  I'd much rather see this kind of money go toward making
> > PostgreSQL better.  I don't know if I can actually get the money, but I
> > would at least like to know what to shoot for.  Maybe I can get multiple
> > customers to split the fee.

> I personally can't (I have a full time job that has nothing to do with
> PostgreSQL which is part of why this hasn't gotten done yet), but I
> certainly wouldn't want that to stop someone who does have the time and
> could take the money from doing it instead. :)

---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://archives.postgresql.org



Tue, 05 Jul 2005 04:06:37 GMT
 Fix FK deadlock, but no magic please

Quote:

> > Record read locks are not quite as good a solution as dirty reads from a
> > performance standpoint, which is why we've been aiming that direction
> > first. You'd need column locks pretty much to get equivalent behavior
> > afaict.  The issue is that with record read locks, you prevent updates to
> > rows that do not affect the key values.

> >From the standpoint of expected behaviour, I don't think you have any choice
> but to use record read locks.  When someone does a write lock on a FK table
> record they have the expectation that they can do anything they want with the
> record including changing the PK or deleting the record.  That is as long as
> there were no referencing records before the write lock was obtained.  This
> means that someone else shouldn't be able to insert a record referencing
> while the FK table record has a write lock.

> Not being able to get a read lock when someone else has a write lock is
> expected behaviour.  A single record should be able to have one write lock or
> multiple read locks, but not both.  If I have a program that checks for
> referencing records, deletes them if found, and obtains a write lock on the
> FK record then I should reasonably assume that I can change anything about
> that record including delete it.  If you don't prevent the write lock when a
> read lock is there then the person obtaining the write lock to very well get
> errors that they wouldn't normally expect.

Well, for example (assuming two pk rows with 1 and 2 as keys)

T1: begin;
T1: insert into fk values (1);
T2: begin;
T2: insert into fk values (2);
T1: update pk set nonkey='a' where key=2;
T2: update pk set nonkey='b' where key=1;

Should this deadlock?  I'd say no, barring triggers/rules, because
those two updates shouldn't affect the constraint and so whenever
possible the constraint's behavior shouldn't interfere.  But the
obvious record read lock solution would afaics.  The inserts would grab a
read lock on the two pk rows, neither transaction would be able to
get the write lock it wants and it'd deadlock.  Or, what about

T1: begin;
T1: insert into fk values (1);
T2: begin;
T2: insert into fk values (1);
T1: update pk set nonkey='a' where key=1;
T2: update pk set nonkey='a' where key=1;

Without those inserts this would be okay, one would wait for the other
and everything would be okay, but with them I think this deadlocks as
well.

Maybe I'm misunderstanding the scheme you'd expect the foreign keys to use
with the read locks.

---------------------------(end of broadcast)---------------------------



Tue, 05 Jul 2005 04:11:31 GMT
 Fix FK deadlock, but no magic please
I am a little confused on your examples


Quote:

> Well, for example (assuming two pk rows with 1 and 2 as keys)

> T1: begin;
> T1: insert into fk values (1);
> T2: begin;
> T2: insert into fk values (2);
> T1: update pk set nonkey='a' where key=2;
> T2: update pk set nonkey='b' where key=1;

Maybe I don't understand this example.  If T2 inserted fk 2, how did T1 manage
to update a record that references it before T2 committed?  For T1, fk 2
doesn't exist yet so there couldn't be any records referencing it.

Quote:
> Should this deadlock?  I'd say no, barring triggers/rules, because
> those two updates shouldn't affect the constraint and so whenever
> possible the constraint's behavior shouldn't interfere.  But the
> obvious record read lock solution would afaics.  The inserts would grab a
> read lock on the two pk rows, neither transaction would be able to
> get the write lock it wants and it'd deadlock.  Or, what about

> T1: begin;
> T1: insert into fk values (1);
> T2: begin;
> T2: insert into fk values (1);
> T1: update pk set nonkey='a' where key=1;
> T2: update pk set nonkey='a' where key=1;

> Without those inserts this would be okay, one would wait for the other
> and everything would be okay, but with them I think this deadlocks as
> well.

Actually, T2 should block until T1 is committed or rolls back.  The system
cannot determine if the T2 fk should succeed or fail until T1 is committed or
rolled back.  Either that or I am mis-understanding your example again.  
Maybe you should use table names.

Quote:

> Maybe I'm misunderstanding the scheme you'd expect the foreign keys to use
> with the read locks.

The concept of a read lock is to make sure the record doesn't change until the
end of the transaction.  Selects on the record are allowed.  Other read locks
are allowed.  A write look should fail or wait until all read locks are
released.  A read lock should fail or wait for a write lock.

What I was trying to point out is that once a write lock is granted, the
grantee should be able to do anything they want with the record that is legal
in that transaction's view of the DB.  Otherwise, updates and deletes may
fail without any way for the code to determine why (it can't select to find
the offending record).  Here is an example:

TEST_TYPE table has a record with PK of 1
TEST_REC table has record (5) that references TEST_TYPE (1)

T1: wants to change all references to (1) so locks TEST_TYPE (1)
T1: inserts TEST_TYPE (2)
T1: updates TEST_REC (5) to reference TEST_TYPE (2)
T2: inserts TEST_REC (6) referencing TEST_TYPE (1)
I am saying that T2 should error or wait but lets say that you allow it
T1: attempts to delete TEST_TYPE (1)
At this point a SQL error would occur because of TEST_REC (6)
T1: doesn't know what to do because it still can't see or change TEST_REC (6)
no matter how good the code is on catching SQL exceptions and handling them,
T1 can't complete.

By the way, you can change the T2 entry to the very top of the list with the
same effect.  One of the great things about transactions and locking is that
you can write code that, short of a DB failure, can handle every situation.  
Your proposing doing away with that.

---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate

message can get through to the mailing list cleanly



Tue, 05 Jul 2005 06:38:01 GMT
 Fix FK deadlock, but no magic please

Quote:

> I am a little confused on your examples


> > Well, for example (assuming two pk rows with 1 and 2 as keys)

> > T1: begin;
> > T1: insert into fk values (1);
> > T2: begin;
> > T2: insert into fk values (2);
> > T1: update pk set nonkey='a' where key=2;
> > T2: update pk set nonkey='b' where key=1;

> Maybe I don't understand this example.  If T2 inserted fk 2, how did T1 manage
> to update a record that references it before T2 committed?  For T1, fk 2
> doesn't exist yet so there couldn't be any records referencing it.

Noone has completed in the above.  They're two concurrent transactions
that may deadlock.

AFAICT, what you want is a sequence like the below (including lock
annotations) for the above.

Transaction 1: begin;
Transaction 2: begin;
Transaction 1: insert into fk values (1);
 - Checks pk table for value, finds it, gets a read lock
Transaction 2: insert into fk values (2);
 - Checks pk table for value, finds it, gets a read lock
Transaction 1: update pk set nonkey='a' where key=2;
 - Wants a write lock on row with pk.key=2, can't get it because
   Transaction 2 has a read lock. It has to wait.
Transaction 2: update pk set nonkey='a' where key=1;
 - Wants a write lock on row with pk.key=1, can't get it because
   Transaction 1 has a read lock. It has to wait.

---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/users-lounge/docs/faq.html



Tue, 05 Jul 2005 06:56:06 GMT
 Fix FK deadlock, but no magic please
Now I understand what you are trying to say, but what you are describing is
normal (happens in most DBs) and rather uncommon (in my experience).  General
DB design is done so reference tables end up with a lot of read locks and
rarely have a write lock.  It would be cool if you could remove that
contention, but not at the expense of expected write lock behaivor.


Quote:
> AFAICT, what you want is a sequence like the below (including lock
> annotations) for the above.

> Transaction 1: begin;
> Transaction 2: begin;
> Transaction 1: insert into fk values (1);
>  - Checks pk table for value, finds it, gets a read lock
> Transaction 2: insert into fk values (2);
>  - Checks pk table for value, finds it, gets a read lock
> Transaction 1: update pk set nonkey='a' where key=2;
>  - Wants a write lock on row with pk.key=2, can't get it because
>    Transaction 2 has a read lock. It has to wait.
> Transaction 2: update pk set nonkey='a' where key=1;
>  - Wants a write lock on row with pk.key=1, can't get it because
>    Transaction 1 has a read lock. It has to wait.

---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster


Tue, 05 Jul 2005 07:21:03 GMT
 Fix FK deadlock, but no magic please

Quote:

> Now I understand what you are trying to say, but what you are describing is
> normal (happens in most DBs) and rather uncommon (in my experience).  General
> DB design is done so reference tables end up with a lot of read locks and
> rarely have a write lock.  It would be cool if you could remove that
> contention, but not at the expense of expected write lock behaivor.

The other example worries me more though.  Two transactions working with
the same pk row throughout.

Transaction 1: begin;
Transaction 2: begin;
Transaction 1: insert into fk values (1);
 - Checks pk table for value, finds it, gets a read lock
Transaction 2: insert into fk values (1);
 - Checks pk table for value, finds it, gets a read lock
Transaction 1: update pk set nonkey='a' where key=1;
 - Wants a write lock on row with pk.key=1, we can't upgrade
   our lock since T2 also has a read lock.
Transaction 2: update pk set nonkey='a' where key=1;
 - Same as above, except T1

For comparison, the dirty read(plus stuff that we aren't calling magic ;)
) version of the above basically goes:

Transaction 1: begin;
Transaction 2: begin;
Transaction 1: insert into fk values (1);
 - Checks pk table for value, finds it
Transaction 2: insert into fk values (1);
 - Checks pk table for value, finds it
Transaction 1: update pk set nonkey='a' where key=1;
 - Notices that the key is not changed, doesn't check
   fk table at all
Transaction 2: update pk set nonkey='a' where key=1;
 - Wait on transaction 1 since it has a lock on the row.

----
 Basically the real difference externally is that in one case the
blocking occurs before the action happens to the row and in the
other, the action happens and the foreign key code is the one
that does the blocking.  It allows things like not blocking based
on cases like the key not changing. I haven't determined if the
"stuff" necessary to get all the cases working is practical yet,
so I can't say for certain it's better, just that it has the
potential.

---------------------------(end of broadcast)---------------------------



Tue, 05 Jul 2005 07:45:55 GMT
 Fix FK deadlock, but no magic please

Quote:

> Now I understand what you are trying to say, but what you are describing is
> normal (happens in most DBs) and rather uncommon (in my experience).  General
> DB design is done so reference tables end up with a lot of read locks and
> rarely have a write lock.  It would be cool if you could remove that
> contention, but not at the expense of expected write lock behaivor.

I think I may have also misunderstood which lock behavior you were worried
about.  In either scheme if someone does something like:

Transaction 1: begin;
Transaction 2: begin;
Transaction 1: select for update from pk where key=1;
 - Gets a write lock on row with pk.key=1
   [Or does an update or a delete or whatever]
Transaction 2: insert into fk values (1);
 - Needs to wait on the write lock above

That will stay true even in the dirty read scheme.

---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://archives.postgresql.org



Tue, 05 Jul 2005 08:26:14 GMT
 Fix FK deadlock, but no magic please
I think I see what you are trying to acheive.  I agree with you and like the
idea of forgoing read lock when the FK field is not modified.  This should be
a nice performance gain on blindly creating a read lock on a record.  I guess
I just got so worried about the term "dirty read" that I didn't understand
the rest.

Now, if we could only have the feature like Oracle of SELECT  ... FOR UPDATE
NOWAIT, so I can control how long we wait for a lock.  Wait... can't do that
until SQL exceptions stop voiding the transaction (I want to be able to retry
the lock several times before giving up).

Hey, forget that, if you can fix FK deadlock then I'll deal with the rest.


Quote:
> I think I may have also misunderstood which lock behavior you were worried
> about.  In either scheme if someone does something like:

> Transaction 1: begin;
> Transaction 2: begin;
> Transaction 1: select for update from pk where key=1;
>  - Gets a write lock on row with pk.key=1
>    [Or does an update or a delete or whatever]
> Transaction 2: insert into fk values (1);
>  - Needs to wait on the write lock above

> That will stay true even in the dirty read scheme.

---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://archives.postgresql.org



Wed, 06 Jul 2005 01:26:30 GMT
 Fix FK deadlock, but no magic please

Quote:

> Now, if we could only have the feature like Oracle of SELECT  ... FOR UPDATE
> NOWAIT, so I can control how long we wait for a lock.  Wait... can't do that
> until SQL exceptions stop voiding the transaction (I want to be able to retry
> the lock several times before giving up).

What's Oracle's behavior when some of the rows can be locked and some
can't?

---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://archives.postgresql.org



Wed, 06 Jul 2005 02:09:51 GMT
 Fix FK deadlock, but no magic please
Oracle's behavior AFAIK depends on which lock you are talking about.  If you
are talking about not being able to get a read lock then Oracle just blocks
until it can, indefinately unless a deadlock is detected.

If you are talking about a write lock, that depends on how the write lock is
called.  If you call SELECT ... FOR UPDATE or call UPDATE/DELETE without
locking first then again Oracle will block until it can get the lock.  If you
call SELECT ... FOR UPDATE NOWAIT then Oracle will throw a specific SQL
exception if a lock cannot be granted immediately.  This allows you to do a
sleep and retry in your code so that you only wait for a lock so long:

boolean locked = false ;
int retryCount = 3 ;
while (!locked) {
  try {
    SELECT 1 FROM some_table WHERE some_condition FOR UPDATE NOWAIT ;
  } catch (SQLException e) {
    if (retryCount > 0) {
      retryCount += 1 ;
      sleep(1);
    } else {
      throw e ;
    } //end if
  } //end try

Quote:
} //end while

With this kind of logic you can control how long you wait for a lock.  If some
idiot did something that locked a whole bunch of records, you don't want the
entire DB to come to a stop waiting to get a lock.  That type of thing can't
be caught by deadlock detection since the idiot isn't trying to lock anything
else.

Unfortunately, this is not possible in PostgreSQL even if you added the NOWAIT
functionality (yet?).  Thats because the first SQL Exception thrown
automatically voids the transaction and you are forced to roll back.  It
doesn't matter that your code knows how to get around the exception.  
PostgreSQL requires that you call rollback and start over.  It is actually
kind of funny.  When I first came across this it was the first time in my
life that I had ever seen a SQL exception on a sequence select (caused by a
SQL Exception just before the select).


Quote:

> > Now, if we could only have the feature like Oracle of SELECT  ... FOR
> > UPDATE NOWAIT, so I can control how long we wait for a lock.  Wait...
> > can't do that until SQL exceptions stop voiding the transaction (I want
> > to be able to retry the lock several times before giving up).

> What's Oracle's behavior when some of the rows can be locked and some
> can't?

---------------------------(end of broadcast)---------------------------
TIP 2: you can get off all lists at once with the unregister command



Wed, 06 Jul 2005 07:38:12 GMT
 Fix FK deadlock, but no magic please

Quote:

> Oracle's behavior AFAIK depends on which lock you are talking about.  If you
> are talking about not being able to get a read lock then Oracle just blocks
> until it can, indefinately unless a deadlock is detected.

> If you are talking about a write lock, that depends on how the write lock is
> called.  If you call SELECT ... FOR UPDATE or call UPDATE/DELETE without
> locking first then again Oracle will block until it can get the lock.  If you
> call SELECT ... FOR UPDATE NOWAIT then Oracle will throw a specific SQL
> exception if a lock cannot be granted immediately.  This allows you to do a
> sleep and retry in your code so that you only wait for a lock so long:

I was wondering about the NOWAIT specific behavior particularly.  You
could send a notice (completion condition) I guess, but an actual
exception wouldn't work.

---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://archives.postgresql.org



Wed, 06 Jul 2005 08:12:42 GMT
 
 [ 12 post ] 

 Relevant Pages 

1. FK deadlock problem addressed

2. FK deadlock problem addressed

3. Fk fix for noaction update/delete

4. Fk fix for noaction update/delete

5. WANTED: MAGIC Expert (MAGIC Software Enterprise)

6. fixing deadlocking even when only single SPID

7. Deadlock fix

8. Fixed Fragmentation Now Deadlocks!

9. MAGIC - your opinions please

10. can you fix a deadlock on server?

11. To FK or not FK

12. Multiple Columns FK and NULL value - Urgent please


 
Powered by phpBB® Forum Software