Concurrency Control PDF

1/31/2023 Parul Saxena 1 CONCURRENCY CONTROL LOCK-BASED PROTOCOLS 1/31/2023 A lock is a mechanism to control concurrent access to a data item Data items can be locked in two mode...

1/31/2023 Parul Saxena 1 CONCURRENCY CONTROL LOCK-BASED PROTOCOLS 1/31/2023 A lock is a mechanism to control concurrent access to a data item Data items can be locked in two modes : Parul Saxena 1. exclusive (X) mode. Data item can be both read as well as written. X-lock is requested using lock-X instruction. 2. shared (S) mode. Data item can only be read. S- lock is requested using lock-S instruction. Lock requests are made to concurrency-control manager. Transaction can proceed only after request is granted. 2  LOCK-BASED PROTOCOLS (CONT.) Lock-compatibility matrix 1/31/2023 Parul Saxena A transaction may be granted a lock on an item if the requested lock is compatible with locks already held on the item by other transactions Any number of transactions can hold shared locks on an item, but if any transaction holds an exclusive on the item no other transaction may hold any lock on the item. If a lock cannot be granted, the requesting transaction is made to wait till all incompatible locks held by other transactions have been released. The lock is then granted. 3 LOCK-BASED PROTOCOLS (CONT.) Example of a transaction performing locking: 1/31/2023 T2: lock-S(A); read (A); unlock(A); Parul Saxena lock-S(B); read (B); unlock(B); display(A+B) Locking as above is not sufficient to guarantee serializability — if A and B get updated in-between the read of A and B, the displayed sum would be wrong. A locking protocol is a set of rules followed by all transactions while requesting and releasing locks. Locking protocols restrict the set of possible schedules. 4 PITFALLS OF LOCK-BASED PROTOCOLS Consider the partial schedule 1/31/2023 Parul Saxena Neither T3 nor T4 can make progress — executing lock-S(B) causes T4 to wait for T3 to release its lock on B, while executing lock-X(A) causes T3 to wait for T4 to release its lock on A. Such a situation is called a deadlock. To handle a deadlock one of T3 or T4 must be rolled back and its locks released. 5 1/31/2023 Parul Saxena ANSWER: C 6  1/31/2023 Parul Saxena ANSWER: A (Transaction is not allowed to read a data 7 item until the last transaction that has written is committed ) PITFALLS OF LOCK-BASED PROTOCOLS (CONT.) 1/31/2023 The potential for deadlock exists in most locking protocols. Deadlocks are a necessary evil. Parul Saxena Starvation is also possible if concurrency control manager is badly designed. For example: A transaction may be waiting for an X-lock on an item, while a sequence of other transactions request and are granted an S- lock on the same item. The same transaction is repeatedly rolled back due to deadlocks. Concurrency control manager can be designed to prevent starvation. 8 THE TWO-PHASE LOCKING PROTOCOL 1/31/2023 This is a protocol which ensures conflict- serializable schedules. Parul Saxena Phase 1: Growing Phase transaction may obtain locks transaction may not release locks Phase 2: Shrinking Phase transaction may release locks transaction may not obtain locks The protocol assures serializability. It can be proved that the transactions can be serialized in the order of their lock points (i.e. the point where a transaction acquired its final lock). 9 1/31/2023 Parul Saxena 10 In the growing phase transaction reaches a point where all the locks it may need has been acquired. This point is called LOCK POINT. 1/31/2023 After the lock point has been reached, the transaction enters a shrinking phase. Strict two phase locking protocol Parul Saxena A transaction can release a shared lock after the lock point, but it cannot release any exclusive lock until the transaction commits. This protocol creates a recoverable and cascade less schedule. Cascading schedule: In this schedule one transaction is dependent on another transaction. So if one has to rollback then the other has to rollback. Rigorous two phase locking protocol A transaction cannot release any lock either shared or exclusive until it commits. The 2PL protocol guarantees serializability, but cannot guarantee 11 that deadlock will not happen. THE TWO-PHASE LOCKING PROTOCOL (CONT.) Two-phase locking does not ensure freedom from 1/31/2023 deadlocks Cascading roll-back is possible under two-phase locking. To avoid this, follow a modified protocol Parul Saxena called strict two-phase locking. Here a transaction must hold all its exclusive locks till it commits/aborts. Rigorous two-phase locking is even stricter: here all locks are held till commit/abort. In this protocol transactions can be serialized in the order in which they commit. 12 1/31/2023 Parul Saxena 13 ANSWER: C LOCK CONVERSIONS Two-phase locking with lock conversions: 1/31/2023 – First Phase: can acquire a lock-S on item Parul Saxena can acquire a lock-X on item can convert a lock-S to a lock-X (upgrade) – Second Phase: can release a lock-S can release a lock-X can convert a lock-X to a lock-S (downgrade) This protocol assures serializability. But still relies on the programmer to insert the various locking instructions. 14  2PL 1/31/2023 X(B) X(B) R(B) R(B) Parul Saxena W(B) W(B) U(B) X(C) X(C) R(C) R(C) W(C) W(C) U(C) U(C) U(B) 15 STRICT 2PL CONSERVATIVE 2PL X(B) X(B) R(B) X(C) 1/31/2023 W(B) R(B) X(C) W(B) Parul Saxena R(C) U(B) W(C) R(C) COMMIT W(C) U(B) U(C) U(C) 16  AUTOMATIC ACQUISITION OF LOCKS A transaction Ti issues the standard read/write 1/31/2023 instruction, without explicit locking calls. The operation read(D) is processed as: Parul Saxena if Ti has a lock on D then read(D) else begin if necessary wait until no other transaction has a lock-X on D grant Ti a lock-S on D; read(D) 17 end AUTOMATIC ACQUISITION OF LOCKS (CONT.) write(D) is processed as: 1/31/2023 if Ti has a lock-X on D then write(D) Parul Saxena else begin if necessary wait until no other trans. has any lock on D, if Ti has a lock-S on D then upgrade lock on D to lock-X else grant Ti a lock-X on D write(D) end; All locks are released after commit or abort 18 IMPLEMENTATION OF LOCKING 1/31/2023 A Lock manager can be implemented as a separate process to which transactions send lock Parul Saxena and unlock requests The lock manager replies to a lock request by sending a lock grant messages (or a message asking the transaction to roll back, in case of a deadlock) The requesting transaction waits until its request is answered The lock manager maintains a data structure called a lock table to record granted locks and 19 pending requests  Black rectangles indicate granted LOCK TABLE locks, white ones indicate waiting requests 1/31/2023 Lock table also records the type of lock granted or requested New request is added to the end of the queue of requests for the data Parul Saxena item, and granted if it is compatible with all earlier locks Unlock requests result in the request being deleted, and later requests are checked to see if they can now be granted If transaction aborts, all waiting or granted requests of the transaction are deleted lock manager may keep a list of locks held by each transaction, to implement this efficiently 20 GRAPH-BASED PROTOCOLS 1/31/2023 Graph-based protocols are an alternative to two- phase locking Parul Saxena Impose a partial ordering → on the set D = {d1, d2 ,..., dh} of all data items. If di → dj then any transaction accessing both di and dj must access di before accessing dj. Implies that the set D may now be viewed as a directed acyclic graph, called a database graph. The tree-protocol is a simple kind of graph protocol. 21 TREE PROTOCOL 1/31/2023 Parul Saxena Only exclusive locks are allowed. The first lock by Ti may be on any data item. Subsequently, a data Q can be locked by Ti only if the parent of Q is currently locked by Ti. Data items may be unlocked at any time. 22 TIMESTAMP ORDERING PROTOCOL 1/31/2023 Timestamp is a unique identifier created by the DBMS to identify a transaction. They are usually assigned in the order in which they are submitted to the system. Refer to the Parul Saxena timestamp of a transaction T as TS(Ti ). The timestamp-ordering protocol ensures serializability among transactions in their conflicting read and write operations. This is the responsibility of the protocol system that the conflicting pair of tasks should be executed according to the timestamp values of the transactions. The timestamp of transaction Ti is denoted as TS(Ti). Read time-stamp of data-item X is denoted by R-timestamp(X). Write time-stamp of data-item X is denoted by W-timestamp(X). 23 10:00 10:10 10:15 T1 T2 T3 100 200 300 1/31/2023 Older Younger Youngest Parul Saxena 24  Two Timestamp Values relating to each database item X are Write-_TS(X) is the last(latest) timestamp of any transaction that executed write(X) successfully. Read_TS(X) is the last (latest) timestamp of any transaction that 1/31/2023 executed read(X) successfully. Parul Saxena TS= 10 20 30 10 20 30 T1 T2 T3 T1 T2 T3 R(A) W(A) R(A) W(A) R(A) W(A) RTS(A) = ? WTS(A) = ? 25 RULES 1/31/2023 Transaction Ti issues a Read(A) operation a) if WTS(A) > TS(Ti ), ROLLBACK Ti Parul Saxena b) otherwise execute R(A) operation Set RTS(A) = Max{ RTS(A), TS(Ti )} Transaction Ti issues a Write(A) operation a) if RTS(A) > TS(Ti ), ROLLBACK Ti b) if WTS(A) > TS(Ti ), ROLLBACK Ti c) otherwise execute Write(A) operation Set WTS(A) = TS(Ti ) 26 QUESTION: 100 200 300 1/31/2023 T1 T2 T3 RTS(A) = 100 WTS(A) = 300 R(A) RTS(B) = 300 WTS(B) = 0 Parul Saxena R(B) RTS(C) = 100 WTS(C) = 100 W(C) R(B) R(C) W(B) W(A) A B C RTS 0 0 0 WTS 0 0 0 27  R (A,B,C,D,E) FDs = {AB -> C, A ->D, D->E, AC->B } FIND CK, PRIME ATTRIBUTE, AND NON 1/31/2023 PRIME ATTRIBUTE A+ = ADE Parul Saxena AB+ = ABCDE AC+ = ACBDE AD+ = ADE AE+ = AED 28 R(A,B,C,D,E) FDS = {A -> B, BC -> E, ED -> A}. FIND CK. 1/31/2023 CDA, CDE, CDB Parul Saxena 29  DEADLOCK HANDLING 1/31/2023 System is deadlocked if there is a set of transactions such that every transaction in the set is waiting for another transaction in the set. Parul Saxena Deadlock prevention protocols ensure that the system will never enter into a deadlock state. Some prevention strategies : Require that each transaction locks all its data items before it begins execution (predeclaration). Impose partial ordering of all data items and require that a transaction can lock data items only in the order specified by the partial order (graph-based protocol). 30  MORE DEADLOCK PREVENTION STRATEGIES Following schemes use transaction timestamps for 1/31/2023 the sake of deadlock prevention alone. wait-die scheme — non-preemptive Parul Saxena older transaction may wait for younger one to release data item. Younger transactions never wait for older ones; they are rolled back instead. a transaction may die several times before acquiring needed data item wound-wait scheme — preemptive older transaction wounds (forces rollback) of younger transaction instead of waiting for it. Younger transactions may wait for older ones. may be fewer rollbacks than wait-die scheme. 31 WAIT-DIE SCHEME — NON-PREEMPTIVE WHEN TRANSACTION TI REQUESTS A DATA ITEM CURRENTLY HELD BY TJ , TI IS ALLOWED TO WAIT ONLY IF IT HAS A TIMESTAMP SMALLER THAN THAT OF TJ 1/31/2023 (TI IS OLDER THAN TJ). OTHERWISE TI IS ROLLED BACK (DIES) E.G. TRANSACTIONS T22, T23 AND T24 HAVE TS 5, 10, 15 RESP. IF T22 REQUESTS A DATA ITEM HELD BY T23 , THEN T22 WILL WAIT. IF T24 REQUESTS Parul Saxena A DATA ITEM HELD BY T23 , THEN T24 WILL BE ROLLED BACK. WOUND-WAIT SCHEME — PREEMPTIVE WHEN TRANSACTION TI REQUESTS A DATA ITEM CURRENTLY HELD BY TJ , TI IS ALLOWED TO WAIT ONLY IF IT HAS A TIMESTAMP LARGER THAN THAT OF TJ (TI IS YOUNGER THAN TJ). OTHERWISE TJ IS ROLLED BACK (TJ IS WOUNDED BY TI) E.G. TRANSACTIONS T22, T23 AND T24 HAVE TS 5, 10, 15 RESP. IF T22 REQUESTS A DATA ITEM HELD BY T23 , THEN THE DATA ITEM WILL BE PREEMPTED FROM T23 AND T23 WILL BE ROLLED BACK. IF T24 REQUESTS A DATA ITEM HELD BY T23 , THEN T24 WILL WAIT. BOTH THE WOUND-WAIT AND THE WAIT-DIE SCHEME AVOID STARVATION. 32  1/31/2023 Parul Saxena 33 ANSWER : C,D  DEADLOCK PREVENTION (CONT.) 1/31/2023 Both in wait-die and in wound-wait schemes, a rolled back transactions is restarted with its original Parul Saxena timestamp. Older transactions thus have precedence over newer ones, and starvation is hence avoided. Timeout-Based Schemes : a transaction waits for a lock only for a specified amount of time. After that, the wait times out and the transaction is rolled back. thus deadlocks are not possible simple to implement; but starvation is possible. Also difficult to determine good value of the timeout interval. 34  DEADLOCK DETECTION 1/31/2023 Deadlocks can be described as a wait-for graph, which consists of a pair G = (V,E), V is a set of vertices (all the transactions in the system) Parul Saxena E is a set of edges; each element is an ordered pair Ti →Tj. If Ti → Tj is in E, then there is a directed edge from Ti to Tj, implying that Ti is waiting for Tj to release a data item. When Ti requests a data item currently being held by Tj, then the edge Ti Tj is inserted in the wait-for graph. This edge is removed only when Tj is no longer holding a data item needed by Ti. The system is in a deadlock state if and only if the wait-for graph has a cycle. Must invoke a deadlock-detection algorithm periodically to look for cycles. 35 DEADLOCK DETECTION (CONT.) 1/31/2023 Parul Saxena Wait-for graph without a cycle Wait-for graph with a cycle 36  DEADLOCK RECOVERY 1/31/2023 When deadlock is detected : Some transaction will have to rolled back (made a victim) to break deadlock. Select that transaction as victim that will incur minimum Parul Saxena cost. Rollback -- determine how far to roll back transaction Total rollback: Abort the transaction and then restart it. More effective to roll back transaction only as far as necessary to break deadlock. Starvation happens if same transaction is always chosen as victim. Include the number of rollbacks in the cost factor to avoid starvation 37 1/31/2023 Parul Saxena END OF CHAPTER 38 1/31/2023 Parul Saxena 39 1/31/2023 Parul Saxena 40 1/31/2023 Parul Saxena 41 B+-TREE FOR ACCOUNT FILE WITH N = 3. 1/31/2023 Parul Saxena 42 INSERTION OF “CLEARVIEW” INTO THE B+-TREE OF FIGURE 16.21 1/31/2023 Parul Saxena 43