Trang 2
Transaction • Programming abstraction • Implement real-world transactions – Banking transaction – Airline reservation 2
Trang 4
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
Trang 6
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
Trang 7
Context • We have seen: – Ensure atomicity in presence of failures • Next: – Ensure Isolation during concurrency 7
Trang 8
Issues with Concurrency: Example Bank database: 3 Accounts A = 500 Account B = 500 Balances C = 500 Property: A + B + C = 1500 Money does not leave the system 8
Trang 9
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
Trang 10
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
Trang 11
Transaction T1 Transaction T2 A B C Read (A, t) 500 500 500 t = t - 100 Read (A, s) s = s - 100 Write (A, s) 400 500 500 Write (A, t) 400 500 500 Read (B, t) t = t + 100 Write (B, t) 400 600 500 Read (C, s) s = s + 100 Write (C, s) 400 600 600 400 + 600 + 600 = 1600
Trang 12
Transaction T1 Transaction T2 A B C Read (A, t) 500 500 500 t = t - 100 Write (A, t) 400 500 500 Read (A, s) s = s - 100 Write (A, s) 300 500 500 Read (B, t) t = t + 100 Write (B, t) 300 600 500 Read (C, s) s = s + 100 Write (C, s) 300 600 600 300 + 600 + 600 = 1500
Trang 14
Problems • Which schedules are “correct”? – Mathematical characterization • How to build a system that allows only “correct” schedules? – Efficient procedure to enforce correctness 14
Trang 15
Correct Schedules: Serializability • Initial database state is consistent • Transaction: – consistent state → consistent state • Serial execution of transactions: – Initial state → consistent state • Serializable schedule: – A schedule equivalent to a serial schedule – Always “correct” 15
Trang 16
Serial Schedule A B C Read (A, t) 500 500 500 t = t - 100 T1 Write (A, t) Read (B, t) t = t + 100 Write (B, t) 400 600 500 Read (A, s) s = s - 100 Write (A, s) T2 Read (C, s) s = s + 100 Write (C, s) 300 600 600 300 + 600 + 600 = 1500
Trang 17
Serial Schedule A B C Read (A, s) 500 500 500 s = s - 100 Write (A, s) T2 Read (C, s) s = s + 100 Write (C, s) 400 500 600 Read (A, t) t = t - 100 Write (A, t) T1 Read (B, t) t = t + 100 Write (B, t) 300 600 600 300 + 600 + 600 = 1500
Trang 19
Is this Serializable? 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) Transaction T1 Transaction T2
Trang 20
Equivalent Serial Schedule Read (A, t) t = t - 100 Write (A, t) Read (B, t) t = t + 100 Write (B, t) Read (A, s) s = s - 100 Write (A, s) Read (C, s) s = s + 100 Write (C, s) Transaction T1 Transaction T2
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!