Timestamp-Based Concurrency Control in Databases

Learn how timestamp-based concurrency control ensures serializability of transactions in databases and explore its variants and trade-offs.

Table of Contents

1. Introduction

Concurrency control is a technique that ensures the correct and consistent execution of multiple transactions in a database system. Concurrency control prevents data anomalies, such as lost updates, dirty reads, unrepeatable reads, and phantom reads, that may occur when transactions access and modify the same data concurrently.

There are two main approaches to concurrency control: locking-based and timestamp-based. Locking-based concurrency control uses locks to control the access of transactions to data items. Locks can be shared or exclusive, depending on the operation (read or write) that the transaction performs. Locking-based concurrency control ensures serializability, which means that the concurrent execution of transactions is equivalent to some serial execution of the same transactions.

Timestamp-based concurrency control, on the other hand, uses timestamps to order the transactions and determine their precedence. Timestamps are unique identifiers that are assigned to each transaction when it starts. Timestamps can be logical or physical, depending on the source of the identifier. Logical timestamps are based on some logical order, such as a counter or a vector. Physical timestamps are based on some physical measure, such as the system clock or a random number generator.

In this tutorial, you will learn about the timestamp-based concurrency control technique and its variants, such as basic timestamp ordering and Thomas’ write rule. You will also learn about the advantages and disadvantages of timestamp-based concurrency control compared to locking-based concurrency control. By the end of this tutorial, you will be able to apply timestamp-based concurrency control to ensure serializability and consistency of transactions in your database system.

2. Timestamp-Based Concurrency Control

In this section, you will learn how timestamp-based concurrency control works and what are the rules that govern its operation. You will also see some examples of how timestamp-based concurrency control handles different scenarios of concurrent transactions.

As mentioned in the previous section, timestamp-based concurrency control assigns a unique timestamp to each transaction when it starts. The timestamp reflects the order of the transactions and determines their precedence. The timestamp can be either logical or physical, depending on the source of the identifier. For example, a logical timestamp can be a counter that increments by one for each new transaction, while a physical timestamp can be the system clock that records the time of the transaction start.

Timestamp-based concurrency control uses two data structures to keep track of the timestamps of the transactions that access each data item: the read timestamp (RTS) and the write timestamp (WTS). The RTS records the largest timestamp of any transaction that has read the data item, while the WTS records the largest timestamp of any transaction that has written the data item. These data structures are updated whenever a transaction performs a read or write operation on a data item.

The main idea of timestamp-based concurrency control is to ensure that the transactions are executed in a serial order that is consistent with their timestamps. This means that a transaction with a smaller timestamp should precede a transaction with a larger timestamp in accessing and modifying the same data item. To achieve this, timestamp-based concurrency control uses two rules: the read rule and the write rule.

The read rule states that a transaction T_i can read a data item X only if the timestamp of T_i is greater than or equal to the WTS of X. This ensures that T_i does not read a value of X that was written by a later transaction. If the read rule is violated, then T_i is aborted and restarted with a new timestamp.

The write rule states that a transaction T_i can write a data item X only if the timestamp of T_i is greater than both the RTS and the WTS of X. This ensures that T_i does not overwrite a value of X that was read or written by a later transaction. If the write rule is violated, then T_i is aborted and restarted with a new timestamp.

Let’s see some examples of how timestamp-based concurrency control applies these rules to handle different scenarios of concurrent transactions. Suppose we have two transactions T₁ and T₂ that access the same data item X. Assume that T₁ has a timestamp of 10 and T₂ has a timestamp of 20. Also, assume that the initial values of the RTS and the WTS of X are both 0.

Scenario 1: T₁ reads X and then T₂ reads X. In this case, both transactions can read X without violating the read rule, since their timestamps are greater than or equal to the WTS of X. After T₁ reads X, the RTS of X is updated to 10. After T₂ reads X, the RTS of X is updated to 20. The final value of X is unchanged.

Scenario 2: T₁ writes X and then T₂ writes X. In this case, both transactions can write X without violating the write rule, since their timestamps are greater than both the RTS and the WTS of X. After T₁ writes X, the WTS of X is updated to 10. After T₂ writes X, the WTS of X is updated to 20. The final value of X is the value written by T₂.

