Skip to main content

KlustronDB Automatic Global Deadlock Detection

KlustronDBAbout 6 min

KlustronDB Automatic Global Deadlock Detection

Note:

Unless otherwise specified, the version numbers in the text can be replaced with the version numbers of any released version. For all released versions, see: Release_notes

Overview

Transaction deadlock is a common phenomenon in database systems that use transaction locks for concurrency control, and databases like MySQL and Oracle have corresponding deadlock handling mechanisms. In the KlustronDB distributed database system, global deadlocks may occur, meaning deadlocks happen across multiple shards. The deadlock handling mechanisms of individual Klustore instances cannot resolve global deadlocks, requiring a global deadlock handling mechanism at the KlustronDB distributed database cluster level to detect and resolve them. This article first introduces deadlocks and global deadlocks in distributed systems, explains how KlustronDB automatically resolves global deadlocks, and finally provides corresponding examples.

Deadlock detection and resolution require no human intervention or configuration; they run automatically in the background.

01 What is a Deadlock

A deadlock refers to a situation where two or more transactions are waiting for each other to release the resources they hold, resulting in all transactions

Cannot continue execution. In this situation, each transaction needs to wait for one or more resources, which are held by other transactions, and no one can release these resources, so the entire system falls into a deadlock.

02 The Impact of Deadlocks on Databases

Since deadlocks can cause all transactions to be unable to proceed, they are very serious and can lead to issues such as backlog. The most obvious impact is the reduction of the database's transaction processing concurrency. For a high-concurrency server, deadlocks can very likely cause the database to be unable to respond to requests, affecting the stability and availability of the entire system.

03 Example of a Deadlock

Below are examples of two sessions generating a deadlock cycle wait.

Session 1Session 2
begin; update bank_accounts set balance=balance-10 where id=100;
begin; update bank_accounts set balance=balance-100 where id=200;
update bank_accounts set balance=balance+10 where id=200;
update bank_accounts set balance=balance+100 where id=100;

The two transactions in Session 1 and 2 each acquired the transaction locks needed by the other, forming a circular wait and resulting in a deadlock.

04 Deadlock Resolution

Currently, common transactional storage engines all support transaction deadlock detection and resolution. The method is to perform a round of deadlock detection either when a transaction lock cannot be obtained or periodically by a deadlock handler: scanning the lock system's wait-for relationships, identifying lock wait cycles, and then selecting one transaction in the cycle as the so-called victim to deny its lock request. As a result, the DML statement being executed by this victim transaction will return an error, which the client needs to handle, such as rolling back the transaction or re-executing the statement.

MySQL's InnoDB storage engine has its own deadlock detection mechanism, so deadlock detection and resolution should be done according to this method.

05 KlustronDB Formation Mechanism of Global Deadlocks

Global deadlock is a new type of database transaction deadlock that occurs at the global level of a distributed database cluster and cannot be detected or resolved by the deadlock handler of a single Klustore instance. However, its occurrence conditions are exactly the same as in the case of a standalone database.

Below is an example of a global deadlock: the bank_accounts record with id 100 is located in shard1, and the record with id 600 is located in shard2.

Global Transaction 1 (GT1)Global Transaction 2 (GT2)
GT1.T11begin; update bank_accounts set balance=balance-10 where id=100;
GT2.T21begin; update bank_accounts set balance=balance-100 where id=600;
GT1.T12update bank_accounts set balance=balance+10 where id=600;
GT2.T22update bank_accounts set balance=balance+100 where id=100;

GT2.T21 blocked GT1.T12, GT2 blocked GT1; GT1.T11 blocked GT2.T22, GT1 blocked GT2. Thus, GT1 and GT2 formed a circular wait.

Global deadlocks have the following characteristics:

  1. The local waiting of transaction branches at the Klustore instance causes the global transaction to wait, and the global transactions form a circular wait relationship.
  2. No deadlock occurs within each Klustore instance, and the Klustore instances cannot automatically detect or resolve a global deadlock.
  3. Global transactions in a global deadlock cycle can originate from transactions started on multiple Kluscomp instances, or they can all come from the same Kluscomp instance.

06 KlustronDB Global Deadlock Handling Methods

KlustronDB discovers and handles global deadlocks in the following steps: First, it obtains the local transaction lock wait relationships within each Klustore instance from the master nodes of all storage shards in the cluster, in order to construct a global transaction lock wait graph. Then, it traverses this graph to search for wait cycles. Once a cycle is found, a victim is selected from the cycle to deny its lock request, causing the victim client to receive a statement execution error.

07 KlustronDB Deadlock Detection Triggering and Client Handling

The KlustronDB global deadlock detection mechanism is a module of the Kluscomp Kluscomp instance. After the Kluscomp instance starts, it runs as a background process called the Global Deadlock Detection Daemon (gdd). If during the execution of a DML statement (insert, delete, update), a statement sent to the Klustore instance does not return within a certain time (start_global_deadlock_detection_wait_timeout), the Kluscomp instance will notify the global_deadlock_detector process to trigger a round of global deadlock detection and resolution. At the same time, gdd also runs periodically in the background, with the time interval set as global_deadlock_detector.naptime=3s.

The global transaction execution statement selected as the victim will return the error ER_QUERY_CANCELED to the client. By default, the transaction is automatically rolled back within the Kluscomp instance, and the user will ignore all subsequent statements in this transaction until the transaction ends.

KlustronDB also supports MySQL's transaction processing mode. If enable_stmt_subxact = true is set before starting a transaction, then execution errors of statements will not automatically roll back the transaction; instead, it is up to the client code to decide how to handle the errors. This mechanism applies to all errors, not just deadlock errors, and it is applicable to both MySQL and PostgreSQL connections. When the client receives any statement execution error, it can ignore the error and continue executing subsequent SQL statements and finally commit the transaction; or re-execute this SQL statement along with the subsequent statements and then commit the transaction; or simply roll back the transaction, after which the transaction can be re-executed.

