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.

Distributed databases have been widely researched and developed in recent years due to their scalability, availability, and consistency guarantees. The write-ahead logging (WAL) system is one of the most vital components in a database. It is still a non-trivial problem to design a replicated logging system as the foundation of a distributed database with the power of ACID transactions. This paper proposes PALF, a Paxos-backed Append-only Log File System, to address these challenges. The basic idea behind PALF is to co-design the logging system with the entire database for supporting database-specific functions and to abstract the functions as PALF primitives to power other distributed systems. Many database functions, including transaction processing, database restore, and physical standby databases, have been built based on PALF primitives. Evaluation shows that PALF greatly outperforms well-known implementations of consensus protocols and is fully competent for distributed database workloads. PALF has been deployed as a component of the OceanBase 4.0 database and has been made open-source along with it.

The problem of deadlock detection and resolution in database systems has been studied for decades. While 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. Don P. Mitchell and Michael J. Merritt (M&M) proposed a simple and fully distributed deadlock detection and resolution algorithm, but its assumption that each process waits on only one resource at a time prevents it from being generally applicable. Inspired by this algorithm, we design and implement LCL (Lock Chain Length), an elegant and generally applicable algorithm for resource deadlock detection and resolution in distributed environments without a restriction of the above kind. Our extensive emulation experiments show that the proposed approach LCL significantly outperforms the state-of-the-art competitor M&M. In addition, it has been applied to the OceanBase distributed relational database system, and our extensive experiments in OceanBase illustrate that LCL is also more efficient than M&M in deadlock detection and resolution.