Detecting deadlock in a cluster environment using big data analytics

• US 10,528,400 B2
• Filed: 06/05/2017
• Issued: 01/07/2020
• Est. Priority Date: 06/05/2017
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Feng, Shuo, Ma, Zhi Hong, Tian, Zhiyong, Zhang, Yan, Zhou, Jia Wei
• Primary Examiner(s): Ghaffari, Abu Zar
• Application Number:
  US15/613,850
• Publication Number:
  US 20180349210A1
• Time in Patent Office: 946 Days
• Field of Search: None
• CPC Class Codes: G06F 11/3404 for parallel or distributed programming
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 13/4036 and deadlock prevention
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

Detecting deadlock in a distributed computing environment. Potential deadlocks between resources of nodes in a computing cluster by determining resource reverse pairs of the resources for each transaction from trace or log files using data analytics. The potential deadlocks are identified offline by matching a global or local resource between the nodes in sub-transactions of each transaction as recursively identified from a transaction resource chain.

Claims

1. A method for detecting deadlock in a distributed computing environment, by a processor device, comprising:

detecting potential deadlocks between resources of nodes in a computing cluster by determining resource reverse pairs of the resources for each transaction from trace or log files generated from additional, separate transactions using data analytics;

wherein the potential deadlocks are identified offline, prior to any execution of each transaction, by matching a global or local resource between the nodes in sub-transactions of each transaction as recursively identified from a transaction resource chain having information of an order of the resources to be used during each transaction; and

wherein the reverse resource pairs comprise those of the resources determined to collide when being taken by one of the sub-transactions while simultaneously being attempted to be taken by another of the sub-transactions as identified in the transaction resource chain;

mitigating an occurrence of the potential deadlock by delaying the one of the sub-transactions until the respective resources used during the one of the sub-transactions are freed or restructuring the order of the resources to be used during the one of the sub-transactions;

defining namespaces for each of the transactions, the sub-transactions, and the resources used by the transactions and sub-transactions;

wherein the namespaces are recorded in the log or trace files; and

extracting information associated with a respective transaction and a resource order of the resources used for the respective transaction from the log or trace files.

2. The method of claim 1, wherein, pursuant to defining the namespaces:

each transaction is identified by at least one of a cluster identification (ID), a file system ID, and a task ID;

each sub-transaction is identified by at least one of a transaction ID and a sub-transaction ID; and

each resource is identified by at least one of a resource serial number, a scope comprising the global or local resource, and a node ID.

3. The method of claim 1, further including generating the transaction resource chain for the respective transaction according to the extracted information.

4. The method of claim 3, further including defining, for each resource, an ancestor set and an inheritor set, the ancestor set and the inheritor set corresponding to the resource order of the resources used in the transaction resource chain for the respective transaction.

5. The method of claim 4, wherein matching the global or local resource between the nodes as recursively identified from the transaction resource chain includes identifying the global or local resource on both the ancestor set and the inheritor set on the transaction resource chain.

6. A system for detecting deadlock in a distributed computing environment, the system comprising:

a processor device operating within and between distributed computing components, wherein the processor device;

detects potential deadlocks between resources of nodes in a computing cluster by determining resource reverse pairs of the resources for each transaction from trace or log files generated from additional, separate transactions using data analytics;

wherein the potential deadlocks are identified offline, prior to any execution of each transaction, by matching a global or local resource between the nodes in sub-transactions of each transaction as recursively identified from a transaction resource chain having information of an order of the resources to be used during each transaction; and

wherein the reverse resource pairs comprise those of the resources determined to collide when being taken by one of the sub-transactions while simultaneously being attempted to be taken by another of the sub-transactions as identified in the transaction resource chain;

mitigates an occurrence of the potential deadlock by delaying the one of the sub-transactions until the respective resources used during the one of the sub-transactions are freed or restructuring the order of the resources to be used during the one of the sub-transactions;

defines namespaces for each of the transactions, the sub-transactions, and the resources used by the transactions and sub-transactions;

wherein the namespaces are recorded in the log or trace files; and

extracts information associated with a respective transaction and a resource order of the resources used for the respective transaction from the log or trace files.

7. The system of claim 6, wherein, pursuant to defining the namespaces:

each transaction is identified by at least one of a cluster identification (ID), a file system ID, and a task ID;

each sub-transaction is identified by at least one of a transaction ID and a sub-transaction ID; and

each resource is identified by at least one of a resource serial number, a scope comprising the global or local resource, and a node ID.

8. The system of claim 6, wherein the processor device generates the transaction resource chain for the respective transaction according to the extracted information.

9. The system of claim 8, wherein the processor device defines, for each resource, an ancestor set and an inheritor set, the ancestor set and the inheritor set corresponding to the resource order of the resources used in the transaction resource chain for the respective transaction.

10. The system of claim 9, wherein matching the global or local resource between the nodes as recursively identified from the transaction resource chain includes identifying the global or local resource on both the ancestor set and the inheritor set on the transaction resource chain.

11. A computer program product for detecting deadlock in a distributed computing environment, by a processor device, the computer program product comprising a physical, non-transitory computer-readable storage medium having computer-readable program code portions stored therein, the computer-readable program code portions comprising:

an executable portion that detects potential deadlocks between resources of nodes in a computing cluster by determining resource reverse pairs of the resources for each transaction from trace or log files generated from additional, separate transactions using data analytics;

wherein the potential deadlocks are identified offline, prior to any execution of each transaction, by matching a global or local resource between the nodes in sub-transactions of each transaction as recursively identified from a transaction resource chain having information of an order of the resources to be used during each transaction; and

wherein the reverse resource pairs comprise those of the resources determined to collide when being taken by one of the sub-transactions while simultaneously being attempted to be taken by another of the sub-transactions as identified in the transaction resource chain;

an executable portion that mitigates an occurrence of the potential deadlock by delaying the one of the sub-transactions until the respective resources used during the one of the sub-transactions are freed or restructuring the order of the resources to be used during the one of the sub-transactions;

an executable portion that defines namespaces for each of the transactions, the sub-transactions, and the resources used by the transactions and sub-transactions;

wherein the namespaces are recorded in the log or trace files; and

an executable portion that extracts information associated with a respective transaction and a resource order of the resources used for the respective transaction from the log or trace files.

12. The computer program product of claim 11, wherein, pursuant to defining the namespaces:

each transaction is identified by at least one of a cluster identification (ID), a file system ID, and a task ID;

each sub-transaction is identified by at least one of a transaction ID and a sub-transaction ID; and

each resource is identified by at least one of a resource serial number, a scope comprising the global or local resource, and a node ID.

13. The computer program product of claim 11, further including an executable portion that generates the transaction resource chain for the respective transaction according to the extracted information.

14. The computer program product of claim 13, further including an executable portion that defines, for each resource, an ancestor set and an inheritor set, the ancestor set and the inheritor set corresponding to the resource order of the resources used in the transaction resource chain for the respective transaction.

15. The computer program product of claim 14, wherein matching the global or local resource between the nodes as recursively identified from the transaction resource chain includes identifying the global or local resource on both the ancestor set and the inheritor set on the transaction resource chain.