KlustronDB Kluscomp instances will record each global transaction rolled back during global deadlock detection in their runtime logs for users to trace and inspect.

08 KlustronDB Deadlock Example

The data preparation is as follows:

psql -h 10.37.129.6 -p 47001 postgres
create user kunlun_test with password 'kunlun';
create database test_db with owner kunlun_test encoding utf8 template template0;
\q
psql -h 10.37.129.6 -p 47001 -U kunlun_test test_db
create table bank_accounts
(
   id         INT NOT NULL AUTO_INCREMENT,
   balance    DECIMAL(18,2) NOT NULL,
   primary key(id)
) partition by range(id);
create table bank_accounts_p0 partition of bank_accounts 
for values from (1) to (501) with (shard=1);
create table bank_accounts_p1 partition of bank_accounts
for values from (501) to (1001) with (shard=2);

create or replace procedure generate_account_data()
AS $$
DECLARE
  v_balance double;
  i integer = 1;
BEGIN
    while i<=1000 loop
        v_balance = ROUND(1000+RANDOM()*9000,2);
        INSERT INTO bank_accounts VALUES (i,v_balance);
        commit;
        i = i+1;
    end loop;
END; $$
LANGUAGE plpgsql;

call generate_account_data();
analyze bank_accounts;

8.1 Deadlock of Data Across Shards

Since KlustronDB's Klustore instances use MySQL, deadlock handling within the same shard uses MySQL's deadlock detection mechanism. The specific execution order is as follows:

Session 1Session 2
begin; update bank_accounts set balance=balance-10 where id=100;
begin; update bank_accounts set balance=balance-100 where id=200;
update bank_accounts set balance=balance+10 where id=200;
update bank_accounts set balance=balance+100 where id=100;

When Session 2 executes the last update statement, the following error occurs:

The second update statement of Session 1 will stop blocking and update successfully.

8.2 Different Shard Data Deadlock

The specific execution order is shown in the figure below:

Global Transaction 1 (GT1)Global Transaction 2 (GT2)
GT1.T11begin; update bank_accounts set balance=balance-10 where id=100;
GT2.T21begin; update bank_accounts set balance=balance-100 where id=600;
GT1.T12Update bank_accounts set balance=balance+10 where id=600;
GT2.T22update bank_accounts set balance=balance+100 where id=100;

After GT2.T22 is executed, the KlustronDB global deadlock detection mechanism will handle it and throw error 1317.

Checking the backend logs shows the following output:

2024-04-05 10:48:18.258 CST [26130]  kunlun_test@test_db/psql: [00000]STATEMENT:  update bank_accounts set balance=balance+100 where id=100;
2024-04-05 10:48:18.761 CST [25104] LOG:  GDD waken up by backends.
2024-04-05 10:48:18.761 CST [25104] LOG:  Performing one round of global deadlock detection on 1 requests.
2024-04-05 10:48:18.766 CST [25104] LOG:  Global deadlock detector: Global deadlock detector found a deadlock and killed the victim(gtxnid: 1-1712285272-1736). Killed txn branches (shardid, connection-id): (1, 112) (2, 110)
2024-04-05 10:48:18.768 CST [26130]  kunlun_test@test_db/psql: [57014]ERROR:  Kunlun-db: MySQL Klustore instance (1, 1) returned error: 1317, Query execution was interrupted.
2024-04-05 10:48:18.768 CST [26130]  kunlun_test@test_db/psql: [57014]STATEMENT:  update bank_accounts set balance=balance+100 where id=100;
2024-04-05 10:48:18.768 CST [25100] LOG:  Start processing 2  sharding topology checks.
2024-04-05 10:48:18.768 CST [25104] LOG:  Performing one round of global deadlock detection on 1 requests.

8.3 Rocksdb Storage Engine Table Deadlock Detection

Recreate the test table using the RocksDB storage engine, and then carry out relevant tests.

drop table bank_accounts;
create table bank_accounts
(
   id         INT NOT NULL AUTO_INCREMENT,
   balance    DECIMAL(18,2) NOT NULL,
   primary key(id)
) partition by range(id);
create table bank_accounts_p0 partition of bank_accounts
for values from (1) to (501) with (shard=1,engine=rocksdb);
create table bank_accounts_p1 partition of bank_accounts
for values from (501) to (1001) with (shard=2,engine=rocksdb);
call generate_account_data();
analyze bank_accounts;

Then repeat the testing process in 8.2, and the expected global deadlock handling result also appeared.

8.4 Rocksdb and InnoDB Mixed Storage Engine Table Deadlock Detection

Recreate the test table for both Rocksdb and InnoDB storage engines, and then carry out the related tests

drop table bank_accounts;
create table bank_accounts
(
   id         INT NOT NULL AUTO_INCREMENT,
   balance    DECIMAL(18,2) NOT NULL,
   primary key(id)
) partition by range(id);
create table bank_accounts_p0 partition of bank_accounts
for values from (1) to (501) with (shard=1,engine=rocksdb);
create table bank_accounts_p1 partition of bank_accounts
for values from (501) to (1001) with (shard=2);
call generate_account_data();
analyze bank_accounts;

Then repeat the testing process in 8.2, and the expected global deadlock handling result also appears.

The KlustronDB global deadlock detection mechanism can quickly and effectively detect global deadlocks. Application developers need to correctly handle deadlock errors according to the content of Section 7 of this article to ensure the high efficiency and smooth operation of the application system.

END

Copyright © KlustronDB
Copyright © 2026 KlustronDB