Chapter 16
Transactions
16.1 Introduction
The concept of a transaction has been very useful in allowing concurrent processing of data with consistent results. A transaction is a sequence of operations such that that entire sequence appears as one indivisible operation. For any observer, it appears as if the entire sequence has been executed or none of the operations in the sequence have been executed. This property of indivisibility is preserved by a transaction despite the presence of concurrency and failures. By concurrency, we mean that multiple transactions may be going on at the same time. We are guaranteed that the transactions do not interfere with each other. The concurrent execution of multiple transactions is equivalent to a serial execution of those transactions. Further, if the transaction has not committed and there is failure, then everything should be restored to appear as if none of the operations of the transaction happened. If the transaction has committed, then the results of the transaction must become permanent even when there are failures.
As an example of a transaction, consider transfer of money from account A to account B. The transaction, say T1 can be written as
begin-transaction
withdraw x from account A;
deposit x to account B;
end_transaction
Once the two operations of withdrawing and depositing have been grouped as a transaction, they become atomic to the rest of the world. Assume, for example, that another transaction T2 is executed concurrently with this transaction. T2 simply adds the balances in accounts A and B. The semantics of the transaction guarantees that T2 will not add the balance of account A after the withdrawal and the balance of account B before the deposit. The all-or-nothing property is also guaranteed when there is a failure. If the second operation cannot be performed for some reason (such as account B does not exist), then the effects of the first operation are also not visible, i.e., the balance is restored in account A.
A transaction can be viewed as implementing the following primitives:
1. begin_transaction: This denotes the beginning of a transaction.
2. end_transaction: This denotes the end of a transaction. All the statements between the beginning and the end of the transaction constitute the transaction. Execution of this primitive results in committing the transaction, and its effects must persist.
3. abort_transaction: The user has the ability to call abort-transaction in the middle of a transaction. This requires that all values prior to the transaction are restored.
4. read: Within a transaction, the program can read objects.
5. write: Within a transaction, the program can also write objects.
16.2 ACID Properties
Sometimes the guarantees provided by a transaction are called ACID properties, where ACID stands for atomicity, consistency, isolation, and durability. These terms are explained next.
• Atomicity: This property refers to all-or-nothing property explained earlier.
• Consistency: A transaction should not violate integrity constraints of the system. A typical example is that of a financial system where the transaction of money transfer from one account to the other should keep the total amount of money in the system constant. It is the responsibility of the programmer writing the transaction to ensure that such constraints are not violated after the transaction has taken place.
• Isolation: This means that transactions are isolated from effects of concurrent transactions. Thus, in spite of concurrency, the net effect is that it appears that all transactions executed sequentially in some order.
• Durability: This property refers to the aspect of committing a transaction. It says that once a transaction has been committed its effects must become permanent even if there are failures.
16.3 Concurrency Control
The isolation property of transaction is also called the serializability condition. A concurrent history H of transactions T1, T2, . . . , Tn, is serializable if it is equivalent to a serial history. As an example, suppose that there are two transactions: T1 and T2. T1 transfers $100 from account A to account B and T2 transfers $200 from account B to account C. Assuming that each account has $1000 initially, the final balances for A, B, and C should be $900, $900 and $1200, respectively. T1 could be implemented as follows:
begin_transaction;
x = read(A);
x = x-100;
write x to A;
x = read(B);
x = x+100;
write x to B;
end_transaction;
T2 could be implemented as follows:
begin_transaction;
y = read(B);
y = y-200;
write y to B;
y = read(C);
y = y+200;
write y to C;
end_transaction;
It is clear that all concurrent histories are not serializable. In the example above, assume that the following history happened:
x = read(A);
x = x-100;
write x to A;
x = read(B);
y = read(B);
y = y-200;
write y to B;
y = read(C);
y = y+200;
write y to C;
x = x+lOO;
write x to B;
In this case, the final values would be 900, 1100, and 1200, which is clearly wrong. One way to ensure serializability would be by locking the entire database whem a transaction is in progress. However, this will allow only serial histories.
A more practical technique frequently employed is called two-phase locking. In this technique, a transaction is viewed as consisting of two phases: the locking phase and the unlocking phase. In the locking phase (sometimes called a “growing” phase), a transaction can only lock data items and in the unlocking phase (sometimes called a “shrinking” phase) it can only unlock them. With this technique, the implementation of T1 would be
begin_transaction;
lock(A) ;
x = read(A) ;
x = x-100 ;
write x to A ;
lock(B) ;
x = read(B) ;
x = x+lOO ;
write x to B ;
unlock(A) ;
unlock(B) ;
end_transaction ;
16.4 Dealing with Failures
There are primarily two techniques used for dealing with failures called private workspace and logging. In the private workspace approach, a transaction does not change the original primary copy. Any object that is affected by the transaction is kept in a separate copy called a shadow copy. If the transaction aborts, then private or shadow copies are discarded and nothing is lost. If the transaction commits, then all the shadow copies become the primary copies. Note that this technique is different from the technique for nonblocking synchronization, which we studied in Chapter 5. In the private workspace approach, we do not make copy of the entire database before a transaction is started. Instead, a copy of only those objects (or pages) are made that have been updated by the transaction. This technique can be implemented as follows. Assume that objects can be accessed only through pointers in the index table. Let S be primary index table of objects. At the beginning of a transaction, a copy of this table, S’, is made and all read and write operations go through S’. Since reads do not change the object, both S and S’ point to the same copy, and thus all the read operations still go to the primary copy. For a write, a new copy of that object is made and the pointer in the table S’ is changed to the updated version. If the transaction aborts, then the table S’ can be discarded; otherwise, S’ becomes the primary table. Observe that this scheme requires locking of the objects for transactions to be serializable.
In the logging scheme, all the updates are performed on a single copy. However, a trail of all the writes are kept so that in case of a failure, one can go to the log and undo all the operations. For example, if an operation changed the value of object x from 5 to 3, then in the log it is maintained that x is changed from 5 to 3. If the transaction has to abort, then it is easy to undo this operation.
16.5 Distributed Commit
When a transaction spans multiple sites, we require that either all sites commit the transaction or all abort it. This problem is called the distributed commit problem. The problem is, of course, quite simple when there are no failures. In this section, we address how to solve the problem when processes may fail. We assume that links are reliable.
The requirements of the problem are as follows:
• Agreement: No two processes (failed or unfailed) decide on different outcome of the transaction.
• Validity: If any process starts with abort, then abort is the only possible final outcome. If all processes start with commit and there are no failures, then commit is the only possible outcome.
• Weak termination: If there are no failures, then all processes eventually decide.
• Non-blocking: All nonfaulty processes eventually decide.
We now give a two-phase commit protocol that satisfies the first three conditions. The steps in the protocol are:
• The coordinator sends a request message to all participants.
• On receiving a request message, each participant replies with either a “yes” or a “no” message. A “yes” message signifies that the participant can commit all the actions performed at its site. This finishes the first phase of the algorithm.
• The coordinator waits to receive messages from all participants. If all of them are “yes,” then the coordinator sends the finalCommit message. Otherwise, it sends a finalAbort message.
• The participant carries out the action associated with the message received from the coordinator.
Thus there are two phases: the voting phase and the decision phase. In the voting phase, the coordinator collects all the votes and in the decision phase it communicates the final decision to all the participants.
The algorithm for the coordinator is shown in Figure 16.1. The coordinator invokes the method doCoordinator() to carry out the protocol. In the first phase, the coordinator waits until the flag donePhasel becomes the. This flag becomes true if all participants have replied with “yes” messages or when one of the participant has replied with a “no” message. These messages are handled in the method handleMsg which make call to notify() appropriately.
The algorithm for a participant is shown in Figure 16.2. A participant implements the consensus interface with the methods propose and decide. When a participant invokes decide, it is blocked until it gets a finalCommit or a finalAbort message from the coordinator. We have not shown the actions that the coordinator and participants need to take when they timeout waiting for messages. We have also not shown the actions that processes need to take on recovering from a crash. This part is left as an exercise for the reader (see Problem 16.6).
Let us now analyze the protocol from the perspective of the coordinator. If it does not hear from any of the participants in the first phase, then it can abort the entire transaction. Therefore, if a participant fails before it sends out its vote in the first phase, the failure is easily handled. What if the participant fails after it has sent out its vote as commit? Since the transaction may have committed, when the process recovers, it must find out the state of the transaction and commit all the changes. This observation implies that a participant can send a “yes” message only if it can make all the changes for committing a transaction despite a fault. In other words, the participant must have logged onto its stable storage the necessary information required to commit the transaction.
Let us now analyze the protocol from the perspective of a participant. Initially it is expecting a request message that may not arrive for the predetermined timeout interval. In this case, the participant can simply send a “no” message to the coordinator and can assume that the global transaction had aborted. The coordinator can also crash in the second phase. What if the participant has replied with a “yes” message in the first phase and does not hear from the coordinator in the second phase? In this case, it does not know whether the coordinator had committed the global transaction. In this case, the participant should inquire other participants about the final decision. If the coordinator crashed after sending finalCommit or finalAbort message to any participant who does not crash, then all participants will learn about the final decision. However, this still leaves out the case when the coordinator crashed before informing any participant (or the participants that it informed also crashed). In this case, all the participants have no choice but to wait for the coordinator to recover. This is the reason why two-phase commit protocol is called blocking.
Figure 16.1: Algorithm for the coordinator of the two-phase commit protocol
Figure 16.2: Algorithm for the participants in the two-phase commit protocol
16.6 Problems
16.1. A contracted two-phase locking scheme is one in which the second phase is contracted, that is, all locks are unlocked at the same time. What are the advantages and disadvantages of this scheme compared with the ordinary two-phase locking scheme ?
16.2. Write a class that provides the following services:(a) lock(String varname; int pid); returns 1 if allowed by two-phase locking scheme, returns 0 otherwise, and (b) unlock(String varname, int pid); returns 1 if locked by the process, returns 0 otherwise. Assume that the processor never crashes.
16.3. Which of the following schedules are serializable ?
(a) r1 (a, b); w1 (b); r2(a); w1(a); w2(a).
(b) r1 (a, b); w1 (b); r2(a); w1(a); r1(b).
(c) r2 (a); r1 (a, b); w2(c); w1(a); w1(c).
(d) r1(a), r2(b), w1(a), w2(b), r1(b), w1(b), r2(c), w2(c)
For each of the serializable schedules, show a possible two-phase locking history.
16.4. Assume that you have two floats representing checking balance and savings balance stored on disk. Write a program that transfers $100 from the checking account to the savings account. Assume that the processor can crash at anytime but disks are error-free. This means that you will also have to write a crash recovery procedure. You are given the following primitives:
class Stable {
float val;
// to copy disk object val to memory object x, use
synchronized void get (float x)
// to copy memory object x to disk object Val, use
synchronized void set (float x)
}
16.5. Explain why the two-phase commit protocol does not violate the FLP impossibility result.
16.6. Complete the code for the participants (Figure 16.2) and the coordinator (Figure 16.1) by specifying actions on timeout and crash recovery.
16.7 Bibliographic Remarks
The reader is referred to the book by Gray and Reuter [GR93] for a comprehensive treatment of transactions.