Transcript Ch17: concurency control

Concurrency Control
Chapter 17
Modified by Donghui Zhang
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
1
Transactions

Concurrent execution of user programs is essential for
good DBMS performance.

Because disk accesses are frequent, and relatively slow, it is
important to keep the cpu humming by working on several
user programs concurrently.
A user’s program may carry out many operations on
the data retrieved from the database, but the DBMS is
only concerned about what data is read/written
from/to the database.
 A transaction is the DBMS’s abstract view of a user
program: a sequence of reads and writes.

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
2
ACID Properties of Transactions
Atomicity: all actions are carried out, or none.
 Consistency: each transaction preserves the
consistency of the database if executed by itself.
(The users make sure of this. E.g. transfer money…)
 Isolation: transactions are isolated from the effect of
concurrently scheduling other transactions.
 Durability: the effect of a committed transaction
should last, even if system crash before all changed
are flushed to disk.

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
3
Transaction Processing

Chapter 17: Concurrency Control
Consistency & Isolation
 Since the users guarantee consistency, we worry about
isolation.
 Serial schedule achieves this goal!

Chapter 18: Recovery
Atomicity & Durability
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
4
Scheduling Transactions
Serial schedule: Schedule that does not interleave the
actions of different transactions.
 Equivalent schedules: For any database state, the effect
(on the set of objects in the database) of executing the
first schedule is identical to the effect of executing the
second schedule.
 Serializable schedule: A schedule that is equivalent to
some serial execution of the transactions.
(Note: If each transaction preserves consistency, every
serializable schedule preserves consistency. )

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
5
Anomalies with Interleaved Execution

Reading Uncommitted Data (WR Conflicts,
“dirty reads”):
T1: R(A), W(A),
R(B), W(B), C
T2:
R(A), W(A), R(B), W(B), C

T1:
T2:
Unrepeatable Reads (RW Conflicts):
R(A),
R(A), W(A), C
R(A), W(A), C
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
6
Anomalies (Continued)

T1:
T2:
Overwriting Uncommitted Data (WW
Conflicts):
W(A),
W(A), W(B), C
W(B), C
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
7
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
•


(Non-strict) 2PL Variant: Release locks anytime, but cannot acquire
locks after releasing any lock.
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.
 Additionally, it simplifies transaction aborts
 (Non-strict) 2PL also allows only serializable schedules,
but involves more complex abort processing
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
8
Aborting a Transaction
If a transaction Ti is aborted, all its actions have to be
undone. Not only that, if Tj reads an object last
written by Ti, Tj must be aborted as well!
 Most systems avoid such cascading aborts by releasing
a transaction’s locks only at commit time.



If Ti writes an object, Tj can read this only after Ti commits.
In order to undo the actions of an aborted transaction,
the DBMS maintains a log in which every write is
recorded. This mechanism is also used to recover
from system crashes: all active Xacts at the time of the
crash are aborted when the system comes back up.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
9
Conflict Serializable Schedules

Two schedules are conflict equivalent if:



Involve the same actions of the same transactions
Every pair of conflicting actions is ordered the
same way
Schedule S is conflict serializable if S is
conflict equivalent to some serial schedule
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
10
Example


Conflict serializable  serializable.
Serializable  conflict serializable
T1: R(A)
W(A), Commit
T2:
W(A), Commit
T3:
W(A), Commit
T1
T3
T2
precedence graph:
1. a node for each transaction
2. an arc from Ti to Tj if an
action in Ti precedes and
conflicts with an action in
Tj.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
11
Precedence Graph
Precedence graph: One node per Xact; edge
from Ti to Tj if Tj has an action which
conflicts with an earlier action in Ti.
 Two actions conflict, if RW, WR, WW of the
same item.
 Theorem: Schedule is conflict serializable if
and only if its precedence graph is acyclic

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
12
Strict 2PL & 2PL
Strict 2PL allows only schedules whose
precedence graph is acyclic.
 Same with 2PL.

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
13
Lock Management


Lock and unlock requests are handled by the lock
manager
Lock table entry:





Number of transactions currently holding a lock
Type of lock held (shared or exclusive)
Pointer to queue of lock requests
Locking and unlocking have to be atomic operations
Lock upgrade: transaction that holds a shared lock
can be upgraded to hold an exclusive lock
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
14
Deadlocks
Deadlock: Cycle of transactions waiting for
locks to be released by each other.
 Two ways of dealing with deadlocks:



Deadlock prevention
Deadlock detection
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
15
Deadlock Prevention

Assign priorities based on timestamps.
Assume Ti wants a lock that Tj holds. Two
policies are possible:



Wait-Die: It Ti has higher priority, Ti waits for Tj;
otherwise Ti aborts
Wound-wait: If Ti has higher priority, Tj aborts;
otherwise Ti waits
If a transaction re-starts, make sure it has its
original timestamp
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
16
Deadlock Detection

Create a waits-for graph:



Nodes are transactions
There is an edge from Ti to Tj if Ti is waiting for Tj
to release a lock
Periodically check for cycles in the waits-for
graph
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
17
Multiple-Granularity Locks
Why? If a transaction needs to scan all
records in a table, do we really want to have a
lock on all tuples individually? Significant
locking overhead!
 Put a single lock on the table!

Database
contains
Tables
Pages
A lock on a node
implicitly locks
all decendents.
Tuples
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
18
Motivation for intension locks
Besides scanning through the table, if we
need to modify a few tuples. What kind of
lock to put on the table?
 Have to be X (if we only have S or X).
 But, blocks all other read requests!

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
19
Solution: New Lock Modes, Protocol
Allow intention locks IS, IX.
 Before S locking an item, must IS lock the root.
 Before X locking an item, must IX lock the root.
 Should make sure:

 If Ti S lock a node, no Tj can X lock an ancestor.
• Achieved if S conflicts with IX.
 If Tj X lock a node, no Ti can S or X lock an ancestor.
• Achieved if X conflicts with IS and IX.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
20
Allowed Sharings
--
IS
IX
S
--




IS




IX



S


X

X


Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
21
Other Notes of the Protocol
May have a separate lock on each level,
where a lower level has a stronger lock.
?? stronger relationship among S, X, IS, IX?
 For unlock, go from specific to general (i.e.,
bottom-up).
?? Why?
 SIX mode: S & IX at the same time.
?? conflicts with what?
?? new lattice of locks?

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
22
Multiple Granularity Lock Protocol


Each Xact starts from the root of the hierarchy.
To get a lock on any node, must hold an intentional lock
on its parent node!
 E.g. to get S lock on a node, must hold IS or IX on parent.
 E.g. to get X lock on a node, must hold IX or SIX on parent.
 Note: having a lock on a node means to have the lock on all
descendant nodes. (Unlike B+-tree).

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 Management Systems 3ed, R. Ramakrishnan and J. Gehrke
23
Examples

T1 scans R, and updates a few tuples:
 T1 gets an SIX lock on R, and occasionally
upgrades to X on the tuples.

T2 uses an index to read only part of R:
 T2 gets an IS lock on R, and repeatedly
gets an S lock on tuples of R.

T3 reads all of R:
 T3 gets an S lock on R.
 OR, T3 could behave like T2; can
use lock escalation to decide which.
--
IS IX S
X





IS 



IX 





--
S
X
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke

24
Dynamic Databases

If we relax the assumption that the DB is a fixed
collection of objects, even Strict 2PL will not assure
serializability:
 T1 locks all pages containing sailor records with rating = 1,
and finds oldest sailor (say, age = 71).
 Next, T2 inserts a new sailor; rating = 1, age = 96.
 T2 also deletes oldest sailor with rating = 2 (and, say, age =
80), and commits.
 T1 now locks all pages containing sailor records with rating
= 2, and finds oldest (say, age = 63).

No consistent DB state where T1 is “correct”!
T1T2: 71,80. T2T1: 96,63. Actual: 71,63.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
25
The Problem

T1 implicitly assumes that it has locked the
set of all sailor records with rating = 1.
 Assumption only holds if no sailor records are
added while T1 is executing!
 Need some mechanism to enforce this
