BIT 4514: Database Technology for Business Fall 2019

BIT 4514: Database Technology for Business Fall 2019 Database concurrency control 1

Concurrency control Concurrency control is the process of managing simultaneous operations 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 2

Need for concurrency control Three examples of potential problems caused by concurrency: – – – Lost updates Uncommitted data Inconsistent retrievals 3

Lost update problem Occurs when a successfully completed update is overwritten by another transaction Example: – T1 withdraws 10 from an account with initial balx 100 – T2 deposits 100 into same account The final balance should be 190, but incorrectly overlapping transactions may lead to a final balance of only 90 4

Lost update problem (illustr.) Result: T 's update is lost 2 5

Uncommitted data problem Occurs when one transaction accesses the intermediate results of another transaction before they are committed – and the second transaction is then rolled back. Example: – T4 updates balx to 200, but there is an error in a later UPDATE, so balx is rolled back to original value of 100 – After the balx update, but before the rollback, T3 reads the new value of balx ( 200) and uses this as the basis of a 10 reduction, giving a final new balance of 190, not 90 6

Uncommitted data problem (illustr.) 7

Inconsistent retrievals problem Occurs when a transaction reads several values, but a different transaction updates some of them in the midst of this process – Some data are read before they are changed and others after they are changed – yielding inconsistent results Example: – T6 is totaling balances of account x ( 100), account y ( 50), and account z ( 25) – Meanwhile, T5 transfers 10 from balx to balz after x is totaled but before z is, so T6 has a result that's 10 too high 8

Inconsistent retrievals problem (illustr.) 9

Scheduler A serializable schedule is a schedule of a transaction's operations in which the interleaved execution of all active transactions yields the same results as if those transactions were executed in serial order – Waiting for one transaction to finish before starting any others may be inefficient – The built-in scheduler ensures efficient use of the DBMS and CPU by interleaving operations when possible If transactions access unrelated data, then there is no conflict among individual operations between transactions 10

Scheduling Methods for scheduling conflicting operations in concurrent transactions: – Locking methods – Timestamping 11

Lock terminology Lock granularity refers to the size of the locked resource: database-level table-level page-level row-level slow data access significant overhead An exclusive lock prohibits other users from reading the locked resource A shared lock allows other users to read the locked resource, but they cannot update it 12

Optimistic vs. Pessimistic locking Optimistic locking assumes that no transaction conflict(s) will occur: – DBMS processes a transaction to a temporary file; checks whether conflict occurred: If not, the transaction is finished If so, the transaction is repeated until there is no conflict Pessimistic locking assumes that conflict(s) will occur: – Locks are issued before a transaction is processed, and then the locks are released Optimistic locking is acceptable for applications with few update operations 13

Two-phase locking Two-phase locking (2PL) guarantees serializability – one of the most common techniques used to achieve this – Transactions are allowed to obtain as many locks as necessary (growing phase) – Once the first lock is released (shrinking phase), no additional locks can be obtained – Two-phase locking doesn't prevent deadlocks 14

Deadlock An impasse that may result when two (or more) transactions are waiting for locks held by the other to be released 15

Controlling deadlocks Three basic techniques: – Deadlock prevention Abort a transaction if possibility of deadlock Reschedule transaction for later execution – Deadlock detection DBMS periodically tests database for deadlocks If found, one transaction ("victim") is rolled back – Deadlock avoidance Transactions obtain all needed locks before execution 16

Timestamping Timestamp: A unique identifier created by DBMS that indicates the relative starting time of a transaction Transactions ordered globally so that older transactions (transactions with smaller timestamps) get priority in the event of conflict Conflict is resolved by rolling back and restarting the associated transaction - no locks, so no deadlocks Demands a lot of system resources (both memory and processing overhead) 17