Transaction Management, Concurrency Control and Recovery

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Lilac Safadi Transaction Management,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Lilac Safadi Transaction Management,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Lilac Safadi Transaction Management,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Lilac Safadi Transaction Management,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Lilac Safadi Transaction Management,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Lilac Safadi Transaction Management,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Lilac Safadi Transaction Management,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Lilac Safadi Transaction Management,*,Transaction Management, Concurrency Control and Recovery,Chapter 20,1,Overview,2,What are transactions?,What is a schedule?,What is concurrency control?,Why we need concurrency control:,Three problems.,Serializabiltiy and Concurrency control:,Theory:,Conflict Serializability,View Serializability,Practice:,Locking,Time-stamping,Optimistic techniques,Recovery facilities,What is a Transaction?,3,Transaction,Action, or series of actions, carried out by user or application, which accesses or changes contents of database.,Logical unit of work on the database.,Transforms database from one consistent state to another, although consistency may be violated during transaction.,Example,:,Read(,staffNo, salary),write(,staffNo, salary),What is a Transaction?,4,Can have one of two outcomes:,Success - transaction,commits,and database reaches a new consistent state.,Failure - transaction,aborts, and database must be restored to consistent state before it started (,rolled back,or,undone,).,Committed transaction cannot be aborted.,Aborted transactions that are rolled back can be restarted later.,Properties of Transactions,5,Four basic,(ACID),properties of a transaction are:,Atomicity,All or nothing property.,Consistency,Must transform database from one consistent state to another.,Isolation,Partial effects of incomplete transactions should not be visible to other transactions.,Durability,Effects of a committed transaction are permanent and must not be lost because of later failure.,We deal with transactions in a,schedule,.,Schedule,6,Time,T,1,T,2,T,3,Balance1,Balance2,t,0,Begin Transaction,100,200,t,1,Read(Balance1),Begin Transaction,100,200,t,2,Read(Balance1),Begin Transaction,100,200,t,3,Balance1 += 500,Read(Balance2),100,200,t,4,Write(Balance1),600,200,t,5,Commit,Read(Balance1),600,200,:,:,:,:,:,:,Order of execution,Running Transactions,Data Items affected,by transactions (optional),Start with t,0,or t,1,Schedule Rules,7,Never start two transactions at the same time.,Never perform Reads and Writes of different transactions at the same time.,Each transaction should end with a,commit,or,abort,(rollback).,Schedule Definitions,8,Schedule,Sequence of reads/writes by set of concurrent transactions.,Serial Schedule,Schedule where operations of each transaction are executed consecutively without any interleaved operations from other transactions.,No guarantee that results of all serial executions of a given set of transactions will be identical.,(Think of an example),Non-Serial Schedule,Schedule where operations from set of concurrent transactions are interleaved,Example of a Serial Schedule,9,Time,T,1,T,2,t,0,Begin Transaction,t,1,Read(Balance1),t,2,Balance1 += 500,t,3,Commit,t,4,Begin Transaction,t,5,Read(Balance1),t,6,Commit,Example of a non-Serial Schedule,10,Time,T,1,T,2,t,0,Begin Transaction,t,1,Begin Transaction,t,2,Read(Balance1),t,3,Read(Balance1),t,4,Commit,t,5,Balance1 += 500,t,6,Commit,What is Concurrency Control?,11,Concurrency,:,transactions running simultaneously.,Concurrency Control,:,Process of managing simultaneous operations (transactions) on the database without having them interfere with one another.,Prevents interference when two or more users are accessing database simultaneously and at least one is updating data.,Although two transactions may be correct in themselves, interleaving of operations may produce an incorrect result.,Why we Need Concurrency Control?,12,Three examples of potential problems caused by concurrency:,Lost update problem.,Uncommitted dependency problem.,Inconsistent analysis problem.,Lost Update Problem,13,Successfully completed update is overridden by another user.,T,1,withdrawing 10 from an account with bal,x, initially 100.,T,2,depositing 100 into same account.,Serially, final balance would be 190.,Loss of T,2,s update avoided by preventing T,1,from reading bal,x,until after update,TimeT,1,T,2,bal,x,t,1,begin-transaction100,t,2,begin-transaction read(,bal,x,)100,t,3,read(,bal,x,),bal,x =,bal,x,+100100,t,4,bal,x =,bal,x,-10 write(,bal,x,)200,t,5,write(,bal,x,) commit90,t,6,commit 90,Uncommitted Dependency Problem,14,Occurs when one transaction can see intermediate results of another transaction before it has committed.,T,4,updates bal,x,to 200 but it aborts, so bal,x,should be back at original value of 100.,T,3,has read new value of bal,x,(200) and uses value as basis of 10 reduction, giving a new balance of 190, instead of 90.,Problem avoided by preventing T,3,from reading bal,x,until after T,4,commits or aborts.,TimeT,3,T,4,bal,x,t,1,begin-transaction100,t,2,read(,bal,x,)100,t,3,bal,x =,bal,x,+100100,t,4,begin_transaction write(,bal,x,) 200,t,5,read(,bal,x,),:,200,t,6,bal,x =,bal,x,-10 rollback100,t,7,write(,bal,x,) 190,t,8,commit 190,Inconsistent Analysis Problem,15,Occurs when transaction reads several values but second transaction updates some of them during execution of first.,Sometimes referred to as,dirty read,or,unrepeatable read,.,T,6,is totaling balances of account x (100), account y (50), and account z (25).,Meantime, T,5,has transferred 10 from bal,x,to bal,z, so T,6,now has wrong result (10 too high).,Inconsistent Analysis Problem,16,Problem avoided by preventing T,6,from reading bal,x,and bal,z,until after T,5,completed updates.,Serializability,17,Serializability is a property of a schedule:,We say,serializable,schedule and,non-serializable,schedule.,But what makes a schedule serializable?,A serializable schedule is a,non-serial,schedule that allows transactions to execute concurrently without interfering with one another.,In other words, a,non-serial,schedule that is,equivalent,to,some,serial,schedule.,Main goal is to prevent transactions interfering with each other (3 problems discussed earlier).,Serializability,18,Two types of seriailizability:,Conflict.,View.,Serializability,Theory,Practice,Conflict Serializability Test,View Serializability Test,Locking,Time-stamping,Optimistic,Conflict Serializability,19,In serializability, ordering of read/writes is important:,(a) If two transactions only read a data item, they do,not conflict,and order is not important.,(b) If two transactions either read or write completely separate data items, they do,not conflict,and order is not important.,(c) If one transaction writes a data item and another reads or writes,same,data item, order of execution is important. They,conflict.,Conflict Serializability,20,Schedule S,1,is,conflict serializable,if it is conflict equivalent to a serial schedule.,Two ways of testing a schedule for conflict serialiazibility:,A schedule is conflict serializable if you can switch order of 2 non-conflicting operations until you reach a serial schedule.,Precedence graph.,Testing for Conflict Serializability,21,Time T,7,T,8,t,1,begin-transaction,t,2,read(,bal,x,),t,3,write(,bal,x,),t,4,begin_transaction,t,5,read(,bal,x,),t,6,write(,bal,x,),t,7,read(,baly,),t,8,write(,baly,),t,9,commit,t,10,read(,baly,),t,11,write(,baly,),t,12,commit,T,7,T,8,begin-transaction,read(,bal,x,),write(,bal,x,),begin_transaction,read(,bal,x,),read(,baly,),write(,bal,x,),write(,baly,),commit,read(,baly,),write(,baly,),commit,Testing for Conflict Serializability,22,Time T,7,T,8,t,1,begin-transaction,t,2,read(,bal,x,),t,3,write(,bal,x,),t,4,begin_transaction,t,5,read(,bal,y,),t,6,read(,balx,),t,7,write(,bal,x,),t,8,write(,baly,),t,9,commit,t,10,read(,baly,),t,11,write(,baly,),t,12,commit,T,7,T,8,begin-transaction,read(,bal,x,),write(,bal,x,),read(,baly,),write(,baly,),commit,begin_transaction,read(,bal,x,),write(,bal,x,),read(,baly,),write(,baly,),commit,Non-conflict Serializable Schedule,23,Time T,7,T,8,t,1,begin-transaction,t,2,read(,bal,x,),t,3,begin_transaction,t,4,write(,bal,x,),t,5,write(,balx,),t,6,commit,t,7,commit,T,7,T,8,begin-transaction,read(,bal,x,),write(,balx,),commit,begin_transaction,write(,bal,x,),commit,Testing for Conflict Serializability Precedence Graph,24,Create:,node for each transaction;,a directed edge T,i,T,j, if T,j,reads the value of an item written by T,i,;,a directed edge T,i,T,j, if T,j,writes a value into an item after it has been read by T,i,.,a directed edge T,i,T,j, if T,j,writes a value into an item after it has been written by T,i,.,If precedence graph contains cycle, schedule is,not conflict serializable,.,Test Schedule: Is it conflict serializable?,25,Time T,7,T,8,t,1,begin-transaction,t,2,read(,bal,x,),t,3,bal,x,=,bal,x,+100,t,4,write(,bal,x,),t,5,begin_transaction,t,6,read(,balx,),t,7,bal,x,=,bal,x,t,8,write(,bal,x,),t,9,read(,baly,),t,10,bal,y,=,bal,y,t,11,write(,bal,y,),t,12,commit,t,13,read(,baly,),t,14,write(,baly,),t,15,commit,View Serializability,26,Offers less stringent definition of schedule equivalence than conflict serializability.,Two schedules S,1,and S,2,are,view equivalent,if:,For each data item x, if T,i,reads initial value of x in S,1, T,i,must also read initial value of x in S,2,.,For each read on x by T,i,in S,1, if value read by x is written by T,j, T,i,must also read value of x produced by T,j,in S,2,.,For each data item x, if last write on x performed by T,i,in S,1, same transaction must perform final write on x in S,2,.,View Serializability,27,Schedule is,view serializable,if it is view equivalent to a serial schedule.,Every conflict serializable schedule is view serializable, although converse is not true.,It can be shown that any view serializable schedule that is not conflict serializable contains one or more,blind writes,.,All Schedules,View Serializable Schedules,Conflict Serializable Schedules,View Serializable Schedule,28,Time T,7,T,8,t,1,begin-transaction,t,2,read(,bal,x,),t,3,write(,bal,x,),t,4,read(,bal,y,),t,5,write(,baly,),t,6,commit,t,7,begin-transaction,t,8,read(,balx,),t,9,write(,bal,x,),t,10,read(,baly,),t,11,write(,baly,),t,12,commit,T,7,T,8,begin-transaction,read(,bal,x,),write(,bal,x,),begin_transaction,read(,balx,),write(,balx,),read(,baly,),write(,baly,),commit,read(,baly,),write(,baly,),commit,View Serializable Schedule,29,Time T,11,T,12,T,13,t,1,begin-transaction,t,2,read(,bal,x,),t,3,begin_transaction,t,4,write(,bal,x,),t,5,commit,t,6,write(,bal,x,),t,7,commit,t,8,begin_transaction,t,9,write(,bal,x,),t,10,commit,Is this schedule conflict serializable?,Recoverable Schedule,30,A schedule where, for each pair of transactions T,i,and T,j, if T,j,reads a data item previously written by T,i, then the commit operation of T,i,precedes the commit operation of T,j.,Concurrency Control Techniques,31,Serializability,Theory,Practice,Conflict Serializability Test,View Serializability Test,Locking,Time-stamping,Optimistic,Concurrency Control Techniques,32,Two basic concurrency control techniques:,Locking,Timestamping.,Both are,conservative,approaches: delay transactions in case they conflict with other transactions.,Optimistic,methods assume conflict is rare and only check for conflicts at commit.,Concurrency Control Techniques Overview,33,Locking,Time-stamping,Optimistic,Basic Rules,2PL,Deadlock Prevention,Basic Time-stamp Ordering,Multi-version Time-stamp Ordering,Deadlock Detection,Wait-Die,Wound-Wait,Wait-for Graph,Thomass Write Rule,Regular,Strict,Rigorous,Time outs,Locking,34,Main Idea:,Transaction uses locks to deny access to other transactions and so prevent incorrect updates.,Most widely used approach to ensure serializability.,A transaction must claim:,a,shared,(,read,) on x before it can read it.,or an,exclusive,(,write,) lock on x before it can write it.,Lock prevents other transactions from reading or writing the locked data item.,Locking Basic Rules,35,Shared Lock:,If transaction has,shared lock,on item, it can read but not update item.,More than one transaction can hold a shared lock on an item.,Exclusive Lock:,If transaction has,exclusive lock,on item, can both read and update item.,Only one transaction can hold an exclusive lock on an item.,Some systems allow transaction to:,upgrade read lock to an exclusive lock.,downgrade exclusive lock to a shared lock.,Locking - Commands,36,To acquire a shared (read) lock on X:,Read_Lock(x),RLock(X),Shared_Lock(X),SLock(X),To acquire an exclusive (write) lock on X:,Write_Lock(X),WLock(X),Exclusive_Lock(X),XLock(X),To release a lock on X:,Unlock(X),Time T,9,T,10,t,1,begin-transaction,t,2,write_lock(,bal,x,),t,3,read(,bal,x,),t,4,bal,x,=,bal,x,+ 100,t,5,write(,bal,x,),t,6,unlock(,bal,x,),t,7,begin_transaction,t,8,write_lock(,bal,x,),t,9,read(,balx,),t,10,bal,x,=,bal,x,t,11,write(,bal,x,),t,12,unlock(,bal,x,),t,13,write_lock(,bal,y,),t,14,read(,baly,),t,15,bal,y,=,bal,y,t,16,write(,bal,y,),t,17,commit/unlock(,bal,y,),t,18,write_lock(,bal,y,),t,19,read(,baly,),t,20,bal,y,=,bal,y,- 100,t,21,write(,baly,),t,22,commit/unlock(,bal,y,),Correct use of locks. But is the execution correct?,37,Two-Phase Locking (2PL),38,We just saw that locking alone doesnt always work.,Solution: 2PL.,Transaction follows 2PL protocol if all locking operations precede first unlock operation in the transaction.,Two phases for transaction:,Growing phase - acquires all locks but cannot release any locks.,Shrinking phase - releases locks but cannot acquire any new locks.,With 2PL, we can prevent the three problems.,Original Lost Update Problem,39,TimeT,1,T,2,bal,x,t,1,begin-transaction100,t,2,begin-transaction read(,bal,x,)100,t,3,read(,bal,x,),bal,x =,bal,x,+100100,t,4,bal,x =,bal,x,-10 write(,bal,x,)200,t,5,write(,bal,x,) commit90,t,6,commit 90,Preventing Lost Update Problem,40,TimeT,1,T,2,bal,x,t,1,begin-transaction100,t,2,begin_transactionwrite_lock(,bal,x,)100,t,3,write_lock(,bal,x,)read(,bal,x,)100,t,4,WAIT,bal,x =,bal,x,+100100,t,5,WAIT write(,bal,x,)200,t,6,WAIT commit/unlock(balx) 200,t,7,read(,bal,x,)200,t,8,bal,x =,bal,x,-10200,t,9,write(,bal,x,) 190,t,10,commit/unlock(,bal,x,) 190,Original Uncommitted Dependency Problem,41,TimeT,3,T,4,bal,x,t,1,begin-transaction100,t,2,read(,bal,x,)100,t,3,bal,x =,bal,x,+100100,t,4,begin_transaction write(,bal,x,) 200,t,5,read(,bal,x,),:,200,t,6,bal,x =,bal,x,-10 rollback100,t,7,write(,bal,x,) 190,t,8,commit 190,Preventing Uncommitted Dependency Problem,42,TimeT,3,T,4,bal,x,t,1,begin-transaction100,t,2,write_lock(,bal,x,)100,t,3,read(,bal,x,)100,t,4,begin_transaction,bal,x =,bal,x,+100100,t,5,write_lock(,bal,x,) write(,bal,x,)200,t,6,WAIT commit/unlock(balx) 200,t,7,read(,bal,x,)200,t,8,bal,x =,bal,x,-10200,t,9,write(,bal,x,) 190,t,10,commit/unlock(,bal,x,) 190,Original Inconsistent Analysis Problem,43,Preventing Inconsistent Analysis Problem,44,A Potential Problem with 2PL,45,Cascading Rollbacks,46,If,every,transaction in a schedule follows 2PL, schedule is serializable.,However, problems can occur with interpretation of when locks can be released.,Cascading rollback,is undesirable since they potentially lead to the undoing of a significant amount of work,To prevent this with 2PL, 2 solutions:,Rigorous 2PL:,Leave release of,all,locks until end of transaction.,Strict 2PL:,Holds only,exclusive,locks until the end of the transaction.,BOTH are still 2PL. So both still have growing and shrinking phases.,2PL still may cause,deadlock.,Problems with 2PL,47,Cascading Rollbacks:,Solved with strict or rigorous 2PL.,Dead Locks:,Happen in regular 2PL, and also in strict and rigorous 2PL.,Handled using deadlock detection and prevention techniques.,Deadlocks,48,Deadlock:,An impasse that may result when two (or more) transactions are each waiting for locks held by the other to be released.,Once a deadlock happens,only one way,to break deadlock:,abort,one or more of the transactions.,Deadlock should be transparent to user, so DBMS should restart aborted transaction(s).,Example Deadlock,49,Time T,9,t,1,begin-transaction,t,2,write_lock(,bal,x,),t,3,read(,bal,x,),t,4,bal,x,=,bal,x,- 10,t,5,write(,bal,x,),t,6,write_lock(,bal,y,),t,7,WAIT,t,8,WAIT,t,9,WAIT,t,10,WAIT,t,11 :,T,10,begin-transaction,write_lock(,bal,y,),read(,bal,y,),bal,y,=,bal,y,+ 100,write(,bal,y,),wait_lock(,bal,x,),WAIT,WAIT,WAIT,:,Deadlock Handling,50,Two general techniques for handling deadlock:,Deadlock prevention: DBMS doesnt allow deadlock to happen.,Timeouts.,Wait-Die.,Wound-wait.,Deadlock detection and recovery: DBMS allows deadlocks to happens but detects and recovers from them.,Wait-for Graphs (WFG).,Timeouts,51,Transaction that requests lock will only wait for a system-defined period of time.,If lock has not been granted within this period, lock request times out.,DBMS assumes transaction deadlocked, even though it may not be, and it aborts and automatically restarts the transaction.,Timestamps,52,Before we discuss Wait-die and Wound-wait techniques, introduce timestamps.,A timestamp is a unique number given to each transaction.,Traditionally, it is the time the transaction started.,The,smaller,the timestamp, the,older,the transaction.,Timestamps,53,TS(T,11,) = 1,TS(T,12,) = 3,TS(T,13,) = 8,Time T,11,T,12,T,13,t,1,begin-transaction,t,2,read(,bal,x,),t,3,begin_transaction,t,4,write(,bal,x,),t,5,commit,t,6,write(,bal,x,),t,7,commit,t,8,begin_tran