Transcript CC2

Concurrency Control II
General Overview
 Relational model - SQL
 Formal & commercial query languages
 Functional Dependencies
 Normalization
 Physical Design
 Indexing
 Query Processing and Optimization
 Transaction Processing and CC
Database System Concepts
15.2
Review: AC[I]D
 Isolation
 Concurrent xctions unaware of each other
 How?
 Serial execution of transactions
 Poor Throughput and response time
 Ensure concurrency
 Prevent “bad” concurrency and allow only “good” concurrency
through analysis of “schedules”
 Allow only “conflict serializable” schedules: schedules that are
equivalent to (some) serial schedules.
 Precedence graph: If PS is acyclic  confl. serializable schedule
Database System Concepts
15.3
How to enforce serializable schedules?
prevent P(S) cycles from occurring using a concurrency control
manager: ensures interleaving of operations amongst
concurrent xctions only result in serializable schedules.
T1 T2 …..
Tn
CC Scheduler
DB
Database System Concepts
15.4
Anomalies with Interleaved Execution
 Reading Uncommitted Data (WR Conflicts, “dirty reads”):
 Unrepeatable Reads (RW Conflicts):
T1:
T2:
R(A), W(A),
T1:
T2:
R(A),
Database System Concepts
R(A), W(A), C
R(A), W(A), C
R(B), W(B), Abort
R(A), W(A), C
15.5
Anomalies (Continued)
 Overwriting Uncommitted Data (WW Conflicts):
T1:
T2:
W(A),
W(A), W(B), C
W(B), C
Solution: Use appropriate CC Protocols to achieve serializable schedules
Database System Concepts
15.6
Agenda
 2PL and variants
 Timestamp-based
 Optimistic CC: Validation-based protocols
 Multiple granularity
 Multi-version
 Weaker Consistency (other than serializability)
 Dealing with Deadlocks
Database System Concepts
15.7
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). Locks
can be either X, or S/X.
Database System Concepts
15.8
Lock-Based Concurrency Control
 Strict Two-phase Locking (Strict 2PL) Protocol:

Each Xact must obtain a S (shared) lock on object before reading, and an X
(exclusive) lock on object before writing.

All locks held by a transaction are released when the transaction completes

If an Xact holds an X lock on an object, no other Xact can get a lock (S or X)
on that object.
 Strict 2PL allows only serializable schedules.
 Has no cascading rollbacks (as locks are released only when txn completes)
Database System Concepts
15.9
Agenda
 2PL and variants
 Timestamp-based
 Optimistic CC: Validation-based protocols
 Multiple granularity
 Multi-version
 Weaker Consistency (other than serializability)
 Dealing with Deadlocks
Database System Concepts
15.10
Timestamp-Based Protocols
 Idea:

Decide in advance ordering of xctions

Ensure concurrent schedule serializes to serial order decided
 Timestamps
1. TS(Ti) is time Ti entered the system
2. Data item timestamps:
1. W-TS(Q): Largest timestamp of any xction that wrote Q
2. R-TS(Q): Largest timestamp of any xction that read Q
 Timestamps -> serializability order
Database System Concepts
15.11
Timestamp CC
 Idea: If action pi of Xact Ti conflicts with action qj of
Xact Tj, and TS(Ti) < TS(Tj), then pi must occur before
qj. Otherwise, restart violating Xact.
Database System Concepts
15.12
When Xact T wants to read Object O
 If TS(T) < W-TS(O), this violates timestamp order of T w.r.t. writer
of O.
 So, abort T and restart it with a new, larger TS. (If restarted with
same TS, T will fail again!)
 If TS(T) > W-TS(O):
 Allow T to read O.
 Reset R-TS(O) to max(R-TS(O), TS(T))
 Change to R-TS(O) on reads must be written to disk! This and
restarts represent overheads.
U writes O
T reads O
T start
Database System Concepts
U start
15.13
When Xact T wants to Write Object O
 If TS(T) < R-TS(Q), then the value of Q that T is producing was
needed previously, and the system assumed that that value would
never be produced. write rejected, T is rolled back.
 If TS(T) < W-TS(Q), then T is attempting to write an obsolete value
of Q. Hence, this write operation is rejected, and T is rolled back.
 Otherwise, the write operation is executed, and W-TS(Q) is set to
TS(T).
U reads Q
T writes Q
T start
Database System Concepts
U start
15.14
When Xact T wants to Write Object O
 If TS(T) < R-TS(Q), this violates timestamp order of T w.r.t. writer of
