1Transaction ProcessingCPS 116Introduction to Database Systems2Announcements (December 1) Homework #4 due next Tuesday (Dec. 6) Project demo period will start next Tuesday Watch for an email tomorrow about scheduling Final exam on December 133Review ACID Atomicity: TX’s are either completely done or not done at all Consistency: TX’s should leave the database in a consistent state Isolation: TX’s must behave as if they are executed in isolation Durability: Effects of committed TX’s are resilient against failures SQL transactions-- Begins implicitlySELECT …;UPDATE …;ROLLBACK | COMMIT;4Concurrency control Goal: ensure the “I” (isolation) in ACIDA B CT1:read(A);write(A);read(B);write(B);commit;T2:read(A);write(A);read(C);write(C);commit;5Good versus bad schedulesT1T2r(A)w(A)r(B)w(B)r(A)w(A)r(C)w(C)T1T2r(A)w(A)r(A)w(A)r(B)r(C)w(B)w(C)T1T2r(A)r(A)w(A)w(A)r(B)r(C)w(B)w(C)Good!Good! (But why?)Bad!Read 400Read 400Write400 – 100Write400 – 506Serial schedule Execute transactions in order, with no interleavingof operations T1.r(A), T1.w(A), T1.r(B), T1.w(B), T2.r(A), T2.w(A), T2.r(C), T2.w(C) T2.r(A), T2.w(A), T2.r(C), T2.w(C), T1.r(A), T1.w(A), T1.r(B), T1.w(B))Isolation achieved by definition! Problem: no concurrency at all Question: how to reorder operations to allow more concurrency27Conflicting operations Two operations on the same data item conflict if at least one of the operations is a write r(X) and w(X) conflict w(X) and r(X) conflict w(X) and w(X) conflict r(X) and r(X) do not r/w(X) and r/w(Y) do not Order of conflicting operations matters E.g., if T1.r(A) precedes T2.w(A), then conceptually, T1should precede T28Precedence graph A node for each transaction A directed edge from Tito Tjif an operation of Tiprecedes and conflicts with an operation of Tjin the scheduleT1T2r(A)w(A)r(A)w(A)r(B)r(C)w(B)w(C)T1T2r(A)r(A)w(A)w(A)r(B)r(C)w(B)w(C)T1T2Good:no cycleT1T2Bad:cycle9Conflict-serializable schedule A schedule is conflict-serializable iff its precedence graph has no cycles A conflict-serializable schedule is equivalent to some serial schedule (and therefore is “good”) In that serial schedule, transactions are executed in the topological order of the precedence graph You can get to that serial schedule by repeatedly swapping adjacent, non-conflicting operations from different transactions10Locking Rules If a transaction wants to read an object, it must first request a shared lock (S mode) on that object If a transaction wants to modify an object, it must first request an exclusive lock (X mode) on that object Allow one exclusive lock, or multiple shared locksMode of lock(s)currently heldby other transactionsMode of the lock requestedGrant the lock?SXSYesNoXNoNoCompatibility matrix11Basic locking is not enoughT1T2r(A)w(A)r(A)w(A)r(B)w(B)r(B)w(B)lock-X(A)lock-X(B)unlock(B)unlock(A)lock-X(A)unlock(A)unlock(B)lock-X(B)Possible scheduleunder lockingBut still notconflict-serializable!T1T2Read 100Write 100+1Read 101Write 101*2Read 100Write 100*2Read 200Write 200+1Add 1 to both A and B(preserve A=B)Multiply both A and B by 2(preserves A=B)A ≠ B!12Two-phase locking (2PL) All lock requests precede all unlock requests Phase 1: obtain locks, phase 2: release locksT1T2r(A)w(A)r(A)w(A)r(B)w(B)r(B)w(B)lock-X(A)lock-X(B)unlock(B)unlock(A)lock-X(A)lock-X(B)Cannot obtain the lock on Buntil T1unlocksT1T2r(A)w(A)r(A)w(A)r(B)w(B)r(B)w(B)2PL guarantees aconflict-serializableschedule313Problem of 2PL T2has read uncommitted data written by T1 If T1aborts, then T2must abort as well Cascading aborts possible if other transactions have read data written by T2 Even worse, what if T2commits before T1? Schedule is not recoverable if the system crashes right after T2commitsT1T2r(A)w(A)r(A)w(A)r(B)w(B)r(B)w(B)Abort!14Strict 2PL Only release locks at commit/abort time A writer will block all other readers until the writer commits or aborts) Used in most commercial DBMS (except Oracle)15Recovery Goal: ensure “A” (atomicity) and “D” (durability) in ACID Execution model: to read/write X The disk block containing X must be first brought into memory X is read/written in memory The memory block containing X, if modified, must be written back (flushed) to disk eventuallyCPUMemoryDiskXY…XY…16Failures System crashes in the middle of a transaction T; partial effects of T were written to disk How do we undo T (atomicity)? System crashes right after a transaction T commits; not all effects of T were written to disk How do we complete T (durability)?17Naïve approach Force: When a transaction commits, all writes of this transaction must be reflected on disk Without force, if system crashes right after T commits, effects of Twill be lost)Problem: Lots of random writes hurt performance No steal: Writes of a transaction can only be flushed to disk at commit time With steal, if system crashes before T commits but after some writes of T have been flushed to disk, there is no way to undo these writes)Problem: Holding on to all dirty blocks requires lots of memory18Logging Log Sequence of log records, recording all changes made to the database Written to stable storage (e.g., disk) during normal operation Used in recovery Hey, one change turns into two—bad for performance? But writes are sequential (append to the end of log) Can use dedicated disk(s) to improve performance419Undo/redo logging rules Record values before and after each modification:h Ti, X, old_value_of_X, new_value_of_X i A transaction Tiis committed when its commit log recordh Ti, commit i is written to disk Write-ahead logging (WAL): Before X is modified on disk, the log record pertaining to X must be flushed Without WAL, system might crash after X is modified on disk but before its log record is written to disk—no way to undo No force: A transaction can commit even if its modified memory blocks have not be written to disk (since redo information is logged) Steal: Modified memory blocks can be flushed to disk anytime (since undo information is logged)20Undo/redo logging exampleread(A, a); a = a – 100;write(A, a);read(B, b); b = b + 100;write(B, b);A = 800B = 400700500<T1, start><T1, A, 800, 700><T1, B, 400, 500><T1, commit>T1(balance transfer of $100 from A to B)MemoryA = 800B = 400DiskLog700Steal: can flushbefore
View Full Document