Computer ScienceComputer Science 425Distributed SystemsLecture 21Transaction Processing andTransaction Processing and Concurrency ControlRdi Sti 13113 2Reading: Sections 13.1-13.2Acknowledgement• The slides during this semester are based on gideas and material from the following sources: – Slides prepared by Professors M. Harandi, J. Hou, I. Gupta, N. Vaidya, Y-Ch. Hu, S. Mitra.Vaidya, YCh. Hu, S. Mitra. – Slides from Professor S. Gosh’s course at University o Iowa.Administrative MP2 t d O t b 5 2009 th•MP2 posted October 5, 2009, on the course website, Ddli N b 6(Fid)–Deadline November 6 (Friday)– Demonstration, 4-6pm, 11/6/2009 Si U f d iFid 46 i 216–Sign Up for demonstrations –Friday 4-6pm in 216 SCExample TransactionClientServerTransactionBanking transaction for a customer (ATM)Transfer $100 from saving to checking account;ggTransfer $200 from money-market to checking account;Withdraw $400 from checking account.Transaction:1. savings.deduct(100)/* includes verification */g()2. checking.add(100) /* depends on success of 1 */3. mnymkt.deduct(200) /* includes verification */4. checking.add(200) /* depends on success of 3 */5. checking.deduct(400) /* includes verification */6. dispense(400)7. commitTransaction Sequence of operations that forms a single step, transforming the server data from one consistent tt t thstate to another. All or nothing principle: a transaction either completes successfully, and the effects are recorded in the objects, or it hassuccessfully, and the effects are recorded in the objects, or it has no effect at all. (multiple clients, or crashes)Transactions’ operations are indivisible (atomic) from the point of view of other transactions No access to intermediate results/statesFree from interference by other operationsFree from interference by other operationsBut… Tti ldtlTransactions could run concurrently Transactions may be distributedTransaction Failure ModesTransaction:1. savings.deduct(100)Af il tg()2. checking.add(100)3. mnymkt.deduct(200)A failure at these points means the c stomer losesA failure at these points does not cause lost money but4. checking.add(200)5. checking.deduct(400)customer loses money; we need to restorelost money, but the transaction cannot be repeated6. dispense(400)7. commitA fail re after theThis is the point of no returnA failure after the commit point (ATM crashes) needs correctiveneeds corrective action; no undoing possible.Properties of Transactions (ACID) Atomicity: All or nothing Consistency: starting in a consistent state, the transaction ends in a consistent stateends in a consistent state. Isolation: Each transaction must be performed without interference from other transactions, i.e., the non-final effects ,,of a transaction must not be visible to other transactions.Durability: After a transaction has completed successfully, all its effects are saved in permanent storageits effects are saved in permanent storage.Data saved in a file will survive if the server process crashes.“To support failure atomicity and durability, objects must be recoverable”Atomicity: store tentative object updates (for later undo/redo))Durability: store entire results of transactions (all updated objects) to recover from permanent server crashes.Bank Server: CoordinatorInterfaceTransactions can be implemented using RPCs/RMIs!Transactions are managed by a coordinator:openTransaction() -> trans;starts a new transaction and delivers a unique transaction identifier (TID) trans. This TID will be used in the other operations in the ()ptransaction.closeTransaction(trans) -> (commit, abort);ends a transaction: acommitreturn value indicates that theends a transaction: a commitreturn value indicates that the transaction has committed; an abort return value indicates that it has aborted.abortTransaction(trans);abortTransaction(trans);aborts the transaction. TID can be passed implicitly (for other operations between open and close) with CORBATransactions are achieved by cooperation between client process the server the coordinator and recoverable objectsprocess, the server, the coordinator, and recoverable objects.Bank Server: Account, Branchinterfacesdeposit(amount)Operations of the Account interfacedeposit amount in the accountwithdraw(amount)withdraw amount from the accountBl ()getBalance() -> amountreturn the balance of the accountsetBalance(amount)tth b l fth tt tset the balance of the account to amountOperations of the Branch interfacecreate(name) -> accountcreate a new account with a given namelookup(name) -> accountreturn a reference to the account with the given namebranchTotal() -> amounthlfllhbl hbhreturn the total of all the balances at the branchACID-IsolationACID IsolationConcurrent Transactions: Lost Update Problem One transaction causes loss of info. for another: consider three account objectsjTransaction T1Transaction T2100200 300a:b: c:Transaction T1Transaction T2 balance = b.getBalance()balance = b.getBalance()b.setBalance(balance*1.1)220b:b.setBalance = (balance*1.1)a.withdraw(balance* 0.1)ithd (b l *0 1)80a:220b:c.withdraw(balance*0.1)T1/T2’s update on the shared object, “b”, is lost280c:Conc. Trans.: Inconsistent Retrieval Prob. Partial, incomplete results of one transaction are retrieved by another transaction.Transaction T1Transaction T2100200a:b:300c:Transaction T1Transaction T2 a.withdraw(100)00000a:totaltotal = a.getBalance()total = total + b.getBalanceb deposit(100)0.00200300b:b.deposit(100) total = total + c.getBalance500300b:T1’s partial result is used by T2, giving the wrong resultConcurrency Control: “Serial Equivalence” An interleaving of the operations of 2 or more transactions is said to be serially equivalent if the combined effect is the same as if these transactions had been performed sequentially (inas if these transactions had been performed sequentially (in some order).100200300a:b:c:Transaction T1 Transaction T2 100200300a:b:c:balance = b.getBalance()b.setBalance = (balance*1.1)b:220== T1 (complete) followedby T2 (complete)balance = b.getBalance()b.setBalance(balance*1.1)242b:a.withdraw(balance* 0.1)c.withdraw(balance*0.1)278c:a:80Concurrency Control: “Serial Equivalence” An interleaving of the operations of 2 or more transactions is said to be serially equivalent if the combined effect is the same as if these transactions had been performed sequentially (inas if these transactions had been
View Full Document
Unlocking...