Scenario 3: T₁ reads X and then T₂ writes X. In this case, both transactions can access X without violating any rule, since T₁ can read X before T₂ writes X. After T₁ reads X, the RTS of X is updated to 10. After T₂ writes X, the WTS of X is updated to 20. The final value of X is the value written by T₂.

Scenario 4: T₁ writes X and then T₂ reads X. In this case, T₁ can write X without violating the write rule, but T₂ cannot read X without violating the read rule, since the timestamp of T₂ is less than the WTS of X. Therefore, T₂ is aborted and restarted with a new timestamp. The final value of X is the value written by T₁.

As you can see, timestamp-based concurrency control ensures that the transactions are executed in a serial order that is consistent with their timestamps. This guarantees serializability and prevents data anomalies. However, timestamp-based concurrency control also has some drawbacks, such as the possibility of cascading aborts, the overhead of maintaining and comparing timestamps, and the lack of deadlock prevention. In the next section, you will learn about some variants of timestamp-based concurrency control that try to overcome these drawbacks, such as basic timestamp ordering and Thomas’ write rule.

2.1. Basic Timestamp Ordering

Basic timestamp ordering is a variant of timestamp-based concurrency control that simplifies the write rule and avoids cascading aborts. Cascading aborts occur when a transaction that is aborted causes other transactions that depend on it to be aborted as well. This can lead to a chain of aborts that wastes resources and reduces throughput.

The write rule of basic timestamp ordering states that a transaction T_i can write a data item X only if the timestamp of T_i is greater than the WTS of X. This means that T_i does not need to check the RTS of X before writing X, as in the original write rule. This also means that T_i can overwrite a value of X that was read by a later transaction, without causing that transaction to abort.

However, this does not mean that basic timestamp ordering allows data anomalies. Instead, basic timestamp ordering uses a mechanism called ignoring or rejecting to handle the situation where a transaction tries to read a value of a data item that was overwritten by an earlier transaction. Ignoring or rejecting means that the transaction does not read the overwritten value, but instead reads the value that was written by the transaction with the largest timestamp that is smaller than its own timestamp. This ensures that the transaction reads a consistent and serializable value of the data item.

Let’s see an example of how basic timestamp ordering works. Suppose we have three transactions T₁, T₂, and T₃ that access the same data item X. Assume that T₁ has a timestamp of 10, T₂ has a timestamp of 20, and T₃ has a timestamp of 30. Also, assume that the initial values of the RTS and the WTS of X are both 0.

Scenario: T₁ writes X, then T₂ reads X, then T₃ writes X, then T₂ writes X. In this case, T₁ can write X without violating the write rule, since its timestamp is greater than the WTS of X. After T₁ writes X, the WTS of X is updated to 10. Then, T₂ can read X without violating the read rule, since its timestamp is greater than or equal to the WTS of X. After T₂ reads X, the RTS of X is updated to 20. Then, T₃ can write X without violating the write rule, since its timestamp is greater than the WTS of X. After T₃ writes X, the WTS of X is updated to 30. Finally, T₂ cannot write X without violating the write rule, since its timestamp is less than the WTS of X. Therefore, T₂ is aborted and restarted with a new timestamp.

As you can see, basic timestamp ordering avoids cascading aborts, since only T₂ is aborted and not T₃, which depends on T₂. However, basic timestamp ordering also introduces a new problem, called overwriting uncommitted data. This occurs when a transaction overwrites a value of a data item that was written by another transaction that has not yet committed. This can lead to data inconsistency and loss of information. For example, in the scenario above, T₃ overwrites the value of X that was written by T₁, which has not yet committed. If T₁ aborts later, then the value of X that was written by T₁ is lost and cannot be recovered.

In the next section, you will learn about another variant of timestamp-based concurrency control that tries to solve the problem of overwriting uncommitted data, called Thomas’ write rule.

2.2. Thomas’ Write Rule

Thomas’ write rule is another variant of timestamp-based concurrency control that solves the problem of overwriting uncommitted data. Overwriting uncommitted data occurs when a transaction overwrites a value of a data item that was written by another transaction that has not yet committed. This can lead to data inconsistency and loss of information.

The write rule of Thomas’ write rule states that a transaction T_i can write a data item X only if one of the following conditions is true:

The timestamp of T_i is greater than both the RTS and the WTS of X. This is the same as the original write rule.
The timestamp of T_i is less than or equal to the WTS of X, but the value of X has not been read by any transaction with a timestamp greater than T_i. This means that T_i can overwrite a value of X that was written by an earlier transaction, as long as that value has not been read by a later transaction.

