Deadlock in Index (where index is B+ tree) Locking with Intention Locks

Deadlock in Index (where index is B+ tree) Locking with Intention Locks

Post by Novi » Sat, 14 Dec 2002 02:07:19



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,
Tim

 
 
 

Deadlock in Index (where index is B+ tree) Locking with Intention Locks

Post by Mikito Harakir » Sat, 14 Dec 2002 03:20:37



Quote:> 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.

Is your protocol deadlock safe? Maybe. But it's not very interesting, since
all your transactions are serialized on the root node. You need to unlock
root node early, and then watch problem to happen!

 
 
 

Deadlock in Index (where index is B+ tree) Locking with Intention Locks

Post by Novi » Sat, 14 Dec 2002 09:27:25


Actually it isn't serialized at the root node.

Perhaps your misunderstanding is due to the concept of the lock IX
(Intentional Exclusive Lock).  This lock allows other Intentional
Exclusive locks to be obtained (or such is my understanding).

For instance the following ordering is allowed:
T1 - IX(root)
T2 - IX(root)
T1 - IX(B)
T2 - IX(B)
T1 - IX(D) IX(H) X(P) X(H) X(D) X(B) U(P) U(H) U(D) U(B) U(root)
T2 - 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)

And of course will not result in deadlock.  Basically, I'm trying to
confirm or deny the theory that "all locking protocols that allow
concurrency can result in deadlock".

The index locking (with a tree) appears to me to be an exception to
this rule.

Thanks for your suggestion though... I don't mean to sound
unappreciative of your feedback.

Thanks,
Tim




> > 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.

> Is your protocol deadlock safe? Maybe. But it's not very interesting, since
> all your transactions are serialized on the root node. You need to unlock
> root node early, and then watch problem to happen!

 
 
 

Deadlock in Index (where index is B+ tree) Locking with Intention Locks

Post by D Gunterman » Sun, 15 Dec 2002 02:48:38





> > 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.

> Is your protocol deadlock safe? Maybe. But it's not very interesting,
since
> all your transactions are serialized on the root node. You need to unlock
> root node early, and then watch problem to happen!

Unlocking the root node early would certainly provide problems if block/page
splits propogated up the hierarchy to the root...doesn't seem like a viable
alternative.
 
 
 

Deadlock in Index (where index is B+ tree) Locking with Intention Locks

Post by D Gunterman » Sun, 15 Dec 2002 05:56:32



Quote:> 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

- Show quoted text -

Quote:> 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,
> Tim

 
 
 

Deadlock in Index (where index is B+ tree) Locking with Intention Locks

Post by Jonathan Leffle » Sun, 15 Dec 2002 14:36:21





>>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>

Guardian of DBD::Informix 1.04.PC1 -- http://dbi.perl.org/

 
 
 

Deadlock in Index (where index is B+ tree) Locking with Intention Locks

Post by Jan Hidde » Wed, 18 Dec 2002 22:22:40



>In class I was told that any locking protocol can result in deadlock
>when there is concurrency.

Actually, that is not completely true. It is well known that the socalled
"tree locking protocol" which basically outlaws bi-directional traversal
cannot dead-lock.

For references see:

  SILBERSCHATZ, A. and KEDEM, Z. Consistency in hierarchical database
  systems. J. of the ACM 27,1 (January 1980) 72-80

or

  Lanin, V. and Shasha, D. 1990. Tree Locking on Changing Trees. Technical
  Report 503, New York University. http://citeseer.nj.nec.com/lanin90tree.html

If you stick to 2PL then a transaction excludes all other operations of
other transactions because it will lock the root, but the beauty of the tree
locking protocol is that you don't have to stick to 2PL to guarantee
serializability.

-- Jan Hidders

 
 
 

1. Indices/Access Methods (not B+ Trees)

Hi,

I'm doing a project for a DB class I'm taking.
I've been looking into disk-based index methods
for mulit-dimensional data.  I've heard that
Informix's recent DBMSs ship with R-tree as
one of the access methods.  Other versions of
the R-tree are apparently implemented in various
DataBlades.

Has anyone worked with R-trees or any other
non-hash, non-B-tree access methods with Informix's
DBMS?  Have any of you implemented your own
access method with Informix's Universal Data Option?

I'd love to hear any comments.  
(Speed, ease of use, effort involved, etc.)

---Tom

2. How to Move servers ??

3. Source for B+ Tree indexing schemes

4. record count property from stored procedure

5. Index Managers and B+ trees

6. Connect via simple name

7. *** HELP - Index Locks are creating DEADLOCKS ***

8. update lock causing an unrelated table index to be locked

9. Databases, Data Structures, B Trees, B+ Trees, Patricia Trees

10. What is a B+ tree? (was Re: Index Managers and B+ trees)

11. No DeadLocks ...Lock file locks