[mysql-dde] Deadlock detection

  • From: "Peter Volk" <Peter.Volk@xxxxxxx>
  • To: mysql-dde@xxxxxxxxxxxxx
  • Date: Wed, 8 Mar 2006 13:01:41 +0100 (MET)

Hey,

I've been spending some brains on the deadlock detection:

In general there seem to be 2 ways of detecting a deadlock:

1) for every lock requested build a lock graph to detect cycles
2) If a dealock accors then build a lock graph to find the transaction
involved with the lock and choose a transaction to roll back.

The first solution is extramly complicated in a distributed system. So my
proposal would be to use the second one. I found a paper on a method that
sounds good (I'll send it to you as soon as I get home). It detects the
deadlock with a timeout of a transaction. Once a transaction has past this
timeout then a graph is build. To build this graph for a distributed system
you can query each server and ask it for their lockgraph. The idea is if a
server suspects a deadlock then it starts to build the deadlock graph. Each
node is queried seperatly and the deadlock graph is build incrementell.
After each increment the deadlock detection is performed on the graph. The
atvantage of this instead of getting the graphs from all servers at once and
then building a big graph the incremental aproach can detect a deadlock
earlier and without querying all server. if e.g. we have 3 servers and
server 1 is in a deadlock with server 2. Server 1 suspects a deadlock. After
this it queries server 2 for its graph and then builds the deadlock graph
locally. If the server already detects a deadlock with this smal subset of
the global graph then the algorithm continues. If not then it queries the
next server until the deadlock is found or the transaction is can continue
(because the tablescan took so long). This method reduces the communication
between the Servers within the cluster since not always all servers are
asked for their lock graph. Also it could be faster then always getting the
complete graph because the graph is smaller and the deadlock could be
detected earlyer.

What do you think?

Peter

-- 
Bis zu 70% Ihrer Onlinekosten sparen: GMX SmartSurfer!
Kostenlos downloaden: http://www.gmx.net/de/go/smartsurfer
MySql-DDE discussion list
www.freelists.org/

Other related posts: