6.826—Principles of Computer Systems 2002 Handout 20. Concurrent Transactions 1 20. Concurrent Transactions We often (usually?) want more from a transaction mechanism than atomicity in the presence of failures: we also want atomicity in the presence of concurrency. As we saw in handout 14 on practical concurrency, the reasons for wanting to run transactions concurrently are slow input/output devices (usually disks) and the presence of multiple processors on which different transactions can run at the same time. The latter is especially important because it is a way of taking advantage of multiple processors that doesn’t require any special programming. In a distributed system it is also important because separate nodes need autonomy. Informally, if there are two transactions in progress concurrently (that is, the Begin of one happens after the Begin and before the Commit of the other), we want all the observable effects to be as though all the actions of one transaction happen either before or after all the actions of the other. This is called serializing the two transactions; it is the same as making each transaction into an atomic action. This is good for the usual reason: it allows the clients to reason about each transaction separately as a sequential program. The clients only have to worry about concurrency in between transactions, and they can use the usual method for doing this: find invariants that each transaction establishes when it commits and can therefore assume when it begins. The simplest way for a program to ensure that it doesn’t depend on anything except the invariants is to discard all state at the end of a transaction, and re-read whatever you need after starting the next transaction. Here is the standard example. We are maintaining bank balances, with deposit, withdraw, and balance transactions. The first two involve reading the current balance, adding or subtracting something, making a test, and perhaps writing the new balance back. If the read and write are the largest atomic actions, then the sequence read1, read2, write1, write2 will result in losing the effect of transaction 1. The third reads lots of balances and expects their total to be a constant. If its reads are interleaved with the writes of the other transactions, it may get the wrong total. The other property we want is that if one transaction precedes another (that is, its Commit happens before the Begin of the other, so that their execution does not overlap) then it is serialized first. This is sometimes called external consistency; it’s not just a picky detail that only a theoretician would worry about, because it’s needed to ensure that when you put two transaction systems together you still get a serializable system. A piece of jargon you will sometimes see is that transactions have the ACID properties: Atomic, Consistent, Isolated, and Durable. Here are the definitions given in Gray and Reuter: Atomicity. A transaction’s changes to the state are atomic: either all happen or none happen. These changes include database changes, messages, and actions on transducers. Consistency. A transaction is a correct transformation of the state. The actions taken as a group do not violate any of the integrity constraints associated with the state. This requires that the transaction be a correct program. 6.826—Principles of Computer Systems 2002 Handout 20. Concurrent Transactions 2 Isolation. Even though transactions execute concurrently, it appears to each transaction T that others executed either before T or after T, but not both. Durability. Once a transaction completes successfully (commits), its changes to the state survive failures. The first three appear to be different ways of saying that all transactions are serializable. Many systems implement something weaker than serializability for committed transactions in order to allow more concurrency. The standard terminology for weaker degrees of isolation is degree 0 through degree 3, which is serializability. Gray and Reuter discuss the specs, code, advantages, and drawbacks of weaker isolation in detail (section 7.6, pages 397-419). We give a spec for concurrent transactions. Coding this spec is called ‘concurrency control’, and we briefly discuss a number of coding techniques. Spec The spec is written in terms of the histories of the transactions: a history is a sequence of (action, result) pairs, called events below. The order of the events for a single transaction is fixed: it is the order in which the transaction did the actions. A spec must say that for all the committed transactions there is a total ordering of all the events in the committed transactions that has three properties: Serializable: Doing the actions in the total order (starting from the initial state) would yield the same result from each action, and the same final state, as the results and final state actually obtained. Externally consistent: The total order is consistent with the partial order established by the Begin’s and Commit’s. Non-blocking: it’s always possible to abort a transaction. This is necessary because when there’s a crash all the active transactions must abort. This is all that most transaction specs say. It allows anything to happen for uncommitted transactions. Operationally, this means that an uncommitted transaction will have to abort if it has seen a result that isn’t consistent with any ordering of it and the committed transactions. It also means that the programmer has to expect completely arbitrary results to come back from the actions. In theory this is OK, since a transaction that gets bad results will not commit, and hence nothing that it does can affect the rest of the world. But in practice this is not very satisfactory, since programs that get crazy results may loop, crash, or otherwise behave badly in ways that are beyond the scope of the transaction system to control. So our spec imposes some constraints on how actions can behave even before they commit. The spec works by keeping track of: • The ordering requirements imposed by external consistency, in a relation xc. • The histories of the transactions, in a map y.6.826—Principles of Computer Systems 2002 Handout 20. Concurrent Transactions 3 It imposes an invariant on xc and y that is defined by the function Invariant. This function says that the committed transactions have to be serializable in a way consistent with xc, and that something