Transcript slides2

Database Isolation
Levels
Reading

Farkas
Database Isolation Levels, lecture
notes by Dr. A. Fekete,
http://www.authorstream.com/P
resentation/AustralianComputer
So-256648-ACS-Frontiers-ICTResearch-13-October-2009-iEducation-ppt-powerpoint/
CSCE 824 - Spring 2013
2
Serializability

Serial execution
Conflict serializable
1-Copy Serializable

Cost of properties!


Farkas
CSCE 824 - Spring 2013
3
Problems



Farkas
Dirty read: read a data item that might
subsequently be rolled back (e.g., aborted
transaction)
Unrepeatable read: read an item twice
during a transaction and get different
results, even though the transaction did not
change the value of the data item
Phantoms: retrieve a collection of objects
twice in a transaction and get different
results even though the transaction did not
change any of the data
CSCE 824 - Spring 2013
4
Database Isolation Levels




Farkas
Serializable
Repeatable read
Read committed
Read un-commited
CSCE 824 - Spring 2013
5
Properties of isolation
levels
Isolation
level
Dirty read
Nonrepeatable
read
phantoms
Serializable
Not allowed
Not allowed
Not allowed
Repeatable
read
Not allowed
Not allowed
Allowed
Read
Committed
Not allowed
Allowed
Allowed
Allowed
Allowed
Read
Allowed
Uncommitted
Farkas
CSCE 824 - Spring 2013
6
Timestamp Ordering



Farkas
Each transaction is assigned a
unique timestamp
Ordering rule: if pi[x] and qj[x]
are conflicting than pi[x] is
processed before qj[x] iff TS(Ti) <
TS(Tj)
Timestamp ordering produces
serializable histories.
CSCE 824 - Spring 2013
7
Timestamp ordering




Farkas
Scheduler: maintains for every item
the max. TS of reads and writes
If an operation pi[x] arrives after the
scheduler submitted qj[x] conflicting
operation, Ti is aborted.
Note: Ti may be resubmitted with a
new, larger TS
Problem: Not strict (not recoverable
and does not avoid cascading aborts)
CSCE 824 - Spring 2013
8
Timestamp Ordering




Farkas
r2[x] w2[x] r1[x]
T1 is aborted
Why?
Could be just give a pre-T2 value
for T1? r1[x] r2[x] w2[x] is OK
CSCE 824 - Spring 2013
9
Multiversion
Timestamp Ordering



Farkas
Multiversion schemes keep old versions of
data item to increase concurrency
– Multiversion Timestamp Ordering
– Multiversion Two-Phase Locking
Write: a new version of the data item written
(timestamped)
Read: select an appropriate version based on
the timestamp of the transaction and return
the value of the selected
CSCE 824 - Spring 2013
10
Multiversion
Timestamp Ordering




Farkas
Each data item d has a sequence of versions <d1,
d2,...., dm>.
Each version dk contains:
– Content: the value of version dk
– W-timestamp(dk): timestamp of the transaction
that wrote dk
– R-timestamp(dk): largest timestamp of a
transaction that read dk
Ti creates a new version dk :
– W-timestamp and R-timestamp are Ti-timestamp
Tj reads dk : R-timestamp of dk is updated to max(Tjtimestamps, R-timestamp(dk))
CSCE 824 - Spring 2013
11
MV Timestamp ordering


Farkas
Suppose : Ti issues a read(d) or write(d)
Let dk denote the version of d whose write timestamp
is the largest write timestamp less than or equal to
TS(Ti).
1. If transaction Ti issues a read(d), then the value
returned is the content of version dk
2. If transaction Ti issues a write(d)
1. if TS(Ti) < R-timestamp(dk), then transaction Ti
is aborted
2. if TS(Ti) = W-timestamp(dk), the contents of dk
are overwritten
3. else a new version of d is created
CSCE 824 - Spring 2013
12
MV Timestamp ordering




Farkas
Reads always succeed
A write by Ti is rejected if some other
transaction Tj that (in the serialization order
defined by the timestamp values) should
read Ti's write, has already read a version
created by a transaction older than Ti
Protocol guarantees serializability
For strictness: Processor delays ci until all Tj
that wrote versions read by Ti are committed
CSCE 824 - Spring 2013
13
Multiversion Two-Phase
Locking


