KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > continuent > sequoia > controller > locks > WaitForGraph


1 /**
2  * Sequoia: Database clustering technology.
3  * Copyright (C) 2005 AmicoSoft, Inc. dba Emic Networks
4  * Contact: sequoia@continuent.org
5  *
6  * Licensed under the Apache License, Version 2.0 (the "License");
7  * you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * http://www.apache.org/licenses/LICENSE-2.0
11  *
12  * Unless required by applicable law or agreed to in writing, software
13  * distributed under the License is distributed on an "AS IS" BASIS,
14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  * See the License for the specific language governing permissions and
16  * limitations under the License.
17  *
18  * Initial developer(s): Damian Arregui.
19  * Contributor(s): _________________________.
20  */
21
22 package org.continuent.sequoia.controller.locks;
23
24 import java.util.ArrayList JavaDoc;
25 import java.util.Collection JavaDoc;
26 import java.util.HashMap JavaDoc;
27 import java.util.HashSet JavaDoc;
28 import java.util.Iterator JavaDoc;
29 import java.util.List JavaDoc;
30 import java.util.Map JavaDoc;
31 import java.util.Set JavaDoc;
32
33 import org.continuent.sequoia.common.log.Trace;
34 import org.continuent.sequoia.controller.backend.DatabaseBackend;
35 import org.continuent.sequoia.controller.loadbalancer.BackendTaskQueueEntry;
36 import org.continuent.sequoia.controller.loadbalancer.tasks.AbstractTask;
37 import org.continuent.sequoia.controller.locks.TransactionLogicalLock.WaitingListElement;
38 import org.continuent.sequoia.controller.sql.schema.DatabaseSchema;
39 import org.continuent.sequoia.controller.sql.schema.DatabaseTable;
40
41 /**
42  * This class defines a WaitForGraph. Nodes in the graph represent active
43  * transactions. Edges represent "waitin for" relationships: the source node is
44  * waiting for the sink node to release a lock on a given resource. This class
45  * allows to detect cycles in the graph, i.e. deadlocks, and to determine which
46  * transaction to abort in order to break one or more cycles.
47  *
48  * @author <a HREF="mailto:Damian.Arregui@continuent.com">Damian Arregui</a>
49  * @version 1.0
50  */
51 public class WaitForGraph
52 {
53   private static final String JavaDoc INDENT = " ";
54   private DatabaseBackend backend;
55   private List JavaDoc storedProcedureQueue;
56   private Node victim;
57
58   private static Trace logger = Trace
59                                          .getLogger("org.continuent.sequoia.controller.loadbalancer");
60
61   /**
62    * Creates a new <code>WaitForGraph</code> object.
63    *
64    * @param backend database backend that will be used to build the graph.
65    * @param storedProcedureQueue also used to build the graph.
66    */
67   public WaitForGraph(DatabaseBackend backend, List JavaDoc storedProcedureQueue)
68   {
69     this.backend = backend;
70     this.storedProcedureQueue = storedProcedureQueue;
71   }
72
73   /**
74    * Detects deadlocks in the wait-for graph. First build the graph from the
75    * database schema, then walk the graph to detect cycles, and finally examines
76    * the cycles (if found) in order to determine a suitable transaction to be
77    * aborted.
78    *
79    * @return true is a deadlock has been detected, false otherwise.
80    */
81   public boolean detectDeadlocks()
82   {
83     Collection JavaDoc nodes = build();
84     Collection JavaDoc cycles = walk(nodes);
85     kill(cycles);
86     return (victim != null);
87   }
88
89   /**
90    * Returns the ID of the transaction that should be aborted first. This method
91    * returns a value computed during the last run of {@link #detectDeadlocks()}.
92    *
93    * @return victiom transaction ID.
94    */
95   public long getVictimTransactionId()
96   {
97     return victim.getTransactionId();
98   }
99
100   private Collection JavaDoc build()
101   {
102     if (logger.isDebugEnabled())
103       logger.debug("Building wait-for graph...");
104
105     // Triggers schema update
106 DatabaseSchema schema = backend.getDatabaseSchema();
107
108     Map JavaDoc transactionToNode = new HashMap JavaDoc();
109     TransactionLogicalLock globalLock = schema.getLock();
110     // Make sure we don't process a DatabaseTable object twice,
111 // which may happen if we reference a table
112 // both by its fully qualified name (i.e. schemaName.tableName)
113 // and by its short name (i.e. tableName).
114 Set JavaDoc uniqueTables = new HashSet JavaDoc(schema.getTables().values());
115     for (Iterator JavaDoc iter = uniqueTables.iterator(); iter.hasNext();)
116     {
117       DatabaseTable table = (DatabaseTable) iter.next();
118       TransactionLogicalLock lock = table.getLock();
119       if (lock.isLocked())
120       {
121         long lockerTransactionId = lock.getLocker();
122         if (logger.isDebugEnabled())
123           logger.debug(table.getName() + " locked by " + lockerTransactionId);
124         Node lockerNode = (Node) transactionToNode.get(new Long JavaDoc(
125             lockerTransactionId));
126         if (lockerNode == null)
127         {
128           lockerNode = new Node(lockerTransactionId);
129           transactionToNode.put(new Long JavaDoc(lockerTransactionId), lockerNode);
130         }
131         for (Iterator JavaDoc iter2 = lock.getWaitingList().iterator(); iter2.hasNext();)
132         {
133           long waitingTransactionId = ((WaitingListElement) iter2.next())
134               .getTransactionId();
135           Node waitingNode = (Node) transactionToNode.get(new Long JavaDoc(
136               waitingTransactionId));
137           if (waitingNode == null)
138           {
139             waitingNode = new Node(waitingTransactionId);
140             transactionToNode.put(new Long JavaDoc(waitingTransactionId), waitingNode);
141           }
142           Edge edge = new Edge(waitingNode, lockerNode, table);
143           waitingNode.addOutgoingEdge(edge);
144           lockerNode.addIncomingEdge(edge);
145         }
146
147         // Check for blocked stored procedures
148 if ((storedProcedureQueue != null) && (globalLock.isLocked()))
149         {
150           for (Iterator JavaDoc iter2 = storedProcedureQueue.iterator(); iter2
151               .hasNext();)
152           {
153             AbstractTask task = ((BackendTaskQueueEntry) iter2.next())
154                 .getTask();
155             long waitingTransactionId = task.getTransactionId();
156             // TODO check this test
157 if ((waitingTransactionId != lockerTransactionId)
158                 && ((task.getLocks(backend) == null) || (task.getLocks(backend)
159                     .contains(lock))))
160             {
161               System.out.println("SP in " + waitingTransactionId
162                   + " waiting for " + lockerTransactionId);
163               Node node = (Node) transactionToNode.get(new Long JavaDoc(
164                   waitingTransactionId));
165               if (node == null)
166               {
167                 node = new Node(waitingTransactionId);
168                 transactionToNode.put(new Long JavaDoc(waitingTransactionId), node);
169               }
170               Edge edge = new Edge(node, lockerNode, table);
171               node.addOutgoingEdge(edge);
172               lockerNode.addIncomingEdge(edge);
173             }
174           }
175         }
176       }
177     }
178     return transactionToNode.values();
179   }
180
181   private Collection JavaDoc walk(Collection JavaDoc nodes)
182   {
183     if (logger.isDebugEnabled())
184       logger.debug("Walking wait-for graph...");
185     List JavaDoc startNodes = new ArrayList JavaDoc();
186     List JavaDoc cycles = new ArrayList JavaDoc();
187     String JavaDoc indent = new String JavaDoc();
188
189     // Need to start from different nodes since graph may not be fully connected
190 for (Iterator JavaDoc iter = nodes.iterator(); iter.hasNext();)
191     {
192       Node node = (Node) iter.next();
193       if (!startNodes.contains(node))
194       {
195         List JavaDoc visitedNodes = new ArrayList JavaDoc();
196         doWalk(node, visitedNodes, new Path(), cycles, indent);
197         startNodes.addAll(visitedNodes);
198       }
199     }
200     return cycles;
201   }
202
203   private void doWalk(Node node, List JavaDoc visitedNodes, Path path, List JavaDoc cycles,
204       String JavaDoc indent)
205   {
206     // Check that we haven't met a cycle
207 if (path.containsSource(node))
208     {
209       if (logger.isDebugEnabled())
210         logger.debug(indent + "Cycle!");
211       path.trimBeforeSource(node);
212
213       // Check if it is a new cycle
214 if (!cycles.contains(path))
215       {
216         cycles.add(path);
217       }
218
219       return;
220     }
221
222     // No cycle, proceed with exploration
223 visitedNodes.add(node);
224     for (Iterator JavaDoc iter = node.getOutgoingEdges().iterator(); iter.hasNext();)
225     {
226       Edge edge = (Edge) iter.next();
227       if (!path.containsEdge(edge))
228       {
229         Path newPath = new Path(path);
230         newPath.addEdge(edge);
231         if (logger.isDebugEnabled())
232           logger.debug(indent + node.getTransactionId() + " waits for "
233               + ((DatabaseTable) edge.getResource()).getName() + " locked by "
234               + edge.getSink().getTransactionId());
235         doWalk(edge.getSink(), visitedNodes, newPath, cycles, indent + INDENT);
236       }
237     }
238   }
239
240   private Node kill(Collection JavaDoc cycles)
241   {
242     if (logger.isDebugEnabled())
243       logger.debug("Choosing victim node...");
244     if (logger.isDebugEnabled())
245       logger.debug(cycles.size() + " cycles detected");
246     Map JavaDoc appearances = new HashMap JavaDoc();
247     int maxCount = 0;
248     victim = null;
249
250     // Count in how many cycles each node appears
251 // FIXME : some cycles may have been detected multiple times
252 for (Iterator JavaDoc iter = cycles.iterator(); iter.hasNext();)
253     {
254       Path cycle = (Path) iter.next();
255       for (Iterator JavaDoc iter2 = cycle.getSources().iterator(); iter2.hasNext();)
256       {
257         Node node = (Node) iter2.next();
258         if (appearances.containsKey(node))
259         {
260           appearances.put(node, new Integer JavaDoc(((Integer JavaDoc) appearances.get(node))
261               .intValue() + 1));
262         }
263         else
264         {
265           appearances.put(node, new Integer JavaDoc(1));
266         }
267         int value = ((Integer JavaDoc) appearances.get(node)).intValue();
268         if (value > maxCount)
269         {
270           maxCount = value;
271           victim = node;
272         }
273       }
274     }
275
276     if (logger.isDebugEnabled())
277     {
278       for (Iterator JavaDoc iter = cycles.iterator(); iter.hasNext();)
279       {
280         StringBuffer JavaDoc printableCycle = new StringBuffer JavaDoc(INDENT);
281         Path cycle = (Path) iter.next();
282         Edge edge = null;
283         for (Iterator JavaDoc iter2 = cycle.getEdges().iterator(); iter2.hasNext();)
284         {
285           edge = (Edge) iter2.next();
286           printableCycle.append(edge.getSource().getTransactionId() + " --"
287               + ((DatabaseTable) edge.getResource()).getName() + "--> ");
288         }
289         printableCycle.append(edge.getSink().getTransactionId());
290         logger.debug(printableCycle);
291       }
292       if (victim == null)
293       {
294         logger.debug("No victim");
295       }
296       else
297       {
298         logger.debug("Victim: " + victim.getTransactionId());
299       }
300     }
301     return victim;
302   }
303
304   private class Node
305   {
306     private long transactionId;
307     private Set JavaDoc outgoingEdges = new HashSet JavaDoc();
308     private Set JavaDoc incomingEdges = new HashSet JavaDoc();
309
310     /**
311      * Creates a new <code>Node</code> object
312      *
313      * @param transactionId the transaction id
314      */
315     public Node(long transactionId)
316     {
317       this.transactionId = transactionId;
318     }
319
320     /**
321      * Add an incoming edge
322      *
323      * @param edge the edge to add
324      */
325     public void addIncomingEdge(Edge edge)
326     {
327       incomingEdges.add(edge);
328     }
329
330     /**
331      * Add an outgoing edge
332      *
333      * @param edge the edge to add
334      */
335     public void addOutgoingEdge(Edge edge)
336     {
337       outgoingEdges.add(edge);
338     }
339
340     /**
341      * Returns the outgoingEdges value.
342      *
343      * @return Returns the outgoingEdges.
344      */
345     public Set JavaDoc getOutgoingEdges()
346     {
347       return outgoingEdges;
348     }
349
350     /**
351      * Returns the transactionId value.
352      *
353      * @return Returns the transactionId.
354      */
355     public long getTransactionId()
356     {
357       return transactionId;
358     }
359   }
360
361   private class Edge
362   {
363     private Object JavaDoc resource;
364     private Node source;
365     private Node sink;
366
367     /**
368      * Creates a new <code>Edge</code> object
369      *
370      * @param source the source node
371      * @param sink the sink node
372      * @param resource the resource
373      */
374     public Edge(Node source, Node sink, Object JavaDoc resource)
375     {
376       this.source = source;
377       this.sink = sink;
378       this.resource = resource;
379     }
380
381     /**
382      * Returns the resource value.
383      *
384      * @return Returns the resource.
385      */
386     public Object JavaDoc getResource()
387     {
388       return resource;
389     }
390
391     /**
392      * Returns the sink value.
393      *
394      * @return Returns the sink.
395      */
396     public Node getSink()
397     {
398       return sink;
399     }
400
401     /**
402      * Returns the source value.
403      *
404      * @return Returns the source.
405      */
406     public Node getSource()
407     {
408       return source;
409     }
410
411   }
412
413   private class Path
414   {
415     private List JavaDoc edges;
416     private List JavaDoc sources;
417     private Map JavaDoc sourceToEdge;
418
419     /**
420      * Creates a new <code>Path</code> object
421      */
422     public Path()
423     {
424       edges = new ArrayList JavaDoc();
425       sources = new ArrayList JavaDoc();
426       sourceToEdge = new HashMap JavaDoc();
427     }
428
429     /**
430      * Creates a new <code>Path</code> object
431      *
432      * @param path the path to clone
433      */
434     public Path(Path path)
435     {
436       edges = new ArrayList JavaDoc(path.edges);
437       sources = new ArrayList JavaDoc(path.sources);
438       sourceToEdge = new HashMap JavaDoc(path.sourceToEdge);
439     }
440
441     /**
442      * @see java.lang.Object#equals(java.lang.Object)
443      */
444     public boolean equals(Object JavaDoc obj)
445     {
446       if (obj == null)
447       {
448         return false;
449       }
450       if (obj instanceof Path)
451       {
452         Set JavaDoc thisEdgesSet = new HashSet JavaDoc(edges);
453         Set JavaDoc objEdgesSet = new HashSet JavaDoc(((Path) obj).edges);
454         return thisEdgesSet.equals(objEdgesSet);
455       }
456       return false;
457     }
458
459     /**
460      * @see java.lang.Object#hashCode()
461      */
462     public int hashCode()
463     {
464       return (new HashSet JavaDoc(edges)).hashCode();
465     }
466
467     /**
468      * Add an edge
469      *
470      * @param edge the edge to add
471      */
472     public void addEdge(Edge edge)
473     {
474       edges.add(edge);
475       sources.add(edge.getSource());
476       sourceToEdge.put(edge.getSource(), edge);
477     }
478
479     /**
480      * Returns true if the given edge is contained in the path
481      *
482      * @param edge the edge to look for
483      * @return true if the edge has been found
484      */
485     public boolean containsEdge(Edge edge)
486     {
487       return edges.contains(edge);
488     }
489
490     /**
491      * Returns true if the sources contain the given node
492      *
493      * @param node the node to look for
494      * @return true if the node has been found
495      */
496     public boolean containsSource(Node node)
497     {
498       return sources.contains(node);
499     }
500
501     /**
502      * Returns the edges value.
503      *
504      * @return Returns the edges.
505      */
506     public List JavaDoc getEdges()
507     {
508       return edges;
509     }
510
511     /**
512      * Returns the sources value.
513      *
514      * @return Returns the sources.
515      */
516     public List JavaDoc getSources()
517     {
518       return sources;
519     }
520
521     /**
522      * Remove elements before the given source node
523      *
524      * @param node the source node
525      */
526     public void trimBeforeSource(Node node)
527     {
528       edges.subList(0, edges.indexOf(sourceToEdge.get(node))).clear();
529       sources.subList(0, sources.indexOf(node)).clear();
530       // Starting here this instance of Path should be garbage-collected
531 // (internal consistency lost)
532 }
533   }
534
535 }
536
Popular Tags