Transactions - Optimistic Concurrency Control Notes | EduRev

: Transactions - Optimistic Concurrency Control Notes | EduRev

 Page 1


1 
CSE 444: Database Internals 
Lectures 15 
Transactions:  
Optimistic Concurrency Control 
1 Magda Balazinska - CSE 444, Spring 2012 
Motivation 
•? Locking ensures serializability 
–? BUT adds overhead and slows-down transactions 
•? Observations:  
–? Many transactions are read-only 
–? Many transactions touch unrelated parts of database 
•? Can we: 
–? Assume no unserializable behavior will occur 
–? Abort transactions in case  of violations 
•? Yes: this is optimistic concurrency control 
Magda Balazinska - CSE 444, Spring 2012 2 
Locking vs Optimistic 
•? Locking prevents unserializable behavior from 
occurring: it causes transactions to wait for locks 
•? Optimistic methods assume no unserializable 
behavior will occur: they abort transactions if it 
does 
•? Locking typically better in case of high levels of 
contention; optimistic better otherwise 
Magda Balazinska - CSE 444, Spring 2012 3 
Outline 
•? Concurrency control by timestamps (18.8) 
•? Concurrency control by validation (18.9) 
Magda Balazinska - CSE 444, Spring 2012 4 
Timestamps 
•? Each transaction receives unique timestamp TS(T) 
 
Could be: 
•? The system’s clock 
•? A unique counter, incremented by the scheduler 
Magda Balazinska - CSE 444, Spring 2012 5 
Timestamps 
The timestamp order defines 
 the serialization order of the transaction 
Main invariant: 
Magda Balazinska - CSE 444, Spring 2012 6 
Page 2


1 
CSE 444: Database Internals 
Lectures 15 
Transactions:  
Optimistic Concurrency Control 
1 Magda Balazinska - CSE 444, Spring 2012 
Motivation 
•? Locking ensures serializability 
–? BUT adds overhead and slows-down transactions 
•? Observations:  
–? Many transactions are read-only 
–? Many transactions touch unrelated parts of database 
•? Can we: 
–? Assume no unserializable behavior will occur 
–? Abort transactions in case  of violations 
•? Yes: this is optimistic concurrency control 
Magda Balazinska - CSE 444, Spring 2012 2 
Locking vs Optimistic 
•? Locking prevents unserializable behavior from 
occurring: it causes transactions to wait for locks 
•? Optimistic methods assume no unserializable 
behavior will occur: they abort transactions if it 
does 
•? Locking typically better in case of high levels of 
contention; optimistic better otherwise 
Magda Balazinska - CSE 444, Spring 2012 3 
Outline 
•? Concurrency control by timestamps (18.8) 
•? Concurrency control by validation (18.9) 
Magda Balazinska - CSE 444, Spring 2012 4 
Timestamps 
•? Each transaction receives unique timestamp TS(T) 
 
Could be: 
•? The system’s clock 
•? A unique counter, incremented by the scheduler 
Magda Balazinska - CSE 444, Spring 2012 5 
Timestamps 
The timestamp order defines 
 the serialization order of the transaction 
Main invariant: 
Magda Balazinska - CSE 444, Spring 2012 6 
2 
Main Idea 
•? For any two conflicting actions, ensure that 
their order is the serialized order: 
In each of these cases 
•? w
U
(X) . . . r
T
(X) 
•? r
U
(X) . . . w
T
(X) 
•? w
U
(X) . . . w
T
(X) 
Answer: Check that TS(U) < TS(T) 
When T wants to read X, r
T
(X), how do we  
know U, and TS(U) ?  
Read too 
late ? 
Write too 
late ? 
7 Magda Balazinska - CSE 444, Spring 2012 
Timestamps 
With each element X, associate 
•? RT(X) = the highest timestamp of any 
transaction that read X 
•? WT(X) = the highest timestamp of any 
transaction that wrote X 
•? C(X) = the commit bit: true when transaction 
with highest timestamp that wrote X committed 
If 1 element = 1 page,  
these are associated with each page X in the buffer pool 
Magda Balazinska - CSE 444, Spring 2012 8 
Magda Balazinska - CSE 444, Spring 2012 9 
Time-based Scheduling 
•? Note: simple version that ignores the commit bit 
•? Transaction wants to read element X 
–? If TS(T) < WT(X)  abort 
–? Else read and update RT(X) to larger of TS(T) or RT(X) 
•? Transaction wants to write element X 
–? If TS(T) < RT(X) abort 
–? Else if TS(T) < WT(X) ignore write & continue (Thomas Write Rule) 
–? Otherwise, write X and update WT(X) to TS(T) 
Details 
Read too late: 
•? T wants to read X, and TS(T) < WT(X) 
START(T) … START(U) … w
U
(X) . . . r
T
(X) 
Need to rollback T ! 
Magda Balazinska - CSE 444, Spring 2012 10 
Details 
Write too late: 
•? T wants to write X, and TS(T) < RT(X) 
START(T) … START(U) … r
U
(X) . . . w
T
(X) 
Need to rollback T ! 
Magda Balazinska - CSE 444, Spring 2012 11 
Details 
Write too late, but we can still handle it: 
•? T wants to write X, and  
TS(T) >= RT(X)  but WT(X) > TS(T) 
START(T) … START(V) … w
V
(X) . . . w
T
(X) 
Don’t write X at all ! 
(but see later…) 
Magda Balazinska - CSE 444, Spring 2012 12 
Page 3


