Efficient detection and resolution of deadlocks in distributed databases

摘要

Deadlock detection and resolution is one of the major components of a successful distributed database management system. In this article, we discuss deadlock detection and resolution strategies and present two approaches for detecting and resolving deadlocks in both general distributed database systems and distributed real-time database systems. Our first approach is to collect information on the connectivity of nodes of the overal Transaction Wait-For Graph (TWFG) of the distributed database system and then use these connectivities information to build a local TWFG at each node of the overal TWFG. We then detect the deadlocks by locating the cycles in each local TWFG. To resolve the deadlocks, the nodes involved in those cycles in each local TWFG, are removed until there is no cycle in the local TWFGs. Our second approach continuously checks for the occurrence of a deadlock between different transaction trees. As soon as it detects a deadlock, it resolves it by aborting one of the transaction tree which has been initiated more recently. Some of the advantages of our approaches over the approaches which use Probe messages are: (1) no extra storage required to store different probe messages, (2) no false (Phantom) deadlocks are reported, (3) detects and resolves all deadlocks. In addition, our approaches use less message and time to detect and resolve all deadlocks in existing TWFG of the distributed database system.