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@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 Fri Dec 13 2002 - 23:36:21 CST