CS计算机代考程序代写 database concurrency data structure 2021/4/28 Optimistic Concurrency Control

2021/4/28 Optimistic Concurrency Control
Optimistic Concurrency Control
Optimistic Concurrency Control Validation
Validation Check
>>
COMP9315 21T1 ♢ Optimistic CC ♢ [0/8]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-optimistic/slides.html 1/10

2021/4/28 Optimistic Concurrency Control
∧ >> ❖ Optimistic Concurrency Control
Locking is a pessimistic approach to concurrency control: limit concurrency to ensure that conicts don’t occur Costs: lock management, deadlock handling, contention.
In scenarios where there are far more reads than writes …
don’t lock (allow arbitrary interleaving of operations) check just before commit that no conicts occurred if problems, roll back conicting transactions
Optimistic concurrency control (OCC) is a strategy to realise this.
COMP9315 21T1 ♢ Optimistic CC ♢ [1/8]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-optimistic/slides.html 2/10

2021/4/28 Optimistic Concurrency Control
<< ∧ >> ❖ Optimistic Concurrency Control (cont)
Under OCC, transactions have three distinct phases:
Reading: read from database, modify local copies of data
Validation: check for conicts in updates Writing: commit local copies of data to database
Timestamps are recorded at points S, V, F :
COMP9315 21T1 ♢ Optimistic CC ♢ [2/8]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-optimistic/slides.html 3/10

2021/4/28 Optimistic Concurrency Control
❖ Validation
Data structures needed for validation:
S … set of txs that are reading data and computing results
V … set of txs that have reached validation (not yet committed)
F … set of txs that have nished (committed data to storage) for each Ti, timestamps for when it reached S, V, F
RS(Ti) set of all data items read by Ti
WS(Ti) set of all data items to be written by Ti
Use the V timestamps as ordering for transactions assume serial tx order based on ordering of V(Ti)’s
COMP9315 21T1 ♢ Optimistic CC ♢ [3/8]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-optimistic/slides.html 4/10

2021/4/28 Optimistic Concurrency Control
❖ Validation (cont) Two-transaction example:
allow transactions T1 and T2 to run without any locking
check that objects used by T2 are not being changed by T1
if they are, we need to roll back T2 and retry Case 0: serial execution … no problem
COMP9315 21T1 ♢ Optimistic CC ♢ [4/8]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-optimistic/slides.html 5/10

2021/4/28 Optimistic Concurrency Control
❖ Validation (cont)
Case 1: reading overlaps validation/writing
T2 starts while T1 is validating/writing
if some X being read by T2 is in WS(T1)
then T2 may not have read the updated version of X so, T2 must start again
<< ∧ >>
COMP9315 21T1 ♢ Optimistic CC ♢ [5/8]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-optimistic/slides.html 6/10

2021/4/28 Optimistic Concurrency Control
<< ∧ >>
❖ Validation (cont)
Case 2: reading/validation overlaps validation/writing
T2 starts validating while T1 is validating/writing if some X being written by T2 is in WS(T1)
then T2 may end up overwriting T1’s update
so, T2 must start again
COMP9315 21T1 ♢ Optimistic CC ♢ [6/8]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-optimistic/slides.html 7/10

2021/4/28 Optimistic Concurrency Control
❖ Validation Check Validation check for transaction T
for all transactions Ti ≠ T if T∈S & Ti∈F, then ok
if T∉V & V(Ti) < S(T) < F(Ti), then check WS(Ti) ∩ RS(T) is empty if T∈V & V(Ti) < V(T) < F(Ti), then check WS(Ti) ∩ WS(T) is empty If this check fails for any Ti, then T is rolled back. COMP9315 21T1 ♢ Optimistic CC ♢ [7/8] << ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-optimistic/slides.html 8/10

2021/4/28 Optimistic Concurrency Control
<< ∧ ❖ Validation Check (cont) OCC prevents: T reading dirty data, T overwriting Ti's changes Problems with OCC: increased roll backs** tendency to roll back "complete" tx's cost to maintain S,V,F sets ** "Roll back" is relatively cheap changes to data are purely local before Writing phase no requirement for logging info or undo/redo (see later) COMP9315 21T1 ♢ Optimistic CC ♢ [8/8] https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-optimistic/slides.html 9/10 2021/4/28 Optimistic Concurrency Control Produced: 15 Apr 2021 https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-optimistic/slides.html 10/10