1 
CSE 444: Database Internals 
Lectures 15 
Transactions:  
Optimistic Concurrency Control 
1 Magda Balazinska - CSE 444, Spring 2012 
Motivation 
•? Locking ensures serializability 
–? BUT adds overhead and slows-down transactions 
•? Observations:  
–? Many transactions are read-only 
–? Many transactions touch unrelated parts of database 
•? Can we: 
–? Assume no unserializable behavior will occur 
–? Abort transactions in case  of violations 
•? Yes: this is optimistic concurrency control 
Magda Balazinska - CSE 444, Spring 2012 2 
Locking vs Optimistic 
•? Locking prevents unserializable behavior from 
occurring: it causes transactions to wait for locks 
•? Optimistic methods assume no unserializable 
behavior will occur: they abort transactions if it 
does 
•? Locking typically better in case of high levels of 
contention; optimistic better otherwise 
Magda Balazinska - CSE 444, Spring 2012 3 
Outline 
•? Concurrency control by timestamps (18.8) 
•? Concurrency control by validation (18.9) 
Magda Balazinska - CSE 444, Spring 2012 4 
Timestamps 
•? Each transaction receives unique timestamp TS(T) 
 
Could be: 
•? The system’s clock 
•? A unique counter, incremented by the scheduler 
Magda Balazinska - CSE 444, Spring 2012 5 
Timestamps 
The timestamp order defines 
 the serialization order of the transaction 
