Unveiling Infinite Database Anomalies: Tencent TDSQL’s Precise Classification and Hands‑On Tool

Background

The TDSQL team at Tencent formalized a theory of data anomalies in concurrent transactions. An anomaly is defined as a directed cycle (conflict ring) in a transaction history that contains at least one conflict operation.

Data‑Anomaly Classification

Based on the partial‑order relations present in the cycle, anomalies are grouped into three primary categories:

Write Anomaly (WAT) : the cycle contains a write‑write partial order.

Read Anomaly (RAT) : the cycle contains one or more write‑read partial orders but no write‑write partial order.

Intersection Anomaly (IAT) : all other anomalies.

Each category can be refined by the number of data items involved:

Single‑Data Anomaly (SDA) : the conflict involves a single variable across two transactions.

Dual‑Data Anomaly (DDA) : the conflict involves two variables across two transactions.

Multi‑Data Anomaly (MDA) : any anomaly that is not SDA or DDA.

Conflict‑Ring (冲突环图) Definition

A conflict ring is a directed graph where:

Each vertex represents a transaction.

Each edge represents a conflict operation between two transactions on the same data item, with at least one operation being a write.

A conflict operation must satisfy three conditions:

It occurs in different transactions.

It accesses the same data item.

At least one of the operations is a write.

If such a directed cycle exists, a data anomaly inevitably occurs. The type of anomaly is determined by the partial‑order relations (write‑write, write‑read, read‑write) present on the edges.

Open‑Source Tool: 3TS‑DAI

The team released a Linux command‑line utility named 3TS‑DAI that automatically detects and classifies data anomalies according to the conflict‑ring theory.

Source Repository

GitHub:

https://github.com/Tencent/3TS

Build Instructions (C++17 compiler required)

mkdir 3TS

wget https://github.com/Tencent/3TS/archive/refs/heads/master.zip

unzip master.zip

cd 3TS-master

./make.sh

./3TS-DAI

If the compiler reports “unrecognized option ‘--std=c++17’”, install a newer GCC (version 8 or later) from https://gcc.gnu.org/.

Interactive Commands

help

or h: display help. \d History: show the definition of a history. \a <anomaly name>: display details of a specific anomaly (e.g., \a Dirty Read). \t <table name>: list table information (e.g., \t Anomalies). \A: show author information. \q: quit.

Operations are encoded as three‑character tokens: R0a (transaction 0 reads item a), W1b (transaction 1 writes item b), C2 (transaction 2 commits), A3 (transaction 3 aborts). A history is a space‑separated sequence of such tokens.

Example: Dirty‑Read

R0a R1a W0a R0a W0a W1a A1 C0

Feeding this history to ./3TS-DAI yields the classification “Dirty Read” (a read anomaly).

Example: Non‑Repeatable‑Read

The following conflict‑ring diagram (Image 1) illustrates a non‑repeatable‑read anomaly. The edge from T1 to T2 is a read‑write partial order (T1 reads x, T2 later writes x). The opposite edge is a write‑read partial order. Together they form a directed cycle, satisfying the conflict‑ring definition, thus guaranteeing the anomaly.

Other Anomalies

Similar conflict‑ring diagrams are provided for lost‑update, phantom read, etc. (Images 2‑4). By entering the corresponding histories, the tool correctly identifies each anomaly type.

Summary

The conflict‑ring framework provides a unified, mathematically grounded classification for an infinite set of data anomalies in concurrent transaction processing. The open‑source 3TS‑DAI utility implements this theory, enabling developers to input transaction histories and obtain precise anomaly detection and classification on Linux platforms.