conflict management in DBMS
This article presents the author's concept of the “Transaction Inspector”, aimed at optimizing the work with transactions in database management systems (DBMS). We propose to use an inverted index to identify conflicting transactions. Before executing a new transaction, the inspector checks whether its set of involved rows intersects with the set of involved rows of already running transactions by comparing the inverted index of the new transaction with the total inverted index of active transactions. If there are no conflicts, the transaction is executed in READ UNCOMMITTED mode, and the overall inverted index is updated both at the start of the transaction and after its completion. Issues of handling conflicts if there is an intersection are also considered. This approach allows you to determine in advance exactly which transactions and records a conflict may arise with, which makes it easier to handle this conflict. We hope that the proposed concept can help improve the performance of the DBMS.
Introduction
One of the main disadvantages of relational DBMSs is the use of long and short locks to ensure data integrity. This leads to delays and unavailability of data, especially in conditions of high competition for resources. As a result, system performance can be significantly reduced, which is critical for applications with a high level of transaction load.
These problems can be illustrated by the behavior of the main character in the film Conspiracy Theory, Jerry Fletcher. His paranoid attitude towards the world around him leads him to lock everything in his house, including the refrigerator and every container of food. This symbolizes his fear of external threats and desire to control every detail of his life.
Similarly, transactions in SERIALIZABLE mode operate with extreme caution, blocking access to resources for other transactions until the current one completes. Although this ensures protection against collisions and anomalies, this behavior also causes delays and reduced system performance. Transactions “isolate” themselves from others, which can lead to locks and waits, similar to how Jerry Fletcher isolates himself from the world.
Thus, both the hero and SERIALIZABLE mode transactions strive for control and security, but this isolation can have negative consequences for their functionality and efficiency.
This article is dedicated to finding a more efficient transaction management mechanism that retains the benefits of SERIALIZABLE mode, including protection against read anomalies and writing data in sequential order, but minimizes or completely eliminates the use of locks. If successful, this will allow transactions to work more freely and efficiently, which is critical for modern applications with a high level of transaction load.
We strive to develop a system concept that is not only high-performance, but also reliable. In this context, it is important to ensure data consistency and protection from possible conflicts without the need to lock resources. This can be achieved through centralized identification of potential conflicts between transactions, allowing the system to proactively predict and handle possible problems.
Thus, the article aims to find solutions that can improve transaction management in database management systems and increase their efficiency in real-world applications.
Transaction Inspector Concept
Our system assumes the use of an inverted index, similar to that used in full-text search, but adapted for working with transactions in database management systems (DBMS). Instead of words, as in a traditional inverted index, we have records in the database, and instead of documents, we have transactions.
The inverted active transaction index consists of the following components:
1. Record Dictionary: This is an ordered list of all unique database records that can be involved in transactions. This dictionary is stored in memory for quick access and allows you to efficiently manage record information.
2. Lists of transaction IDs: For each entry from the dictionary, a list of IDs of active transactions that interact with this entry is created. This list contains information about which transactions are already using or planning to use specific records.
For example, if we have three active transactions operating on different records:
Transaction T1: Updates record R1
Transaction T2: reads record R1 and updates record R2
Transaction T3: Reads record R2
The inverted index will look like this:
R1: {(T1, update), (T2, select)}
R2: {(T2, update), (T3, select)}
Here, each record points to a set of active transactions that interact with it.
When a new transaction is executed, the Inspector uses the inverted index to check the intersection of the sets of records involved. Before starting a new transaction, the system analyzes which records it will use and compares them with the overall inverted index of active transactions. If no intersections are found, a new transaction can be executed in READ UNCOMMITTED mode.
If an intersection with already running transactions is detected, the Inspector initiates the conflict processing process. This allows you to identify possible problems in advance and choose the most appropriate way to resolve them.
An example of the Transaction Inspector working without conflicts
Let's say we have three active transactions working on different records in the database:
Transaction T1: Updates record R1.
Transaction T2: Reads record R2.
Transaction T3: Reads record R3.
Step 1: Inverted Index Structure
According to the description of our concept, the inverted index will look like this:
R1: {(T1, update)}
R2: {(T2, select)}
R3: {(T3, select)}
Step 2: Perform a new transaction
Now let's say we want to execute a new transaction T4 that also reads record R2. Before executing this transaction, the Inspector checks the inverted index to identify possible conflicts.
Step 3: Checking Interferences
The “inspector” analyzes the records that will be involved in transaction T4. In this case it is record R2. It matches it with the inverted index:
For R2, the index indicates that transaction T2 (read) interacts with it.
Step 4: Determine if there is a conflict
Since both transactions (T2 and T4) only read record R2, the Inspector determines that there is an intersection, but it can be ignored because it will not cause conflict.
Step 5: Execute the transaction
Since no conflicts were detected, the new transaction T4 can be executed in READ UNCOMMITTED mode. This allows her to access data without locks. Before starting and after a transaction completes, the inverted index is updated to reflect the new state.
Handling conflicts
1. Lost update
Problem: A lost update occurs when two transactions simultaneously update the same record and one of the updates is lost. For example, if transaction T1 updates record R1, and then transaction T2 also updates R1, then the changes made by T1 may be lost.
Solution in the Transaction Inspector system:
The system uses an inverted index to pre-check intersections. Before executing a new transaction, the Inspector analyzes which records will be involved. If a new transaction attempts to update a record that is already being updated by another active transaction, the Inspector initiates a conflict handling process. We propose the following option for resolving the conflict: suspending T2 at the step before updating R1 until T1 updates R1; if T1 is rolled back, T2 is also rolled back. If T2 completes early (and there is no rollback), a second pause occurs before the commit, waiting for T1 to commit/rollback.
2. Dirty reading
Problem: A dirty read occurs when one transaction reads data that has been modified by another pending transaction. If the second transaction rolls back, the first one will receive invalid data.
Solution in the Transaction Inspector system:
The conflict is resolved using the same logic as in a lost update: when a read transaction completes, we suspend it before committing: if a write transaction is rolled back, we restart the read transaction (from the point where the conflicting record was saved to read).
3. Unrepeatable reading
Problem: A non-repeatable read occurs when one transaction reads the same record twice and gets different values due to changes made by another transaction between reads.
Example:
Transaction T1 reads the value of record R1.
Transaction T2 updates record R1.
Transaction T1 reads R1's record again and gets a new value different from the first one.
Solution in the Transaction Inspector system:
If T2 has started its execution before T1 has read R1, T1 will pause at the step before R1 is read until T2 modifies R1. The logic is the same as in the diagram in the lost update.
If T2 began its execution after T1 had already read R1, then the system selects the more optimal option from the following two:
restart T1 if the inverted index indicates that T1 will access R1's entry again;
or upon reaching T2 of record R1, suspending T2 until T1 of record R1 is read again.
4. Phantom reading
Problem: Phantom reads occur when one transaction executes a query to fetch data and gets different results on subsequent queries because another transaction added or deleted records.
Solution in the Transaction Inspector system:
The problem of deleted records is resolved using the same logic as in non-repeatable reading.
The added entry problem requires that the inverted index entry dictionary also contain “ghost entries” added during analysis. Phantom records reflect those records that are not yet in the database, but that can be added by current transactions. Further, the logic is the same as everywhere else before: when the “Inspector” analyzes a fetch request, it checks the inverted index for the presence of such ghost records and decides on the need to suspend the current transaction until all conflicting operations are completed, that is, roughly speaking, until ghost entry will be added.
Additional system components
The Transaction Inspector system has two key additional components that play an important role in transaction management and conflict handling.
1. Inverted transaction index
Description: Each transaction has its own personal inverted index, which allows you to track which fields the transaction has already interacted with and which fields it plans to use in the future. This index is created during the analysis phase of a transaction and is updated as the transaction progresses.
Functionality:
When a transaction starts, the inspector analyzes its actions and generates an inverted index, which contains information about all the records with which the transaction will work.
The index is updated in real time, allowing the inspector to monitor the current state and prevent conflicts with other active transactions.
2. General inverted index controller
Description: The shared inverted index controller is responsible for managing situations where two or more inspectors simultaneously add transactions to free execution mode, which can lead to conflicts. This controller ensures data integrity and prevents inspectors from seeing conflicting changes due to simultaneous additions.
Functionality:
The general inverted index records the mode of each transaction (free or conflict handling mode).
If the controller detects that multiple transactions are in free mode and can process the same record, it immediately moves later transactions from free mode to conflict handling mode.
