Computer Science 425 Distributed SystemsAcknowledgementAdministrativeExample TransactionTransactionTransaction Failure ModesProperties of Transactions (ACID)Bank Server: Coordinator InterfaceBank Server: Account, Branch interfacesACID - IsolationConcurrent Transactions: Lost Update ProblemConc. Trans.: Inconsistent Retrieval Prob.Concurrency Control: “Serial Equivalence”Slide 14Conflicting OperationsRead and Write Operation Conflict RulesConflicting Operators ExampleInconsistent Retrievals ProblemA Serially Equivalent Interleaving of V and WSlide 20A Dirty Read When Transaction T AbortsHow to avoid dirty readsPremature WritesSlide 24Example Transaction – Need Concurrency ControlTransaction Processing SystemsSummaryComputer Science 425Distributed SystemsComputer Science 425Distributed SystemsLecture 21Transaction Processing and Concurrency ControlReading: Sections 13.1-13.2AcknowledgementAcknowledgement•The slides during this semester are based on ideas and material from the following sources: –Slides prepared by Professors M. Harandi, J. Hou, I. Gupta, N. Vaidya, Y-Ch. Hu, S. Mitra. –Slides from Professor S. Gosh’s course at University o Iowa.Administrative Administrative •MP2 posted October 5, 2009, on the course website, –Deadline November 6 (Friday)–Demonstration, 4-6pm, 11/6/2009 –Sign Up for demonstrations – Friday 4-6pm in 216 SCBanking transaction for a customer (ATM)Transfer $100 from saving to checking account;Transfer $200 from money-market to checking account;Withdraw $400 from checking account.Transaction:1. savings.deduct(100) /* includes verification */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. commit Example TransactionExample TransactionClientServerTransactionTransaction Transaction Sequence of operations that forms a single step, transforming the server data from one consistent state to another. All or nothing principle: a transaction either completes successfully, 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/states Free from interference by other operationsBut… Transactions could run concurrently Transactions may be distributedTransaction:1. savings.deduct(100) 2. checking.add(100) 3. mnymkt.deduct(200) 4. checking.add(200) 5. checking.deduct(400) 6. dispense(400)7. commit Transaction Failure Modes Transaction Failure Modes A failure at these points means the customer loses money; we need to restoreA failure at these points does not cause lost money, but the transaction cannot be repeatedThis is the point of no returnA failure after the commit point (ATM crashes) needs corrective action; no undoing possible.Properties of Transactions (ACID) Properties of Transactions (ACID) Atomicity: All or nothing Consistency: starting in a consistent state, the transaction ends 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 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: Coordinator InterfaceBank Server: Coordinator InterfaceTransactions 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 transaction.closeTransaction(trans) -> (commit, abort);ends a transaction: a commit return value indicates that the transaction has committed; an abort return value indicates that it has aborted.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 objects.Transactions can be implemented using RPCs/RMIs!Bank Server: Account, Branch interfacesBank Server: Account, Branch interfacesdeposit(amount)deposit amount in the accountwithdraw(amount)withdraw amount from the accountgetBalance() -> amountreturn the balance of the accountsetBalance(amount)set the balance of the account to amountcreate(name) -> accountcreate a new account with a given namelookup(name) -> account return a reference to the account with the given name branchTotal() -> amountreturn the total of all the balances at the branchOperations of the Branch interfaceOperations of the Account interfaceACID - IsolationACID - IsolationConcurrent Transactions: Lost Update ProblemConcurrent Transactions: Lost Update Problem One transaction causes loss of info. for another: consider three account objects Transaction T1 Transaction T2 balance = b.getBalance() balance = b.getBalance() b.setBalance(balance*1.1)b.setBalance = (balance*1.1)a.withdraw(balance* 0.1) c.withdraw(balance*0.1)T1/T2’s update on the shared object, “b”, is lost100200 300a:b: c:280c:80a:220b:220b:Conc. Trans.: Inconsistent Retrieval Prob.Conc. Trans.: Inconsistent Retrieval Prob. Partial, incomplete results of one transaction are retrieved by another transaction. Transaction T1 Transaction T2 a.withdraw(100) total = a.getBalance() total = total + b.getBalanceb.deposit(100) total = total + c.getBalance T1’s partial result is used by T2, giving the wrong result1002000.00a:b: 00a:500200300c:total300b: 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 (in some order). Transaction T1 Transaction T2 balance = b.getBalance()b.setBalance = (balance*1.1) balance = b.getBalance() b.setBalance(balance*1.1)a.withdraw(balance* 0.1) c.withdraw(balance*0.1) Concurrency
View Full Document
Unlocking...