Re: Deadlock in Index (where index is B+ tree) Locking with Intention Locks
From: Jonathan Leffler <jleffler_at_earthlink.net>
Date: Sat, 14 Dec 2002 05:36:21 GMT
Message-ID: <3DFAC323.9030308_at_earthlink.net>
>>In class I was told that any locking protocol can result in deadlock
>>when there is concurrency.
>>
>>Also in class, the professor gave us a simple example of deadlock
>>occurring in the tree, if bi-directional traversal (traversing both up
>>and down the tree) is allowed. This is very easy to understand how
>>deadlock can occur in this case.
>>
>>But I can't come up with an example of deadlock occuring in a tree
>>based structure when you don't allow this bi-directional traversal.
>>
>>For example, in the following tree:
>>http://www.cs.queensu.ca/~cassidy/media/images/tree.jpg
>>
>>let's say that there are two transactions:
>>T1 and T2
>>
>>And they all want to delete database objects - you'll notice in some
>>cases that an X (exclusive lock) is obtained on the inner nodes of the
>>tree and not in others. This is because in some cases the B+ tree's
>>index will change if one of it's node's order falls beneath its
>>predefined number and this change could perculate up the tree.
>>
>>And let's imagine the following scenario:
>>T1 - IX(root) IX(B) IX(D) IX(H) X(P) X(H) X(D) X(B) U(P) U(H) U(D)
>>U(B) U(root)
>>T2 - IX(root) IX(B) IX(D) IX(H) X(O) X(H) X(D) X(B) U(O) U(H) U(D)
>>U(B) U(root)
>>T3 - IX(root) IX(B) IX(D) IX(G) X(N) X(G) X(D) X(B) U(N) U(G) U(D)
>>U(B) U(root)
>>
>>There is no permutation I could find of the above that would result in
>>deadlock.
>>
>>If you can think of a more simple set of transactions that would
>>result in deadlock I would also be interested in that.
>>
>>Thanks for any suggestions,
Date: Sat, 14 Dec 2002 05:36:21 GMT
Message-ID: <3DFAC323.9030308_at_earthlink.net>
D Guntermann wrote:
> "Novice" <6tc1_at_qlink.queensu.ca> wrote in message > news:b80e4a77.0212120907.7cfb153d_at_posting.google.com... >
>>In class I was told that any locking protocol can result in deadlock
>>when there is concurrency.
>>
>>Also in class, the professor gave us a simple example of deadlock
>>occurring in the tree, if bi-directional traversal (traversing both up
>>and down the tree) is allowed. This is very easy to understand how
>>deadlock can occur in this case.
>>
>>But I can't come up with an example of deadlock occuring in a tree
>>based structure when you don't allow this bi-directional traversal.
>>
>>For example, in the following tree:
>>http://www.cs.queensu.ca/~cassidy/media/images/tree.jpg
>>
>>let's say that there are two transactions:
>>T1 and T2
>>
>>And they all want to delete database objects - you'll notice in some
>>cases that an X (exclusive lock) is obtained on the inner nodes of the
>>tree and not in others. This is because in some cases the B+ tree's
>>index will change if one of it's node's order falls beneath its
>>predefined number and this change could perculate up the tree.
>>
>>And let's imagine the following scenario:
>>T1 - IX(root) IX(B) IX(D) IX(H) X(P) X(H) X(D) X(B) U(P) U(H) U(D)
>>U(B) U(root)
>>T2 - IX(root) IX(B) IX(D) IX(H) X(O) X(H) X(D) X(B) U(O) U(H) U(D)
>>U(B) U(root)
>>T3 - IX(root) IX(B) IX(D) IX(G) X(N) X(G) X(D) X(B) U(N) U(G) U(D)
>>U(B) U(root)
>>
>>There is no permutation I could find of the above that would result in
>>deadlock.
>>
> > > Assuming the multiple granularity locking protocol with 2PL, would the > following schedule achieve the effect you are looking for? > > > Time | T1 | T2 | T3 > -----|--------------|--------------|------------------ > T1 | IX(root) | | > T2 | IX(B) | | > T3 | IX(D) | | > T4 | IX(H) | | > T5 | | | IX(root) > T6 | | | IX(B) > T7 | | | IX(D) > T8 | | | IX(G) > T9 | X(P) | | > T10 | | IX(root) | > T11 | | IX(B) | > T12 | | IX(D) | > T13 | | IX(H) | > T14 | | IX(O) | > T15 | | waiting X(H) | > T16 | waiting X(H) | waiting X(H) | > T17 | waiting X(H) | waiting X(H) | X(N) > T17 | waiting X(H) | waiting X(H) | X(G) > T18 | waiting X(H) | waiting X(H) | waiting X(O) > T19 | waiting X(H) | waiting X(H) | waiting X(O) > > I am also assuming that alternative locking protocols such as B-link trees > are not considered in the question you pose. > > > Dan >
>>If you can think of a more simple set of transactions that would
>>result in deadlock I would also be interested in that.
>>
>>Thanks for any suggestions,
Try:
http://www.informatik.uni-trier.de/~ley/db/conf/vldb/Mohan90.html
I seem to remember reading about a paper (rather than reading the paper :-() which showed how you could manage locking in B+trees w/o locking the root node automatically.
I'm not sure it's the one cited above -- maybe a visit to citeseer would help too. Or even google?
-- Jonathan Leffler #include <disclaimer.h> Email: jleffler_at_earthlink.net, jleffler_at_us.ibm.com Guardian of DBD::Informix 1.04.PC1 -- http://dbi.perl.org/Received on Sat Dec 14 2002 - 06:36:21 CET