Farkas
Differentiates between read-only
transactions and update transactions
Read-only transactions:
– Assigned a timestamp by reading the
current value of ts-counter before they
start execution
– Follow the multiversion timestampordering protocol for performing reads
CSCE 824 - Spring 2013
14
MV 2PL

Update transactions
– acquire read and write locks, and hold all locks up
to the end of the transaction (strict 2PL)
– Write: create a new version of the data
item
– Each version of a data item:


Farkas
has a single timestamp whose value is obtained
from a counter ts-counter
ts-counter is incremented during commit
processing.
CSCE 824 - Spring 2013
15
MV 2PL



Farkas
Read by an update transaction: sl, read
latest value
Write an item by an update transaction: xl,
sets this version's timestamp to .
When update transaction commits:
– Sets timestamp on the versions it has
created to ts-counter + 1
– Increments ts-counter by 1
CSCE 824 - Spring 2013
16
MV 2PL


Farkas
Read-only transactions:
– started after Ti increments ts-counter:
will see the values updated by Ti
– started before Ti increments the
ts-counter: will see the value before the
updates by Ti.
Only serializable schedules are produced.
CSCE 824 - Spring 2013
17
Snapshot Isolation


Motivation: Decision support queries that
read large amounts of data have concurrency
conflicts with OLTP transactions that update
a few rows
– Poor performance results
Solution 1: Give logical “snapshot” of
database state to read only transactions,
read-write transactions use normal locking
– Multiversion 2-phase locking
– Works well, but how does system know a
transaction is read only?
Farkas
CSCE 824 - Spring 2013
18
Snapshot Isolation

Solution 2: Give snapshot of database state
to every transaction, updates alone use 2phase locking to guard against concurrent
updates
– Problem: variety of anomalies such as lost
update can result
– Partial solution: snapshot isolation level (next
slide)
 Proposed by Berenson et al, SIGMOD 1995
 Implemented in many database systems,
Oracle, PostgreSQL, SQL Server 2005
Farkas
CSCE 824 - Spring 2013
19
Snapshot Isolation

A transaction T1 executing with
Snapshot Isolation
– takes snapshot of committed data
at start
– always reads/modifies data in its
own snapshot
– updates of concurrent transactions
are not visible to T1
– writes of T1 complete when it
commits
– First-committer-wins rule:
 Commits only if no other
concurrent transaction has
already written data that T1
intends to write.
Farkas
Concurrent updates not visible
Own updates are visible
Not first-committer of X
Serialization error, T2 is rolled back
CSCE 824 - Spring 2013
T1
T2
T3
W(Y := 1)
Commit
Start
R(X)  0
R(Y) 1
W(X:=2)
W(Z:=3)
Commit
R(Z)  0
R(Y)  1
W(X:=3)
Commit-Req
Abort
20
Overview of SI




Farkas
Reading is never blocked
Performance similar to Read Committed
Avoids the usual anomalies
– No dirty read
– No lost update
– No non-repeatable read
Problems with SI
– SI does not always give serializable
executions (transactions don’t see
concurrent writes)
CSCE 824 - Spring 2013
21
Example Problem
T1
A
B
C
1
2
3
5
4
3
T2
Farkas
A
B
C
1
2
6
5
4
3
A
B
C
1
2
3
5
4
6
CSCE 824 - Spring 2013
22
How to Avoid SI
inconsistencies?


Static conflict graph: detect
cycles
Fekete et al.: modify SI
– Detect w/r conflicts at runtime
– Abort conflicting transactions
– Don’t wait for full cycle
Farkas
CSCE 824 - Spring 2013
23
Serializable SI

Timestamps:
– Begin transaction (snapshot read)
– Commit transaction (conflict with
committed)
Problem:
T1 wrote x and
Committed before c0
Farkas
c0
r0(x) w0(y)
b0
CSCE 824 - Spring 2013
Problem:
T2 read y and
Committed before c0
24
Solution

Two flags for each transactionL
– In
– Out



Farkas
Set T.out if r/w-conflict T & T’
Set T.in if r/w-conflict T’& T
Abort T if both T.in and T.out are
set
CSCE 824 - Spring 2013
25
Example 1

T1 writes x before T0 commits
Lock y SI read
Lock x write
b1
b0
w1(x)
c1
r2(y)
r0(x) w0(y)
Lock x SI read Lock y write
c2
c0
T2.out: True
T0.in: True
T1.in: True
T0.out: True
Farkas
b2
CSCE 824 - Spring 2013
26
Next Class
Data Integration
Ch. 4
Farkas
27