Seite 2
Transaction • Programming abstraction • Implement real-world transactions – Banking transaction – Airline reservation 2
Seite 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
Seite 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
Seite 7
Context • We have seen: – Ensure atomicity in presence of failures • Next: – Ensure Isolation during concurrency 7
Seite 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
Seite 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
Seite 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
Seite 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
Seite 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
Seite 14
Problems • Which schedules are “correct”? – Mathematical characterization • How to build a system that allows only “correct” schedules? – Efficient procedure to enforce correctness 14
Seite 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
Seite 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
Seite 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
Seite 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
Seite 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
Die ersten 20 Seiten werden angezeigt. Laden Sie das Dokument herunter, um alles zu sehen.
Kommentare (0)
Noch keine Kommentare. Seien Sie der Erste!