11 Transaction Processing and Control - How to Manage Concurrent Transactions #
In the previous lecture, we introduced the basic concept of transactions and the process of database recovery, which involved how transaction durability is ensured. In this lecture, we will focus on transaction isolation.
The strongest isolation level in a database is serializability, which guarantees that a transaction appears to have exclusive control over all resources. However, serializability has poor performance, so we introduce multiple isolation levels to improve performance. In the final part of this lecture, I will introduce common concurrency control methods used in distributed databases, which are effective solutions for achieving isolation levels, with the most common being snapshot isolation implemented using multi-versioning.
Now let’s begin today’s content.
Isolation Levels #
Before discussing isolation levels, let’s talk about the concept of “serializability”.
The concept of serializability is closely related to transaction scheduling. A schedule contains all the operations of a transaction. We can use CPU scheduling theory as an analogy. Once a transaction is scheduled, it can access all the resources of the database system, assuming that there are no other transactions that can affect the state of the database. This is similar to a process being scheduled by a CPU, thereby having exclusive access to that CPU resource (where CPU refers to a time-sharing system). In practice, when designing a schedule, internal operations of a transaction may be reordered to allow for parallel execution. These optimizations are permissible as long as they do not violate the principles of ACID and the correctness of the results.
So what is serializability? If a schedule is said to be serializable, it refers to the relationship between the schedule and other schedules: when the schedule is executed, there are no other scheduled transactions running concurrently. In other words, the schedule is executed one after another, with one schedule successfully completing before another schedule starts. One benefit of this approach is that the execution result is more predictable. However, we find that this approach has a clear drawback: it has low performance. In implementation, a serializable schedule may execute multiple transaction operations in parallel while ensuring that it produces the same results as if they were executed one after another.
That is the concept of serializability, which reveals the occurrence of concurrent execution even in serializable schedules. This point is important because in the theory of isolation, an isolation concept only describes a behavior, while there can be multiple implementation choices as long as the results of this behavior meet the necessary conditions.
Serializability is the strongest transaction isolation level and it represents an ideal isolation state, where concurrently running transactions are unaware of each other’s existence and can safely carry out their operations. However, in the implementation of database transactions, serializability poses challenges and has poor performance. Consequently, database theorists have proposed the concept of isolation levels to make compromises to different extents. Before delving into the detailed explanation of isolation levels, let’s first understand what we can “compromise”.
These “compromises” are called anomalies. Read anomalies are more well-known, including “dirty reads,” “non-repeatable reads,” and “phantom reads.” Write anomalies are less known and include “lost updates,” “dirty writes,” and “write skew.” Read and write anomalies are observed from the perspectives of users and data itself respectively, and we will introduce them in pairs. Traditionally, isolation levels are described from the perspective of read anomalies, but in recent years, some papers have approached it from the perspective of write anomalies as well. We hope you can understand that there is a connection between these two ways of expression. The following table shows the relationship between classic isolation levels and read anomalies.
From the table, we can see that serializability does not allow any read or write anomalies to exist. Allowing repeatable reads allows phantom reads to occur. Phantom reads occur when a transaction reads a set of data and then reads the same set of data again, only to find that they may have been modified. The corresponding write anomaly to phantom reads is write skew. Write skew is observed from the perspective of writes, where a transaction reads a batch of data for modification within a transaction. Due to the existence of phantom reads, the final modification results appear to violate the constraints of data consistency as a whole.
Read committed gives up non-repeatable reads on the basis of repeatable reads. Similar to phantom reads, non-repeatable reads target a single data item. This means that if you read a single data item and then read it again within the same transaction, the data may have changed.
Students who are new to this concept may find it perplexing that there are two isolation levels based on just one data item. The reason behind this is that ensuring the consistency of a single data item is much easier than ensuring the consistency of multiple data items. Therefore, the main consideration for defining these two isolation levels is the underlying principle. And this principle involves performance and cost issues. As I have repeatedly emphasized in this column, some theoretical concepts have profound considerations behind them. You need to understand the underlying principles to grasp the essence. However, don’t worry, I will explain the differences in implementation between them in detail later.
The corresponding write anomaly to non-repeatable reads is lost updates. Similar to write skew, lost updates are caused by multiple transactions operating on a single data item.
The lowest isolation level is read uncommitted, which allows dirty reads to occur. Dirty reads are quite simple to understand; they describe a situation where a transaction can read data that has not been committed by other transactions. It can be understood as having no isolation at all. Dirty reads themselves also lead to the write anomaly: dirty writes. Dirty writes occur because of reading uncommitted data.
Above, we have provided a detailed explanation of the classic isolation levels. However, this theory is quite outdated, and the newer MVCC (multi-version concurrency control) technology provides a flexible option for traditional isolation levels. This can be understood as the repeatable read isolation level, which means non-repeatable reads are not allowed. However, under the repeatable read isolation level, it is ensured that data cannot be read if it has been modified. However, the behavior of snapshot isolation is different: once it reads data that has been previously read and modified, it immediately terminates the current transaction, which means it performs a rollback operation. In a highly concurrent transaction scenario, only one transaction will succeed. You can carefully examine the differences between the two.
Snapshot isolation can solve the problem of lost updates because it can create a snapshot of the same data item to detect modifications. However, it cannot prevent write skew.
Snapshot isolation is the most commonly used isolation level in modern distributed database storage engines, and solving write skew is also the problem that storage engines need to address at this isolation level. SSI (Serializable Snapshot Isolation) is the solution to this problem, and I will provide a detailed introduction to this solution in the article “18 | Distributed Transactions: Latest Research and Practices on the ‘Biggest Challenges’”.
So far, we have discussed the typical isolation levels. I have already explained the relationship between isolation levels and distributed consistency in the article “<05 | Consistency and CAP Theorem: Why We Need Distributed Consistency>”. If you need a review, please turn left at the door. Now let’s continue discussing how to implement these isolation levels.
Concurrency Control #
Currently, storage engines have introduced various concurrency models to implement the aforementioned isolation levels. Different models have their preferences for implementing different levels, although theoretically, each control model can implement all levels. Below, I will introduce the optimistic and pessimistic approaches, as well as the multi-version and lock-based approaches.
Optimistic and Pessimistic #
The concepts of optimistic and pessimistic are similar to those of optimistic and pessimistic locks in concurrent programming. However, you should note that implementing them does not necessarily require lock management. The optimistic control is used in scenarios where there are not many parallel transactions, that is, only a small amount of time is needed to resolve conflicts. In such cases, conflict resolution methods can be used to achieve isolation levels. The most commonly used solution is to perform conflict checks before committing.
There are various implementation patterns for conflict checks, such as the commonly used multi-version pattern. Another ancient pattern requires checking the data operated by parallel transactions directly, that is, observing whether there is any overlap in the data they operate on. Due to its poor performance, it is rarely found in modern storage engines. It is important to note that optimistic control does not necessarily mean only the implementation of multi-versions, there are other options available.
Similarly, pessimistic control is not limited to just locks. One possible lock-free implementation is to first set two global timestamps, the maximum read time and the maximum write time. If a read operation occurs before the maximum write time, the transaction in which the operation occurs is considered to be terminated because it likely reads old data. Similarly, if a write operation occurs before the maximum read time, it is considered an abnormal operation because a read operation has just occurred and the current transaction should not modify the data. These two values are updated with write and read operations. This pessimistic control is called the Thomas Write Rule. If you are interested, you can search and learn more about it.
Although there are multiple implementation options for both optimistic and pessimistic control, the most common implementation for optimistic control is multi-version control, and the most common implementation for pessimistic control is lock control. Now let me provide a detailed introduction to them.
Multi-Version Control #
Multi-Version Concurrency Control (MVCC) is a classic pattern for implementing optimistic control. It assigns a version number to each row of data and uses a monotonically increasing version number generator to generate these version numbers, ensuring that each record has a unique version number. Each transaction is assigned an ID or timestamp to ensure that read operations can read the old values before the transaction is committed.
MVCC distinguishes between committed versions and uncommitted versions. The most recent committed version is considered the current version and can be read by all transactions. Depending on the isolation level, read operations can or cannot read uncommitted versions.
The most common usage of MVCC is to implement snapshot isolation. When a transaction starts, the current time is recorded, and all read operations within that transaction can only read data whose current committed version is less than the transaction start time. Uncommitted data and data with committed versions greater than the transaction start time cannot be read. If the data read by a transaction has been modified by other transactions, it should be in the undo log mentioned in the previous lecture, and the current transaction can still read this data. Therefore, the data in the undo log cannot be cleared when the transaction is committed because there may be other transactions reading it.
When a transaction is committed, the data is already written. Only the version status needs to be changed from uncommitted to committed. Therefore, the commit operation in MVCC is very fast, which has many implications for distributed transactions.
The mentioned SSI mode can introduce conflict resolution mechanisms based on MVCC to solve the write skew problem. When a commit occurs, the transaction checks whether the data it modifies and reads has been modified by other committed transactions before the commit. If so, the current transaction is terminated and rolled back. There are two timing options for this conflict detection: one is to perform the check during read operations within the transaction, called forward detection. Conversely, performing the check during commit is called backward detection. You can clearly see that the former will fail quickly but have lower performance, while the latter responds slower to exceptions but has an advantage in speed.
This is the classic MVCC concurrency control. Now let me continue with the typical pessimistic control: lock control.
Lock-based Control #
Lock-based control is a typical pessimistic control. It uses explicit locks to control shared resources, rather than relying on scheduling methods. Lock control can easily achieve “serialized operations,” but it also has problems such as lock contention and difficulty in scalability. A well-known locking technique is two-phase locking (2PL), which summarizes lock operations into two phases.
- Lock expansion phase. In this phase, the transaction gradually acquires all the locks it needs, without releasing any locks. During this period, the transaction can operate on locked data.
- Lock contraction phase. In this phase, all the locks obtained in the previous phase are released. This transaction is gradual, and during this period, the transaction can still operate on data that is still locked.
The above process is simple and clear. It is proposed for one-time locking. The disadvantage of one-time locking is that it lacks concurrency and has low performance. Two-phase locking can ensure a certain degree of concurrency, but its disadvantage is that it can lead to deadlocks.
A deadlock occurs when two transactions hold each other’s locks, causing them to be unable to continue running. Solving deadlock requires the introduction of a timeout mechanism, but the timeout mechanism has obvious performance drawbacks. At this time, people will introduce a deadlock detection mechanism to detect deadlocks as early as possible. The general implementation method is to build a dependency graph of the locks of all transactions, and then use graph algorithms to detect circular deadlock structures in order to quickly determine the occurrence of deadlocks.
The opposite concept of locks is “latch”. Generally, it is said that latches are lightweight, while locks are heavyweight. This is reflected in two aspects.
First, it refers to the objects they handle. Latches are generally used in small-grained data, such as data blocks, index tree nodes, etc. Locks generally act on large-grained operations, such as locking multiple rows of data, transactions, and modifying storage structures.
Second, their implementations are different. Latches are generally implemented using CAS instructions, which are lock-free instructions based on compare-and-set. If the original value changes, the above operations will be performed again, and this process is called spinning. Locks, on the other hand, use dedicated resources and have lock managers to control them. As you can imagine, scheduling locks is a time-consuming and complex process.
This leads to the difference between the isolation levels “Serializable” and “Read Committed” mentioned earlier. “Serializable” requires heavyweight locks to ensure the consistency of a set of data read repeatedly, which is very costly. “Read Committed” only needs to ensure the consistency of reading a single row of data, which can be achieved using lightweight latches. Therefore, it is very reasonable for isolation levels to classify them into two types, because in terms of principles, they are completely different.
Above is the relevant content about locking-based control.
Summary #
That’s all for this lecture. Transactions are the longest topic in our course so far, and it took two lectures to explain in detail. The topic of transactions has always been popular in the field of databases. I started from the perspective of transaction principles and explained the technical means required for ACID and different isolation levels. These contents lay a solid foundation for the study of distributed transactions. At the same time, you can consider this column as a reference material and consult it at any time.
From the essence, a transaction is a concept oriented towards users. It provides a contract to users in order to enable reliable use of databases to store and share data, which is the core function of databases. Many applications are based on this function, which is also the fundamental reason why distributed databases need to implement transactions under distributed conditions.