Duke CPS 116 - Transaction Processing

Unformatted text preview:

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

Duke CPS 116 - Transaction Processing

Documents in this Course
Part I

Part I

8 pages

XSLT

XSLT

4 pages

XSLT

XSLT

8 pages

Part I

Part I

8 pages

XSLT

XSLT

8 pages

Load more
Download Transaction Processing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Transaction Processing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Transaction Processing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?