95-702 Distributed Systems An introduction to Transaction Processing (TP) and the Two Phase Commit ProtocolTransaction Processing (TP) SystemsTP System ArchitectureTransactions (ACID)Review the Synchronized KeywordReview Communicating Threads (1)Review Communicating Threads (2)Back to TransactionsAssume Each Operation Is SynchronizedSlide 10Slide 11Slide 12Slide 13Interacting with a coordinatorTransaction Life HistoriesLocking to Attain SerializabilityWhat might Lock_Item() look like?And unlock_item() ?Slide 19Locks May Lead to DeadlockDeadlockDistributed TransactionsPowerPoint PresentationSlide 24Participants Talk to CoordinatorSuppose All Goes Well (1)Suppose All Goes Well (2)This Time No Cars Available (1)This Time No Cars Available (2)This Time No Cars Available (3)Slide 31Slide 32Slide 33Two-Phase Commit ProtocolTwo-Phase Commit Protocol2PC Finite State Machine from Tanenbaum2PC Blocks in Three PlacesSlide 38Slide 39Slide 40Slide 41Slide 42Slide 4395-702 Transactions195-702 Distributed SystemsAn introduction to Transaction Processing (TP) and the Two Phase Commit Protocol Notes adapted from: Coulouris: Distributed Transactions,Tanenbaum’s “Distributed Systems Principles and Paradigms” andBernstein and Newcomer: Principles of Transaction ProcessingTransaction Processing (TP) Systems •One of the first was American Airlines SABRE – 83,000 transactions per day•Became IBM’s Airline Control Program•Became IBM’s Transaction Processing Facility (TPF)•Many such systems exist:•Oracle Tuxedo (Thousands of transactions per second)•IBM’s Customer Information Control System (CICS)•Most databases and messaging systems provide for transactional support•JEE and Microsoft .NET both provide extensive capabilities for creating and deploying TP applications95-702 Transactions2TP System ArchitectureAdapted From "Principles Of Transaction Processing" Bernstein and Newcomer3User deviceFront end Program takes requests from the user deviceFront end Program takes requests from the user deviceRequest Controllerselects the proper transaction to runRequest Controllerselects the proper transaction to runThe Transaction Server executes the required activitiesThe Transaction Server executes the required activitiesDatabaseDatabase95-702 Transactions495-702 Transactions495-702 Transactions4Transactions (ACID)•Atomic: All or nothing. No intermediate states are visible. No possibility that only part of the transaction ran. If a transaction fails prior to committing, the TP system will undo the effects of any updates. We either commit or abort the entire process. Logging can be used to ensure a transaction is atomic with respect to failures.•Consistent: system invariants preserved, e.g., if there were n dollars in a bank before a transfer transaction then there will be n dollars in the bank after the transfer. This is largely in the hands of the application programmer.•Isolated: Two transactions do not interfere with each other. They appear as serial executions. This is the case even though transactions may run concurrently. Locking is often used to prevent one transaction from interfering with another.•Durable: The commit causes a permanent change to stable storage. This property may be obtained with log-based recovery algorithms. If there has been a commit but updates have not yet been completed due to a crash, the logs will hold the necessary information on recovery.Review the Synchronized Keyword private double balance; public synchronized void deposit(double amount) throws RemoteException { add amount to the balance } public synchronized void withdraw(double amount) throws RemoteException { subtract amount from the balance }95-702 Transactions5If one thread invokesa method it acquires a lock. Another threadwill be blocked untilthe lock is released. This is all that is required for many applications. ButTP middleware must do much more.Review Communicating Threads (1)Consider a shared queue and twooperations: synchronized first() { removes from front } synchronized append() { adds to rear } Is this sufficient? No. If the queue is empty the client of first() willhave to poll on the method.It is also potentially unfair. Why?95-702 Transactions6Review Communicating Threads (2)Consider again the shared queue and twooperations: synchronized first() { if queue is empty call wait() remove from front } synchronized append() { adds to rear call notify() } 95-702 Transactions7When threads can synchronizetheir actions on an object by meansof wait and notify, the server holdson to requests that cannot immediately be satisfied and theclient waits for a reply untilanother client has produced whatever they need.Note that both methods are synchronized. Only one thread ata time is allowed in. This is a simple example. It gets real tricky fast.Back to Transactions•A client may require that a sequence of separate requests to a single server be isolated and atomic. - Isolated => Free from interference from other concurrent clients. Serializable. - Atomic => Either all of the operations complete successfully or they have no effect at all in the presence of server crashes. 95-702 Transactions8Assume Each Operation Is SynchronizedClient 1 Transaction T;a.withdraw(100);b.deposit(100);c.withdraw(200);b.deposit(200);95-702 Transactions9Client 2 Transaction W;total = a.getBalance();total = total + b.getBalance();total = total + c.getBalance();Are we isolated?Suppose both run to completion (no partial execution)=> atomic.Assume Each Operation Is SynchronizedClient 1 Transaction T;a.withdraw(100);b.deposit(100);c.withdraw(200);b.deposit(200);95-702 Transactions10Client 2 Transaction W;total = a.getBalance();total = total + b.getBalance();total = total + c.getBalance();Inconsistent retrieval!Assume Each Operation Is SynchronizedClient 1 Transaction T;bal = b.getBalance(); b.setBalance(bal*1.1);95-702 Transactions11Client 2 Transaction W;bal = b.getBalance();b.setBalance(bal*1.1);But are we isolated?Suppose both run to completion with no partial execution => Atomic.Assume Each Operation Is SynchronizedClient 1 Transaction T;bal = b.getBalance()b.setBalance(bal*1.1);95-702 Transactions12Client 2 Transaction W;bal = b.getBalance();b.setBalance(bal*1.1);Lost Update!Assume Each Operation Is SynchronizedTransaction
View Full Document
Unlocking...