assumption. (Index locking)

Example shows that conflict serializability
guarantees serializability only if the set of
objects is fixed!
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
26
Data
Index Locking
If there is no suitable index, T1 must lock the
whole table to prevent new records with
rating = 1 being added and records with
rating=2 being deleted.
 If we have an index on rating, we can lock the
index nodes.

Index
Put a lock here.
r=1
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
27
Locking in B+ Trees

How can we efficiently lock a particular leaf
node?
 Btw, don’t confuse this with multiple granularity
locking!
One solution: Ignore the tree structure, just lock
pages while traversing the tree, following 2PL.
 This has terrible performance!

 Root node (and many higher level nodes) become
bottlenecks because every tree access begins at the
root.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
28
Two Useful Observations
Higher levels of the tree only direct searches
for leaf pages.
 For inserts, a node on a path from root to
modified leaf must be locked (in X mode, of
course), only if a split can propagate up to it
from the modified leaf. (Similar point holds
w.r.t. deletes.)
 We can exploit these observations to design
efficient locking protocols that guarantee
serializability even though they violate 2PL.

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
29
Tree Locking Algorithm
Search: Start at root and go down;
repeatedly, S lock child then unlock parent.
 Insert/Delete: Start at root and go down,
obtaining X locks as needed. Once child is
locked, check if it is safe:

 If child is safe, release all locks on ancestors.

Safe node: Node such that changes will not
propagate up beyond this node.
 Inserts: Node is not full.
 Deletes: Node is not half-empty.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
30
ROOT
A
20
Example
B
35
F
23
H
G
20*
22*
23*
24*
38
44
I
35*
Do:
1) Search 38*
2) Delete 38*
3) Insert 45*
4) Insert 25*
36*
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
C
D
38*
41*
E
44*
31
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 Management Systems 3ed, R. Ramakrishnan and J. Gehrke
32
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 Management Systems 3ed, R. Ramakrishnan and J. Gehrke
ROOT
new
33
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.
 ReadSet(Ti): Set of objects read by Xact Ti.
 WriteSet(Ti): Set of objects modified by Ti.

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
34
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 Management Systems 3ed, R. Ramakrishnan and J. Gehrke
V
W
35
Test 2

For all i and j such that Ti < Tj, check that:
 Ti completes before Tj begins its Write phase +
 WriteSet(Ti)
ReadSet(Tj) is empty.
Ti
R
V
W
R
V
W
Tj
Does Tj read dirty data? Does Ti overwrite Tj’s writes?
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
36
Test 3

For all i and j such that Ti < Tj, check that:
 Ti completes Read phase before Tj does +
 WriteSet(Ti)
ReadSet(Tj) is empty +
 WriteSet(Ti)
WriteSet(Tj) is empty.
Ti
R
V
R
W
V
W
Tj
Does Tj read dirty data? Does Ti overwrite Tj’s writes?
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
37
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 Management Systems 3ed, R. Ramakrishnan and J. Gehrke
38
Timestamp CC

Idea: Give each object a read-timestamp
(RTS) and a write-timestamp (WTS), give
each Xact a timestamp (TS) when it begins:
 If action ai of Xact Ti conflicts with action aj
of Xact Tj, and TS(Ti) < TS(Tj), then ai must
occur before aj. Otherwise, restart
violating Xact.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
39
When Xact T wants to read Object O

If TS(T) < WTS(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! Contrast
use of timestamps in 2PL for ddlk prevention.)
If TS(T) > WTS(O):
 Allow T to read O.
 Reset RTS(O) to max(RTS(O), TS(T))
 Change to RTS(O) on reads must be written to
disk! This and restarts represent overheads.

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
40
When Xact T wants to Write Object O
If TS(T) < RTS(O), this violates timestamp order
of T w.r.t. writer of O; abort and restart T.
 If TS(T) < WTS(O), violates timestamp order of
T w.r.t. writer of O.

 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.)
T1
T2
Allows some serializable but non R(A)
conflict serializable schedules:
W(A)
Commit
 Else, allow T to write O.
W(A)
Commit
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
41