Introduction to Database SystemsCSE 444Lecture 12 Transactions: concurrency control(part 2)CSE 444 - Summer 2010 1Outline• Concurrency control by timestamps (18.8)• Concurrency control by validation (18.9)yy ()• Concurrency control by snapshot isolation• But first, a word about Phantoms…CSE 444 - Summer 2010 2Phantom Problem•So far we have assumed the database to be aSo far we have assumed the database to be a static collection of elements (=tuples)• If tuples are inserted/deleted then the phantom problem appears3CSE 444 – Summer 2010The Phantom Problem“Phantom”=tuplevisible only during some part ofthe transactionT1: select count(*) from R where price>20T2: Phantom tuplevisible only during some part ofthe transaction. . . .. . . . . . . .. . . .. . . .insert into R(name,price)values(‘Gizmo’50). . . . select count(*) from R where price>20values( Gizmo, 50). . . .R1(X), R1(Y), R1(Z), W2(New), R1(X), R1(Y), R1(Z), R1(New) The schedule is conflictserializableyet we getdifferentcounts!4The schedule is conflict-serializable, yet we getdifferent counts !Not serializible because of phantoms.Dealing with Phantoms•In astaticdatabase:In a static database:– Conflict serializability implies serializabilityIdidtb thi fild t h t•In a dynamic database, this may fail due to phantoms•Strict 2PL guarantees conflictserializability, but notStrict 2PL guarantees conflict serializability, but not serializabilityE i f d li ith h t•Expensive ways of dealing with phantoms:– Lock the entire table, or– Lock the index entry for ‘price’ (if index is available)5–Or use predicate locks (a lock on an arbitrary predicate)Serializable transactions are very expensiveConcurrency Control Mechanisms• Pessimistic:– Locks• Optimistic– Timestamp based: basic, multiversion– ValidationShtilti itfbth–Snapshot isolation: a variant of bothCSE 444 - Summer 2010 6Timestamps• Each transaction receives a unique timestamp TS(T)Could be:• The system’s clock•A unique counter incremented by the scheduler•A unique counter, incremented by the schedulerCSE 444 - Summer 2010 7TimestampsMain invariant:The timestamp order definesthe serializationorder of the transactionthe serialization order of the transactionWill generate a schedule that is view-equivalentto a serial schedule, and is recoverableCSE 444 - Summer 2010 8Main IdeaMain Idea•For any two conflicting actions ensure that•For any two conflicting actions, ensure that their order is the serialized order:In each of these casesIn each of these cases•wU(X) . . . rT(X)•r(X)w(X)Read toolate ?•rU(X) . . . wT(X)•wU(X) . . . wT(X)Write toolate ?When T requests r/wT(X), needt h k TS(U) < TS(T)late ?to check TS(U) <= TS(T)9TimestampsWith each element X, associate•RT(X)= the highest timestamp of any ttithtdXtransaction that read X•WT(X) = the highest timestamp of any transaction that wrote Xtransaction that wrote X• C(X) = the commit bit: true when transaction with highest timestamp that wrote X committedgpIf 1 element = 1 page, these are associated with eachpageXinthe buffer pooleach page X in the buffer poolCSE 444 - Summer 2010 10Time-based Scheduling• Note: simple version that ignores the commit bit– If transactions abort, may result in non-recoverable schedule• Transaction wants to read element X– If TS(T) < WT(X) then ROLLBACK–Else read X and update RT(X) to larger of TS(T) or RT(X)•Transaction wants to writeelement XTransaction wants to writeelement X– If TS(T) < RT(X) then ROLLBACK– Else if TS(T) < WT(X) ignore write & continue (Thomas Write Rule)–Otherwise writeXand updateWT(X)to TS(T)CSE 444 - Summer 2010 11Otherwise, writeX and update WT(X) to TS(T)DetailsRead too late:• T wants to read X, and TS(T)< WT(X)()()START(T) … START(U) … wU(X) . . . rT(X)Need to rollback T !CSE 444 - Summer 2010 12DetailsWrite too late:• T wants to write X, and TS(T)< RT(X)()()START(T) … START(U) … rU(X) . . . wT(X)Need to rollback T !CSE 444 - Summer 2010 13DetailsWrite 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 !(Thomas’rule)(Thomas rule)CSE 444 - Summer 2010 14Ensuring Recoverable Schedules• Recall the definition: if 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 t ti th t l t t X h itt dtransaction that last wrote X has committedCSE 444 - Summer 2010 15Ensuring Recoverable SchedulesRead 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)() ()U()T()()If C(X)=false, T needs to wait for it to become trueCSE 444 - Summer 2010 16Ensuring Recoverable SchedulesNeed to revise Thomas’ rule:• 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)() ()U()T()()If C(X)=false, T needs to wait for it to become trueCSE 444 - Summer 2010 17Timestamp-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:and decides one of:•To grant the request or•To grant the request, or• To rollback T (and restart with later timestamp)•To delay T until C(X) =true•To delay T until C(X) =trueCSE 444 - Summer 2010 18Timestamp-based SchedulingTransaction wants to READ element XIf TS(T) < WT(X) then ROLLBACKElse If C(X) = false, then WAITElse READ and update RT(X) to larger of TS(T) or RT(X)se a d upda e ( ) o a ge o S( ) o ( )Transaction wants to WRITE element XIf TS(T) < RT(X) then ROLLBACKIf TS(T) < RT(X) then ROLLBACKElse if TS(T) < WT(X)Then If C(X) = false then WAIT else IGNORE write (Thomas Write Rule)else IGNORE write (Thomas Write Rule) Otherwise, WRITE, and update WT(X)=TS(T), C(X)=falseSee book sec 18 8 4 for detailed rules19CSE 444 – Summer 2010 See book sec. 18.8.4 for detailed rulesSummary of Timestamp-basedSummary of Timestampbased Scheduling• Conflict-serializable• Recoverable– Even avoids cascading aborts• Does NOT handle phantomspCSE 444 - Summer 2010 20Multiversion Timestamp• When transaction T requests r(X)but WT(X) > TS(T), then T must rollback• Idea: keep multiple versions of X:XXXXt, Xt-1, Xt-2, . . .TS(Xt) > TS(Xt-1) > TS(Xt-2) > . . .• Let T read an older version, with appropriate timestamppCSE 444 - Summer 2010
View Full Document
Unlocking...