Advertisement

Concurrent transactions

As long as only one transaction executes on the network at any given time, you can easily provide this guarantee: All transaction steps perform consecutively, with no one else permitted to read or write the data those steps access. When one transaction completes before another begins, the transactions execute serially.

To illustrate this, imagine another transaction that uses the credit card service but is unrelated to the book purchase -- a transaction that arranges your utility bill payment using your credit card, for example. This transaction transfers money between two accounts: your credit card and the utility company's bank account. It coordinates work (the transfer) between CreditCard and a utility account service, Utility. Let's designate this transaction as T_PayUtility, and denote the original book purchase transaction as T_BuyBook.

Figure 2 shows the steps of these two transactions when all T_BuyBook steps complete before any T_PayUtility steps begin (i.e., when the two transactions execute serially).

Neat as this arrangement appears, the Jini federation cannot ensure a purely serial transaction execution. Doing so requires a central controller -- a transaction scheduler -- that tracks the beginnings and ends of transactions, causing others to wait to begin until a transaction executes all its steps. In addition, forcing serial transaction execution severely limits the network's ability to execute transactions on time -- the network's transaction throughput -- as most transactions are delayed. Transactions that don't execute sequentially can easily violate the consistency of shared data. To see how this could happen, we must first change our vantage point of what occurs inside a transaction.

Thus far, we've taken a birds-eye view. We've considered the distributed transaction's actions in all the nodes (services) with which it interacts. However, in a distributed system without a central controlling entity, that is an artificial viewpoint. Any service involved in a transaction is aware only of what read and write operations occur locally, and has no way to gain a global perspective on a transaction. Therefore, we will change our observation point and look at the serial execution of two transactions as they interact with just one service, CreditCard.

Viewed inside CreditCard, T_BuyBook first reads the credit card's existing balance as well as the maximum allowed balance. If the purchase falls below the maximum limit, the transaction then increments the current balance, and writes that amount back to stable storage. If the purchase of the book would push the card's balance over the credit limit, the current balance is left intact; in that case, the service returns a CreditCardException from the method call. T_PayUtility works similarly: It begins by reading the account balance and maximum allowed credit limit, and determines if it can charge the utility bill on the card. If so, it increments the balance, and writes the new amount to persistent store. Figure 3 illustrates the performance of these transactions inside CreditCard.

While these actions occur, each transaction interacts with other services, of which CreditCard is not aware and any of which can cause the transactions to abort. For instance, after T_BuyBook-related actions complete inside CreditCard, the ShippingService might cause the transaction to abort for lack of available shipping route. At that point, CreditCard must restore the old balance. Therefore, the transaction's abort will appear as a new write operation inside CreditCard.

Figure 4 shows four possible sequences of read and write operations, considering a transaction abort as a new write action. The four possible execution histories show what can go wrong when actions from concurrently executing transactions interleave.

Figure 4. Concurrently executing transactions introduce possible anomalies: lost updates, dirty reads, and unrepeatable reads. If both transactions only read the data, no anomalies occur.

You can easily imagine what goes wrong in H₁, H₂, and H₃ with an example. Suppose you purchase the book for $30, and the Jini service pays the $50 utility bill. Your initial account balance is $100. Based on these initial facts, concurrently executing transactions would introduce the following anomalies:

1. Lost updates: In H₁, one transaction (T_BuyBook) reads the account balance, followed by another transaction (T_PayUtility) reading the balance. At that point, both transactions know that the account balance is $100. Next, T_BuyBook increments the balance, adding the book's price, and writes the new value, $130, to stable store. Finally, T_PayUtility computes the balance, adding the utility bill price to the old balance, and writes its value to stable store ($150). Thus, the book purchase price is lost -- in effect, you receive a free book.
2. Dirty reads: In this scenario, T_BuyBook succeeds in setting the new balance to $130. Following this, T_PayUtility reads this balance, and determines that the new balance, with the utility bill added, should be $180. At that point, however, T_BuyBook aborts, reverting the balance to $100. That $130 was dirty data -- that is, data changed by a transaction (T_BuyBook) that had not yet committed. T_PayUtility should not have seen the $130 until T_BuyBook committed. If your credit limit was less than $180, T_PayUtility would fail, even though the actual account balance never reached that amount.
3. Unrepeatable reads: If a transaction reads a value, and then another transaction changes that value, when the first transaction tries to reread that data, it gets a different value, even though it never changes that data item. For instance, if T_BuyBook reads the account balance, and then T_PayUtility changes that balance, T_BuyBook's reread produces a different amount, even though T_BuyBook never changes the data.

You can avoid these anomalies, and ensure consistency, by making concurrently executing transactions appear as if they were executing serially. In other words, from the Jini federation's point of view, transactions might execute concurrently, but from a service's vantage point, transactions should appear to execute one after another, in isolation (the I in ACID). As long as each service ensures transaction isolation, concurrently executing transactions won't threaten data consistency.