Q; abort and restart T.
 If TS(T) < WTS(Q), violates timestamp order of T w.r.t. writer of Q.
 Thomas Write Rule: We can safely ignore such outdated writes;
need not restart T! (T’s write is effectively followed by another
write, with no intervening reads.)
Allows some
serializable but non
conflict serializable schedules:
 Else, allow T to write O.
T1
R(A)
W(A)
Commit
Allows non-Conflict-serializable schedules
W(A)
Commit
Database System Concepts
15.15
T2
How Locking works in practice
Ti
Read(A),Write(B)
lock
table
Scheduler, part I
l(A),Read(A),l(B),Write(B)…
Scheduler, part II
Read(A),Write(B)
DB
Database System Concepts
15.16
Agenda
 2PL and variants
 Timestamp-based
 Optimistic CC: Validation-based protocols
 Multiple granularity
 Multi-version
 Weaker Consistency (other than serializability)
 Dealing with Deadlocks
Database System Concepts
15.17
Optimistic CC (Kung-Robinson)
 Locking is a conservative approach in which conflicts are
prevented. Disadvantages:
 Lock management overhead.
 Deadlock detection/resolution.
 Lock contention for heavily used objects.
 If conflicts are rare, we might be able to gain concurrency by not
locking, and instead checking for conflicts before Xacts commit.
Database System Concepts
15.18
Optimistic CC: Kung-Robinson Model
 Xacts have three phases:
 READ: Xacts read from the database, but make changes to
private copies of objects.
 VALIDATE: Check for conflicts.
 WRITE: Make local copies of changes public.
old
modified
objects
Database System Concepts
ROOT
new
15.19
Validation
 Test conditions that are sufficient to ensure that no conflict
occurred.
 Each Xact is assigned a numeric id.
 Just use a timestamp.
 Xact ids assigned at end of READ phase, just before validation
begins. (Why then?)
 ReadSet(Ti): Set of objects read by Xact Ti.
 WriteSet(Ti): Set of objects modified by Ti.
Database System Concepts
15.20
Test 1
 For all i and j such that Ti < Tj, check that Ti completes before Tj
begins.
Ti
R
V
Tj
W
R
Database System Concepts
15.21
V
W
Test 1
 For all i and j such that Ti < Tj, check that Ti completes before Tj
begins.
Ti
R
V
Tj
W
R
Database System Concepts
15.22
V
W
Test 2
 For all i and j such that Ti < Tj, check that:
 Ti completes before Tj begins its Write phase +
 WriteSet(Ti)
Ti
R
ReadSet(Tj) is empty.
V
W
R
V
W
Tj
Does Tj read dirty data? Does Ti overwrite Tj’s writes?
Database System Concepts
15.23
Test 3
 For all i and j such that Ti < Tj, check that:
 Ti completes Read phase before Tj does +
Ti
 WriteSet(Ti)
ReadSet(Tj) is empty +
 WriteSet(Ti)
WriteSet(Tj) is empty.
R
V
R
W
V
W
Tj
Does Tj read dirty data? Does Ti overwrite Tj’s writes?
Database System Concepts
15.24
Example of what validation must prevent:
RS(T2)={B}
WS(T2)={B,D}
T2
start
T3
start

RS(T3)={A,B} =

WS(T3)={C}
T2
T3
validated
validated
time
Database System Concepts
15.25
Example of what validation must allow:
RS(T2)={B}
WS(T2)={B,D}
T2
start
T3
start

RS(T3)={A,B}
WS(T3)={C}
T2
T3
validated
validated
T2
finish
phase 3
Database System Concepts
=
15.26
T3
start
time
Another thing validation must prevent:
RS(T2)={A}
RS(T3)={A,B}
WS(T2)={D,E} WS(T3)={C,D}
T2
validated
T3
validated
finish
BAD: w3(D) w2(D)
Database System Concepts
15.27
T2
time
Another thing validation must allow:
RS(T2)={A}
RS(T3)={A,B}
WS(T2)={D,E} WS(T3)={C,D}
T2
T3
validated
Database System Concepts
validated
finish
finish
T2
T2
15.28
time
Comments on Serial Validation
 Assignment of Xact id, validation, and the Write phase are inside
a critical section!
 I.e., Nothing else goes on concurrently.
 If Write phase is long, major drawback.
 Optimization for Read-only Xacts:
 Don’t need critical section (because there is no Write phase).
