LCL+: a Lock Chain Length-based Distributed Deadlock Detection and Resolution Service Built for OceanBase

The problem of deadlock detection and resolution in database systems has been studied for decades. Although it has long been a mature feature of classical centralized database systems for many years, its use in distributed database systems remains in its infancy. A simple and fully distributed deadlock detection and resolution algorithm was proposed by Don P. Mitchell and Michael J. Merritt ( M&M ), but its assumption that each process waits for only one resource at a time prevents it from being generally applicable. The distributed deadlock detection algorithm based on Lock Chain Length (LCL) surpasses the limitations of the M&M algorithm. However, it is less effective in quickly detecting deadlocks that encompass both distributed and local deadlocks. In this article, we introduce LCL + , an advanced and universally applicable algorithm specifically designed for the detection and resolution of resource deadlocks in distributed environments. This algorithm improves the efficiency of identifying distributed deadlocks by accelerating the detection of hybrid deadlocks. Our extensive experiments demonstrate that LCL + significantly outperforms its predecessor, LCL, in efficiency. In addition, it has been successfully implemented in the OceanBase distributed relational database system. Detailed analyses from multiple perspectives within OceanBase confirm that LCL + significantly improves the system’s scalability and ensures the provision of high-quality service.