Database Management Systems - Chapter 6. Concurrency Control Techniques - Võ Thị Ngọc Châu

Nội dung text: Database Management Systems - Chapter 6. Concurrency Control Techniques - Võ Thị Ngọc Châu

1. 6.2. Two-Phase Locking Figure 21.2 Locking and unlocking operations for two-mode (read-write or shared-exclusive) locks. [1], pp. 785. 14
2. 6.2. Two-Phase Locking Figure 21.2 Locking and unlocking operations for two-mode (read-write or shared-exclusive) locks. [1], pp. 785. 16
3. 6.2. Two-Phase Locking Conversion of locks  A transaction that already holds a lock on item X is allowed under certain conditions to convert the lock from one locked state to another.  Upgrade: read_lock(X) write_lock(X) None of other transactions holds a lock on X.  Downgrade: write_lock(X) read_lock(X)  When upgrading and downgrading of locks is used, the lock table must include transaction identifiers in the record structure for each lock to store the information on which transactions hold locks on the item. 18
4. 6.2. Two-Phase Locking Two-phase locking techniques: essential components  Lock Manager: Managing locks on data items.  Lock Table: a table that stores the identity of transaction locking (the data item, lock mode and pointer to the next data item locked). One simple way to implement a lock table is through linked lists. Transaction ID Data item id lock mode Ptr to next data item T1 X1 Read Next 20
5. 6.2. Two-Phase Locking 22
6. 6.2. Two-Phase Locking Variations of two-phase locking (2PL)  Basic 2PL  Conservative 2PL (static 2PL) A transaction locks all the items it accesses before the transaction begin execution, by predeclaring its read-set and write-set. If any of the predeclared items needed cannot be locked, the transaction does not lock any item. This is a deadlock-free protocol.  Strict 2PL A transaction T does not release any of its exclusive (write) locks until after it commits or aborts. Hence, no other transaction can read or write an item that is written by T unless T has committed, leading to a strict schedule for recoverability. This is not deadlock-free.  Rigorous 2PL A transaction T does not release any of its locks (exclusive or shared) until after it commits or aborts, leading to a strict schedule for recoverability but easier for implementation. This is not deadlock-free. 24
7. 6.2. Two-Phase Locking Deadlock prevention  Conservative 2PL  Timestamp-based deadlock prevention schemes: wait-die & wound- wait Wait-die: if transaction Ti tries to lock an item X and is older than transaction Tj that currently locks X with a conflicting lock, Ti is allowed to wait; otherwise Ti dies and is restarted with the same timestamp. Wound-wait: If Ti is older than Tj, Ti wounds Tj, abort Tj and restart it later with the same timestamp; otherwise, Ti is allowed to wait.  Deadlock prevention schemes that do not require timestamps: no- waiting & cautious-waiting No-waiting: if a transaction is unable to obtain a lock, it is immediately aborted and then restarted after a certain time delay without checking whether a deadlock will actually occur or not. Cautious-waiting: if Tj is not blocked (not waiting for some other locked item), then T is blocked and allowed to wait; otherwise abort T . i i 26
8. 6.2. Two-Phase Locking Deadlock detection  Construct and maintain a wait-for graph One node is created for each transaction that is currently executing. A directed edge (Ti Tj) is created whenever a transaction Ti is waiting to lock an item X that is currently locked by a transaction Tj. The directed edge (Ti Tj) is dropped when Tj releases the lock(s) on the items that Ti was waiting for. A state of deadlock if and only if the wait-for graph has a cycle. 28
9. 6.2. Two-Phase Locking Starvation  A transaction cannot proceed for an indefinite period of time while other transactions in the system continue normally. The waiting scheme for locked items is unfair, giving priority to some transactions over others. Victim selection if the algorithm selects the same transaction as victim repeatedly, thus causing it to abort and never finish execution.  Solutions: A fair waiting scheme . Using a first-come-first-served queue; transactions are enabled to lock an item in the order in which they originally requested the lock. Priority-based schemes Wait-die and wound-wait schemes 30
10. 6.3. Concurrency Control Based On Timestamp Ordering Transaction timestamp - TS(T): a unique identifier to identify a transaction T, assigned in the order in which the transaction is submitted to the system Read timestamp of item X – read_TS(X): the largest timestamp among all the timestamps of transactions that have successfully read item X – that is, read_TS(X) = TS(T), where T is the youngest transaction that has read X successfully Write timestamp of item X – write_TS(X): the largest of all the timestamps of transactions that have successfully written item X – that is, write_TS(X) = TS(T), where T is the youngest transaction that has written X successfully. 32
11. 6.3. Concurrency Control Based On Timestamp Ordering T1 T2 X Y Read_TS = 0 Read_TS = 0 Timestamp TS = 1 TS = 2 Write_TS = 0 Write_TS = 0 Read_item(X) Read_item(X) Write_item(X) Write_item(X) Read_item(Y) Write_item(Y) Serial schedule S of transactions T1 & T2 based on timestamp: S = T1; T2 = r1(X); w1(X); r1(Y); w1(Y); r2(X); w2(X) 34
12. 6.3. Concurrency Control Based On Timestamp Ordering T1 T2 X Y Read_TS = 0 Read_TS = 0 Timestamp TS = 1 TS = 2 Write_TS = 0 Write_TS = 0 Read_item(X) Read_TS = 1 Write_item(X) Write_TS = 1 Read_item(X) Read_TS = 2 Write_item(X) Write_TS = 2 Read_item(Y) Read_TS = 1 Write_item(Y) Write_TS = 1 Schedule D (Figure 20.5.d) is conflict serializable. 36
13. 6.3. Concurrency Control Based On Timestamp Ordering Thomas‟s Write Rule  A modification of the basic timestamp ordering algorithm that does not enforce conflict serializability; but rejects fewer write operations  Checks for the write_item(X) operation: 1. If read_TS(X) > TS(T), then abort and roll back T and reject the operation. 2. If write_TS(X) > TS(T), then do not execute the write operation but continue processing. This is because some transaction with timestamp greater than TS(T) – and hence, after T in the timestamp ordering – has already written the value of X. 3. Otherwise, execute the write_item(X) operation of T and set write_TS(X) to TS(T). 38
14. 6.4. Multiversion concurrency control techniques Multiversion technique based on timestamp ordering  Several versions X1, X2, , Xk of each data item X are maintained. For each version, the value of version Xi and the two timestamps are kept: . Read_TS(Xi): the largest of all the timestamps of transactions that have successfully read version Xi . Write_TS(Xi): the timestamp of the transaction that wrote the value of version Xi  Whenever a transaction T is allowed to execute a write_item(X) operation, a new version Xk+1 of item X is created, with both the write_TS(Xk+1) and the read_TS(Xk+1) set to TS(T). 40
15. 6.4. Multiversion concurrency control techniques Multiversion technique based on timestamp ordering T1 T2 T3 X0 Y0 Z0 Read_TS = 0 Read_TS = 0 Read_TS = 0 TS = 20 TS = 25 TS = 15 Write_TS = 0 Write_TS = 0 Write_TS = 0 R1(X) R2(Z) R3(Y) W1(X) R2(Y) R3(Z) R1(Y) W2(Y) W3(Y) W1(Y) R2(X) W3(Z) W2(X) Serial schedule S of transactions T1, T2, & T3 based on timestamp: S = T3; T1; T2 42
16. 6.4. Multiversion concurrency control techniques T1 T2 T3 X0 Y0 Z0 X20 Y15 Z15 Y20 Y25 X25 R=0 R=0 R=0 R=20 R=15 R=15 R=20 R=25 R=25 TS = 20 TS = 25 TS = 15 W=0 W=0 W=0 W=20 W=15 W=15 W=20 W=25 W=25 R3(Y) R=15 R3(Z) R=15 R1(X) R=20 W1(X) created W3(Y) created W3(Z) created R2(Z) R=25 R1(Y) R=20 W1(Y) created R2(Y) R=25 W2(Y) created R2(X) R=25 W2(X) created What happens with the W1(Y) operation of transaction T1?
17. 6.4. Multiversion concurrency control techniques Original schedule T1 T2 T3 T4 A Read_TS=0; TS=150 TS=200 TS=175 TS=225 Write_TS=0 R1(A) Read_TS = 150 W1(A) Write_TS = 150 R2(A) Read_TS = 200 W2(A) Write_TS = 200 R3(A) (abort T3) R4(A) Read_TS = 225 The traditional timestamp ordering technique 46
18. 5.4. Multiversion concurrency control techniques Original schedule T1 T2 T3 A B C Read_TS=0; Read_TS=0; Read_TS=0; TS=200 TS=150 TS=175 Write_TS=0 Write_TS=0 Write_TS=0 R1(B) R2(A) R3(C) W2(A) W1(B) W1(A) W2(C) W3(A) Your turn: perform concurrency control on this schedule using the traditional timestamp ordering technique and then the multiversion one. 48
19. 6.4. Multiversion concurrency control techniques Original schedule T1 T2 T3 A AT2 AT1 AT3 B BT1 C Read_TS= Read_TS = Read_TS = Read_TS = Read_TS=0 Read_TS = Read_TS= 0; TS = TS = TS = 0; 150; 200; 175; ; 200; Write_TS= 200 150 175 Write_TS= Write_TS = Write_TS = Write_TS = Write_TS= Write_TS = 0 0 150 200 175 0 200 Read_TS = R (B) 1 200 Read_TS = R (A) 2 150 Read_TS = R (C) 3 175 W2(A) Created W1(B) Created W1(A) Created W2(C) (abort T2) W3(A) Created Your turn: perform concurrency control on this schedule using the multiversion timestamp ordering technique 50
20. 6.4. Multiversion concurrency control techniques Multiversion two-phase locking using certify locks  In the standard 2PL scheme, once a transaction obtains a write lock on an item X, no other transactions can access X.  In the multiversion 2PL scheme, other transactions T‟ are allowed to read an item X while a single transaction T holds a write lock on X. Two versions for each item X: one version written by some committed transaction; another version X‟ created by transaction T that acquires a write lock on X Other transactions (different from T) can continue to read the committed version of X while T holds the write lock. Once T is ready to commit, T must obtain a certify lock on all items that it currently holds write locks on before it can commit. Once the certify locks are acquired, the committed version X of the data item is set to the value of version X‟, version X‟ is discarded, and the certify locks are then released. No cascading aborts; but deadlocks may occur with lock upgradings. 52
21. Multiversion two-phase locking using certify locks T1’ T2’ Xcommitted Ycommitted XT1’ YT2’ Read_lock(Y) Read_locked (T1‟) Read_item(Y) T1‟ reads Write_lock(X) Write_locked (T1‟) Read_lock(X) Read_locked (T2‟) Read_item(X) T2‟ reads Write_lock(Y) Write_locked (T2‟) Read_item(X) T1‟ reads Write_item(X) created Certify_lock(X) XT1’ Xcommitted discarded Read_item(Y) T2‟ reads Write_item(Y) created Certify_lock(Y) YT2’ Ycommited discarded Certify_lock(X): waiting for other transactions‟ release DEADLOCK of Read_lock(X). Certify_lock(Y): waiting for other transactions‟ release of Read_lock(Y).
22. Multiversion two-phase locking using certify locks Original schedule Transactions in traditional 2PL T1 T2 T1 T2 Read_item(X) Read_lock(X) Read_lock(Y) Read_item(Y) Read_item(X) Read_item(Y) Write_item(Y) Write_lock(Y) Unlock(Y) Write_item(Y) Unlock(X) Schedule with mutliversion 2PL Unlock(Y) using certify locks T1 T2 Xcommitted Ycommitted YT2 Read_lock(X) Read_locked (T1) Read_item(X) T1 reads Read_lock(Y) Read_locked(T2) Read_item(Y) T2 reads Write_lock(Y) Write_locked(T1) Write_item(Y) Created Unlock(Y) Certify_lock(Y) YT2 Ycommited Discarded Unlock(Y) Unlock(X) 56
23. 6.5. Validation (optimistic) concurrency control techniques There are three phases for this concurrency control protocol:  1. Read phase: a transaction can read values of committed data items from the database. Updates are applied only to local copies (versions) of the data items kept in the transaction workspace.  2. Validation phase: checking is performed to ensure that serializability will not be violated if the transaction updates are applied to the database.  3. Write phase: if the validation phase is successful, the transaction updates are applied to the database; otherwise, the updates are discarded and the transaction is restarted. 58
24. 6.6. Granularity of Data Items and Multiple Granularity Locking Technique In this multiple granularity locking scheme, the granularity level (size of the data item) may be changed dynamically.  A field value of a database record  A database record  A disk block  A whole file  The whole database Fine granularity refers to small item sizes; coarse granularity refers to large item sizes. The larger the data item size is, the lower the degree of concurrency permitted. The smaller the data item size is, the more the number of items in the database; leading to a larger number of active locks to be handled by the lock manager. 60
25. 6.6. Granularity of Data Items and Multiple Granularity Locking Technique Types of locks  Shared lock (S) on node N: N is locked in shared mode.  Exclusive lock (X) on node N: N is locked in exclusive mode.  Intention-shared lock (IS) on node N: a shared lock(s) will be requested on some descendant node(s) of N.  Intention-exclusive (IX) lock on node N: an exclusive lock(s) will be requested on some descendant node(s) of N.  Shared-intention-exclusive (SIX) lock on node N: N is locked in shared mode but an exclusive lock(s) will be requested on some descendant node(s). Intention locks: what type of lock (shared or exclusive) a transaction will require from one of the node‟s descendants along the path from the root to the desired node. 62
26. 6.6. Granularity of Data Items and Multiple Granularity Locking Technique The multiple granularity locking protocol consists of the following rules: 1. The lock compatibility must be adhered to. 2. The root of the tree must be locked first, in any mode. 3. A node N can be locked by a transaction T in S or IS mode only if the parent of node N is already locked by transaction T in either IS or IX mode. 4. A node N can be locked by a transaction T in X, IX, or SIX mode only if the parent of node N is already locked by transaction T in either IX or SIX mode. 5. A transaction T can lock a node only if it has not unlocked any node (to enforce the 2PL protocol for serializability). 6. A transaction T can unlock a node, N, only if none of the children of node N are currently locked by T. 64
27. 6.6. Granularity of Data Items and Multiple Granularity Locking Technique Figure 21.7 A granularity hierarchy for illustrating multiple granularity level locking. [1], pp. 802. Your turn: Write schedules with the lock and unlock operations for transaction T4 that wants to read record r211, update page p22, and read page p12; for transaction T5 that wants to read p21 and update record r211. 66
28. 6.8. Other Concurrency Control Issues Insertion, deletion, and phantom records  Locking and timestamps for insertion and deletion  Index locking for the phantom record problem Interactive transactions  A problem occurs when interactive transactions read input and write output to an interactive device before they are committed. postpone output of transactions to the screen until they have committed Latches  Locks for a short duration no two-phase locking 68
29. Concurrency Control in Today‟s DBMSs Oracle 19c – Locking Mechanism  Oracle Database provides data concurrency, consistency, and integrity among transactions through its locking mechanisms.  Locking occurs automatically and requires no user action. Manual data locks User-defined locks  Before the database permits a session to process data, the session must first lock the data. The lock gives the session exclusive control over the data so that no other transaction can modify the locked data until the lock is released.  Because the locking mechanisms of Oracle Database are tied closely to transaction control, application designers need only define transactions properly, and Oracle Database automatically manages locking. Users never need to lock any resource explicitly, although Oracle Database also enables users to lock data manually. 70
30. Concurrency Control in Today‟s DBMSs Oracle 19c – Locking Mechanism  Oracle Database automatically detects deadlocks and resolves them by rolling back one statement involved in the deadlock, releasing one set of the conflicting row locks. the signaled transaction should be rolled back explicitly, but it can retry the rolled-back statement after waiting. Because Oracle Database does not escalate locks and does not use read locks for queries, but does use row-level (rather than page-level) locking, deadlocks occur infrequently.  Lock categories DML locks: protect data . Row locks . Table locks DDL locks: protect the structure of schema objects System locks: protect internal database structures such as data files. Latches, mutexes (similar to latches but on single objects), and internal locks are entirely automatic. 72
31. Summary Timestamp ordering techniques  Basic Thomas‟ Write Rule (not guarantee serializability)  Strict  Multiversion Serializable schedules by ordering transaction timestamps Other issues  index locking, insertion, deletion, the phantom record problem, interactive transactions, latches 74
32. Check for Understandings 6.1. State the purposes of concurrency control. Give several examples. 6.2. What is a lock? Give an example. 6.3. What is two-phase locking? How does it ensure serializability? Give an example. 6.4. Differentiate the variations of the two- phase locking technique: conservative, strict, rigorous. 6.5. Describe deadlock and starvation problems and the approaches to dealing with them. Give an example. 76
33. Check for Understandings 6.8. Describe the two-phase locking technique using certify locks. Give an example. 6.9. Describe the multiple granularity level two-phase locking technique. Give an example. 6.10. Describe the lock compatibility matrix for multiple granularity locking. Why is IS compatible with SIX? Why is IX incompatible with SIX? 6.11. Describe the optimistic concurrency control technique. How different is it from other concurrency control techniques? 78
34. Check for Understandings 6.16. Describe index locking. Give an example. 6.17. What are latches? When are they used? 6.18. What is an interactive transaction? Give an example. 6.19. What is a phantom record? Describe its problem for concurrency control. 6.20. Describe two-phase locking for insertions and deletions. 80
35. Check for Understandings 6.22. Consider the set of transactions accessing database element A. These transactions are operating under a basic timestamp-based scheduler. Explain why the transaction T3 has to be aborted. What happens if these transactions are operating under a multiversion timestamp-based scheduler? T1 T2 T3 T4 A 150 200 175 225 RT=0 WT=0 r1(A) RT=150 w1(A) WT=150 r2(A) RT=200 w2(A) WT=200 r3(A) ABORTED r4(A) RT=225 82
36. Check for Understandings S1 S2 6.24. Given two T1 T2 T1 T2 write_lock(Z) write_lock(Z) transactions and r2(Z) r2(Z) read_lock(Y) write_lock(X) their schedules: r2(Y) r1(X) T1 T2 w2(Z) read_lock(Y) read_lock(X) r (Y) r (X) r (Z) 2 1 2 r2(X) w2(Z) unlock(X) write_lock(Z) r1(Z) r2(Y) w (X) w (Z) read_lock(X) read_lock(X) 1 2 r (X) r (X) 1 2 r1(Y) r2(X) unlock(Z) unlock(X) w (Z) write_lock(Z) r (Z) 1 1 r1(Z) w1(X) write_lock(X) unlock(Z) Which schedule w1(X) unlock(Y) is serializable? unlock(Y) read_lock(Y) read_lock(Y) r1(Y) r (Y) w (Z) Which schedule 1 1 w1(Z) unlock(Z) faces deadlock? unlock(Z) unlock(Y) unlock(Y) unlock(X) unlock(X) 84