Database System Concepts
15.29
Overheads in Optimistic CC
 Must record read/write activity in ReadSet and WriteSet per Xact.
 Must create and destroy these sets as needed.
 Must check for conflicts during validation, and must make validated
writes ``global’’.
 Critical section can reduce concurrency.
 Scheme for making writes global can reduce clustering of objects.
 Optimistic CC restarts Xacts that fail validation.
 Work done so far is wasted; requires clean-up.
Database System Concepts
15.30
``Optimistic’’ 2PL
 If desired, we can do the following:
 Set S locks as usual.
 Make changes to private copies of objects.
 Obtain all X locks at end of Xact, make writes global, then
release all locks.
 In contrast to Optimistic CC as in Kung-Robinson, this scheme
results in Xacts being blocked, waiting for locks.
 However, no validation phase, no restarts (modulo deadlocks).
Database System Concepts
15.31
Agenda
 2PL and variants
 Timestamp-based
 Optimistic CC: Validation-based protocols
 Multiple granularity
 Multi-version
 Weaker Consistency (other than serializability)
 Dealing with Deadlocks
Database System Concepts
15.32
Multiple Granularity
 Allow data items to be of various sizes and define a hierarchy of
data granularities, where the small granularities are nested within
larger ones
 When a transaction locks a node in the hierarchy explicitly, it
implicitly locks all the node's descendents in the same mode.
Database
contains
Tables
Pages
Tuples
Database System Concepts
15.33
Multiple Granularity
 If we lock large objects (e.g., Relations)
 Need few locks
 Low concurrency
 If we lock small objects (e.g., tuples,fields)
 Need more locks
 More concurrency
Database System Concepts
15.34
Example of Granularity Hierarchy
The highest level in the example hierarchy is the entire database.
The levels below are of type area, file or relation and record in that
order.
Database System Concepts
15.35
Multiple-Granularity Locks
 Hard to decide what granularity to lock (tuples vs. pages vs.
tables).
 Shouldn’t have to decide!
 Data “containers” are nested:
Database
contains
Tables
Pages
Tuples
Database System Concepts
15.36
Solution: New Lock Modes, Protocol
 Allow Xacts to lock at each level, but with a special protocol
using new “intention” locks:
Before locking an item, Xact
must set “intention locks”
on all its ancestors.
 For unlock, go from specific
to general (i.e., bottom-up).
 SIX mode: Like S & IX at
the same time.
 Scanning the table but
updating few rows

Database System Concepts
15.37
--
IS IX S
X





IS 



IX 





--
S
X

Multiple Granularity Lock Protocol
 Each Xact starts from the root of the hierarchy.
 To get S or IS lock on a node, must hold IS or IX on parent node.
 What if Xact holds SIX on parent? S on parent?
 To get X or IX or SIX on a node, must hold IX or SIX on parent node.
 Must release locks in bottom-up order.
Protocol is correct in that it is equivalent to directly setting
locks at the leaf levels of the hierarchy.
Database System Concepts
15.38
Compatibility Matrix with
Intention Lock Modes
 The compatibility matrix for all lock modes is:
requestor
IS
IX
S
S IX
IS





IX





S





S IX





X





holder
Database System Concepts
15.39
X
Parent
locked in
IS
IX
S
SIX
X
Database System Concepts
Child can be
locked in
IS, S
IS, S, IX, X, SIX
[S, IS] not necessary
X, IX, [SIX]
none
15.40
P
C
Example
T1(IS) , T2(IX)
R1
t1
t2
t3
T2(X)
T1(S)
Database System Concepts
t4
15.41
Multiple Granularity Locking Scheme
 Transaction Ti can lock a node Q, using the following rules:
(1) Follow multiple granularity comp function
 Lock root of tree first, any mode
 Node Q can be locked by Ti in S or IS only if
parent(Q) can be locked by Ti in IX or IS
 Node Q can be locked by Ti in X,SIX,IX only
if parent(Q) locked by Ti in IX,SIX
(2) Ti is two-phase (2PL)
(3) Ti can unlock node Q only if none of Q’s
children are 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
15.42
Examples
T1(IX)
T1(IS)
R
R
T1(IX)
t3
t2
t1
T1(S)
t4
t3
t2
t1
t4
T1(X)
f2.1
f2.2
f4.2
f4.2
f2.1
Can T2 access object f2.2 in X mode?
What locks will T2 get?
 Parent
