Concurrency Control in Database Systems
1
October 5, 2024
Database System Internals
CSE 444 - Winter 2022
Optimistic Concurrency Control
Announcements
HW 4 out now
•
Transactions (locking and OCC)
•
Due 2/22
CSE 444 - Winter 2022
2
October 5, 2024
Pessimistic vs. Optimistic
Pessimistic CC
(locking)
•
Prevents unserializable schedules
•
Never abort for serializability (but may abort for deadlocks)
•
Best for workloads with high levels of contention
Optimistic CC
(timestamp, multi-version, validation)
•
Assume schedule will be serializable
•
Abort when conflicts detected
•
Best for workloads with low levels of contention
CSE 444 - Winter 2022
3
October 5, 2024
Outline
Concurrency control by timestamps (18.8)
Concurrency control by validation (18.9)
Snapshot Isolation
CSE 444 - Winter 2022
4
October 5, 2024
Timestamps
Each transaction receives unique timestamp
TS(T)
Could be:
The system’s clock
A unique counter, incremented by the scheduler
CSE 444 - Winter 2022
5
October 5, 2024
Timestamps
CSE 444 - Winter 2022
6
The timestamp order defines
the serialization order of the transaction
Main invariant:
Will generate a schedule that is view-equivalent
to a serial schedule, and recoverable
October 5, 2024
Timestamps
With each element X, associate
RT(X)
= the highest timestamp of any transaction U
that read X
WT(X)
= the highest timestamp of any transaction U
that wrote X
C
(
X
)
=
t
h
e
c
o
m
m
i
t
b
i
t
:
t
r
u
e
w
h
e
n
t
r
a
n
s
a
c
t
i
o
n
w
i
t
h
h
i
g
h
e
s
t
t
i
m
e
s
t
a
m
p
t
h
a
t
w
r
o
t
e
X
c
o
m
m
i
t
t
e
d
7
CSE 444 - Winter 2022
October 5, 2024
Timestamps
With each element X, associate
RT(X)
= the highest timestamp of any transaction U
that read X
WT(X)
= the highest timestamp of any transaction U
that wrote X
C
(
X
)
=
t
h
e
c
o
m
m
i
t
b
i
t
:
t
r
u
e
w
h
e
n
t
r
a
n
s
a
c
t
i
o
n
w
i
t
h
h
i
g
h
e
s
t
t
i
m
e
s
t
a
m
p
t
h
a
t
w
r
o
t
e
X
c
o
m
m
i
t
t
e
d
I
f
t
r
a
n
s
a
c
t
i
o
n
s
a
b
o
r
t
,
w
e
m
u
s
t
r
e
s
e
t
t
h
e
t
i
m
e
s
t
a
m
p
s
8
CSE 444 - Winter 2022
October 5, 2024
Main Idea
For any
r
T
(X)
or
w
T
(X)
request, check for
conflicts:
w
U
(X) . . .
r
T
(X)
r
U
(X) . . .
w
T
(X)
w
U
(X) . . .
w
T
(X)
CSE 444 - Winter 2022
9
How do we check
if Read too late ?
Write too
late ?
October 5, 2024
Main Idea
For any
r
T
(X)
or
w
T
(X)
request, check for
conflicts:
w
U
(X) . . .
r
T
(X)
r
U
(X) . . .
w
T
(X)
w
U
(X) . . .
w
T
(X)
CSE 444 - Winter 2022
10
When T requests
r
T
(X)
, need to check
TS(U)
≤
TS(T)
How do we check
if Read too late ?
Write too
late ?
October 5, 2024
Read Too Late
T wants to read X
CSE 444 - Winter 2022
11
START(T) … START(U) … w
U
(X) . . .
r
T
(X)
October 5, 2024
Read Too Late
T wants to read X
CSE 444 - Winter 2022
12
START(T) … START(U) … w
U
(X) . . .
r
T
(X)
I
f
W
T
(
X
)
>
T
S
(
T
)
t
h
e
n
n
e
e
d
t
o
r
o
l
l
b
a
c
k
T
!
T
t
r
i
e
d
t
o
r
e
a
d
t
o
o
l
a
t
e
October 5, 2024
Write Too Late
T wants to write X
CSE 444 - Winter 2022
13
START(T) … START(U) … r
U
(X) . . .
w
T
(X)
October 5, 2024
Write Too Late
T wants to write X
CSE 444 - Winter 2022
14
START(T) … START(U) … r
U
(X) . . .
w
T
(X)
If
RT(X) >
TS(T)
then need to rollback T !
T
t
r
i
e
d
t
o
w
r
i
t
e
t
o
o
l
a
t
e
October 5, 2024
Thomas’ Rule
But… we can still handle it in one case:
T wants to write X
START(T) … START(V) … w
V
(X) . . .
w
T
(X)
CSE 444 - Winter 2022
15
October 5, 2024
Thomas’ Rule
But we can still handle it:
T wants to write X
START(T) … START(V) … w
V
(X) . . .
w
T
(X)
If
RT(X) ≤
TS(T)
and
WT(X) >
TS(T)
then don’t write X at all !
CSE 444 - Winter 2022
16
Why does this work?
October 5, 2024
Thomas’ Rule
But we can still handle it:
T wants to write X
START(T) … START(V) … w
V
(X) . . .
w
T
(X)
If
RT(X) ≤
TS(T)
and
WT(X) >
TS(T)
then don’t write X at all !
CSE 444 - Winter 2022
17
Why does this work?
View-serializable:
V will have overwritted T!
October 5, 2024
View-Serializability
By using Thomas’ rule we do obtain a view-
serializable schedule
CSE 444 - Winter 2022
18
October 5, 2024
Summary So Far
Only for transactions that do not abort
Otherwise, may result in non-recoverable schedule
CSE 444 - Winter 2022
19
T
r
a
n
s
a
c
t
i
o
n
w
a
n
t
s
t
o
R
E
A
D
e
l
e
m
e
n
t
X
If
WT(X)
>
TS(T)
then ROLLBACK
Else READ and update
RT(X)
to larger of
TS(T)
or
RT(X)
T
r
a
n
s
a
c
t
i
o
n
w
a
n
t
s
t
o
W
R
I
T
E
e
l
e
m
e
n
t
X
If
RT(X)
>
TS(T)
then ROLLBACK
Else if
WT(X)
>
TS(T)
ignore write & continue (
Thomas Write Rule
)
Otherwise, WRITE and update
WT(X)
=
TS(T)
October 5, 2024
Ensuring Recoverable Schedules
Recall:
Schedule avoids cascading aborts if whenever a
transaction reads an element, then the transaction
that wrote it must have
already committed
U
s
e
t
h
e
c
o
m
m
i
t
b
i
t
C
(
X
)
t
o
k
e
e
p
t
r
a
c
k
i
f
t
h
e
t
r
a
n
s
a
c
t
i
o
n
t
h
a
t
l
a
s
t
w
r
o
t
e
X
h
a
s
c
o
m
m
i
t
t
e
d
(just a read will not change the commit bit)
CSE 444 - Winter 2022
20
October 5, 2024
Ensuring Recoverable Schedules
Read dirty data:
T wants to read X, and
WT(X)
<
TS(T)
Seems OK, but…
CSE 444 - Winter 2022
21
START(U) … START(T) … w
U
(X). . .
r
T
(X)
… ABORT(U)
If C(X)=false, T needs to wait for it to become true
October 5, 2024
Ensuring Recoverable Schedules
Thomas’ rule needs to be revised:
T wants to write X, and WT(X) >
TS(T)
Seems OK not to write at all, but …
CSE 444 - Winter 2022
22
START(T) … START(U)… w
U
(X). . .
w
T
(X)
… ABORT(U)
If C(X)=false, T needs to wait for it to become true
October 5, 2024
Timestamp-based Scheduling
When a transaction T requests r
T
(X) or w
T
(X),
the scheduler examines
RT(X)
,
WT(X)
,
C(X)
,
and decides one of:
•
To grant the request, or
•
To rollback T (and restart with later timestamp)
•
To delay T until
C(X)
= true
CSE 444 - Winter 2022
23
October 5, 2024
Timestamp-based Scheduling
RULES including commit bit
There are 4 long rules in Sec. 18.8.4
You should be able to derive them yourself, based
on the previous slides
Make sure you understand them !
READING ASSIGNMENT:
Garcia-Molina et al. 18.8.4
CSE 444 - Winter 2022
24
October 5, 2024
Timestamp-based Scheduling (sec.
18.8.4)
CSE 444 - Winter 2022
25
Transaction wants to READ element X
If
WT(X)
>
TS(T)
then ROLLBACK
Else If
C(X)
= false, then WAIT
Else READ and update
RT(X)
to larger of
TS(T)
or
RT(X)
Transaction wants to WRITE element X
If
RT(X)
>
TS(T)
then ROLLBACK
Else if
WT(X)
>
TS(T)
Then If
C(X)
= false then WAIT
else IGNORE write (
Thomas Write Rule
)
Otherwise, WRITE, and update
WT(X)
=
TS(T)
,
C(X)
=false
October 5, 2024
T
1
1
R
1
(A)
A
b
o
r
t
T
2
2
W
2
(A)
C
T
3
3
R
3
(A)
D
e
l
a
y
R
3
(A)
W
3
(A)
d
e
l
a
y
W3(A)
A
RT=0
WT=0
C=true
WT=2
C=false
RT=0
C=true
RT=3
WT=4
C=false
WT=2
C=true
WT=3
C=false
T
4
4
W
4
(A)
a
b
o
r
t
CSE 444 - Winter 2022
26
T
i
m
e
October 5, 2024
Basic Timestamps with Commit Bit
Basic Timestamps with Commit Bit
T
1
1
R
1
(A)
A
b
o
r
t
T
2
2
W
2
(A)
C
T
3
3
R
3
(A)
D
e
l
a
y
R
3
(A)
W
3
(A)
d
e
l
a
y
W3(A)
A
RT=0
WT=0
C=true
WT=2
C=false
RT=0
C=true
RT=3
WT=4
C=false
WT=2
C=true
WT=3
C=false
T
4
4
W
4
(A)
a
b
o
r
t
CSE 444 - Winter 2022
27
T
i
m
e
October 5, 2024
Summary of Timestamp-based Scheduling
View-serializable
Avoids cascading aborts (hence: recoverable)
Does NOT handle phantoms
•
These need to be handled separately, e.g. predicate
locks
CSE 444 - Winter 2022
28
October 5, 2024
Multiversion Timestamp
When transaction T requests r(X)
but
WT(X)
>
TS(T)
, then T must rollback
Idea: keep multiple versions of X:
X
t
, X
t-1
, X
t-2
, . . .
CSE 444 - Winter 2022
29
TS(X
t
)
>
TS(X
t-1
)
>
TS(X
t-2
)
> . . .
October 5, 2024
Details
When
w
T
(X)
occurs,
if the write is legal then
create a
new version
, denoted X
t
where t =
TS(T)
30
CSE 444 - Winter 2022
October 5, 2024
Details
When
w
T
(X)
occurs,
if the write is legal then
create a
new version
, denoted X
t
where t =
TS(T)
When
r
T
(X)
occurs,
find
most recent version
X
t
such that t <=
TS(T)
Notes:
•
WT(X
t
)
= t and it never changes for that version
•
RT(X
t
)
must still be maintained to check legality of writes
Can delete X
t
if we have a later version X
t1
and all active
transactions T have
TS(T)
> t1
31
CSE 444 - Winter 2022
October 5, 2024
Example (in class)
CSE 444 - Winter 2022
32
X
3
X
9
X
12
X
18
R
6
(X) -- Read X
3
W
21
(X) – Check read timestamp of X
18
R
15
(X) – Read X
12
W
5
(X) – Check read timestamp of X
3
When can we delete X
3
?
Four versions of X:
October 5, 2024
Example w/ Basic Timestamps
T
1
150
R
1
(A)
W
1
(A)
T
2
200
R
2
(A)
W
2
(A)
T
3
175
R
3
(A)
A
b
o
r
t
A
RT=0
WT=0
RT=150
WT=150
RT=200
WT=200
RT=225
T
4
225
R
4
(A)
CSE 444 - Winter 2022
33
Timestamps:
October 5, 2024
Example w/ Multiversion
T
1
150
R
1
(A)
W
1
(A)
T
2
200
R
2
(A)
W
2
(A)
T
3
175
R
3
(A)
W
3
(A)
a
b
o
r
t
A
0
RT=150
T
4
225
R
4
(A)
A
150
Create
RT=200
RT=200
A
200
Create
RT=225
CSE 444 - Winter 2022
34
October 5, 2024
Example w/ Multiversion
T
1
150
R
1
(A)
W
1
(A)
T
2
200
R
2
(A)
W
2
(A)
T
3
175
R
3
(A)
W
3
(A)
a
b
o
r
t
A
0
RT=150
T
4
225
R
4
(A)
A
150
Create
RT=200
RT=200
A
200
Create
RT=225
CSE 444 - Winter 2022
35
October 5, 2024
Example w/ Multiversion
T
1
150
R
1
(A)
W
1
(A)
T
2
200
R
2
(A)
W
2
(A)
T
3
175
R
3
(A)
W
3
(A)
a
b
o
r
t
A
0
RT=150
T
4
225
R
4
(A)
A
150
Create
RT=200
RT=200
A
200
Create
RT=225
CSE 444 - Winter 2022
36
October 5, 2024
T
5
5
R
5
(A)
W
5
(A)
Second Example w/ Multiversion
T
1
1
W1(A)
R
1
(A)
C
T
2
2
R
2
(A)
W
2
(A)
a
b
o
r
t
T
3
3
R
3
(A)
C
A
0
X
T
4
4
W
4
(A)
R
4
(A)
A
1
Create
RT=2
RT=3
RT=3
X
A
2
CSE 444 - Winter 2022
37
A
3
A
4
Create
RT=5
RT=5
A
5
Create
October 5, 2024
X means that we can delete this version
T
1
1
W1(A)
R
1
(A)
C
T
2
2
R
2
(A)
W
2
(A)
a
b
o
r
t
T
3
3
R
3
(A)
C
A
0
X
T
4
4
W
4
(A)
R
4
(A)
A
1
Create
RT=2
RT=3
RT=3
X
A
2
CSE 444 - Winter 2022
38
A
3
A
4
Create
RT=5
RT=5
A
5
Create
T
5
5
R
5
(A)
W
5
(A)
October 5, 2024
Second Example w/ Multiversion
Outline
Concurrency control by timestamps (18.8)
Concurrency control by validation (18.9)
Snapshot Isolation
CSE 444 - Winter 2022
39
October 5, 2024
Concurrency Control by Validation
Each transaction T defines:
•
Read set
RS(T)
= the elements it reads
•
Write set
WS(T)
= the elements it writes
Each transaction T has three phases:
•
Read phase; time =
START(T)
•
Validate phase (may need to rollback); time =
VAL(T)
•
Write phase; time =
FIN(T)
Main invariant: the serialization order is VAL(T)
CSE 444 - Winter 2022
40
October 5, 2024
Avoid r
T
(X) - w
U
(X) Conflicts
START(U)
VAL(U)
FIN(U)
START(T)
IF
RS(T)
∩ WS(U) and
FIN(U) >
START(T)
(
U has validated and U has not finished before
T
begun)
Then
ROLLBACK(T)
conflicts
VAL(T)
CSE 444 - Winter 2022
41
October 5, 2024
Avoid w
T
(X) - w
U
(X) Conflicts
START(U)
VAL(U)
FIN(U)
START(T)
VAL(T)
IF
WS(T)
∩ WS(U) and
FIN(U) >
VAL(T)
(
U has validated and U has not finished before
T
validates)
Then
ROLLBACK(T)
conflicts
CSE 444 - Winter 2022
42
October 5, 2024
Outline
Concurrency control by timestamps (18.8)
Concurrency control by validation (18.9)
Snapshot Isolation
•
Not in the book, but good overview in Wikipedia
CSE 444 - Winter 2022
43
October 5, 2024
Snapshot Isolation
A type of multiversion concurrency control algorithm
Provides yet another level of isolation
Very efficient, and very popular
•
Oracle, PostgreSQL, SQL Server 2005
Prevents many classical anomalies BUT…
Not serializable (!), yet ORACLE and PostgreSQL use it
even for SERIALIZABLE transactions!
•
But “serializable snapshot isolation” now in PostgreSQL
44
CSE 444 - Winter 2022
October 5, 2024
Snapshot Isolation Overview
Each transactions receives a timestamp TS(T)
Transaction T sees snapshot at time TS(T) of the database
W
/
W
c
o
n
f
l
i
c
t
s
r
e
s
o
l
v
e
d
b
y
“
f
i
r
s
t
c
o
m
m
i
t
t
e
r
w
i
n
s
”
r
u
l
e
•
Loser gets aborted
R/W conflicts are ignored
CSE 444 - Winter 2022
45
October 5, 2024
Snapshot Isolation Details
Multiversion concurrency control:
•
Versions of X: X
t1
, X
t2
, X
t3
, . . .
When T reads X, return X
TS(T)
.
When T writes X (to avoid lost update):
•
If latest version of X is TS(T) then
proceed
•
Else if C(X) = true then
abort
•
Else if C(X) = false then
wait
•
When T commits, write its updates to disk
CSE 444 - Winter 2022
46
October 5, 2024
What Works and What Not
No dirty reads (Why ?)
•
Start each snapshot with consistent state
No inconsistent reads (Why ?)
•
Two reads by the same transaction will read same
snapshot
No lost updates (“first committer wins”)
Moreover: no reads are ever delayed
However: read-write conflicts not caught!
•
A txn can read and commit even though the value had
changed in the middle
CSE 444 - Winter 2022
47
October 5, 2024
Write Skew
48
T1:
READ(X);
if X >= 50
then Y = -50; WRITE(Y)
COMMIT
T2:
READ(Y);
if Y >= 50
then X = -50; WRITE(X)
COMMIT
In our notation:
R
1
(X), R
2
(Y), W
1
(Y), W
2
(X), C
1
,C
2
Starting with X=50,Y=50, we end with X=-50, Y=-50.
Non-serializable !!!
CSE 444 - Winter 2022
October 5, 2024
Write Skews Can Be Serious
Acidicland had two viceroys, Delta and Rho
Budget had two registers: taXes, and spendYng
They had high taxes and low spending…
49
Delta:
READ(taXes);
if taXes = ‘High’
then { spendYng = ‘Raise’;WRITE(spendYng) }
COMMIT
Rho:
READ(spendYng);
if spendYng = ‘Low’
then {taXes = ‘Cut’;WRITE(taXes) }
COMMIT
… and they ran a deficit ever since.
October 5, 2024
CSE 444 - Winter 2022
Discussion: Tradeoffs
Pessimistic CC: Locks
•
Great when there are many conflicts
•
Poor when there are few conflicts
Optimistic CC: Timestamps, Validation, SI
•
Poor when there are many conflicts (rollbacks)
•
Great when there are few conflicts
Compromise
•
READ ONLY transactions
timestamps
•
READ/WRITE transactions
locks
CSE 444 - Winter 2022
50
October 5, 2024
51
Commercial Systems
Always check documentation!
DB2
: Strict 2PL
SQL Server
:
•
Strict 2PL for standard 4 levels of isolation
•
Multiversion concurrency control for snapshot isolation
PostgreSQL:
SI; recently: serializable SI (!)
Oracle:
SI
CSE 444 - Winter 2022
October 5, 2024
Dig into the world of concurrency control in database systems, exploring topics such as pessimistic vs. optimistic concurrency, snapshot isolation, and the importance of timestamps in ensuring transaction order and recoverability. Learn about the mechanisms behind preventing unserializable schedules, handling conflicts, and the role of timestamps in transaction management.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Database System Internals Optimistic Concurrency Control October 5, 2024 CSE 444 - Winter 2022 1
Announcements HW 4 out now Transactions (locking and OCC) Due 2/22 October 5, 2024 CSE 444 - Winter 2022 2
Pessimistic vs. Optimistic Pessimistic CC (locking) Prevents unserializable schedules Never abort for serializability (but may abort for deadlocks) Best for workloads with high levels of contention Optimistic CC (timestamp, multi-version, validation) Assume schedule will be serializable Abort when conflicts detected Best for workloads with low levels of contention October 5, 2024 CSE 444 - Winter 2022 3
Outline Concurrency control by timestamps (18.8) Concurrency control by validation (18.9) Snapshot Isolation October 5, 2024 CSE 444 - Winter 2022 4
Timestamps Each transaction receives unique timestamp TS(T) Could be: The system s clock A unique counter, incremented by the scheduler October 5, 2024 CSE 444 - Winter 2022 5
Timestamps Main invariant: The timestamp order defines the serialization order of the transaction Will generate a schedule that is view-equivalent to a serial schedule, and recoverable October 5, 2024 CSE 444 - Winter 2022 6
Timestamps With each element X, associate RT(X) = the highest timestamp of any transaction U that read X WT(X) = the highest timestamp of any transaction U that wrote X C(X) = the commit bit: true when transaction with highest timestamp that wrote X committed October 5, 2024 CSE 444 - Winter 2022 7
Timestamps With each element X, associate RT(X) = the highest timestamp of any transaction U that read X WT(X) = the highest timestamp of any transaction U that wrote X C(X) = the commit bit: true when transaction with highest timestamp that wrote X committed If transactions abort, we must reset the timestamps October 5, 2024 CSE 444 - Winter 2022 8
Main Idea For any rT(X) or wT(X) request, check for conflicts: How do we check if Read too late ? wU(X) . . . rT(X) rU(X) . . . wT(X) wU(X) . . . wT(X) Write too late ? October 5, 2024 CSE 444 - Winter 2022 9
Main Idea For any rT(X) or wT(X) request, check for conflicts: How do we check if Read too late ? wU(X) . . . rT(X) rU(X) . . . wT(X) wU(X) . . . wT(X) Write too late ? When T requests rT(X), need to check TS(U) TS(T) October 5, 2024 CSE 444 - Winter 2022 10
Read Too Late T wants to read X START(T) START(U) wU(X) . . . rT(X) October 5, 2024 CSE 444 - Winter 2022 11
Read Too Late T wants to read X START(T) START(U) wU(X) . . . rT(X) If WT(X) > TS(T) then need to rollback T ! T tried to read too late October 5, 2024 CSE 444 - Winter 2022 12
Write Too Late T wants to write X START(T) START(U) rU(X) . . . wT(X) October 5, 2024 CSE 444 - Winter 2022 13
Write Too Late T wants to write X START(T) START(U) rU(X) . . . wT(X) If RT(X) > TS(T) then need to rollback T ! T tried to write too late October 5, 2024 CSE 444 - Winter 2022 14
Thomas Rule But we can still handle it in one case: T wants to write X START(T) START(V) wV(X) . . . wT(X) October 5, 2024 CSE 444 - Winter 2022 15
Thomas Rule But we can still handle it: T wants to write X START(T) START(V) wV(X) . . . wT(X) If RT(X) TS(T) and WT(X) > TS(T) then don t write X at all ! Why does this work? October 5, 2024 CSE 444 - Winter 2022 16
Thomas Rule But we can still handle it: T wants to write X START(T) START(V) wV(X) . . . wT(X) If RT(X) TS(T) and WT(X) > TS(T) then don t write X at all ! View-serializable: V will have overwritted T! Why does this work? October 5, 2024 CSE 444 - Winter 2022 17
View-Serializability By using Thomas rule we do obtain a view- serializable schedule October 5, 2024 CSE 444 - Winter 2022 18
Summary So Far Only for transactions that do not abort Otherwise, may result in non-recoverable schedule Transaction wants to READ element X If WT(X) > TS(T) then ROLLBACK Else READ and update RT(X) to larger of TS(T) or RT(X) Transaction wants to WRITE element X If RT(X) > TS(T) then ROLLBACK Else if WT(X) > TS(T) ignore write & continue (Thomas Write Rule) Otherwise, WRITE and update WT(X) =TS(T) October 5, 2024 CSE 444 - Winter 2022 19
Ensuring Recoverable Schedules Recall: Schedule avoids cascading aborts if whenever a transaction reads an element, then the transaction that wrote it must have already committed Use the commit bit C(X) to keep track if the transaction that last wrote X has committed (just a read will not change the commit bit) October 5, 2024 CSE 444 - Winter 2022 20
Ensuring Recoverable Schedules Read dirty data: T wants to read X, and WT(X) < TS(T) Seems OK, but START(U) START(T) wU(X). . . rT(X) ABORT(U) If C(X)=false, T needs to wait for it to become true October 5, 2024 CSE 444 - Winter 2022 21
Ensuring Recoverable Schedules Thomas rule needs to be revised: T wants to write X, and WT(X) > TS(T) Seems OK not to write at all, but START(T) START(U) wU(X). . . wT(X) ABORT(U) If C(X)=false, T needs to wait for it to become true October 5, 2024 CSE 444 - Winter 2022 22
Timestamp-based Scheduling When a transaction T requests rT(X) or wT(X), the scheduler examines RT(X), WT(X), C(X), and decides one of: To grant the request, or To rollback T (and restart with later timestamp) To delay T until C(X) = true October 5, 2024 CSE 444 - Winter 2022 23
Timestamp-based Scheduling RULES including commit bit There are 4 long rules in Sec. 18.8.4 You should be able to derive them yourself, based on the previous slides Make sure you understand them ! READING ASSIGNMENT: Garcia-Molina et al. 18.8.4 October 5, 2024 CSE 444 - Winter 2022 24
Timestamp-based Scheduling (sec. 18.8.4) Transaction wants to READ element X If WT(X) > TS(T) then ROLLBACK Else If C(X) = false, then WAIT Else READ and update RT(X) to larger of TS(T) or RT(X) Transaction wants to WRITE element X If RT(X) > TS(T) then ROLLBACK Else if WT(X) > TS(T) Then If C(X) = false then WAIT else IGNORE write (Thomas Write Rule) Otherwise, WRITE, and update WT(X)=TS(T), C(X)=false October 5, 2024 CSE 444 - Winter 2022 25
Basic Timestamps with Commit Bit T1 1 T2 2 T3 3 T4 4 A RT=0 WT=0 C=true WT=2 C=false RT=0 W2(A) R1(A) Abort Time R3(A) Delay C RT=3 WT=4 C=false C=true R3(A) W4(A) W3(A) delay WT=2 C=true WT=3 C=false abort W3(A) October 5, 2024 CSE 444 - Winter 2022 26
Basic Timestamps with Commit Bit T1 1 T2 2 T3 3 T4 4 A RT=0 WT=0 C=true WT=2 C=false RT=0 W2(A) R1(A) Abort Time R3(A) Delay C RT=3 WT=4 C=false C=true R3(A) W4(A) W3(A) delay WT=2 C=true WT=3 C=false abort W3(A) October 5, 2024 CSE 444 - Winter 2022 27
Summary of Timestamp-based Scheduling View-serializable Avoids cascading aborts (hence: recoverable) Does NOT handle phantoms These need to be handled separately, e.g. predicate locks October 5, 2024 CSE 444 - Winter 2022 28
Multiversion Timestamp When transaction T requests r(X) but WT(X) > TS(T), then T must rollback Idea: keep multiple versions of X: Xt, Xt-1, Xt-2, . . . TS(Xt) > TS(Xt-1) > TS(Xt-2) > . . . October 5, 2024 CSE 444 - Winter 2022 29
Details When wT(X) occurs, if the write is legal then create a new version, denoted Xt where t = TS(T) October 5, 2024 CSE 444 - Winter 2022 30
Details When wT(X) occurs, if the write is legal then create a new version, denoted Xt where t = TS(T) When rT(X) occurs, find most recent version Xt such that t <= TS(T) Notes: WT(Xt) = t and it never changes for that version RT(Xt) must still be maintained to check legality of writes Can delete Xt if we have a later version Xt1 and all active transactions T have TS(T) > t1 October 5, 2024 CSE 444 - Winter 2022 31
Example w/ Basic Timestamps T1 150 T2 200 T3 175 T4 225 A RT=0 WT=0 RT=150 WT=150 RT=200 WT=200 Timestamps: R1(A) W1(A) R2(A) W2(A) R3(A) Abort R4(A) RT=225 October 5, 2024 CSE 444 - Winter 2022 33
Example w/ Multiversion T1 150 T2 200 T3 175 T4 225 A0 A150 A200 RT=150 R1(A) W1(A) Create RT=200 R2(A) W2(A) Create R3(A) W3(A) abort RT=200 R4(A) RT=225 October 5, 2024 CSE 444 - Winter 2022 34
Example w/ Multiversion T1 150 T2 200 T3 175 T4 225 A0 A150 A200 RT=150 R1(A) W1(A) Create RT=200 R2(A) W2(A) Create R3(A) W3(A) abort RT=200 R4(A) RT=225 October 5, 2024 CSE 444 - Winter 2022 35
Example w/ Multiversion T1 150 T2 200 T3 175 T4 225 A0 A150 A200 RT=150 R1(A) W1(A) Create RT=200 R2(A) W2(A) Create R3(A) W3(A) abort RT=200 R4(A) RT=225 October 5, 2024 CSE 444 - Winter 2022 36
Second Example w/ Multiversion T1 1 T2 2 T3 3 T4 4 W4(A) T5 5 A0 A1 A2 A3 A4 A5 Create W1(A) Create RT=2 RT=3 R2(A) R3(A) W2(A) abort R5(A) W5(A) RT=5 Create RT=5 R4(A) R1(A) C RT=3 X C X October 5, 2024 CSE 444 - Winter 2022 37
Second Example w/ Multiversion T1 1 T2 2 T3 3 T4 4 W4(A) T5 5 A0 A1 A2 A3 A4 A5 Create W1(A) Create RT=2 RT=3 R2(A) R3(A) W2(A) abort R5(A) W5(A) RT=5 Create RT=5 R4(A) R1(A) C RT=3 X C X X means that we can delete this version October 5, 2024 CSE 444 - Winter 2022 38
Outline Concurrency control by timestamps (18.8) Concurrency control by validation (18.9) Snapshot Isolation October 5, 2024 CSE 444 - Winter 2022 39
Concurrency Control by Validation Each transaction T defines: Read set RS(T) = the elements it reads Write set WS(T) = the elements it writes Each transaction T has three phases: Read phase; time = START(T) Validate phase (may need to rollback); time = VAL(T) Write phase; time = FIN(T) Main invariant: the serialization order is VAL(T) October 5, 2024 CSE 444 - Winter 2022 40
Avoid rT(X) - wU(X) Conflicts VAL(U) FIN(U) START(U) U: Read phase Validate Write phase conflicts T: Read phase Validate ? START(T) VAL(T) IF RS(T) WS(U) and FIN(U) > START(T) (U has validated and U has not finished before T begun) Then ROLLBACK(T) October 5, 2024 CSE 444 - Winter 2022 41
Avoid wT(X) - wU(X) Conflicts VAL(U) FIN(U) START(U) U: Read phase Validate Write phase conflicts T: Read phase Validate Write phase ? START(T) VAL(T) IF WS(T) WS(U) and FIN(U) > VAL(T) (U has validated and U has not finished before T validates) Then ROLLBACK(T) October 5, 2024 CSE 444 - Winter 2022 42
Outline Concurrency control by timestamps (18.8) Concurrency control by validation (18.9) Snapshot Isolation Not in the book, but good overview in Wikipedia October 5, 2024 CSE 444 - Winter 2022 43
Snapshot Isolation A type of multiversion concurrency control algorithm Provides yet another level of isolation Very efficient, and very popular Oracle, PostgreSQL, SQL Server 2005 Prevents many classical anomalies BUT Not serializable (!), yet ORACLE and PostgreSQL use it even for SERIALIZABLE transactions! But serializable snapshot isolation now in PostgreSQL October 5, 2024 CSE 444 - Winter 2022 44
Snapshot Isolation Overview Each transactions receives a timestamp TS(T) Transaction T sees snapshot at time TS(T) of the database W/W conflicts resolved by first committer wins rule Loser gets aborted R/W conflicts are ignored October 5, 2024 CSE 444 - Winter 2022 45
Snapshot Isolation Details Multiversion concurrency control: Versions of X: Xt1, Xt2, Xt3, . . . When T reads X, return XTS(T). When T writes X (to avoid lost update): If latest version of X is TS(T) then proceed Else if C(X) = true then abort Else if C(X) = false then wait When T commits, write its updates to disk October 5, 2024 CSE 444 - Winter 2022 46
What Works and What Not No dirty reads (Why ?) Start each snapshot with consistent state No inconsistent reads (Why ?) Two reads by the same transaction will read same snapshot No lost updates ( first committer wins ) Moreover: no reads are ever delayed However: read-write conflicts not caught! A txn can read and commit even though the value had changed in the middle October 5, 2024 CSE 444 - Winter 2022 47
Write Skew T1: READ(X); if X >= 50 then Y = -50; WRITE(Y) COMMIT T2: READ(Y); if Y >= 50 then X = -50; WRITE(X) COMMIT In our notation: R1(X), R2(Y), W1(Y), W2(X), C1,C2 Starting with X=50,Y=50, we end with X=-50, Y=-50. Non-serializable !!! October 5, 2024 CSE 444 - Winter 2022 48
Write Skews Can Be Serious Acidicland had two viceroys, Delta and Rho Budget had two registers: taXes, and spendYng They had high taxes and low spending Delta: READ(taXes); if taXes = High then { spendYng = Raise ; WRITE(spendYng) } COMMIT Rho: READ(spendYng); if spendYng = Low then {taXes = Cut ; WRITE(taXes) } COMMIT and they ran a deficit ever since. October 5, 2024 CSE 444 - Winter 2022 49
Discussion: Tradeoffs Pessimistic CC: Locks Great when there are many conflicts Poor when there are few conflicts Optimistic CC: Timestamps, Validation, SI Poor when there are many conflicts (rollbacks) Great when there are few conflicts Compromise READ ONLY transactions timestamps READ/WRITE transactions locks October 5, 2024 CSE 444 - Winter 2022 50
Commercial Systems Always check documentation! DB2: Strict 2PL SQL Server: Strict 2PL for standard 4 levels of isolation Multiversion concurrency control for snapshot isolation PostgreSQL: SI; recently: serializable SI (!) Oracle: SI CSE 444 - Winter 2022 October 5, 2024 51
