Concurrency Control
Concurrency Control
P.J. Mc.Brien
Imperial College London
P.J. Mc.Brien (Imperial College London) Concurrency Control 1 / 46
Transactions ACID properties
Transactions: ACID properties
ACID properties
database management systems (DBMS) implements indivisible tasks called
transactions
Atomicity all or nothing
Consistency consistent before → consistent after
Isolation independent of any other transaction
Durability completed transaction are durable
BEGIN TRANSACTION
UPDATE branch
SET cash=cash −10000.00
WHERE so r t code =56
UPDATE branch
SET cash=cash +10000.00
WHERE so r t code =34
COMMIT TRANSACTION
Note that if total cash is £137,246.12
before the transaction, then it will be
the same after the transaction.
P.J. Mc.Brien (Imperial College London) Concurrency Control 2 / 46
Transactions ACID properties
SQL Conversion to Histories
branch
sortcode bname cash
56 ’Wimbledon’ 94340.45
34 ’Goodge St’ 8900.67
67 ’Strand’ 34005.00
BEGIN TRANSACTION T1
UPDATE branch
SET cash=cash-10000.00
WHERE sortcode=56
UPDATE branch
SET cash=cash+10000.00
WHERE sortcode=34
COMMIT TRANSACTION T1
H1 = r1[b56] , cash=94340.45,
w1[b56] , cash=84340.45,
r1[b34] , cash=8900.67,
w1[b34] , cash=18900.67, c1
history of transaction Tn
1 Begin transaction bn (only given if necessary for discussion)
2 Various read operations on objects rn[oj ] and write operations wn[oj ]
3 Either cn for the commitment of the transaction, or an for the abort of the
transaction
P.J. Mc.Brien (Imperial College London) Concurrency Control 3 / 46
Transactions ACID properties
SQL Conversion to Histories
branch
sortcode bname cash
56 ’Wimbledon’ 84340.45
34 ’Goodge St’ 18900.67
67 ’Strand’ 34005.00
BEGIN TRANSACTION T2
UPDATE branch
SET cash=cash-2000.00
WHERE sortcode=34
UPDATE branch
SET cash=cash+2000.00
WHERE sortcode=67
COMMIT TRANSACTION T2
H2 = r2[b34] , cash=18900.67,
w2[b34] , cash=16900.67,
r2[b67] , cash=34005.00,
w2[b67] , cash=36005.00, c2
history of transaction Tn
1 Begin transaction bn (only given if necessary for discussion)
2 Various read operations on objects rn[oj ] and write operations wn[oj ]
3 Either cn for the commitment of the transaction, or an for the abort of the
transaction
P.J. Mc.Brien (Imperial College London) Concurrency Control 4 / 46
Concurrency Definition
Concurrent Execution
Concurrent Execution of Transactions
Interleaving of several transaction histories
Order of operations within each history preserved
H1 = r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1
H2 = r2[b34] , w2[b34] , r2[b67] , w2[b67] , c2
Some possible concurrent executions are
Hx = r2[b34] , r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1 , w2[b34] , r2[b67] , w2[b67] , c2
Hy = r2[b34] , w2[b34] , r1[b56] , w1[b56] , r1[b34] , w1[b34] , r2[b67] , w2[b67] , c2 , c1
Hz = r2[b34] , w2[b34] , r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1 , r2[b67] , w2[b67] , c2
P.J. Mc.Brien (Imperial College London) Concurrency Control 5 / 46
Concurrency Definition
Which concurrent executions should be allowed?
Concurrency control → controlling interaction
serialisability
A concurrent execution of transactions should always has the same end result as
some serial execution of those same transactions
recoverability
No transaction commits depending on data that has been produced by another
transaction that has yet to commit
P.J. Mc.Brien (Imperial College London) Concurrency Control 6 / 46
Concurrency Definition
Quiz 1: Serialisability and Recoverability (1)
Hx = r2[b34] , r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1 , w2[b34] , r2[b67] , w2[b67] , c2
Is Hx
A
Not Serialisable, Not Recoverable
B
Not Serialisable, Recoverable
C
Serialisable, Not Recoverable
D
Serialisable, Recoverable
P.J. Mc.Brien (Imperial College London) Concurrency Control 7 / 46
Concurrency Definition
Quiz 2: Serialisability and Recoverability (2)
Hy = r2[b34] , w2[b34] , r1[b56] , w1[b56] , r1[b34] , w1[b34] , r2[b67] , w2[b67] , c2 , c1
Is Hy
A
Not Serialisable, Not Recoverable
B
Not Serialisable, Recoverable
C
Serialisable, Not Recoverable
D
Serialisable, Recoverable
P.J. Mc.Brien (Imperial College London) Concurrency Control 8 / 46
Concurrency Definition
Quiz 3: Serialisability and Recoverability (3)
Hz = r2[b34] , w2[b34] , r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1 , r2[b67] , w2[b67] , c2
Is Hz
A
Not Serialisable, Not Recoverable
B
Not Serialisable, Recoverable
C
Serialisable, Not Recoverable
D
Serialisable, Recoverable
P.J. Mc.Brien (Imperial College London) Concurrency Control 9 / 46
Concurrency Anomalies
Anomaly 1: Lost update
BEGIN TRANSACTION T1
EXEC move cash(56,34,10000.00)
COMMIT TRANSACTION T1
r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1
BEGIN TRANSACTION T2
EXEC move cash(34,67,2000.00)
COMMIT TRANSACTION T2
r2[b34] , w2[b34] , r2[b67] , w2[b67] , c2
r1[b56] , cash=94340.45, w1[b56] , cash=84340.45, r1[b34] , cash=8900.67,
r2[b34] , cash=8900.67, w1[b34] , cash=18900.67lostupdate, c1 , w2[b34] , cash=6900.42
r2[b67] , cash=34005.00, w2[b67] , cash=36005.25, c2
− serialisable + recoverable
P.J. Mc.Brien (Imperial College London) Concurrency Control 10 / 46
Concurrency Anomalies
Anomaly 2: Inconsistent analysis
BEGIN TRANSACTION T1
EXEC move cash(56,34,10000.00)
COMMIT TRANSACTION T1
r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1
BEGIN TRANSACTION T4
SELECT SUM(cash) FROM branch
COMMIT TRANSACTION T4
H4 = r4[b56] , r4[b34] , r4[b67] , c4
r1[b56] , cash=94340.45, w1[b56] , cash=84340.45, r4[b56] , cash=84340.45,
r4[b34] , cash=8900.67, r4[b67] , cash=34005.00, r1[b34] , cash=8900.67,
w1[b34] , cash=18900.67, c1 , c4
− serialisable + recoverable
P.J. Mc.Brien (Imperial College London) Concurrency Control 11 / 46
Concurrency Anomalies
Anomaly 3: Dirty Reads
BEGIN TRANSACTION T1
EXEC move cash(56,34,10000.00)
COMMIT TRANSACTION T1
r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1
BEGIN TRANSACTION T2
EXEC move cash(34,67,2000.00)
COMMIT TRANSACTION T2
r2[b34] , w2[b34] , r2[b67] , w2[b67] , c2
r1[b56] , cash=94340.45, w1[b56] , cash=84340.45, r2[b34] , cash=8900.67,
w2[b34] , cash=6900.42, r1[b34] , cash=6900.67, w1[b34] , cash=16900.67, c1 ,
r2[b67] , cash=34005.00, w2[b67] , cash=36005.25, a2
+ serialisable − recoverable
P.J. Mc.Brien (Imperial College London) Concurrency Control 12 / 46
Concurrency Anomalies
Quiz 4: Anomalies (1)
Hx = r2[b34] , r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1 , w2[b34] , r2[b67] , w2[b67] , c2
Which anomaly does Hx suffer?
A
None
B
Lost Update
C
Inconsistent Analysis
D
Dirty Read
P.J. Mc.Brien (Imperial College London) Concurrency Control 13 / 46
Concurrency Anomalies
Quiz 5: Anomalies (2)
Hz = r2[b34] , w2[b34] , r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1 , r2[b67] , w2[b67] , c2
Which anomaly does Hz suffer?
A
None
B
Lost Update
C
Inconsistent Analysis
D
Dirty Read
P.J. Mc.Brien (Imperial College London) Concurrency Control 14 / 46
Concurrency Anomalies
Worksheet: Anomalies
rental charge
H1 = r1[d1000] , w1[d1000] , r1[d1001] , w1[d1001] , r1[d1002] , w1[d1002]
transfer charge
H2 = r2[d1000] , w2[d1000] , r2[d1002] , w2[d1002]
total charge
H3 = r3[d1000] , r3[d1001] , r3[d1002]
P.J. Mc.Brien (Imperial College London) Concurrency Control 15 / 46
Concurrency Anomalies
Account Table
account
no type cname rate sortcode
100 ’current’ ’McBrien, P.’ NULL 67
101 ’deposit’ ’McBrien, P.’ 5.25 67
103 ’current’ ’Boyd, M.’ NULL 34
107 ’current’ ’Poulovassilis, A.’ NULL 56
119 ’deposit’ ’Poulovassilis, A.’ 5.50 56
125 ’current’ ’Bailey, J.’ NULL 56
P.J. Mc.Brien (Imperial College London) Concurrency Control 16 / 46
Concurrency Anomalies
Anomaly 4: Dirty Writes
BEGIN TRANSACTION T5
UPDATE account
SET rate=5.5
WHERE type=’deposit’
COMMIT TRANSACTION T5
H5 = w5[a101] , rate=5.5,
w5[a119] , rate=5.5, c5
BEGIN TRANSACTION T6
UPDATE account
SET rate=6.0
WHERE type=’deposit’
COMMIT TRANSACTION T6
H6 = w6[a101] , rate=6.0,
w6[a119] , rate=6.0, c6
w6[a101] , rate=6.0, w5[a101] , rate=5.5, w5[a119] , rate=5.5,
w6[a119] , rate=6.0, c5 , c6
− serialisable + recoverable
P.J. Mc.Brien (Imperial College London) Concurrency Control 17 / 46
Serialisability
Serialisable Transaction Execution
Solve anomalies → H ≡ serial execution
Only interested in the committed projection
Hc =
r1[b56] , r2[b34] , w2[b34] ,
r3[m1000] , r3[m1001] , r3[m1002] ,
w1[b56] , r4[b56] ,
r3[m1003] , r3[m1004] , r3[m1005] ,
r1[b34] , a3 , w1[b34] , c1 , r4[b34] ,
r2[b67] , w2[b67] , c2 , r4[b67] , c4
C(Hc) =
r1[b56] , r2[b34] , w2[b34] ,
w1[b56] , r4[b56] ,
r1[b34] , w1[b34] , c1 , r4[b34] ,
r2[b67] , w2[b67] , c2 , r4[b67] , c4
P.J. Mc.Brien (Imperial College London) Concurrency Control 18 / 46
Serialisability
Possible Serial Equivalents
Hcp = r1[b56] , r2[b34] , w2[b34] , w1[b56] , r4[b56] , r1[b34] , w1[b34] , c1 , r4[b34] , r2[b67] ,
w2[b67] , c2 , r4[b67] , c4
H1 , H2 , H4 H1 , H4 , H2 H2 , H1 , H4 H2 , H4 , H1 H4 , H1 , H2 H4 , H2 , H1
how to determine that histories are equivalent?
how to check this during execution?
P.J. Mc.Brien (Imperial College London) Concurrency Control 19 / 46
Serialisability
Conflicts: Potential For Problems
conflict
A conflict occurs when there is a interaction between two transactions
rx[o] and wy[o] are in H where x 6= y
or
wx[o] and wy [o] are in H where x 6= y
conflicts
Hx = r2[b34] , r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1 , w2[b34] , r2[b67] , w2[b67] , c2
Hy = r2[b34] , w2[b34] , r1[b56] , w1[b56] , r1[b34] , w1[b34] , r2[b67] , w2[b67] , c2 , c1
Hz = r2[b34] , w2[b34] , r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1 , r2[b67] , w2[b67] , c2
Conflicts
w2[b34] → r1[b34] T1 reads from T2 in Hy,Hz
w1[b34] → w2[b34] T2 writes over T1 in Hx
r2[b34] → w1[b34] T1 writes after T2 reads in Hx
P.J. Mc.Brien (Imperial College London) Concurrency Control 20 / 46
Serialisability
Quiz 6: Conflicts
Hw =
r2[a100] , w2[a100] , r2[a107] , r1[a119] , w1[a119] , r1[a107] , w1[a107] , c1 , w2[a107] , c2
Which of the following is not a conflict in Hw?
A
r2[a107] → r1[a107]
B
r2[a107] → w1[a107]
C
r1[a107] → w2[a107]
D
w1[a107] → w2[a107]
P.J. Mc.Brien (Imperial College London) Concurrency Control 21 / 46
Serialisability
Conflict Equivalence and Conflict Serialisable
Conflict Equivalence
Two histories Hi and Hj are conflict equivalent if:
1 Contain the same set of operations
2 Order conflicts (of non-aborted transactions) in the same way.
Conflict Serialisable
a history H is conflict serialisable (CSR) if C(H) ≡CE a serial history
Failure to be conflict serialisable
Hx = r2[b34] , r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1 , w2[b34] , r2[b67] , w2[b67] , c2
Contains conflicts r2[b34] → w1[b34] and w1[b34] → w2[b34] and so is not conflict
equivalence to H1,H2 nor H2,H1, and hence is not conflict serialisable.
P.J. Mc.Brien (Imperial College London) Concurrency Control 22 / 46
Serialisability
Testing for Conflict Equivalence
Hcp = r1[b56] , r2[b34] , w2[b34] , w1[b56] , r4[b56] , r1[b34] ,
w1[b34] , c1 , r4[b34] , r2[b67] , w2[b67] , c2 , r4[b67] , c4
≡
H2 , H1 , H4 = r2[b34] , w2[b34] , r2[b67] , w2[b67] , c2 , r1[b56] ,
w1[b56] , r1[b34] , w1[b34] , c1 , r4[b56] , r4[b34] , r4[b67] , c4
1 Hcp and H2 , H1 , H4 contain the same set of operations
2 conflicting pairs are
w2[b34] → r1[b34] , w2[b67] → r4[b67] ,
w1[b34] → r4[b34] , w1[b56] → r4[b56]
3 H2 , H1 , H4 ≡CE Hcp → Hcp ∈ CSR
P.J. Mc.Brien (Imperial College London) Concurrency Control 23 / 46
Serialisability
Serialisation Graph
Serialisation Graph
A serialisation graph SG(H) contains a node for each transaction in H , and an
edge Ti → Tj if there is some object o for which a conflict rwi[o] → rwj [o] exists in H .
If SG(H) is acyclic, then H is conflict serialisable.
Demonstrating a History is CSR
Given Hcp= r1[b56] , r2[b34] , w2[b34] , w1[b56] , r4[b56] , r1[b34] , w1[b34] ,
c1 , r4[b34] , r2[b67] , w2[b67] , c2 , r4[b67] , c4
Conflicts are w2[b34] → r1[b34] , w2[b67] → r4[b67] , w1[b34] → r4[b34] ,
w1[b56] → r4[b56]
Then serialisation graph is
T1T2 T4✲ ✲
❘
SG(Hcp) is acyclic, therefore Hcp is CSR
P.J. Mc.Brien (Imperial College London) Concurrency Control 24 / 46
Serialisability
Worksheet: Serialisability
H1 = r1[o1] , w1[o1] , w1[o2] , w1[o3] , c1
H2 = r2[o2] , w2[o2] , w2[o1] , c2
H3 = r3[o1] , w3[o1] , w3[o2] , c3
H= r1[o1] , w1[o1] , r2[o2] , w2[o2] , w2[o1] , c2 , w1[o2] , r3[o1] , w3[o1] ,
w3[o2] , c3 , w1[o3] , c1
P.J. Mc.Brien (Imperial College London) Concurrency Control 25 / 46
Recoverability Definition
Recoverability
Serialisability necessary for isolation and consistency of committed transactions
Recoverability necessary for isolation and consistency when there are also
aborted transactions
Recoverable execution
A recoverable (RC) history H has no transaction committing before another
transaction from which it read
Execution avoiding cascading aborts
A history which avoids cascading aborts (ACA) does not read from a
non-committed transaction
Strict execution
A strict (ST) history does not read from a non-committed transaction nor write
over a non-committed transaction
ST ⊂ ACA ⊂ RC
P.J. Mc.Brien (Imperial College London) Concurrency Control 26 / 46
Recoverability Definition
Non-recoverable executions
BEGIN TRANSACTION T1
UPDATE branch
SET cash=cash-10000.00
WHERE sortcode=56
UPDATE branch
SET cash=cash+10000.00
WHERE sortcode=34
COMMIT TRANSACTION T1
H1 = r1[b56] , w1[b56] , a1
BEGIN TRANSACTION T4
SELECT SUM(cash) FROM branch
COMMIT TRANSACTION T4
H4 = r4[b56] , r4[b34] , r4[b67] , c4
Hc = r1[b56] , cash=94340.45, w1[b56] , cash=84340.45, r4[b56] , cash=84340.45,
r4[b34] , cash=8900.67, r4[b67] , cash=34005.00, c4 , a1
Hc 6∈ RC
P.J. Mc.Brien (Imperial College London) Concurrency Control 27 / 46
Recoverability Types of Recoverability
Cascading Aborts
BEGIN TRANSACTION T1
UPDATE branch
SET cash=cash-10000.00
WHERE sortcode=56
UPDATE branch
SET cash=cash+10000.00
WHERE sortcode=34
COMMIT TRANSACTION T1
H1 = r1[b56] , w1[b56] , a1
BEGIN TRANSACTION T4
SELECT SUM(cash) FROM branch
COMMIT TRANSACTION T4
H4 = r4[b56] , r4[b34] , r4[b67] , c4
Hc = r1[b56] , cash=94340.45, w1[b56] , cash=84340.45, r4[b56] , cash=84340.45,
r4[b34] , cash=8900.67, r4[b67] , cash=34005.00, a1 , a4
Hc ∈ RC
Hc 6∈ ACA
P.J. Mc.Brien (Imperial College London) Concurrency Control 28 / 46
Recoverability Types of Recoverability
Strict Execution
BEGIN TRANSACTION T5
UPDATE account
SET rate=5.5
WHERE type=’deposit’
COMMIT TRANSACTION T5
H5 = w5[a101] , rate=5.5,
w5[a119] , rate=5.5, a5
BEGIN TRANSACTION T6
UPDATE account
SET rate=6.0
WHERE type=’deposit’
COMMIT TRANSACTION T6
H6 = w6[a101] , rate=6.0,
w6[a119] , rate=6.0, c6
Hc = w6[a101] , rate=6.0, w5[a101] , rate=5.5,
w5[a119] , rate=5.5, w6[a119] , rate=6.0, a5 , c6
Hc ∈ ACA
Hc 6∈ ST
P.J. Mc.Brien (Imperial College London) Concurrency Control 29 / 46
Recoverability Types of Recoverability
Quiz 7: Recoverability
Hz = r2[b34] , w2[b34] , r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1 , r2[b67] , w2[b67] , c2
Which describes the recoverability of Hz?
A
Non-recoverable
B
Recoverable
C
Avoids Cascading Aborts
D
Strict
P.J. Mc.Brien (Imperial College London) Concurrency Control 30 / 46
Recoverability Types of Recoverability
Worksheet: Recoverability
Hw = r2[o1] , r2[o2] , w2[o2] , r1[o2] , w2[o1] , r2[o3] , c2 , c1
Hx = r2[o1] , r2[o2] , w2[o1] , w2[o2] , w1[o1] , w1[o2] , c1 , r2[o3] , c2
Hy = r2[o1] , r2[o2] , w2[o2] , r1[o2] , w2[o1] , c1 , r2[o3] , c2
Hz = r2[o1] , w1[o1] , r2[o2] , w2[o2] , r2[o3] , c2 , r1[o2] , w1[o2] , w1[o3] , c1
P.J. Mc.Brien (Imperial College London) Concurrency Control 31 / 46
Recoverability Types of Recoverability
Maintaining Serialisability and Recoverability
two-phase locking (2PL)
conflict based
uses locks to prevent problems
common technique
time-stamping
add a timestamp to each object
write sets timestamp to that of transaction
may only read or write objects with earlier timestamp
abort when object has new timestamp
common technique
optimistic concurrency control
do nothing until commit
at commit, inspect history for problems
good if few conflicts
P.J. Mc.Brien (Imperial College London) Concurrency Control 32 / 46
2PL Basic 2PL
The 2PL Protocol
1 read locks rl[o], . . . , r[o], . . . , ru[o]
2 write locks wl[o], . . . , w[o], . . . , wu[o]
3 Two phases
i growing phase
ii shrinking phase
4 refuse rli[o] if wlj [o] already held
refuse wli[o] if rlj [o] or wlj [o] already held
5 rli[o] or wli[o] refused → delay Ti
✲
time
✻
no.
locks
in Hi
bi ei
P.J. Mc.Brien (Imperial College London) Concurrency Control 33 / 46
2PL Basic 2PL
Quiz 8: Two Phase Locking (2PL)
Which history is not valid in 2PL?
A
rl1[a107] , r1[a107] , wl1[a107] , w1[a107] , wu1[a107] , ru1[a107]
B
wl1[a107] , wl1[a100] , r1[a107] , w1[a107] , r1[a100] , w1[a100] , wu1[a100] , wu1[a107]
C
wl1[a107] , r1[a107] , w1[a107] , wu1[a107] , wl1[a100] , r1[a100] , w1[a100] , wu1[a100]
D
wl1[a107] , r1[a107] , w1[a107] , wl1[a100] , r1[a100] , wu1[a107] , w1[a100] , wu1[a100]
P.J. Mc.Brien (Imperial College London) Concurrency Control 34 / 46
2PL Basic 2PL
Anomaly 1: Lost update
BEGIN TRANSACTION T1
EXEC move cash(56,34,10000.00)
COMMIT TRANSACTION T1
r1[b56] , w1[b56] , r1[b34] , w1[b34] , c1
BEGIN TRANSACTION T2
EXEC move cash(34,67,2000.00)
COMMIT TRANSACTION T2
r2[b34] , w2[b34] , r2[b67] , w2[b67] , c2
r1[b56] , cash=94340.45, w1[b56] , cash=84340.45, r1[b34] , cash=8900.67,
r2[b34] , cash=8900.67, w1[b34] , cash=18900.67lostupdate, c1 , w2[b34] , cash=6900.42
r2[b67] , cash=34005.00, w2[b67] , cash=36005.25, c2
− serialisable + recoverable
P.J. Mc.Brien (Imperial College London) Concurrency Control 35 / 46
2PL Basic 2PL
Lost Update Anomoly with 2PL
BEGIN TRANSACTION T1
EXEC move cash(56,34,10000.00)
COMMIT TRANSACTION T1
b1 , wl1[b56] , r1[b56] , w1[b56] , wl1[b34] ,
r1[b34] , w1[b34] , c1 , wu1[b56] , wu1[b34]
BEGIN TRANSACTION T2
EXEC move cash(34,67,2000.00)
COMMIT TRANSACTION T2
b2 , wl2[b34] , r2[b34] , w2[b34] , wl2[b67] ,
r2[b67] , w2[b67] , c2 , wu2[b34] , wu2[b67]
b1 , wl1[b56] , r1[b56] , w1[b56] , wl1[b34] , r1[b34] , b2 , wl2[b34] , r2[b34] , w1[b34] , c1 ,
wu1[b56] , wu1[b34] , w2[b34] , wl2[b67] , r2[b67] , w2[b67] , c2 , wu2[b34] , wu2[b67]
Lost Update history not permitted by 2PL, since wl2[b34] not granted
P.J. Mc.Brien (Imperial College London) Concurrency Control 36 / 46
2PL Basic 2PL
Lost Update Anomoly with 2PL
BEGIN TRANSACTION T1
EXEC move cash(56,34,10000.00)
COMMIT TRANSACTION T1
b1 , wl1[b56] , r1[b56] , w1[b56] , wl1[b34] ,
r1[b34] , w1[b34] , c1 , wu1[b56] , wu1[b34]
BEGIN TRANSACTION T2
EXEC move cash(34,67,2000.00)
COMMIT TRANSACTION T2
b2 , wl2[b34] , r2[b34] , w2[b34] , wl2[b67] ,
r2[b67] , w2[b67] , c2 , wu2[b34] , wu2[b67]
b1 , wl1[b56] , r1[b56] , w1[b56] , wl1[b34] , r1[b34] , b2 , w1[b34] , c1 , wu1[b56] , wu1[b34] ,
wl2[b34] , r2[b34] , w2[b34] , wl2[b67] , r2[b67] , w2[b67] , c2 , wu2[b34] , wu2[b67]
2PL causes T2 to be delayed
P.J. Mc.Brien (Imperial College London) Concurrency Control 36 / 46
2PL Basic 2PL
Why does 2PL Work?
✲
time
✻
no. locks
bi eibj ej
Hi Hj
two-phase rule → maximum lock period
can re-time history so all operations take place during maximum lock period
CSR since all conflicts prevented during maximum lock period
P.J. Mc.Brien (Imperial College London) Concurrency Control 37 / 46
2PL Scheduling
When to lock: Aggressive Scheduler
b1, r1[b56], w1[b56], r1[b34], w1[b34], c1
rl1[b56]
⇓
wl1[b56]
⇓
rl1[b34]
wl1[b56]
⇓
wl1[b34]
wl1[b56]
⇓
wl1[b34]
wl1[b56]
⇓
∅
⇓
delay taking locks as long as possible
maximises concurrency
might suffer delays later on
P.J. Mc.Brien (Imperial College London) Concurrency Control 38 / 46
2PL Scheduling
When to lock: Conservative Scheduler
b2, r2[b34], w2[b34], r2[b67], w2[b67], c2
wl2[b34]
wl2[b67]
⇓
wl2[b34]
wl2[b67]
⇓
wl2[b67]
⇓
wl2[b67]
⇓
∅
⇓
take locks as soon as possible
removes risks of delays later on
might refuse to start
P.J. Mc.Brien (Imperial College London) Concurrency Control 39 / 46
2PL 2PL Implementation
Deadlock Detection: WFG with No Cycle = No Deadlock
b1 r1[b56] w1[b56] b2 r2[b34] w2[b34]
rl1[b56]
⇓
wl1 [b56]
⇓
wl1[b56]
⇓
rl2[b34]
wl1[b56]
⇓
wl2[b34]
wl1[b56]
⇓
H1 H2
waits-for graph (WFG)
describes which transactions waits for others
P.J. Mc.Brien (Imperial College London) Concurrency Control 40 / 46
2PL 2PL Implementation
Deadlock Detection: WFG with No Cycle = No Deadlock
b1 r1[b56] w1[b56] b2 r2[b34] w2[b34]
rl1[b56]
⇓
wl1 [b56]
⇓
wl1[b56]
⇓
rl2[b34]
wl1[b56]
⇓
wl2[b34]
wl1[b56]
⇓
H1 H2
rl1[b34]
❘
H1 attempts r1[b34] , but is refused since H2 has a write-lock, and so is put on WFG
waits-for graph (WFG)
describes which transactions waits for others
P.J. Mc.Brien (Imperial College London) Concurrency Control 40 / 46
2PL 2PL Implementation
Deadlock Detection: WFG with No Cycle = No Deadlock
b1 r1[b56] w1[b56] b2 r2[b34] w2[b34] r2[b67] w2[b67] c2
rl1[b56]
⇓
wl1 [b56]
⇓
wl1[b56]
⇓
rl2[b34]
wl1[b56]
⇓
wl2[b34]
wl1[b56]
⇓
rl2[b67]
wl2[b34]
wl1[b56]
⇓
wl2[b67]
wl2[b34]
wl1[b56]
⇓
wl2[b67]
wl2[b34]
wl1[b56]
⇓
wl1[b56]
⇓
H1 H2
rl1[b34]
❘
H2 can proceed to complete its execution, after which it will have released all its locks
waits-for graph (WFG)
describes which transactions waits for others
P.J. Mc.Brien (Imperial College London) Concurrency Control 40 / 46
2PL 2PL Implementation
Deadlock Detection: WFG with No Cycle = No Deadlock
b1 r1[b56] w1[b56] b2 r2[b34] w2[b34] r2[b67] w2[b67] c2 r1[b34] w1[b34] c1
rl1[b56]
⇓
wl1 [b56]
⇓
wl1[b56]
⇓
rl2[b34]
wl1[b56]
⇓
wl2[b34]
wl1[b56]
⇓
rl2[b67]
wl2[b34]
wl1[b56]
⇓
wl2[b67]
wl2[b34]
wl1[b56]
⇓
wl2[b67]
wl2[b34]
wl1[b56]
⇓
wl1[b56]
⇓
rl1[b34]
wl1[b56]
⇓
wl1 [b34]
wl1 [b56]
⇓
wl1[b34]
wl1[b56]
⇓
H1
waits-for graph (WFG)
describes which transactions waits for others
P.J. Mc.Brien (Imperial College London) Concurrency Control 40 / 46
2PL 2PL Implementation
Deadlock Detection: WFG with Cycle = Deadlock
b1 r1[b56] w1[b56] r1[b34] b2 r2[b34]
dead-
lock
rl1[b56]
⇓
wl1[b56]
⇓
rl1[b34]
wl1[b56]
⇓
rl1[b34]
wl1[b56]
⇓
rl2[b34]
rl1[b34]
wl1[b56]
⇓
rl2[b34]
rl1[b34]
wl1[b56]
⇓
H1 H2
wl1[b34]
❘
wl2[b34]
■
Cycle in WFG means DB in a deadlock state, must abort either H1 or H2
P.J. Mc.Brien (Imperial College London) Concurrency Control 41 / 46
2PL 2PL Implementation
Quiz 9: Resolving Deadlocks in 2PL
H1 = r1[p1] , r1[p2] , r1[p3] , r1[p4] , r1[p5] , r1[p6]
H2 = r2[p5] , w2[p5] , r2[p1] , w2[p1]
H3 = r3[p6] , w3[p6] , r3[p2] , w3[p2]
H4 = r4[p4] , r4[p5] , r4[p6]
Suppose the transactions above have reached the following deadlock state
Hd = r1[p1] , r1[p2] , r1[p3] , r1[p4] , r2[p5] , w2[p5] , r2[p1] ,
r3[p6] , w3[p6] , r3[p2] , r4[p4]
Which transaction should be aborted?
A
H1
B
H2
C
H3
D
H4
P.J. Mc.Brien (Imperial College London) Concurrency Control 42 / 46
2PL 2PL Implementation
Worksheet: Deadlocks
H1 = w1[o1] , r1[o2] , r1[o4]
H2 = r2[o3] , r2[o2] , r2[o1]
H3 = r3[o4] , w3[o4] , r3[o3] , w3[o3]
P.J. Mc.Brien (Imperial College London) Concurrency Control 43 / 46
2PL 2PL Implementation
Conservative Locking
✲
time
✻
no. locks
in Hi
bi ei
Conservative Locking
prevents deadlock
when to release locks problem
not recoverable
P.J. Mc.Brien (Imperial College London) Concurrency Control 44 / 46
2PL 2PL Implementation
Strict Locking
✲
time
✻
no.
locks
in Hi
bi ei
❄
only release read
locks before ei
strict locking
✲
time
✻
no.
locks
in Hi
bi eistrong strict locking
Strict Locking
prevents write locks being released before transaction end
recoverable (with cascading aborts) but allows deadlocks
Strong Strict Locking
no locks released before end → recoverable
allows deadlocks
no problem determining when to release locks
suitable for distributed transactions (using atomic commit)
P.J. Mc.Brien (Imperial College London) Concurrency Control 45 / 46
Isolation Levels Need for Serialisability?
Transaction Isolation Levels
Do we always need ACID properties?
BEGIN TRANSACTION T3
SELECT DISTINCT no
FROM movement
WHERE amount>=1000.00
COMMIT TRANSACTION T3
Some transactions only need ‘approximate’ results
e.g. Management overview
e.g. Estimates
May execute these transactions at a ‘lower’ level of concurrency control
SQL allows you to vary the level of concurrency control
P.J. Mc.Brien (Imperial College London) Concurrency Control 46 / 46
Transactions
ACID properties
Concurrency
Definition
Anomalies
Serialisability
Recoverability
Definition
Types of Recoverability
2PL
Basic 2PL
Scheduling
2PL Implementation
Isolation Levels
Need for Serialisability?