1Chapter 18 1Chapter 18:Concurrency Control(Slides by Hector Garcia-Molina,http://www-db.stanford.edu/~hector/cs245/notes.htm)Chapter 18 2Chapter 18 Concurrency Control T1 T2 … TnDB(consistencyconstraints)Chapter 18 3What’s Concurrency Control• The general process ofassuring that transactionspreserve consistencywhen executingsimultaneously.• Scheduler may delay therequests, or abort thetransactionTransactionManagerSchedulerBufferRead/writerequestsReads/writes2Chapter 18 4Assumption• Every individual transaction transforms theDB from a consistent state to anotherconsistent state– Transactions maintain DB consistency• Problem: Concurrently running transactions– Schedules of concurrent actions of transactionsmake a difference– A schedule is a time-ordered actions taken by oneor more transactionsChapter 18 5Example:T1: Read(A) T2: Read(A)A ← A+100 A ← A×2Write(A) Write(A)Read(B) Read(B)B ← B+100 B ← B×2Write(B) Write(B)Constraint: A=BChapter 18 6Schedule AT1 T2Read(A); A ← A+100Write(A);Read(B); B ← B+100;Write(B);Read(A);A ← A×2;Write(A); Read(B);B ← B×2;Write(B);A B25 25125125250250250 2503Chapter 18 7Schedule BT1 T2Read(A);A ← A×2;Write(A);Read(B);B ← B×2;Write(B);Read(A); A ← A+100Write(A);Read(B); B ← B+100;Write(B);A B25 255050150150150 150Chapter 18 8Schedule CT1 T2Read(A); A ← A+100Write(A);Read(A);A ← A×2;Write(A);Read(B); B ← B+100;Write(B); Read(B);B ← B×2;Write(B);A B25 25125250125250250 250Chapter 18 9Schedule DT1 T2Read(A); A ← A+100Write(A);Read(A);A ← A×2;Write(A); Read(B);B ← B×2;Write(B);Read(B); B ← B+100;Write(B);A B25 2512525050150250 1504Chapter 18 10Schedule ET1 T2’Read(A); A ← A+100Write(A);Read(A);A ← A×1;Write(A); Read(B);B ← B×1;Write(B);Read(B); B ← B+100;Write(B);A B25 2512512525125125 125Same as Schedule Dbut with new T2’Chapter 18 11• Want schedules that are “good”,regardless of– initial state and– transaction semantics• Only look at order of read and writesExample:Sc=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)Chapter 18 12Sc’=r1(A)w1(A) r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) T1 T2Example:Sc=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)5Chapter 18 13However, for Sd:Sd=r1(A)w1(A)r2(A)w2(A) r2(B)w2(B)r1(B)w1(B)Chapter 18 14T1 T2 Sd cannot be rearrangedinto a serial scheduleSd is not “equivalent” toany serial scheduleSd is “bad”• T2 → T1• Also, T1 → T2Chapter 18 15Returning to ScSc=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) T1 → T2 T1 → T2 no cycles ⇒ Sc is “equivalent” to aserial schedule(in this case T1,T2)In a serial schedule, actions from different transactions do not mix.6Chapter 18 16Conflict Actions• A pair of actions such that if their orderis changed, then the behavior of atleast one of the transactions canchange• Actions that do not conflict– ri(x), rj(y), even if x=y– ri(x), wj(y) is not a conflict provided x!=y– wi(x), wj(y) is not a conflict provided x!=yChapter 18 17Conflict Actions• Actions that do conflict– Two actions of the same transaction• ri(x), ri(y)– A read and a write of the same DB elementby two different transactions• ri(x), wj(x)– Two writes of the same DB element by twodifferent transactions• wi(x), wj(x)Chapter 18 18Conflict Actions• Simple rules– Two actions of different transactionsconflict if• They involve the same DB element, and• At least one is a write• Conflict actions cannot be swappedwithout affecting the involvedtransactions7Chapter 18 19ConceptsTransaction: sequence of ri(x), wi(x) actionsConflicting actions: r1(A) w2(A) w1(A) w2(A) r1(A) w2(A)Schedule: represents chronological orderin which actions are executedSerial schedule: no interleaving of actions or transactionsChapter 18 20DefinitionS1, S2 are conflict equivalent schedulesif S1 can be transformed into S2 by aseries of swaps on non-conflictingactions.Chapter 18 21Exercise• S1: r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)• S2: r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)• S3: r2(A)w2(A)r1(A)w1(A)r1(B)w1(B)r2(B)w2(B)• Is S1 conflict equivalent to S2?• How about S1 and S3?• How about S2 and S3?8Chapter 18 22DefinitionA schedule is conflict serializable if it isconflict equivalent to some serialschedule.Chapter 18 23Exercise• S1: r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)• S2: r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)• S3: r2(A)w2(A)r1(A)w1(A)r1(B)w1(B)r2(B)w2(B)• Is S1 conflict serializable?• How about S2?• How about S3?Chapter 18 24Nodes: transactions in SArcs: Ti → Tj whenever- pi(A), qj(A) are actions in S- pi(A) <S qj(A)- at least one of pi, qj is a writePrecedence graph P(S) (S is schedule)9Chapter 18 25Exercise:• What is P(S) forS = w3(A) w2(C) r1(A) w1(B) r1(C) w2(A) r4(A) w4(D)• Is S serializable?Chapter 18 26LemmaS1, S2 conflict equivalent ⇒ P(S1)=P(S2)Chapter 18 27Note: P(S1)=P(S2) ⇒ S1, S2 conflict equivalentCounter example:S1=w1(A) r2(A) w2(B) r1(B)S2=r2(A) w1(A) r1(B) w2(B)10Chapter 18 28TheoremP(S1) acyclic ⇐⇒ S1 conflict serializableProof:⇐: by cycle ⇒ not conflict serializable⇒: inductionKey observation: acyclic implies that atleast one node Ti has no incoming arc;all actions in Ti can be moved to thefront of S1Chapter 18 29Conflict Serializable v.s.Serializable• w1(y); w2(y); w2(x); w1(x); w3(x)– Conflict serializable?– Serializable?• Writes of X by T1 and T2 have no effectChapter 18 30How to enforce serializable schedules?Option 1: run system, recording P(S); at end of day, check for P(S) cycles and declare if execution was good11Chapter 18 31Option 2: prevent P(S) cycles from occurringT1 T2 ….. TnSchedulerDBHow to enforce serializable schedules?Chapter 18 32A locking protocolTwo new actions:lock (exclusive): li (A) unlock: ui (A)schedulerT1 T2locktableChapter 18 33Rule #1: Consistent transactionsTi: … li(A) … pi(A) … ui(A) ...12Chapter 18 34Rule #2 Legal schedulerS = …….. li(A) ………... ui(A) ……... no lj(A)Chapter 18 35• What schedules are legal?What transactions are consistent?S1 = l1(A)l1(B)r1(A)w1(B)l2(B)u1(A)u1(B)r2(B)w2(B)u2(B)l3(B)r3(B)u3(B)S2 = l1(A)r1(A)w1(B)u1(A)u1(B)l2(B)r2(B)w2(B)l3(B)r3(B)u3(B)S3 = l1(A)r1(A)u1(A)l1(B)w1(B)u1(B)l2(B)r2(B)w2(B)u2(B)l3(B)r3(B)u3(B)Exercise:Chapter 18 36Schedule FT1 T2l1(A);Read(A)A A+100;Write(A);u1(A) l2(A);Read(A)A Ax2;Write(A);u2(A)l2(B);Read(B)B Bx2;Write(B);u2(B)l1(B);Read(B)B B+100;Write(B);u1(B)13Chapter 18