Main invariant: 
Magda Balazinska - CSE 444, Spring 2012 6 
2 
Main Idea 
•? For any two conflicting actions, ensure that 
their order is the serialized order: 
In each of these cases 
•? w
U
(X) . . . r
T
(X) 
•? r
U
(X) . . . w
T
(X) 
•? w
U
(X) . . . w
T
(X) 
Answer: Check that TS(U) < TS(T) 
When T wants to read X, r
T
(X), how do we  
know U, and TS(U) ?  
Read too 
late ? 
Write too 
late ? 
7 Magda Balazinska - CSE 444, Spring 2012 
Timestamps 
With each element X, associate 
•? RT(X) = the highest timestamp of any 
transaction that read X 
•? WT(X) = the highest timestamp of any 
transaction that wrote X 
•? C(X) = the commit bit: true when transaction 
with highest timestamp that wrote X committed 
If 1 element = 1 page,  
these are associated with each page X in the buffer pool 
Magda Balazinska - CSE 444, Spring 2012 8 
Magda Balazinska - CSE 444, Spring 2012 9 
Time-based Scheduling 
•? Note: simple version that ignores the commit bit 
•? Transaction wants to read element X 
–? If TS(T) < WT(X)  abort 
–? Else read and update RT(X) to larger of TS(T) or RT(X) 
•? Transaction wants to write element X 
–? If TS(T) < RT(X) abort 
–? Else if TS(T) < WT(X) ignore write & continue (Thomas Write Rule) 
–? Otherwise, write X and update WT(X) to TS(T) 
Details 
Read too late: 
•? T wants to read X, and TS(T) < WT(X) 
START(T) … START(U) … w
U
(X) . . . r
T
(X) 
Need to rollback T ! 
Magda Balazinska - CSE 444, Spring 2012 10 
Details 
Write too late: 
•? T wants to write X, and TS(T) < RT(X) 
START(T) … START(U) … r
U
(X) . . . w
T
(X) 
Need to rollback T ! 
Magda Balazinska - CSE 444, Spring 2012 11 
Details 
Write too late, but we can still handle it: 
•? T wants to write X, and  
TS(T) >= RT(X)  but WT(X) > TS(T) 
START(T) … START(V) … w
V
(X) . . . w
T
(X) 
Don’t write X at all ! 
(but see later…) 
Magda Balazinska - CSE 444, Spring 2012 12 
3 
More Problems 
Read dirty data: 
•? T wants to read X, and WT(X) < TS(T) 
•? Seems OK, but… 
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 
Magda Balazinska - CSE 444, Spring 2012 13 
More Problems 
Write dirty data: 
•? T wants to write X, and WT(X) > TS(T) 
•? Seems OK not to write at all, but … 
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 
Magda Balazinska - CSE 444, Spring 2012 14 
Timestamp-based Scheduling 
•? When a transaction T requests r(X) or w(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 
Magda Balazinska - CSE 444, Spring 2012 15 
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: 18.8.4 
Magda Balazinska - CSE 444, Spring 2012 16 
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
, . . . 
•? Let T read an older version, with appropriate 
timestamp 
TS(X
t
) > TS(X
t-1
) > TS(X
t-2
) > . . . 
Magda Balazinska - CSE 444, Spring 2012 17 
Details 
•? When w
T
(X) occurs,  
 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 
–? 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 
Magda Balazinska - CSE 444, Spring 2012 18 
Page 4


1 
CSE 444: Database Internals 
Lectures 15 
Transactions:  
Optimistic Concurrency Control 
1 Magda Balazinska - CSE 444, Spring 2012 
Motivation 
•? Locking ensures serializability 
–? BUT adds overhead and slows-down transactions 
•? Observations:  
–? Many transactions are read-only 
–? Many transactions touch unrelated parts of database 
•? Can we: 
–? Assume no unserializable behavior will occur 
–? Abort transactions in case  of violations 
•? Yes: this is optimistic concurrency control 
Magda Balazinska - CSE 444, Spring 2012 2 
Locking vs Optimistic 
•? Locking prevents unserializable behavior from 
occurring: it causes transactions to wait for locks 
•? Optimistic methods assume no unserializable 
behavior will occur: they abort transactions if it 
does 
•? Locking typically better in case of high levels of 
contention; optimistic better otherwise 
Magda Balazinska - CSE 444, Spring 2012 3 
Outline 
•? Concurrency control by timestamps (18.8) 
•? Concurrency control by validation (18.9) 
Magda Balazinska - CSE 444, Spring 2012 4 
Timestamps 
•? Each transaction receives unique timestamp TS(T) 
 
Could be: 
•? The system’s clock 
•? A unique counter, incremented by the scheduler 
Magda Balazinska - CSE 444, Spring 2012 5 
Timestamps 
The timestamp order defines 
 the serialization order of the transaction 
Main invariant: 
Magda Balazinska - CSE 444, Spring 2012 6 
2 
Main Idea 
•? For any two conflicting actions, ensure that 
their order is the serialized order: 
In each of these cases 
•? w
U
(X) . . . r
T
(X) 
•? r
U
(X) . . . w
T
(X) 
•? w
U
(X) . . . w
T
(X) 
Answer: Check that TS(U) < TS(T) 
When T wants to read X, r
T
(X), how do we  
know U, and TS(U) ?  
Read too 
late ? 
Write too 
late ? 
7 Magda Balazinska - CSE 444, Spring 2012 
Timestamps 
With each element X, associate 
•? RT(X) = the highest timestamp of any 
transaction that read X 
•? WT(X) = the highest timestamp of any 
transaction that wrote X 
•? C(X) = the commit bit: true when transaction 
with highest timestamp that wrote X committed 
If 1 element = 1 page,  
these are associated with each page X in the buffer pool 
Magda Balazinska - CSE 444, Spring 2012 8 
Magda Balazinska - CSE 444, Spring 2012 9 
Time-based Scheduling 
•? Note: simple version that ignores the commit bit 
•? Transaction wants to read element X 
–? If TS(T) < WT(X)  abort 
–? Else read and update RT(X) to larger of TS(T) or RT(X) 
•? Transaction wants to write element X 
–? If TS(T) < RT(X) abort 
–? Else if TS(T) < WT(X) ignore write & continue (Thomas Write Rule) 
–? Otherwise, write X and update WT(X) to TS(T) 
Details 
Read too late: 
•? T wants to read X, and TS(T) < WT(X) 
START(T) … START(U) … w
U
(X) . . . r
T
(X) 
Need to rollback T ! 
Magda Balazinska - CSE 444, Spring 2012 10 
Details 
Write too late: 
•? T wants to write X, and TS(T) < RT(X) 
START(T) … START(U) … r
U
(X) . . . w
T
(X) 
Need to rollback T ! 
Magda Balazinska - CSE 444, Spring 2012 11 
Details 
Write too late, but we can still handle it: 
•? T wants to write X, and  
TS(T) >= RT(X)  but WT(X) > TS(T) 
START(T) … START(V) … w
V
(X) . . . w
T
(X) 
Don’t write X at all ! 
(but see later…) 
Magda Balazinska - CSE 444, Spring 2012 12 
3 
More Problems 
Read dirty data: 
•? T wants to read X, and WT(X) < TS(T) 
•? Seems OK, but… 
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 
Magda Balazinska - CSE 444, Spring 2012 13 
More Problems 
Write dirty data: 
•? T wants to write X, and WT(X) > TS(T) 
•? Seems OK not to write at all, but … 
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 
Magda Balazinska - CSE 444, Spring 2012 14 
Timestamp-based Scheduling 
•? When a transaction T requests r(X) or w(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 
Magda Balazinska - CSE 444, Spring 2012 15 
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: 18.8.4 
Magda Balazinska - CSE 444, Spring 2012 16 
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
, . . . 
•? Let T read an older version, with appropriate 
timestamp 
TS(X
t
) > TS(X
t-1
) > TS(X
t-2
) > . . . 
Magda Balazinska - CSE 444, Spring 2012 17 
Details 
•? When w
T
(X) occurs,  
 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 
–? 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 
Magda Balazinska - CSE 444, Spring 2012 18 
4 
Example using Basic Timestamps 
T
1 
150 
 
R
1
(A) 
W
1
(A) 
Magda Balazinska - CSE 444, Spring 2012 19 
T
2 
200 
 
 
 
R
2
(A) 
W
2
(A) 
T
3 
175 
 
 
 
 
 
R
3
(A) 
Abort 
A
 
RT=0 
WT=0 
RT=150 
WT=150 
RT=200 
WT=200 
 
 
RT=225 
T
4 
225 
 
 
 
 
 
 
 
R
4
(A) 
Example using Multiversion  
T
1 
150 
 
R
1
(A) 
W
1
(A) 
Magda Balazinska - CSE 444, Spring 2012 20 
T
2 
200 
 
 
 
R
2
(A) 
W
2
(A) 
T
3 
175 
 
 
 
 
 
R
3
(A) 
A
0 
 
 
Read 
T
4 
225 
 
 
 
 
 
 
 
R
4
(A) 
A
150 
 
 
 
 
Create 
Read 
 
Read 
A
200 
 
 
 
 
 
Create 
 
 
Read 
 
 
 
Tradeoffs 
•? Locks: 
–? Great when there are many conflicts 
–? Poor when there are few conflicts 
•? Timestamps 
–? Poor when there are many conflicts (rollbacks) 
–? Great when there are few conflicts 
•? Compromise 
–? READ ONLY transactions ? timestamps 
–? READ/WRITE transactions ? locks 
Magda Balazinska - CSE 444, Spring 2012 21 
Outline 
•? Concurrency control by timestamps (18.8) 
•? Concurrency control by validation (18.9) 
Magda Balazinska - CSE 444, Spring 2012 22 
Concurrency Control by Validation 
•? Each transaction T defines a read set RS(T) and a 
write set WS(T) 
•? Each transaction proceeds in three phases: 
–? Read all elements in RS(T).  Time = START(T) 
–? Validate (may need to rollback).  Time = VAL(T) 
–? Write all elements in WS(T). Time = FIN(T) 
Main invariant: the serialization order is VAL(T) 
Magda Balazinska - CSE 444, Spring 2012 23 
Avoid r
T
(X) - w
U
(X) Conflicts 
U: Read phase Validate Write phase 
START(U) 
VAL(U) FIN(U) 
T: Read phase Validate ? 
START(T) 
IF  RS(T) n WS(U) and FIN(U) > START(T)  
        (U has validated and  U has not finished before T begun) 
Then ROLLBACK(T) 
conflicts 
Magda Balazinska - CSE 444, Spring 2012 24 
Page 5


1 
CSE 444: Database Internals 
Lectures 15 
Transactions:  
Optimistic Concurrency Control 
1 Magda Balazinska - CSE 444, Spring 2012 
Motivation 
•? Locking ensures serializability 
–? BUT adds overhead and slows-down transactions 
•? Observations:  
–? Many transactions are read-only 
–? Many transactions touch unrelated parts of database 
•? Can we: 
–? Assume no unserializable behavior will occur 
–? Abort transactions in case  of violations 
•? Yes: this is optimistic concurrency control 
Magda Balazinska - CSE 444, Spring 2012 2 
Locking vs Optimistic 
•? Locking prevents unserializable behavior from 
occurring: it causes transactions to wait for locks 
•? Optimistic methods assume no unserializable 
behavior will occur: they abort transactions if it 
does 
•? Locking typically better in case of high levels of 
contention; optimistic better otherwise 
Magda Balazinska - CSE 444, Spring 2012 3 
Outline 
•? Concurrency control by timestamps (18.8) 
•? Concurrency control by validation (18.9) 
Magda Balazinska - CSE 444, Spring 2012 4 
Timestamps 
•? Each transaction receives unique timestamp TS(T) 
 
Could be: 
•? The system’s clock 
•? A unique counter, incremented by the scheduler 
Magda Balazinska - CSE 444, Spring 2012 5 
Timestamps 
The timestamp order defines 
 the serialization order of the transaction 
Main invariant: 
Magda Balazinska - CSE 444, Spring 2012 6 
2 
Main Idea 
•? For any two conflicting actions, ensure that 
their order is the serialized order: 
In each of these cases 
•? w
U
(X) . . . r
T
(X) 
•? r
U
(X) . . . w
T
(X) 
•? w
U
(X) . . . w
T
(X) 
Answer: Check that TS(U) < TS(T) 
When T wants to read X, r
T
(X), how do we  
know U, and TS(U) ?  
Read too 
late ? 
Write too 
late ? 
7 Magda Balazinska - CSE 444, Spring 2012 
Timestamps 
With each element X, associate 
•? RT(X) = the highest timestamp of any 
transaction that read X 
•? WT(X) = the highest timestamp of any 
transaction that wrote X 
•? C(X) = the commit bit: true when transaction 
with highest timestamp that wrote X committed 
If 1 element = 1 page,  
these are associated with each page X in the buffer pool 
Magda Balazinska - CSE 444, Spring 2012 8 
Magda Balazinska - CSE 444, Spring 2012 9 
Time-based Scheduling 
•? Note: simple version that ignores the commit bit 
•? Transaction wants to read element X 
–? If TS(T) < WT(X)  abort 
–? Else read and update RT(X) to larger of TS(T) or RT(X) 
•? Transaction wants to write element X 
–? If TS(T) < RT(X) abort 
–? Else if TS(T) < WT(X) ignore write & continue (Thomas Write Rule) 
–? Otherwise, write X and update WT(X) to TS(T) 
Details 
Read too late: 
•? T wants to read X, and TS(T) < WT(X) 
START(T) … START(U) … w
U
(X) . . . r
T
(X) 
Need to rollback T ! 
Magda Balazinska - CSE 444, Spring 2012 10 
Details 
Write too late: 
•? T wants to write X, and TS(T) < RT(X) 
START(T) … START(U) … r
U
(X) . . . w
T
(X) 
Need to rollback T ! 
Magda Balazinska - CSE 444, Spring 2012 11 
Details 
Write too late, but we can still handle it: 
•? T wants to write X, and  
TS(T) >= RT(X)  but WT(X) > TS(T) 
START(T) … START(V) … w
V
(X) . . . w
T
(X) 
Don’t write X at all ! 
(but see later…) 
Magda Balazinska - CSE 444, Spring 2012 12 
3 
More Problems 
Read dirty data: 
•? T wants to read X, and WT(X) < TS(T) 
•? Seems OK, but… 
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 
Magda Balazinska - CSE 444, Spring 2012 13 
More Problems 
Write dirty data: 
•? T wants to write X, and WT(X) > TS(T) 
•? Seems OK not to write at all, but … 
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 
Magda Balazinska - CSE 444, Spring 2012 14 
Timestamp-based Scheduling 
•? When a transaction T requests r(X) or w(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 
Magda Balazinska - CSE 444, Spring 2012 15 
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: 18.8.4 
Magda Balazinska - CSE 444, Spring 2012 16 
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
, . . . 
•? Let T read an older version, with appropriate 
timestamp 
TS(X
t
) > TS(X
t-1
) > TS(X
t-2
) > . . . 
Magda Balazinska - CSE 444, Spring 2012 17 
Details 
•? When w
T
(X) occurs,  
 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 
–? 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 
Magda Balazinska - CSE 444, Spring 2012 18 
4 
Example using Basic Timestamps 
T
1 
150 
 
R
1
(A) 
W
1
(A) 
Magda Balazinska - CSE 444, Spring 2012 19 
T
2 
200 
 
 
 
R
2
(A) 
W
2
(A) 
T
3 
175 
 
 
 
 
 
R
3
(A) 
Abort 
A
 
RT=0 
WT=0 
RT=150 
WT=150 
RT=200 
WT=200 
 
 
RT=225 
T
4 
225 
 
 
 
 
 
 
 
R
4
(A) 
Example using Multiversion  
T
1 
150 
 
R
1
(A) 
W
1
(A) 
Magda Balazinska - CSE 444, Spring 2012 20 
T
2 
200 
 
 
 
R
2
(A) 
W
2
(A) 
T
3 
175 
 
 
 
 
 
R
3
(A) 
A
0 
 
 
Read 
T
4 
225 
 
 
 
 
 
 
 
R
4
(A) 
A
150 
 
 
 
 
Create 
Read 
 
Read 
A
200 
 
 
 
 
 
Create 
 
 
Read 
 
 
 
Tradeoffs 
•? Locks: 
–? Great when there are many conflicts 
–? Poor when there are few conflicts 
•? Timestamps 
–? Poor when there are many conflicts (rollbacks) 
–? Great when there are few conflicts 
•? Compromise 
–? READ ONLY transactions ? timestamps 
–? READ/WRITE transactions ? locks 
Magda Balazinska - CSE 444, Spring 2012 21 
Outline 
•? Concurrency control by timestamps (18.8) 
•? Concurrency control by validation (18.9) 
Magda Balazinska - CSE 444, Spring 2012 22 
Concurrency Control by Validation 
•? Each transaction T defines a read set RS(T) and a 
write set WS(T) 
•? Each transaction proceeds in three phases: 
–? Read all elements in RS(T).  Time = START(T) 
–? Validate (may need to rollback).  Time = VAL(T) 
–? Write all elements in WS(T). Time = FIN(T) 
Main invariant: the serialization order is VAL(T) 
Magda Balazinska - CSE 444, Spring 2012 23 
Avoid r
T
(X) - w
U
(X) Conflicts 
U: Read phase Validate Write phase 
START(U) 
VAL(U) FIN(U) 
T: Read phase Validate ? 
START(T) 
IF  RS(T) n WS(U) and FIN(U) > START(T)  
        (U has validated and  U has not finished before T begun) 
Then ROLLBACK(T) 
conflicts 
Magda Balazinska - CSE 444, Spring 2012 24 
5 
Avoid w
T
(X) - w
U
(X) Conflicts 
U: Read phase Validate Write phase 
START(U) 
VAL(U) FIN(U) 
T: Read phase Validate Write phase ? 
START(T) VAL(T) 
IF  WS(T) n WS(U) and FIN(U) > VAL(T)  
        (U has validated and  U has not finished before T validates) 
Then ROLLBACK(T) 
conflicts 
25 Magda Balazinska - CSE 444, Spring 2012 
Validation Rules Summary 
•? Check that RS(T) n WS(U) is empty for any 
previously validated U that did not finish before 
T started (i.e., FIN(U) > START(T)) 
•? Check that WS(T) n WS(U) is empty for any 
previously validated U that did not finish before 
T validated (i.e, FIN(U) > VAL(T))   
Magda Balazinska - CSE 444, Spring 2012 26 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!