1Transaction ProcessingCPS 116Introduction to Database Systems2Announcements (November 27) Homework #4 due this Thursday Project demo period starts on December 7 Each project gets a 30-minute with me and Yi Watch for an email this weekend scheduling demo slots Final exam on December 153Review 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 isolationDurability: Effects of committed TX’s are resilient against failuresDurability: Effects of committed TX s are resilient against failures SQL transactions-- Begins implicitlySELECT …;UPDATE …;ROLLBACK | COMMIT;24Concurrency control Goal: ensure the “I” (isolation) in ACIDT1:read(A);write(A);T2:read(A);write(A);A B Cread(B);write(B);commit;read(C);write(C);commit;5Good versus bad schedulesT1T2r(A)(A)T1T2r(A)(A)T1T2r(A)(A)Good!w(A)r(B)w(B)r(A)w(A)r(C)w(C)w(A)r(A)w(A)r(B)r(C)w(B)w(C)r(A)w(A)w(A)r(B)r(C)w(B)w(C)6Serial 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 concurrency37Conflicting 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 cycleT1T29Conflict-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 transactions410Locking 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 li lk(X d)hbjrequest 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?Compatibility matrixSXSYesNoXNoNo11Basic locking is not enoughT1T2r(A)w(A)r(A)lock-X(A)unlock(A)lock-X(A)Pibl hdlT1Read 100Write 100+1R d 101Add 1 to both A and B(preserve A=B)Multiply both A and B by 2(preserves A=B)r(A)w(A)r(B)w(B)r(B)w(B)lock-X(B)unlock(B)unlock(A)unlock(B)lock-X(B)Possible scheduleunder lockingBut still notconflict-serializable!1T2Read 101Write 101*2Read 100Write 100*2Read 200Write 200+1A ≠ B!12Two-phase locking (2PL) All lock requests precede all unlock requests Phase 1: obtain locks, phase 2: release locksT1T2r(A)lock-X(A)T1T2r(A)2PL guarantees aconflict-serializablew(A)r(A)w(A)r(B)w(B)r(B)w(B)lock-X(B)unlock(B)unlock(A)lock-X(A)lock-X(B)Cannot obtain the lock on Buntil T1unlocksw(A)r(A)w(A)r(B)w(B)r(B)w(B)schedule513Problem of 2PL T2has read uncommitted data written by T1 If T1aborts, then T2must abort as wellT1T2r(A)w(A)r(A)w(A)r(B) 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 T2commitsr(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 memoryThe memory block containingXif modified must be writtenThe memory block containing X, if modified, must be written back (flushed) to disk eventuallyCPUMemoryDiskXY…XY…616Failures 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: 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:18Logging Log Sequence of log records, recording all changes made to the database Written to stable storage (e.g., disk) during normal ioperation 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 performance719Undo/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 = 400700500T1(balance transfer of $100 from A to B)Memoryi<T1, start><T1, A, 800, 700><T1, B, 400, 500><T1,
View Full Document
Unlocking...