Concurrency Control and RecoveryFlight ReservationProblem #1Bank TransfersTransactionsACID PropertiesHow Do We Assure ACID?More on SQL and TransactionsDirty DataProblems with Dirty DataConcurrency Control MethodsSchedulesAcceptable SchedulesAborted TransactionsLocksHandling Lock RequestsTwo-Phase Locking (2PL)Serializability GraphsConflict SerializabilityDeadlocksDeadlock PreventionAn Alternative to PreventionDeadlock DetectionDetection Versus PreventionMotivation for RecoveryHandling the Buffer PoolBasic Idea: LoggingSlide 29RecoverySummaryConcurrency Control and Recovery• In real life:• users access the database concurrently, and• systems crash.• Concurrent access to the database also improves performance, yields better utilization of resources.• BUT: if not careful, concurrent access can lead to incorrect database states. Crashes can also leave the database in incoherent states.• Basic concurrency/recovery concept: transaction • executed atomically. All or nothing.• We cover:• transactions in SQL• implementation of transactions and recovery.Flight Reservation get values for :flight, :date, :seat EXEC SQL SELECT occupied INTO :occ FROM Flight WHERE fltNum = :flight AND fltdt= :date AND fltSeat=:seat if (!occ) { EXEC SQL UPDATE Flights SET occupied = ‘true’ WHERE fltNum= :flight AND fltdt= :date AND fltSeat=:seat /* more code missing */ } else /* notify customer that seat is not available */Problem #1Customer 1 - finds a seat emptyCustomer 2 - finds the same seat emptyCustomer 1 - reserves the seat.Customer 2 - reserves the seat.Customer 1 will not be happy.serializabilityBank TransfersTransfer :amount from :account1 to :account2EXEC SQL SELECT balance INTO :balance1 FROM Accounts WHERE accNo = :account1if (balance1 >= amount) EXEC SQL UPDATE Accounts SET balance = balance + :amount WHERE acctNo = :account2; EXEC SQL UPDATE Accounts SET balance = balance - :amount WHERE acctNo = :account1;Crash...TransactionsThe user/programmer can group a sequence of commands so that they are executed atomically and in a serializable fashion: • Transaction commit: all the operations should be done and recorded.• Transaction abort: none of the operations should be done.In SQL:• EXEC SQL COMMIT;• EXEC SQL ROLLBACK; Easier said than done...ACIDACID PropertiesAAtomicity: all actions of a transaction happen, or none happen.CConsistency: if a transaction is consistent, and the database starts from a consistent state, then it will end in a consistent state.IIsolation: the execution of one transaction is isolated from other transactions.DDurability: if a transaction commits, its effects persist in the database.How Do We Assure ACID?Concurrency control: Guarantees consistency and isolation, given atomicity.Logging and Recovery: Guarantees atomicity and durability.If you are going to be in the logging business, one of the thingsthat you’ll have to do is learn about heavy equipment. -- Robert VanNatta Logging History of Columbia CountyMore on SQL and TransactionsRead only transactions:• if the transaction is only reading, we can allow more operations in parallel. EXEC SQL SET TRANSACTION READ ONLY;The default is: SET TRANSACTION READ WRITE;Dirty DataData that has been written by a transaction that has not committedyet is called dirty data.Do we allow our transaction to read dirty data? It may go away…In SQL: SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTEDNote: default for READ UNCOMMITTED transactions is that they are READ ONLY.Problems with Dirty DataTransfer program: 1. Transfer $N from account 1 to account 2 2a. If account 1 has enough for the transfer, 2b. subtract $N from account 1, and commit. 2c. Subtract $N from account 2, and commit.Bad scenario: A1: $100, A2: $200, A3: $300 T1: transfer $150 from A1 to A2 T2: transfer $250 from A2 to A3.Events:• T2 does step 1, -> A3 has $550• T1 does step 1, -> A2 has $350• T2 does step 2a, all is ok.• T1 does step 2a and finds that A1 doesn’t have enough funds.• T2 does step 2b, -> A2 now has $100• T1 does step 2c, -> A2 now has -$50.Concurrency Control Methods• Schedules• Serial schedules• Serializable schedules• Locking• Lock manager• 2 Phase Locking• Deadlocks: • Prevention• DetectionSchedules•A schedule is an interleaving of a set of actionsof different transactions, such that the actions of any single transaction are in order.• A schedule represents some actual sequence of database actions.• In a complete schedule, every transaction either commits or aborts.• Initial state + Schedule -> Final state.Acceptable SchedulesSerial schedules:• The transactions run one at a time from beginning to completion. • Note: there are many possible serial schedules. Each one is OK. The DBMS does not provide any guarantee in which order concurrently submitted transactions are executed.Serializable schedules:• Final state is what some serial schedule would have produced.Aborted TransactionsSlight modification to the definition:A schedule is serializable if it is equivalent to a serial scheduleof committed transactions.• As if the aborted transactions never happened.Two issues to consider w.r.t. aborted transactions:• how does one undo the effect of a transaction?• What if another transaction sees the effects of an aborted one?LocksConcurrency control is usually done via locking.The lock manager maintains a list of entries:• object identifier (can be page, record, etc.)• number of objects holding lock on the object• nature of the lock (shared or exclusive)• pointer to a list of lock requests.Lock compatibility table: If a transaction cannot get a lock, it is suspended on a wait queue.--S X--SX Handling Lock RequestsLock Request (XID, OID, Mode)Currently Locked?Grant LockEmpty Wait Queue?Mode==XMode==SNoYesNoYesPut on QueueYesNoTwo-Phase Locking (2PL)• 2 phase locking:• if T wants to read an object, it first obtains an S lock.• If T wants to write
View Full Document