001: /**
002: * Sequoia: Database clustering technology.
003: * Copyright (C) 2005 AmicoSoft, Inc. dba Emic Networks
004: * Contact: sequoia@continuent.org
005: *
006: * Licensed under the Apache License, Version 2.0 (the "License");
007: * you may not use this file except in compliance with the License.
008: * You may obtain a copy of the License at
009: *
010: * http://www.apache.org/licenses/LICENSE-2.0
011: *
012: * Unless required by applicable law or agreed to in writing, software
013: * distributed under the License is distributed on an "AS IS" BASIS,
014: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015: * See the License for the specific language governing permissions and
016: * limitations under the License.
017: *
018: * Initial developer(s): Damian Arregui.
019: * Contributor(s): _________________________.
020: */package org.continuent.sequoia.common.locks;
021:
022: import java.util.ArrayList;
023: import java.util.Collection;
024: import java.util.HashMap;
025: import java.util.HashSet;
026: import java.util.Iterator;
027: import java.util.List;
028: import java.util.Map;
029: import java.util.Set;
030:
031: import org.continuent.sequoia.common.locks.TransactionLogicalLock.WaitingListElement;
032: import org.continuent.sequoia.common.log.Trace;
033: import org.continuent.sequoia.common.sql.schema.DatabaseSchema;
034: import org.continuent.sequoia.common.sql.schema.DatabaseTable;
035: import org.continuent.sequoia.controller.backend.DatabaseBackend;
036: import org.continuent.sequoia.controller.loadbalancer.BackendTaskQueueEntry;
037: import org.continuent.sequoia.controller.loadbalancer.tasks.AbstractTask;
038:
039: /**
040: * This class defines a WaitForGraph. Nodes in the graph represent active
041: * transactions. Edges represent "waitin for" relationships: the source node is
042: * waiting for the sink node to release a lock on a given resource. This class
043: * allows to detect cycles in the graph, i.e. deadlocks, and to determine which
044: * transaction to abort in order to break one or more cycles.
045: *
046: * @author <a href="mailto:Damian.Arregui@continuent.com">Damian Arregui</a>
047: * @version 1.0
048: */
049: public class WaitForGraph {
050: private static final String INDENT = " ";
051: private DatabaseBackend backend;
052: private List storedProcedureQueue;
053: private Node victim;
054:
055: private static Trace logger = Trace
056: .getLogger("org.continuent.sequoia.controller.loadbalancer");
057:
058: /**
059: * Creates a new <code>WaitForGraph</code> object.
060: *
061: * @param backend database backend that will be used to build the graph.
062: * @param storedProcedureQueue also used to build the graph.
063: */
064: public WaitForGraph(DatabaseBackend backend,
065: List storedProcedureQueue) {
066: this .backend = backend;
067: this .storedProcedureQueue = storedProcedureQueue;
068: }
069:
070: /**
071: * Detects deadlocks in the wait-for graph. First build the graph from the
072: * database schema, then walk the graph to detect cycles, and finally examines
073: * the cycles (if found) in order to determine a suitable transaction to be
074: * aborted.
075: *
076: * @return true is a deadlock has been detected, false otherwise.
077: */
078: public boolean detectDeadlocks() {
079: Collection nodes = build();
080: Collection cycles = walk(nodes);
081: kill(cycles);
082: return (victim != null);
083: }
084:
085: /**
086: * Returns the ID of the transaction that should be aborted first. This method
087: * returns a value computed during the last run of {@link #detectDeadlocks()}.
088: *
089: * @return victiom transaction ID.
090: */
091: public long getVictimTransactionId() {
092: return victim.getTransactionId();
093: }
094:
095: private Collection build() {
096: if (logger.isDebugEnabled())
097: logger.debug("Building wait-for graph...");
098:
099: // Triggers schema update
100: DatabaseSchema schema = backend.getDatabaseSchema();
101:
102: Map transactionToNode = new HashMap();
103: TransactionLogicalLock globalLock = schema.getLock();
104: // Make sure we don't process a DatabaseTable object twice,
105: // which may happen if we reference a table
106: // both by its fully qualified name (i.e. schemaName.tableName)
107: // and by its short name (i.e. tableName).
108: Set uniqueTables = new HashSet(schema.getTables().values());
109: for (Iterator iter = uniqueTables.iterator(); iter.hasNext();) {
110: DatabaseTable table = (DatabaseTable) iter.next();
111: TransactionLogicalLock lock = table.getLock();
112: if (lock.isLocked()) {
113: long lockerTransactionId = lock.getLocker();
114: if (logger.isDebugEnabled())
115: logger.debug(table.getName() + " locked by "
116: + lockerTransactionId);
117: Node lockerNode = (Node) transactionToNode
118: .get(new Long(lockerTransactionId));
119: if (lockerNode == null) {
120: lockerNode = new Node(lockerTransactionId);
121: transactionToNode.put(
122: new Long(lockerTransactionId), lockerNode);
123: }
124: for (Iterator iter2 = lock.getWaitingList().iterator(); iter2
125: .hasNext();) {
126: long waitingTransactionId = ((WaitingListElement) iter2
127: .next()).getTransactionId();
128: Node waitingNode = (Node) transactionToNode
129: .get(new Long(waitingTransactionId));
130: if (waitingNode == null) {
131: waitingNode = new Node(waitingTransactionId);
132: transactionToNode.put(new Long(
133: waitingTransactionId), waitingNode);
134: }
135: Edge edge = new Edge(waitingNode, lockerNode, table);
136: waitingNode.addOutgoingEdge(edge);
137: lockerNode.addIncomingEdge(edge);
138: }
139:
140: // Check for blocked stored procedures
141: if ((storedProcedureQueue != null)
142: && (globalLock.isLocked())) {
143: for (Iterator iter2 = storedProcedureQueue
144: .iterator(); iter2.hasNext();) {
145: AbstractTask task = ((BackendTaskQueueEntry) iter2
146: .next()).getTask();
147: long waitingTransactionId = task
148: .getTransactionId();
149: // TODO check this test
150: if ((waitingTransactionId != lockerTransactionId)
151: && ((task.getLocks(backend) == null) || (task
152: .getLocks(backend)
153: .contains(lock)))) {
154: Node node = (Node) transactionToNode
155: .get(new Long(waitingTransactionId));
156: if (node == null) {
157: node = new Node(waitingTransactionId);
158: transactionToNode.put(new Long(
159: waitingTransactionId), node);
160: }
161: Edge edge = new Edge(node, lockerNode,
162: table);
163: node.addOutgoingEdge(edge);
164: lockerNode.addIncomingEdge(edge);
165: }
166: }
167: }
168: }
169: }
170: return transactionToNode.values();
171: }
172:
173: private Collection walk(Collection nodes) {
174: if (logger.isDebugEnabled())
175: logger.debug("Walking wait-for graph...");
176: List startNodes = new ArrayList();
177: List cycles = new ArrayList();
178: String indent = new String();
179:
180: // Need to start from different nodes since graph may not be fully connected
181: for (Iterator iter = nodes.iterator(); iter.hasNext();) {
182: Node node = (Node) iter.next();
183: if (!startNodes.contains(node)) {
184: List visitedNodes = new ArrayList();
185: doWalk(node, visitedNodes, new Path(), cycles, indent);
186: startNodes.addAll(visitedNodes);
187: }
188: }
189: return cycles;
190: }
191:
192: private void doWalk(Node node, List visitedNodes, Path path,
193: List cycles, String indent) {
194: // Check that we haven't met a cycle
195: if (path.containsSource(node)) {
196: if (logger.isDebugEnabled())
197: logger.debug(indent + "Cycle!");
198: path.trimBeforeSource(node);
199:
200: // Check if it is a new cycle
201: if (!cycles.contains(path)) {
202: cycles.add(path);
203: }
204:
205: return;
206: }
207:
208: // No cycle, proceed with exploration
209: visitedNodes.add(node);
210: for (Iterator iter = node.getOutgoingEdges().iterator(); iter
211: .hasNext();) {
212: Edge edge = (Edge) iter.next();
213: if (!path.containsEdge(edge)) {
214: Path newPath = new Path(path);
215: newPath.addEdge(edge);
216: if (logger.isDebugEnabled())
217: logger.debug(indent
218: + node.getTransactionId()
219: + " waits for "
220: + ((DatabaseTable) edge.getResource())
221: .getName() + " locked by "
222: + edge.getSink().getTransactionId());
223: doWalk(edge.getSink(), visitedNodes, newPath, cycles,
224: indent + INDENT);
225: }
226: }
227: }
228:
229: private Node kill(Collection cycles) {
230: if (logger.isDebugEnabled())
231: logger.debug("Choosing victim node...");
232: if (logger.isDebugEnabled())
233: logger.debug(cycles.size() + " cycles detected");
234: Map appearances = new HashMap();
235: int maxCount = 0;
236: victim = null;
237:
238: // Count in how many cycles each node appears
239: // FIXME : some cycles may have been detected multiple times
240: for (Iterator iter = cycles.iterator(); iter.hasNext();) {
241: Path cycle = (Path) iter.next();
242: for (Iterator iter2 = cycle.getSources().iterator(); iter2
243: .hasNext();) {
244: Node node = (Node) iter2.next();
245: if (appearances.containsKey(node)) {
246: appearances.put(node, new Integer(
247: ((Integer) appearances.get(node))
248: .intValue() + 1));
249: } else {
250: appearances.put(node, new Integer(1));
251: }
252: int value = ((Integer) appearances.get(node))
253: .intValue();
254: if (value > maxCount) {
255: maxCount = value;
256: victim = node;
257: }
258: }
259: }
260:
261: if (logger.isDebugEnabled()) {
262: for (Iterator iter = cycles.iterator(); iter.hasNext();) {
263: StringBuffer printableCycle = new StringBuffer(INDENT);
264: Path cycle = (Path) iter.next();
265: Edge edge = null;
266: for (Iterator iter2 = cycle.getEdges().iterator(); iter2
267: .hasNext();) {
268: edge = (Edge) iter2.next();
269: printableCycle.append(edge.getSource()
270: .getTransactionId()
271: + " --"
272: + ((DatabaseTable) edge.getResource())
273: .getName() + "--> ");
274: }
275: printableCycle
276: .append(edge.getSink().getTransactionId());
277: logger.debug(printableCycle);
278: }
279: if (victim == null) {
280: logger.debug("No victim");
281: } else {
282: logger.debug("Victim: " + victim.getTransactionId());
283: }
284: }
285: return victim;
286: }
287:
288: private class Node {
289: private long transactionId;
290: private Set outgoingEdges = new HashSet();
291: private Set incomingEdges = new HashSet();
292:
293: /**
294: * Creates a new <code>Node</code> object
295: *
296: * @param transactionId the transaction id
297: */
298: public Node(long transactionId) {
299: this .transactionId = transactionId;
300: }
301:
302: /**
303: * Add an incoming edge
304: *
305: * @param edge the edge to add
306: */
307: public void addIncomingEdge(Edge edge) {
308: incomingEdges.add(edge);
309: }
310:
311: /**
312: * Add an outgoing edge
313: *
314: * @param edge the edge to add
315: */
316: public void addOutgoingEdge(Edge edge) {
317: outgoingEdges.add(edge);
318: }
319:
320: /**
321: * Returns the outgoingEdges value.
322: *
323: * @return Returns the outgoingEdges.
324: */
325: public Set getOutgoingEdges() {
326: return outgoingEdges;
327: }
328:
329: /**
330: * Returns the transactionId value.
331: *
332: * @return Returns the transactionId.
333: */
334: public long getTransactionId() {
335: return transactionId;
336: }
337: }
338:
339: private class Edge {
340: private Object resource;
341: private Node source;
342: private Node sink;
343:
344: /**
345: * Creates a new <code>Edge</code> object
346: *
347: * @param source the source node
348: * @param sink the sink node
349: * @param resource the resource
350: */
351: public Edge(Node source, Node sink, Object resource) {
352: this .source = source;
353: this .sink = sink;
354: this .resource = resource;
355: }
356:
357: /**
358: * Returns the resource value.
359: *
360: * @return Returns the resource.
361: */
362: public Object getResource() {
363: return resource;
364: }
365:
366: /**
367: * Returns the sink value.
368: *
369: * @return Returns the sink.
370: */
371: public Node getSink() {
372: return sink;
373: }
374:
375: /**
376: * Returns the source value.
377: *
378: * @return Returns the source.
379: */
380: public Node getSource() {
381: return source;
382: }
383:
384: }
385:
386: private class Path {
387: private List edges;
388: private List sources;
389: private Map sourceToEdge;
390:
391: /**
392: * Creates a new <code>Path</code> object
393: */
394: public Path() {
395: edges = new ArrayList();
396: sources = new ArrayList();
397: sourceToEdge = new HashMap();
398: }
399:
400: /**
401: * Creates a new <code>Path</code> object
402: *
403: * @param path the path to clone
404: */
405: public Path(Path path) {
406: edges = new ArrayList(path.edges);
407: sources = new ArrayList(path.sources);
408: sourceToEdge = new HashMap(path.sourceToEdge);
409: }
410:
411: /**
412: * @see java.lang.Object#equals(java.lang.Object)
413: */
414: public boolean equals(Object obj) {
415: if (obj == null) {
416: return false;
417: }
418: if (obj instanceof Path) {
419: Set this EdgesSet = new HashSet(edges);
420: Set objEdgesSet = new HashSet(((Path) obj).edges);
421: return this EdgesSet.equals(objEdgesSet);
422: }
423: return false;
424: }
425:
426: /**
427: * @see java.lang.Object#hashCode()
428: */
429: public int hashCode() {
430: return (new HashSet(edges)).hashCode();
431: }
432:
433: /**
434: * Add an edge
435: *
436: * @param edge the edge to add
437: */
438: public void addEdge(Edge edge) {
439: edges.add(edge);
440: sources.add(edge.getSource());
441: sourceToEdge.put(edge.getSource(), edge);
442: }
443:
444: /**
445: * Returns true if the given edge is contained in the path
446: *
447: * @param edge the edge to look for
448: * @return true if the edge has been found
449: */
450: public boolean containsEdge(Edge edge) {
451: return edges.contains(edge);
452: }
453:
454: /**
455: * Returns true if the sources contain the given node
456: *
457: * @param node the node to look for
458: * @return true if the node has been found
459: */
460: public boolean containsSource(Node node) {
461: return sources.contains(node);
462: }
463:
464: /**
465: * Returns the edges value.
466: *
467: * @return Returns the edges.
468: */
469: public List getEdges() {
470: return edges;
471: }
472:
473: /**
474: * Returns the sources value.
475: *
476: * @return Returns the sources.
477: */
478: public List getSources() {
479: return sources;
480: }
481:
482: /**
483: * Remove elements before the given source node
484: *
485: * @param node the source node
486: */
487: public void trimBeforeSource(Node node) {
488: edges.subList(0, edges.indexOf(sourceToEdge.get(node)))
489: .clear();
490: sources.subList(0, sources.indexOf(node)).clear();
491: // Starting here this instance of Path should be garbage-collected
492: // (internal consistency lost)
493: }
494: }
495:
496: }
|