CSCE-608 Database Systems
Two-phase locking protocol, transaction ACID properties, lock table, conflict-serializability in database systems, and understanding how to test conflict-serializability. Explore the impact of various factors on transaction ACID and learn about the techniques to ensure database consistency and isolation
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSCE-608 Database Systems Spring 2024 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 38: Two-phase locking protocol
Tranactions Transaction ACID: Atomicity: either all steps of a transaction happen, or none happen Consistency: a transaction transforms a consistent DB into a consistent DB Isolation: execution of a transaction is isolated from that of other transactions Durability: if a transaction commits, its effects persist. T1 Tn What can affect transaction ACID? Accident system failures may destroy Atomicity and Durability, thus Consistency; Concurrent executions of transactions (which is highly desired) may affect Isolation, thus Consistency. Database
lock table DDL DDL language concurrency database file logging & administrator complier control manager recovery transaction manager index/file buffer manager manager query database execution programmer DML (query) DML engine main language complier memory secondary buffers storage DBMS (disks) Graduate Database
Conflict-Serializability (A sufficient condition for serializability) Consider: swap? swap? T1: w1(*)r1(*) swap? r1(*)r1(*) swap? Violate T1 s logic! w1(*)w1(*) r1(*)w1(*) swap? swap? Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write T1, T2: w1(A)r2(B) swap? r1(A)r2(B) swap? w1(A)w2(B) swap? r1(A)w2(B) swap? w1(A)r2(A) swap? r1(A)r2(A) swap? w1(A)w2(A) r1(A)w2(A)
Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Conflict-Serializability (A sufficient condition for serializability) Thus: Swapping two non-conflicting actions gives an equivalent schedule. A schedule S1 is conflict-serializable if it can be converted into a serial schedule by swapping non- conflicting actions. A conflict-serializable schedule is serializable. A serializable schedule may not be conflict-serializable. How do we know if a schedule is conflict-serializable?
Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Testing Conflict-Serializability conflict- serializable Algorithm TestCS. Input: a schedule S 1. Build a directed graph GS; 2. Each transaction is a node in GS; 3. If two actions a1 and a2 conflict, where a1 and a2 are by T1 and T2, resp., and a1 is before a2 in S, then add an edge from T1 to T2 in GS; 4. S is conflict-serializable if and only if GS contains no cycle. S1: r2(A)r1(B)w2(A)r3(A)w1(B)w3(A)r2(B)w2(B) 1 2 3 S2: r2(A)r1(B)w2(A)r2(B)r3(A)w1(B)w3(A)w2(B) 1 2 3 Not conflict- serializable Why does the algorithm work? Claim: If GS is acyclic, then S is equivalent to any serial schedule obtained by topologically sorting GS. Proof. Let T1T2 Tk be a topological order of GS. Since there is no edge into T1, for each action a in T1, there is no action from other transactions that conflict a and appears in S before a. Therefore, the actions of T1 can be all swapped with non-conflict actions and move to the front of the schedule, resulting in an equivalent schedule. Now by induction we can also convert the rest of the schedule into an equivalent serial schedule.
Enforcing Conflict-Serializability Using locking protocol T1 T2 Tn lock table scheduler
Enforcing Conflict-Serializability Using locking protocol T1 T2 Tn lock table scheduler Two new actions: lock: (transaction Ti exclusively locks the element A) unlock: (transaction Ti releases the lock on the element A) li(A) ui(A)
Enforcing Conflict-Serializability Using locking protocol T1 T2 Tn lock table scheduler Two new actions: lock: (transaction Ti exclusively locks the element A) unlock: (transaction Ti releases the lock on the element A) li(A) ui(A) A transaction can lock an unlocked element, and must release (unlock) it later. A transaction cannot access a locked element until it is released by the transaction holding the lock.
A transaction can lock an unlocked element, and must release (unlock) it later. A transaction cannot access a locked element until it is released by the transaction holding the lock. Locking is not enough for conflict-serializability Schedule D A B 25 25 T1 T2 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); Read(A); A A 2; Write(A); Read(B); B B 2; Write(B); 125 250 50 150 250 150
A transaction can lock an unlocked element, and must release (unlock) it later. A transaction cannot access a locked element until it is released by the transaction holding the lock. Locking is not enough for conflict-serializability Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; Write(B); u1(B); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); 125 250 50 150 250 150
A transaction can lock an unlocked element, and must release (unlock) it later. A transaction cannot access a locked element until it is released by the transaction holding the lock. Locking is not enough for conflict-serializability Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; Write(B); u1(B); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); 125 Inconsistent, so isolation was destroyed 250 50 150 250 150
Two phase locking (2PL) (for transactions) Ti: ... li(A) li(B) ui(B) ui(A) ... no unlocks no locks In a transaction, all lockings precede all unlockings
Two phase locking (2PL) (for transactions) Ti: ... li(A) li(B) ui(B) ui(A) ... no unlocks no locks # of locks held by Ti time growing phase shrinking phase In a transaction, all lockings precede all unlockings
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); 125 250 50 l1(B); Read(B); B B+100; Write(B); u1(B); 150 250 150
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); 125 250 50 l1(B); Read(B); B B+100; Write(B); u1(B); 150 250 150 not conflict-serializable even with locks
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); l1(B); Read(B); B B+100; Write(B); u1(B); Try to apply 2PL On the transactions
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); l1(B); Read(B); B B+100; Write(B); u1(B); Try to apply 2PL On the transactions
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); l1(B); Read(B); B B+100; u1(A); Write(B); u1(B); Try to apply 2PL On the transactions
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); l1(B); Read(B); B B+100; u1(A); Write(B); u1(B); Try to apply 2PL On the transactions
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); 125 l1(B); Read(B); B B+100; u1(A); Write(B); u1(B);
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); blocked, so delayed 125 l1(B); Read(B); B B+100; u1(A); Write(B); u1(B);
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); blocked, so delayed 125 Write(B); u1(B);
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); blocked, so delayed 125 Write(B); u1(B);
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); 125 l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); Write(B); u1(B);
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); 125 l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); 250 Write(B); u1(B);
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); 125 l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); 250 Write(B); u1(B); blocked, so delayed
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); Write(B); u1(B); 125 l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); 250 blocked, so delayed
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); Write(B); u1(B); 125 l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); 250 125 blocked, so delayed
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); Write(B); u1(B); 125 l2(A); Read(A); A A 2; Write(A); u2(A); 250 125 l2(B); Read(B); B B 2; Write(B); u2(B); u2(A);
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); Write(B); u1(B); 125 l2(A); Read(A); A A 2; Write(A); u2(A); 250 125 l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); 250 250 250
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); Write(B); u1(B); 125 l2(A); Read(A); A A 2; Write(A); u2(A); 250 125 l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); 250 250 250 This execution of Schedule D is: r1(A)w1(A)r1(B)r2(A)w2(A)w1(B)r2(B)w2(B),
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); Write(B); u1(B); 125 l2(A); Read(A); A A 2; Write(A); u2(A); 250 125 l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); 250 250 250 This execution of Schedule D is: r1(A)w1(A)r1(B)r2(A)w2(A)w1(B)r2(B)w2(B),
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); Write(B); u1(B); 125 l2(A); Read(A); A A 2; Write(A); u2(A); 250 125 l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); 250 250 250 This execution of Schedule D is: r1(A)w1(A)r1(B)r2(A)w2(A)w1(B)r2(B)w2(B), equivalent to the serial schedule: r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B).
Two actions conflict if they are by two transactions on the same element and at least one of the actions is write Why does 2PL work? Theorem. The execution of a 2PL schedule is equivalent to the serial schedule in which transactions are ordered by the time when they start to unlock.
Two actions conflict if they are by two transactions on the same element and at least one of the actions is write Why does 2PL work? Theorem. The execution of a 2PL schedule is equivalent to the serial schedule in which transactions are ordered by the time when they start to unlock. Proof. Let S be a 2PL schedule in which transaction T1 starts its unlocks the latest. Let a be any action of T1. Suppose that there is an action a by another transactions Tkthat conflicts a and appears after a in the schedule S. Thus, S = a a
Two actions conflict if they are by two transactions on the same element and at least one of the actions is write Why does 2PL work? Theorem. The execution of a 2PL schedule is equivalent to the serial schedule in which transactions are ordered by the time when they start to unlock. Proof. Let S be a 2PL schedule in which transaction T1 starts its unlocks the latest. Let a be any action of T1. Suppose that there is an action a by another transactions Tkthat conflicts a and appears after a in the schedule S. Thus, S = a a Since a and a conflict, they are on the same element A. Both T1 and Tk need to lock A before their corresponding actions a and a can be executed. Since a appears in S before a , T1 must lock A before Tkdoes. So the schedule S looks like S = l1(A) a lk (A) a
Two actions conflict if they are by two transactions on the same element and at least one of the actions is write Why does 2PL work? Theorem. The execution of a 2PL schedule is equivalent to the serial schedule in which transactions are ordered by the time when they start to unlock. Proof. Let S be a 2PL schedule in which transaction T1 starts its unlocks the latest. Let a be any action of T1. Suppose that there is an action a by another transactions Tkthat conflicts a and appears after a in the schedule S. Thus, S = a a Since a and a conflict, they are on the same element A. Both T1 and Tk need to lock A before their corresponding actions a and a can be executed. Since a appears in S before a , T1 must lock A before Tkdoes. So the schedule S looks like S = l1(A) a lk (A) a Tk cannot lock A before T1 unlocks A. So S = l1(A) a u1(A) lk (A) a . Since S is 2PL, the first unlock of Tkmust appear after lk (A) , thus after u1(A). But this contradicts the assumption that T1 starts its unlock the latest.
Two actions conflict if they are by two transactions on the same element and at least one of the actions is write Why does 2PL work? Theorem. The execution of a 2PL schedule is equivalent to the serial schedule in which transactions are ordered by the time when they start to unlock. Proof. Let S be a 2PL schedule in which transaction T1 starts its unlocks the latest. Let a be any action of T1. Suppose that there is an action a by another transactions Tkthat conflicts a and appears after a in the schedule S. Thus, S = a a Since a and a conflict, they are on the same element A. Both T1 and Tk need to lock A before their corresponding actions a and a can be executed. Since a appears in S before a , T1 must lock A before Tkdoes. So the schedule S looks like S = l1(A) a lk (A) a Tk cannot lock A before T1 unlocks A. So S = l1(A) a u1(A) lk (A) a . Since S is 2PL, the first unlock of Tkmust appear after lk (A) , thus after u1(A). But this contradicts the assumption that T1 starts its unlock the latest. Thus, in the schedule S, there is no action by transactions other than T1 that conflicts an action of T1 and appears after the conflicting action of T1. So, we can swap the actions in S to move all actions of T1 to the tail of the schedule. The new schedule has a form S1 = 1T1. The new schedule S1 is equivalent to S.
Two actions conflict if they are by two transactions on the same element and at least one of the actions is write Why does 2PL work? Theorem. The execution of a 2PL schedule is equivalent to the serial schedule in which transactions are ordered by the time when they start to unlock. Proof. Let S be a 2PL schedule in which transaction T1 starts its unlocks the latest. Let a be any action of T1. Suppose that there is an action a by another transactions Tkthat conflicts a and appears after a in the schedule S. Thus, S = a a Since a and a conflict, they are on the same element A. Both T1 and Tk need to lock A before their corresponding actions a and a can be executed. Since a appears in S before a , T1 must lock A before Tkdoes. So the schedule S looks like S = l1(A) a lk (A) a Tk cannot lock A before T1 unlocks A. So S = l1(A) a u1(A) lk (A) a . Since S is 2PL, the first unlock of Tkmust appear after lk (A) , thus after u1(A). But this contradicts the assumption that T1 starts its unlock the latest. Thus, in the schedule S, there is no action by transactions other than T1 that conflicts an action of T1 and appears after the conflicting action of T1. So, we can swap the actions in S to move all actions of T1 to the tail of the schedule. The new schedule has a form S1 = 1T1. The new schedule S1 is equivalent to S. Using the same argument, we can move all actions of the transaction T2 that started its unlocks the second latest, to construct a schedule of the form S2 = 2T2T1 that is also equivalent to S. Repeating this process, we will eventually get a serial schedule that is equivalent to S.
Containment Relations Serializable schedules 2PL serial Conflict-serializable schedules Serializable schedule: equivalent to a serial schedule Conflict-serializable schedule: can be swapped into a serial schedule 2PL: transactions locks before any unlock. Serial schedule: transactions are executed one after the other
Containment Relations Serializable schedules 2PL serial Conflict-serializable schedules Serializable schedule: equivalent to a serial schedule Conflict-serializable schedule: can be swapped into a serial schedule 2PL: transactions locks before any unlock. Serial schedule: transactions are executed one after the other
Containment Relations Serializable schedules 2PL serial Conflict-serializable schedules Serializable schedule: equivalent to a serial schedule Conflict-serializable schedule: can be swapped into a serial schedule 2PL: transactions locks before any unlock. Serial schedule: transactions are executed one after the other
Containment Relations Serializable schedules 2PL serial Conflict-serializable schedules Serializable schedule: equivalent to a serial schedule Conflict-serializable schedule: can be swapped into a serial schedule 2PL: transactions locks before any unlock. Serial schedule: transactions are executed one after the other
Containment Relations Serializable schedules 2PL serial Conflict-serializable schedules Serializable schedule: equivalent to a serial schedule Conflict-serializable schedule: can be swapped into a serial schedule 2PL: transactions locks before any unlock. Serial schedule: transactions are executed one after the other
Beyond the simple 2PL protocol, it is all a matter of improving performance and allowing more concurrency .
