Skip to main content

Global Deadlock Detection in Klustron

KlustronAbout 6 min

Global Deadlock Detection in Klustron

Note:

Unless specifically stated, any version number mentioned can be substituted with any released version number. For all released versions, please visit: Release_notes

Objective:

Transactional deadlocks are a common phenomenon in database systems that rely on transactional locks, with mechanisms for handling deadlocks present in databases like MySQL and Oracle. In Klustron's distributed database system, global deadlocks can occur, where the deadlock resolution mechanisms of individual storage nodes are insufficient. A global deadlock resolution mechanism at the distributed database cluster level is required to detect and resolve these deadlocks. This document first introduces what a deadlock and a global deadlock in distributed systems are, how Klustron addresses global deadlock issues, and finally provides relevant examples.

01 What is a Deadlock

A deadlock occurs when two or more transactions mutually wait for each other to release resources they hold, causing all involved transactions to be unable to proceed. In such situations, each transaction waits for one or more resources that are held by others, with no one able to relinquish these resources, leading the entire system into a stalemate.

02 The Impact of Deadlocks on Databases

Because deadlocks prevent all involved transactions from continuing, they pose a severe problem and can lead to issues like accumulation. The most apparent effect is the reduced concurrency in database transaction processing. In high-concurrency servers, deadlocks can cause the database to fail to respond to requests, affecting the overall stability and availability of the system.

03 Examples of Deadlocks

Below is an example of two sessions creating a deadlock loop waiting on each other.

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;

In this scenario, the two transactions in Session 1 and 2 each obtain the transaction locks needed by the other, forming a circular wait and creating a deadlock.

04 Resolving Deadlocks

Currently, common transactional storage engines support the detection and resolution of transaction deadlocks. The method involves failing to acquire a transaction lock and regularly conducting a round of deadlock detection by a deadlock handler: scanning the lock system's waiting relationships, finding deadlock loops, and then selecting one transaction in the loop as the so-called victim to deny its lock request. Consequently, the DML statement being executed by this victim transaction will return an error, and the client will need to handle this error, such as rolling back the transaction or retrying the statement.

MySQL’s InnoDB storage engine has its own deadlock detection mechanism that follows this method for deadlock detection and resolution.

05 Mechanisms of Global Deadlocks in Klustron

Global deadlocks are a type of transactional deadlock that occurs at the global level within a distributed database cluster, which single-node deadlock processors are unable to detect or resolve. However, the conditions for their occurrence are completely the same as in the case of a single-machine database.

Here's an example of a global deadlock scenario, where the record of bank_accounts id 100 is located on shard1, and id 600 on 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;

In this case, GT2.T21 blocks GT1.T12, and GT2 blocks GT1; GT1.T11 blocks GT2.T22, and GT1 blocks GT2, forming a circular wait between GT1 and GT2.

Global deadlocks are characterized by:

  1. Local waits in the transaction branches of storage nodes lead to global transaction waits, which in turn create circular wait relationships among these global transactions.
  2. No deadlock occurs within individual storage nodes; they cannot automatically detect or resolve global deadlocks.
  3. Global transactions in the deadlock loop can originate from transactions started from multiple compute nodes or all from the same compute node.

06 Handling Global Deadlocks in Klustron

The detection and resolution of global deadlocks in Klustron involve the following steps: first, it is necessary to obtain the current local transaction lock waiting relationships from each storage node's master within the cluster to construct a global transaction lock waiting relationship graph. Next, this graph is traversed to identify any waiting cycles. Upon finding a cycle, a victim is chosen from within the cycle to have its lock request denied, resulting in an execution error being sent to the victim’s client.

07 Triggering Deadlock Detection and Client Handling in Klustron

Klustron's global deadlock detection mechanism is a module of the kunlun-server compute node, running as a background process after the compute node is launched, known as the Global Deadlock Detector (GDD). If a CRUD (Create, Read, Update, Delete) DML statement takes longer than a set duration (start_global_deadlock_detection_wait_timeout) to return a response from a storage node, the compute node will notify the global_deadlock_detector process to trigger a round of global deadlock detection and resolution. Additionally, the GDD also runs periodically in the background with an interval set by global_deadlock_detector.naptime=3s.

A global transaction selected as a victim will return an error ER_QUERY_CANCELED to the client. By default, this transaction is automatically rolled back within the compute node, and all subsequent statements in this transaction are ignored until the transaction ends.

Klustron also supports MySQL's transaction processing mode. If enable_stmt_subxact = true is set before a transaction starts, then a statement execution error will not automatically roll back the transaction, but instead, the client code decides how to handle the error. This mechanism applies to all errors, not just deadlock errors, and is valid for both MySQL and PostgreSQL connections. Upon receiving any statement execution error, the client may choose to ignore the error and continue running subsequent SQL statements, then commit the transaction; or retry the failed SQL statement and those following it, then commit the transaction; or directly roll back the transaction and possibly retry it.

Klustron compute nodes log every global deadlock detection and the rollback of global transactions in their operational logs, providing a trace for users to review and check.

08 Klustron Deadlock Examples

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 Deadlocks Within the Same Shard

Since Klustron's storage nodes use MySQL, deadlocks within the same shard are handled using MySQL’s deadlock detection mechanism. The sequence of events 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, it results in an error as shown:

Session 1's second update statement stops being blocked and updates successfully.

8.2 Deadlocks Across Different Shards

The execution sequence is as follows:

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;

When GT2.T22 executes, Klustron's global deadlock detection mechanism processes it and throws an error 1317.

The logs show 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 storage node (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 Deadlock Detection

Recreate the test table with the Rocksdb storage engine, then conduct 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,engine=rocksdb);
call generate_account_data();
analyze bank_accounts;

Then repeat the test process from 8.2 and observe the expected global deadlock resolution result.

8.4 Mixed Storage Engine Deadlock Detection with Rocksdb and InnoDB

Recreate the test table with both Rocksdb and InnoDB storage engines, then conduct 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 test process from 8.2 and again observe the expected global deadlock resolution result.

Klustron's global deadlock detection mechanism effectively and rapidly identifies and resolves global deadlocks. Application developers should correctly handle deadlock errors based on the content of section 7 to ensure the efficient and smooth operation of application systems.

END

Copyright © Klustron
Copyright © 2025 Klustron