Chapter 15: Concurrency Control
■ Lock-Based Protocols
■ Timestamp-Based Protocols
■ Validation-Based Protocols
■ Multiple Granularity
■ Multiversion Schemes
■ Insert and Delete Operations
■ Concurrency in Index Structures
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.1 ©Silberschatz, Korth and Sudarshan
Lock-Based Protocols
■ A lock is a mechanism to control concurrent access to a data item
■ Data items can be locked in two modes:
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.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.2 ©Silberschatz, Korth and Sudarshan
Lock-Based Protocols (Cont.)
■ Lock-compatibility matrix
S
X
S
true
false
X
false
false
■ 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,
● butifanytransactionholdsanexclusiveontheitemnoother
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.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.3 ©Silberschatz, Korth and Sudarshan
Lock-Based Protocols (Cont.)
■ Example of a transaction performing locking: T2: lock-S(A);
read (A); unlock(A); 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.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.4 ©Silberschatz, Korth and Sudarshan
Pitfalls of Lock-Based Protocols
■ Consider the partial schedule
■ 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.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.5 ©Silberschatz, Korth and Sudarshan
Pitfalls of Lock-Based Protocols (Cont.)
■ The potential for deadlock exists in most locking protocols. Deadlocks are a necessary evil.
■ 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.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.6 ©Silberschatz, Korth and Sudarshan
The Two-Phase Locking Protocol
■ This is a protocol which ensures conflict-serializable schedules.
■ 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).
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.7 ©Silberschatz, Korth and Sudarshan
Proof: 2PLàConflict Serializability
■ Suppose two transactions have a conflict on variable X ■ Thus, at least one access is a write
■ This transaction needs an exclusive lock
■ Thus, transactions cannot have lock on X at same time
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.8 ©Silberschatz, Korth and Sudarshan
Proof: 2PLàConflict Serializability
■ Suppose two transactions have a conflict on variable X
■ Thus, at least one access is a write
■ This transaction needs an exclusive lock
■ Thus, transactions cannot have lock on X at same time
■ Suppose T1 has the lock first
■ Thus, T1 has to release lock before T2 gets it
■ Thus, T1 goes into shrinking phase before T2
■ Schedules can be serialized based on order of phase change
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.9 ©Silberschatz, Korth and Sudarshan
The Two-Phase Locking Protocol (Cont.)
■ Two-phase locking does not ensure freedom from deadlocks.
■ Cascading roll-back is possible under two-phase locking. To avoid this, follow a modified protocol 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 until commit/abort. In this protocol transactions can be serialized in the order in which they commit.
■ There can be conflict serializable schedules that cannot be obtained if two-phase locking is used.
■ However, in the absence of extra information (e.g., ordering of access to data), two-phase locking is needed for conflict serializability in the following sense:
Given a transaction Ti that does not follow two-phase locking, we can find a transaction Tj that uses two-phase locking, and a schedule for Ti and Tj that is not conflict serializable.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.10 ©Silberschatz, Korth and Sudarshan
Lock Conversions
■ Two-phase locking with lock conversions: – First Phase:
● can acquire a lock-S on item
● 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.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.11 ©Silberschatz, Korth and Sudarshan
Automatic Acquisition of Locks
■ A transaction Ti issues the standard read/write instruction, without explicit locking calls.
■ The operation read(D) is processed as: ifTi hasalockonD
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)
end
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.12 ©Silberschatz, Korth and Sudarshan
■
write(D) is processed as: if Ti has a lock-X on D
then
write(D)
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
■
Automatic Acquisition of Locks (Cont.)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.13 ©Silberschatz, Korth and Sudarshan
Implementation of Locking
■ A lock manager can be implemented as a separate process to which transactions send lock 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 pending requests.
■ The lock table is usually implemented as an in-memory
hash table indexed on the name of the data item being
locked.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.14 ©Silberschatz, Korth and Sudarshan
17
T23
1912
T23
14
T1
144
T8
123
T1
T8 T2
■ Black rectangles indicate granted locks, white ones indicate waiting requests
■ 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 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 Table
Database System Concepts – 6
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
th
T23
Edition
14.15
©Silberschatz, Korth and Sudarshan
●
lock manager may keep a list of locks held by each transaction, to implement this efficiently
granted waiting
Graph-Based Protocols
■ Graph-based protocols are an alternative to two- phase locking.
■ Impose a partial ordering → on the set D = {d1, d2 ,…, dh} of all data items.
● Ifdi→dj thenanytransactionaccessingbothdi 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.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.16 ©Silberschatz, Korth and Sudarshan
Tree Protocol
A BC F
E
I
J
1. Onlyexclusivelocksareallowed.
2. 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.
3. Dataitemsmaybeunlockedatanytime.
4. A data item that has been locked and unlocked by Ti cannot subsequently be relocked by Ti .
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.17 ©Silberschatz, Korth and Sudarshan
D GH
Graph-Based Protocols (Cont.)
■ The tree protocol ensures conflict serializability as well as freedom from deadlock.
■ Unlocking may occur earlier in the tree-locking protocol than in the two- phase locking protocol.
● shorterwaitingtimes,andincreaseinconcurrency
● protocolisdeadlock-free,norollbacksarerequired
■ Drawbacks
● Protocoldoesnotguaranteerecoverabilityorcascadefreedom
! Need to introduce commit dependencies to ensure recoverability
● Transactionsmayhavetolockdataitemsthattheydonotaccess. ! increased locking overhead, and additional waiting time
! potential decrease in concurrency
! In particular, a lot of contention for higher levels of the tree
■ Schedules not possible under two-phase locking are possible under tree protocol, and vice versa.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.18 ©Silberschatz, Korth and Sudarshan
Deadlock Handling
■ Consider the following two transactions:
T1: write (X) write(Y)
■ Schedule with deadlock
T2:
write(Y) write(X)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.19
©Silberschatz, Korth and Sudarshan
Deadlock Handling
■ 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.
■ 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).
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.20 ©Silberschatz, Korth and Sudarshan
More Deadlock Prevention Strategies
■ Following schemes use transaction timestamps for the sake of deadlock prevention alone.
■ wait-die scheme — non-preemptive
● 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
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.21 ©Silberschatz, Korth and Sudarshan
Deadlock prevention (Cont.)
■ Both in wait-die and in wound-wait schemes, a rolled back transactions is restarted with its original 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.
● Timeouts can be used in addition to other methods
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.22 ©Silberschatz, Korth and Sudarshan
Deadlock Detection
■ 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)
● 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.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.23 ©Silberschatz, Korth and Sudarshan
Deadlock Detection (Cont.)
T17
T18 T20 T19
T18 T20 T19
Wait-for graph with a cycle
T17
Wait-for graph without a cycle
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
14.24
©Silberschatz, Korth and Sudarshan
Deadlock Recovery
■ 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 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
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.25 ©Silberschatz, Korth and Sudarshan
Multiple Granularity
■ Allowdataitemstobeofvarioussizesanddefineahierarchy of data granularities, where the small granularities are nested within larger ones.
■ Can be represented graphically as a tree (but don’t confuse with tree-locking protocol)
■ When a transaction locks a node in the tree explicitly, it implicitly locks all the node’s descendents in the same mode.
■ Granularity of locking (level in tree where locking is done): ● fine granularity (lower in tree): high concurrency, high
locking overhead
● coarse granularity (higher in tree): low locking overhead, low concurrency
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.26 ©Silberschatz, Korth and Sudarshan
Example of Granularity Hierarchy
DB
A1
A2
Fa Fb Fc
ra1 ra2 ran rb1 rbk
The levels, starting from the coarsest (top) level are: ● database
● area
● file
● record Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
rc1 rcm
14.27
©Silberschatz, Korth and Sudarshan
Intention Lock Modes
■ In addition to S and X lock modes, there are three additional lock modes with multiple granularity:
● intention-shared (IS): indicates explicit locking at a lower level of the tree but only with shared locks.
● intention-exclusive (IX): indicates explicit locking at a lower level with exclusive or shared locks
● shared and intention-exclusive (SIX): the subtree rooted by that node is locked explicitly in shared mode and explicit locking is being done at a lower level with exclusive-mode locks.
■ Intention locks allow a higher level node to be locked in S or X mode without having to check all descendent nodes.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.28 ©Silberschatz, Korth and Sudarshan
Compatibility Matrix with Intention Lock Modes
■ The compatibility matrix for all lock modes is:
IS
IX
S
SIX
X
IS
true
true
true
true
false
IX
true
true
false
false
false
S
true
false
true
false
false
SIX
true
false
false
false
false
X
false
false
false
false
false
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.29 ©Silberschatz, Korth and Sudarshan
Multiple Granularity Locking Scheme
■ Transaction Ti can lock a node Q, using the following rules:
1. The lock compatibility matrix must be observed.
2. The root of the tree must be locked first, and may be locked in any mode.
3. AnodeQcanbelockedbyTi inSorISmodeonlyifthe parent of Q is currently locked by Ti in either IX or IS mode.
4. AnodeQcanbelockedbyTi inX,SIX,orIXmodeonlyifthe parent of Q is currently locked by Ti in either IX or SIX mode.
5. Ti can lock a node only if it has not previously unlocked any node (that is, Ti is two-phase).
6. Ti can unlock a node Q only if none of the children of Q are currently locked by Ti.
■ Observe that locks are acquired in root-to-leaf order, whereas they are released in leaf-to-root order.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 14.30 ©Silberschatz, Korth and Sudarshan
Timestamp-Based Protocols
■ Each transaction is issued a timestamp when it enters the system. If an old transaction Ti has time-stamp TS(Ti), a new transaction Tj is assigned time-stamp TS(Tj) such that TS(Ti)