The second condition of Thomas’ write rule allows a transaction to write a data item that was written by an earlier transaction, without causing that transaction to abort. However, this also means that the write operation of the earlier transaction is ignored or skipped, since it does not affect the final value of the data item. Ignoring or skipping a write operation does not affect serializability, as long as the value of the data item is not read by a later transaction.

Let’s see an example of how Thomas’ write rule works. Suppose we have three transactions T₁, T₂, and T₃ that access the same data item X. Assume that T₁ has a timestamp of 10, T₂ has a timestamp of 20, and T₃ has a timestamp of 30. Also, assume that the initial values of the RTS and the WTS of X are both 0.

Scenario: T₁ writes X, then T₂ writes X, then T₃ reads X, then T₁ commits, then T₂ commits, then T₃ commits. In this case, T₁ can write X without violating the write rule, since its timestamp is greater than both the RTS and the WTS of X. After T₁ writes X, the WTS of X is updated to 10. Then, T₂ can write X without violating the write rule, since its timestamp is less than or equal to the WTS of X, and the value of X has not been read by any transaction with a timestamp greater than T₂. However, the write operation of T₂ is ignored or skipped, since it does not change the value of X. The WTS of X remains 10. Then, T₃ can read X without violating the read rule, since its timestamp is greater than or equal to the WTS of X. The RTS of X is updated to 30. The final value of X is the value written by T₁.

As you can see, Thomas’ write rule avoids overwriting uncommitted data, since T₂ does not overwrite the value of X that was written by T₁, which has not yet committed. However, Thomas’ write rule also introduces a new problem, called phantom aborts. This occurs when a transaction is aborted because it tries to write a data item that was written by an earlier transaction that has already committed. This can lead to unnecessary aborts and reduced throughput. For example, in the scenario above, if T₁ commits before T₂ writes X, then T₂ will be aborted and restarted with a new timestamp, even though the value of X written by T₁ is already committed and consistent.

In the next section, you will learn about the advantages and disadvantages of timestamp-based concurrency control and its variants, compared to locking-based concurrency control.

3. Advantages and Disadvantages of Timestamp-Based Concurrency Control

In this section, you will learn about the advantages and disadvantages of timestamp-based concurrency control compared to locking-based concurrency control. You will also see how some of the drawbacks of timestamp-based concurrency control can be mitigated by using some variants, such as basic timestamp ordering and Thomas’ write rule.

One of the main advantages of timestamp-based concurrency control is that it does not require locking, which reduces the overhead of acquiring and releasing locks. Locking can also cause performance issues, such as blocking and deadlock, when transactions have to wait for locks held by other transactions or when transactions form a cycle of waiting for each other’s locks. Timestamp-based concurrency control avoids these problems by using timestamps to order the transactions and determine their precedence.

Another advantage of timestamp-based concurrency control is that it ensures serializability, which means that the concurrent execution of transactions is equivalent to some serial execution of the same transactions. Serializability is an important property that guarantees the correctness and consistency of the database state. Timestamp-based concurrency control achieves serializability by enforcing the read and write rules, which prevent data anomalies, such as lost updates, dirty reads, unrepeatable reads, and phantom reads.

However, timestamp-based concurrency control also has some disadvantages, such as the possibility of cascading aborts, the overhead of maintaining and comparing timestamps, and the lack of deadlock prevention. Let’s look at each of these drawbacks in more detail.

A cascading abort occurs when a transaction is aborted and causes other transactions that depend on its results to be aborted as well. This can lead to a chain of aborts that affects many transactions and wastes resources. Timestamp-based concurrency control can cause cascading aborts when a transaction violates the read or write rule and has to be aborted and restarted with a new timestamp. This can affect other transactions that have read or written the same data item as the aborted transaction.

For example, suppose we have three transactions T₁, T₂, and T₃ that access the same data item X. Assume that T₁ has a timestamp of 10, T₂ has a timestamp of 20, and T₃ has a timestamp of 30. Also, assume that the initial values of the RTS and the WTS of X are both 0. Suppose the following sequence of events occurs:

T₁ writes X and updates the WTS of X to 10.
T₂ reads X and updates the RTS of X to 20.
T₃ writes X and updates the WTS of X to 30.
T₁ tries to read X but violates the read rule, since its timestamp is less than the WTS of X. Therefore, T₁ is aborted and restarted with a new timestamp.
T₂ tries to write X but violates the write rule, since its timestamp is less than the WTS of X. Therefore, T₂ is aborted and restarted with a new timestamp.

