Introduction to Database Systems CSE 444 Lecture 14 Transactions: concurrency control (part 2) Magda Balazinska - CSE 444, Fall 2010 1Outline • Concurrency control by timestamps (18.8) • Concurrency control by validation (18.9) Magda Balazinska - CSE 444, Fall 2010 2Timestamps • Each transaction receives a unique timestamp TS(T) Could be: • The system’s clock • A unique counter, incremented by the scheduler Magda Balazinska - CSE 444, Fall 2010 3Timestamps The timestamp order defines the serialization order of the transaction Main invariant: Magda Balazinska - CSE 444, Fall 2010 4Main Idea • For any two conflicting actions, ensure that their order is the serialized order: In each of these cases • wU(X) . . . rT(X) • rU(X) . . . wT(X) • wU(X) . . . wT(X) Answer: Check that TS(U) < TS(T) When T wants to read X, rT(X), how do we know U, and TS(U) ? Read too late ? Write too late ? 5Timestamps 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, Fall 2010 6Magda Balazinska - CSE 444, Fall 2010 7 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) … wU(X) . . . rT(X) Need to rollback T ! Magda Balazinska - CSE 444, Fall 2010 8Details Write too late: • T wants to write X, and TS(T) < RT(X) START(T) … START(U) … rU(X) . . . wT(X) Need to rollback T ! Magda Balazinska - CSE 444, Fall 2010 9Details 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) … wV(X) . . . wT(X) Don’t write X at all ! (but see later…) Magda Balazinska - CSE 444, Fall 2010 10More Problems 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 Magda Balazinska - CSE 444, Fall 2010 11More 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)… wU(X). . . wT(X)… ABORT(U) If C(X)=false, T needs to wait for it to become true Magda Balazinska - CSE 444, Fall 2010 12Timestamp-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, Fall 2010 13Timestamp-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, Fall 2010 14Multiversion 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, . . . • Let T read an older version, with appropriate timestamp TS(Xt) > TS(Xt-1) > TS(Xt-2) > . . . Magda Balazinska - CSE 444, Fall 2010 15Details • When wT(X) occurs, 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 – 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 Magda Balazinska - CSE 444, Fall 2010 16Tradeoffs • 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, Fall 2010 17Outline • Concurrency control by timestamps (18.8) • Concurrency control by validation (18.9) Magda Balazinska - CSE 444, Fall 2010 18Concurrency 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, Fall 2010 19Avoid rT(X) - wU(X) Conflicts U: Read phase Validate Write phase START(U) VAL(U) FIN(U) T: Read phase Validate ? 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 Magda Balazinska - CSE 444, Fall 2010 20Avoid wT(X) - wU(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) ∩ WS(U) and FIN(U) > VAL(T) (U has validated and U has not finished before T validates) Then ROLLBACK(T) conflicts 21 Magda Balazinska - CSE 444, Fall
View Full Document
Unlocking...