[infinispan-dev] deadlock detection on local caches

[Mircea Markus]

Hi,

Original design[1] treats the situation in which two replicating 
transaction are in a deadlock.
Here is an idea for a similar mechanism intended for detecting deadlocks 
on a local cache.

T1, T2 two transactions running on the same local cache.
T1 has lock on k1 and tries to acquire k2
T2 has lock on k2 and tries to acquire k1

Each thread runs the following algorithm, (similar to one described in [1])

lock(int timeout)
{
   while (currentTime < startTime + timeout)
   {
      if (acquire(smallTimeout)) break;
      testEDD(globalTransaction, key);
   }
}



//will run the same algorithm, by both T1 and T2:
//globalTransaction - this is the tx that couldn't acquire lock in 'smallTimeout'
//key - the key that couldn't be locked by globalTransation

testEDD(globalTransaction, key) 

globalTransaction.setLockIntention(key); //we intend to lock the given key...
Object lockOwner = getLockOwner(key);
if (isLocallyOriginatedTx(lockOwner)) {
   Object keyToBeLocked = lockOwner.getLockIntention(); 
   if (globalTransaction.ownsLock(keyToBeLocked)) {
	//this is a deadlock situation
	//use coin toss to determine which tx should rollback!!!
	return;
   } else {
	return; //this will go back to the main loop in 'lock(int timeout)' method
   }
}

Cheers,
Mircea


[1] http://tinyurl.com/nunmyu