In this scenario, T₁ causes a cascading abort of T₂, since T₂ depends on the value of X written by T₁. This can be avoided by using a variant of timestamp-based concurrency control called basic timestamp ordering, which we will discuss in the next section.

Another disadvantage of timestamp-based concurrency control is that it requires maintaining and comparing timestamps for each data item and each transaction. This can incur a significant overhead, especially when the database system has a large number of data items and transactions. The overhead can also increase the response time and reduce the throughput of the system. Moreover, the timestamps have to be unique and consistent, which can be challenging to achieve in a distributed system.

A final disadvantage of timestamp-based concurrency control is that it does not prevent deadlock, which is a situation where two or more transactions are waiting for each other to finish and none of them can proceed. Deadlock can occur in timestamp-based concurrency control when a transaction has to wait for a data item that is being accessed by another transaction with a larger timestamp. For example, suppose we have two transactions T₁ and T₂ that access two data items X and Y. Assume that T₁ has a timestamp of 10 and T₂ has a timestamp of 20. Also, assume that the initial values of the RTS and the WTS of X and Y are both 0. Suppose the following sequence of events occurs:

T₁ writes X and updates the WTS of X to 10.
T₂ writes Y and updates the WTS of Y to 20.
T₁ tries to write Y but has to wait for T₂ to finish, since its timestamp is less than the WTS of Y.
T₂ tries to write X but has to wait for T₁ to finish, since its timestamp is less than the WTS of X.

In this scenario, T₁ and T₂ form a cycle of waiting for each other and neither of them can proceed. This is a deadlock situation that can be avoided by using a variant of timestamp-based concurrency control called Thomas’ write rule, which we will discuss in the next section.

As you can see, timestamp-based concurrency control has some advantages and disadvantages compared to locking-based concurrency control. In the next section, you will learn about some variants of timestamp-based concurrency control that try to overcome some of the drawbacks, such as basic timestamp ordering and Thomas’ write rule.

4. Conclusion

In this tutorial, you have learned about the timestamp-based concurrency control technique and its variants, such as basic timestamp ordering and Thomas’ write rule. You have also learned about the advantages and disadvantages of timestamp-based concurrency control compared to locking-based concurrency control.

Timestamp-based concurrency control is a technique that uses timestamps to order the transactions and determine their precedence. Timestamps are unique identifiers that are assigned to each transaction when it starts. Timestamps can be logical or physical, depending on the source of the identifier.

Timestamp-based concurrency control uses two rules to ensure that the transactions are executed in a serial order that is consistent with their timestamps: the read rule and the write rule. The read rule states that a transaction can read a data item only if its timestamp is greater than or equal to the WTS of the data item. The write rule states that a transaction can write a data item only if its timestamp is greater than both the RTS and the WTS of the data item.

Timestamp-based concurrency control has some advantages over locking-based concurrency control, such as avoiding locking overhead, blocking, and deadlock. It also ensures serializability, which guarantees the correctness and consistency of the database state.

However, timestamp-based concurrency control also has some disadvantages, such as causing cascading aborts, requiring timestamp maintenance and comparison, and not preventing deadlock. Some of these drawbacks can be mitigated by using some variants of timestamp-based concurrency control, such as basic timestamp ordering and Thomas’ write rule.

Basic timestamp ordering is a variant of timestamp-based concurrency control that prevents cascading aborts by using a stricter write rule. The write rule of basic timestamp ordering states that a transaction can write a data item only if its timestamp is greater than the WTS of the data item. This means that a transaction cannot overwrite a value that was written by an earlier transaction, even if it has not been read by any later transaction.

Thomas’ write rule is another variant of timestamp-based concurrency control that prevents deadlock by using a more relaxed write rule. The write rule of Thomas’ write rule states that a transaction can write a data item only if its timestamp is greater than the RTS of the data item. This means that a transaction can overwrite a value that was written by a later transaction, as long as it has not been read by any transaction.

We hope that this tutorial has helped you understand the timestamp-based concurrency control technique and its variants, as well as their advantages and disadvantages. You can apply this technique to ensure serializability and consistency of transactions in your database system. Thank you for reading and happy learning!