Transactions Transactions Example Example transaction Committing and Aborting ACID Atomicity Consistency Isolation Isolation Durability Common problems in transaction processing Lost updates Lost updates Inconsistent retrievals Inconsistent retrievals Serial equivalence Conflicting operations Conflicting operations Locking Locking example Locking Locking Locks Deadlocks Deadlock example Preventing deadlock Detecting deadlock Distributed Transactions Nested transactions Nested transactions Committing in nested transactions Flat and Nested Distributed transactions Coordinators Two-phase commit Two-phase commit Two-phase commit Two-phase commit Two-phase commit Two-phase commit Two-phase commit Nested two-phase commit Failure in Two-phase commit Locking and Deadlock Distributed Deadlock Edge chasing Edge chasing Edge Chasing Example Edge Chasing Example Edge Chasing Example Edge Chasing Example Breaking deadlock SummaryDistributed Software DevelopmentDistributed TransactionsChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment of Computer Science — University of San Francisco – p. 1/??Transactions•Features of transactions•Serial equivalence•Locking and deadlock•Distributed transactions•Two-phase commit•Distributed deadlockDepartment of Computer Science — University of San Francisco – p. 2/??Transactions•A transaction is a sequence of operations between aclient and a server.•Goal: make sure that:•Objects remain in a consistent state•System is tolerant to crash failures•Transaction effects are independent of othertransactions•Transactions are either completed or not started.Department of Computer Science — University of San FranciscoExample•As an example, we’ll look at an interface to a bankingsystem.•We’d like to be able to do the following operations onaccounts:•deposit(amt)•withdraw(amt)•getBalance()•setBalance(amt)•We’d also like the following operations to be availablefor branches:•CreateAccount(name)•lookUpAccount(name)•totalAccounts()Department of Computer Science — University of San Francisco – p. 4/??Example transaction•A transaction may involve several operations, each ofwhich changes the state of a different object:•Transaction T:1. alexAcct.withdraw(100)2. nancyAcct.deposit(100)3. nancyAcct.widthdraw(200)4. brooksAcct.deposit(200)•We can’t stop in the middle, lose any of theoperations, or do them in the wrong order.Department of Computer Science — University of San Francisco – p. 5/??Committing and Aborting•A transaction may be either committed or aborted.•When all operations are complete and the transactionis ready to be accepted, it is committed.•Written to permanent storage•After this point, it cannot be undone•If the server decided that a transaction cannot beprocessed (undone by the client, or it will leave thesystem in an inconsistent state), it is aborted.•All operations are undoneDepartment of Computer Science — University of San FranciscoACID•The desirable features of a transactional DBMS aresometimes referred to as ACID•Atomicity•Consistency•Isolation•DurabilityDepartment of Computer Science — University of San Francisco – p. 7/??Atomicity•Atomicity is sometimes referred to as “all-or-nothing”.•Either a transaction completes successfully, and alleffects are applied to all objects, or it has no effect atall.•Either all withdraws and deposits are made, or noneof them are.Department of Computer Science — University of San Francisco – p. 8/??Consistenc•A transaction must move the system from consistentstate to consistent state.•For example, the sum of all the accountBalancesmust always be equal to the branch’s totalAccounts•Depending on the application, at database may haveother constraints•No negative balances on an account•No post-dated transactions•If the system is in an inconsistent state after atransaction, the transaction must be undone, so as torestore consistency.Department of Computer Science — University of San FranciscoIsolation•The intermediate effects of a transaction must not bevisible to other transactions.•In our example, Nancy’s bank account balancebriefly went up by $100. (the money was thentransferred to Brooks’ account)•No other process or transaction should see thatbalance.•In other words, to the outside world, a transactionmust appear as a single operation.Department of Computer Science — University of San Francisco – p. 10/??Isolation•How to provide isolation?•Perform all transactions in a single thread•Works, but doesn’t scale.•Use locks to control concurrent access.•Better, although now we need to detect (and undo)deadlocks.Department of Computer Science — University of San Francisco – p. 11/??Durability•After a transaction has been processed, its effectsare saved to permanent storage.•The transaction will never be undone or lost, even inthe presence of a server crash.•This typically also requires some guarantees aboutthe nature of the permanent storage.Department of Computer Science — University of San FranciscoCommon problems in transactionprocessing•If we assume that a server will process multipletransaction simultaneously (in separate threads),problems can occur.•Lost updates•Inconsistent retrievalsDepartment of Computer Science — University of San Francisco – p. 13/??Lost updates•’Lost updates’ refer to the problem of one transactionoverwriting the result of another transaction.•For example:•Consider transactions T and U. T wants to transfer 10% of the balance in accountB from A to B. U wants to transfer 10% of the balance in account B from C to B. Bstarts at $200.•Transaction T:•balance1 = B.getBalance()•B.setBalance(balance1 * 1.1)•A.withdraw(balance1 / 10)•Transaction U:•balance2 = B.getBalance()•B.setBalance(balance2 * 1.1)•C.withdraw(balance1 / 10)Department of Computer Science — University of San Francisco – p. 14/??Lost updates•At the end, the balance in account B should be $242.•But what if the operations happen in this order:•(T) = balance1 = B.getBalance() ($200)•(U) = balance2 = B.getBalance() ($200)•(U) = b.setBalance(balance2 * 1.1)($220)•(T) = b.setBalance(balance1 * 1.1)($220)•(T) = A.withdraw(balance1 / 10)•(U) = C.withdraw(balance2 / 10)•We lose one of the updates, due to the fact that thesecond setBalance is working with stale data.Department of Computer Science
View Full Document
Unlocking...