95-702 Transactions 1 95-702 Distributed Systems Transactions and Concurrency Control Transaction Notes mainly from Coulouris Distributed Transactions Notes adapted from Tanenbaum’s “Distributed Systems Principles and Paradigms”Transactions • A transaction is specified by a client as a set of operations on objects to be performed as an indivisible unit by the servers managing those objects. • The servers must guarantee that either the entire transaction is carried out and the results recorded in permanent storage or, in the case that one or more of them crashes, its effects are completely erased. 95-702 Transactions 295-702 Transactions 3 95-702 Transactions 3 95-702 Transactions 3 Transactions (ACID) • Atomic: All or nothing. No intermediate states are visible. • 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. • Isolated: Two transactions do not interfere with each other. They appear as serial executions. • Durable: The commit causes a permanent change.Recall 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 Transactions 4 If one thread invokes a method it acquires a lock. Another thread will be blocked until the lock is released. These operations are atomic. This is all that is required for many applications.Communicating Threads Consider a shared queue and two operations: synchronized first() { removes from front } synchronized append() { adds to rear } Is this sufficient? No. If the queue is empty the client of first() will have to poll on the method. It is also potentially unfair. 95-702 Transactions 5Communicating Threads Consider again the shared queue and two operations: synchronized first() { if queue is empty call wait() remove from front } synchronized append() { adds to rear call notify() } 95-702 Transactions 6 When threads can synchronize their actions on an object by means of wait and notify, the server holds on to requests that cannot immediately be satisfied and the client waits for a reply until another client has produced whatever they need. Note that both methods are synchronized. Only one thread at a time is allowed in. This is general. It can get tricky fast.Back to Transactions • A client may require that a sequence of separate requests to a single server be atomic. - Free from interference from other concurrent clients. - Either all of the operations complete successfully or they have no effect at all in the presence of server crashes. 95-702 Transactions 7Assume Each Operation Is Synchronized Client 1 Transaction T; a.withdraw(100); b.deposit(100); c.withdraw(200); b.deposit(200); 95-702 Transactions 8 Client 2 Transaction W; total = a.getBalance(); total = total + b.getBalance(); total = total + c.getBalance(); Are we OK?Assume Each Operation Is Synchronized Client 1 Transaction T; a.withdraw(100); b.deposit(100); c.withdraw(200); b.deposit(200); 95-702 Transactions 9 Client 2 Transaction W; total = a.getBalance(); total = total + b.getBalance(); total = total + c.getBalance(); Inconsistent retrieval!Assume Each Operation Is Synchronized Client 1 Transaction T; bal = b.getBalance(); b.setBalance(bal*1.1); 95-702 Transactions 10 Client 2 Transaction W; bal = b.getBalance(); b.setBalance(bal*1.1); Are we OK?Assume Each Operation Is Synchronized Client 1 Transaction T; bal = b.getBalance() b.setBalance(bal*1.1); 95-702 Transactions 11 Client 2 Transaction W; bal = b.getBalance(); b.setBalance(bal*1.1); Lost Update!Assume Each Operation Is Synchronized Transaction T; a.withdraw(100); b.deposit(100); c.withdraw(200); b.deposit(200); 95-702 Transactions 12 The aim of any server that supports transactions is to maximize concurrency. So, transactions are allowed to execute concurrently if they would have the same effect as serial execution. Each transaction is created and managed by a coordinator.Example Transaction T tid = openTransaction(); a.withdraw(tid,100); b.deposit(tid,100); c.withdraw(tid,200); b.deposit(tid,200); closeTransaction(tid) or abortTransaction(tid) 95-702 Transactions 13 Coordinator Interface: openTransaction() -> transID closeTransaction(transID) -> commit or abort abortTransaction(TransID)Transaction Life Histories 95-702 Transactions 14 Successful Client Aborts Server Aborts openTransaction openTransaction openTransaction operation operation operation operation operation operation : : : operation operation : closeTransaction abortTransaction closeTransaction returns an abort from server95-702 Transactions 15!Locks • A lock is a variable associated with a data item and describes the status of that item with respect to possible operations that can be applied to that item. • Generally, there is one lock for each item. • Locks provide a means of synchronizing the access by concurrent transactions to the items. • The server sets a lock, labeled with the transaction identifier, on each object just before it is accessed and removes these locks when the transaction has completed. Two types of locks are used: read locks and write locks. Two transactions may share a read lock. This is called two phase locking.95-702 Transactions 16 Example: Binary Lock (1) Lock_Item(x) B: if(Lock(x) == 0) Lock(x) = 1 else { wait until Lock(x) == 0 and we are woken up. GOTO B } Now, a transaction is free to use x. Not interleaved with other code until this terminates or waits. In java, this would be a synchronized method.95-702 Transactions 17 Master of Information System Management Example: Binary Lock(2) The transaction is done using x. Unlock_Item(x) Lock(x) = 0 if any transactions are waiting then wake up one of the waiting transactions. Not interleaved with other code. If this were java, this method would be synchronized.95-702 Transactions 18 Master of Information System Management Locks Are Often Used To Support
View Full Document
Unlocking...