DepState: Detecting Synchronization Failure Bugs in Distributed Database Management Systems

Distributed Database Management Systems (DDBMSs) are crucial for managing large-scale distributed data. Unlike single-node databases, they are deployed across clusters, distributing data among multiple nodes. The synchronization process in DDBMSs maintains data consistency against data and cluster updates. Due to its complexity, synchronization bugs are inevitable and may cause data inconsistencies, transaction errors, or cluster crashes, severely compromising the availability and reliability of a DDBMS. However, there has been relatively little focus on testing the DDBMS synchronization process. In this paper, we propose DepState, a framework to detect synchronization failure bugs. DepState enhances synchronization testing by simulating the complexities of data sharding and dynamic cluster conditions. It establishes dependencies between tables across nodes and systematically introduces controlled variations in cluster states. We utilize DepState on four DDBMSs: MySQL NDB Cluster, MySQL InnoDB Cluster, MariaDB Galera Cluster, and TiDB Cluster, discovering 25 new bugs, with 13 confirmed. We compare DepState against state-of-the-art tools. DepState finds 14 more synchronization failure bugs and covers 6.13%-66.51%, 5.82%-57.28%, 14.12%-83.30%, 36.81%-83.88%, and 43.24%-54.28% more lines in synchronization-related functions than Jepsen, Mallory, SQLsmith, SQLancer, and Mozi in 24 hours, respectively.