Data-Intensive Computing Systems Concurrency Control Shivnath Babu 1 Transaction Programming abstraction Implement real-world transactions Banking transaction Airline reservation 2 Transaction: Programmer’s Role Transaction Consistent State Consistent State 3 Transaction: System’s Role Atomicity All changes of the transaction recorded or none at all Durability All future transactions see the changes made by this transaction if it completes Isolation Net effect as if the transaction executed in isolation 4 Transaction: States Abort Begin Run Commit 5 Transactions Historical note: Turing Award for Transaction concept Jim Gray (1998) Interesting reading: Transaction Concept: Virtues and Limitations by Jim Gray http://www.hpl.hp.com/techreports/tandem/TR-81.3.pdf 6 Context We have seen: Ensure atomicity in presence of failures Next: Ensure Isolation during concurrency 7 Issues with Concurrency: Example Bank database: 3 Accounts A = 500 Account Balances B = 500 C = 500 Property: A + B + C = 1500 Money does not leave the system 8 Issues with Concurrency: Example Transaction T1: Transfer 100 from A to B A = 500, B = 500, C = 500 Read (A, t) t = t - 100 Write (A, t) Read (B, t) t = t + 100 Write (B, t) A = 400, B = 600, C = 500 9 Issues with Concurrency: Example Transaction T2: Transfer 100 from A to C Read (A, s) s = s - 100 Write (A, s) Read (C, s) s = s + 100 Write (C, s) 10 Transaction T1 Transaction T2 Read (A, t) t = t - 100 Read (A, s) s = s - 100 Write (A, s) Write (A, t) Read (B, t) t = t + 100 Write (B, t) Read (C, s) s = s + 100 Write (C, s) A B C 500 500 500 400 500 500 400 500 500 400 600 500 400 600 600 400 + 600 + 600 = 1600 Transaction T1 Transaction T2 Read (A, t) t = t - 100 Write (A, t) Read (A, s) s = s - 100 Write (A, s) Read (B, t) t = t + 100 Write (B, t) Read (C, s) s = s + 100 Write (C, s) A B C 500 500 500 400 500 500 300 500 500 3