Child
 IS
IS,S
 IX
IS,S, IX, X, SIX
 S
[S, IS] not necessary
 SIX
X, IX, [SIX]
 X
Database System Concepts
f4.2
f2.2
T1(SIX)
R
T1(IX)
t2
t1
t3
t4
T1(X)
f2.1
none
15.43
f2.2
f4.2
f4.2
f4.2
Agenda
 2PL and variants
 Timestamp-based
 Optimistic CC: Validation-based protocols
 Multiple granularity
 Multi-version
 Weaker Consistency (other than serializability)
 Dealing with Deadlocks
Database System Concepts
15.44
Multiversion Schemes
 Multiversion schemes keep old versions of data item to increase
concurrency.
 Multiversion Timestamp Ordering
 Multiversion Two-Phase Locking
 Each successful write results in the creation of a new version of
the data item written.
 Use timestamps to label versions.
 When a read(Q) operation is issued, select an appropriate
version of Q based on the timestamp of the transaction, and
return the value of the selected version.
 reads never have to wait as an appropriate version is returned
immediately.
Database System Concepts
15.45
More on Consistency
 We have seen thus far: Serializability -- 2PL and timestamp
 Weaker levels of consistency
1. Degree-two consistency: differs from two-phase locking in that
S-locks may be released at any time, and locks may be acquired
at any time
 X-locks must be held till end of transaction
 Serializability is not guaranteed, programmer must ensure that no
erroneous database state will occur
2. Cursor stability:
 For reads, each tuple is locked, read, and lock is immediately
released
 X-locks are held till end of transaction
 Special case of degree-two consistency
Database System Concepts
15.46
Weak Levels of Consistency in SQL
 SQL allows non-serializable executions
 Serializable: is the default
 Repeatable read: allows only committed records to be read, and
repeating a read should return the same value (so read locks should
be retained)
 However, the phantom phenomenon need not be prevented
– T1 may see some records inserted by T2, but may not see
others inserted by T2
 Read committed: same as degree two consistency, but most
systems implement it as cursor-stability
 Read uncommitted: allows even uncommitted data to be read
 In many database systems (Oracle), Read Committed is the
default consistency level
 has to be explicitly changed to serializable when required
 set isolation level serializable
Database System Concepts
15.47
Agenda
 2PL and variants
 Timestamp-based
 Optimistic CC: Validation-based protocols
 Multiple granularity
 Multi-version
 Weaker Consistency (other than serializability)
 Dealing with Deadlocks
Database System Concepts
15.48
Dealing with Deadlocks
 Deadlock Prevention (read from the book)
 Deadlock detection; How do you detect a deadlock?
 Wait-for graph
T2
 Directed edge from Ti to Tj
T4
 Ti waiting for Tj
T1
T2
T3
T1
T4
T3
X(Z)
X(V)
X(W)
Suppose T4 requests lock-S(Z)....
S(V)
S(W)
S(V)
S(Z)
Database System Concepts
15.49
Detecting Deadlocks
 Wait-for graph has a cycle  deadlock
T2
T2, T3, T4 are deadlocked
T4
T1
•Build wait-for graph, check for cycle
T3
•How often?
- Tunable
Expect many deadlocks or many xctions involved
Run often to avoid aborts
Else run less often to reduce overhead
Database System Concepts
15.50
Recovering from Deadlocks
 Rollback one or more xction
 Which one?
 Rollback the cheapest ones
 Cheapest ill-defined
– Was it almost done?
– How much will it have to redo?
– Will it cause other rollbacks?
 How far?
– May only need a partial rollback
 Avoid starvation
– Ensure same xction not always chosen to break deadlock
 Simplest mechanism:
– Timeout : abort after a lengthy wait time
Database System Concepts
15.51
Concurrency Control : Summary
 2PL, Strict 2PL,..
 Ensure Conflict-Serializable schedules
 Timestamp-based CC
 Thomas-Write Rule: can give non Conflict-serializable schedules
 Optimistic CC
 No locking overheads but critical-section overheads
 Multiple Granularity
 Additional intention locks to lock ancestors before we lock leaves in
S or X modes.
 Release is always from leaf-to-root
 Multi-version: fast for reads
 Weaker versions
 Oracle default: Read Committed + Multi-version => high throughput
(patented technology)
Database System Concepts
15.52