Class Note for EECS 647 with Professor Huan at KU
Class Note for EECS 647 with Professor Huan at KU
Popular in Course
Popular in Department
This 26 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 20 views.
Reviews for Class Note for EECS 647 with Professor Huan at KU
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
EECS 647 Introduction to Database Systems Instructor Luke Huan Spring 2009 Today s Topic o Guarantee con ictserializable schedule 4262009 Luke Huan Univ of Kansas Locking 0 Rules 0 If a transaction wants to read an object it must first request a shared lock S mode on that object o If a transaction wants to modify an object it must first request an exclusive lock X mode on that object 0 Allow one exclusive lock or multiple shared locks Mode of the lock requested S X MOde Of100k5 S Y N Grant the lock currently held x N N by other transactions Compatibility matrix 4262009 Luke Huan Univ of Kansas Basic locking is not enough Add 1 to both A and B T1 T2 Multiply both A and B by 2 preserve AB preserves AB lockXA Read 100 rA Write lOOl WA unlockA ockXA Possible schedule 1 A Read 101 a under locking WA Write 1012 unlockA 3 But still not lockXB con ictserializable 13 Read 100 Wag Write 1002 unlockB lockXB Read 200 rB A 72 B Write 2001 W 3 4262009 Ck eBgr Univ of Kansas Twophase locking 2PL o All lock requests precede all unlock requests a Phase I obtain locks phase 2 release locks T1 lockXA rA WA lockXB unlockA rB WB 4262009uIIIOCkB T2 T1 2PL guarantees a con ictserializable rA schedule WA lockXA rA rB WA WB lockXB rB WB Cannot obtain the lock on B until T1 unlocks Luke Huan Univ of Kansas rA WA rB WB Problem of 2PL 0 T2 has read uncommitted data T1 T2 written by T1 2431 0 If T1 aborts then T 2 must W rA abort as well r03 MA 0 Cascading aborts are possible wB if other transactions have read rB data written by T 2 wB Abort 0 Even worse what if T 2 commits before T1 0 Schedule is not recoverable if the system crashes right after T 2 commits 4262009 Luke Huan Univ of Kansas 6 Strict 2PL 0 Only release locks at commitabort time o A writer will block all other readers until the writer commits or aborts Used in most commercial DBMS 4262009 Luke Huan Univ of Kansas Next o A few examples 4262009 Luke Huan Univ of Kansas NonZPL A 1000 B2000 Output L0ckXA ReadA L0ckSA A A50 WriteA UnlockA ReadA UnlockA L0ckSB L0ckXB ReadB UnlockB PRINTAB ReadB B B 50 WriteB leggzanCMB E U 9 2PL A 1000 B2000 Output LockXA ReadA LockSA A A50 WriteA LockXB UnlockA ReadA LockSB ReadB B B 50 WriteB UnlockB UnlockA ReadB UnlockB PRINTAB 4262009 Luke Huan Univ of Kansas Strict 2PL A 1000 B2000 Output LockXA ReadA LockSA A A50 WriteA LockXB ReadB B B 50 WriteB UnlockA UnlockB ReadA LockSB ReadB PRINTAB UnlockA UnlockB 4262009 Luke Huan Univ of Kansas 11 Lock Management 0 Lock and unlock requests handled by Lock Manager 0 LM keeps an entry for each currently held lock 0 Entry contains 0 List of xacts currently holding lock 0 Type of lock held shared or exclusive 0 Queue of lock requests Lock Management cont a When lock request arrives Q Does any other xact hold a con icting lock 0 If no grant the lock 0 If yes put requestor into wait queue 0 Lock upgrade 0 Shared lock can request to upgrade to exclusive Deadlocks o Deadlock Cycle of transactions waiting for locks to be released by each other 0 Two ways of dealing with deadlocks o prevention 0 detection 0 Many systems just punt and use Timeouts o What are the dangers with this approach Deadlock Detection o Create and maintain a waitsfor graph 0 Periodically check for cycles in graph Deadlock Detection Continued Example T1 SA 31 33 T2 XB XC T3 SD SC XA T4 XB Deadlock Deadlock Prevention Assign priorities based on timestamps Say Ti wants a lock that Tj holds Two policies are possible WaitDie If Ti has higher priority Ti waits for Tj otherwise Ti aborts Woundwait If Ti has higher priority Tj aborts otherwise Ti waits Why do these schemes guarantee no deadlocks Important detail If a transaction restarts make sure it gets its original timestamp Why Summary o Correctness criterion for isolation is serializability o In practice we use conflict serializability which is somewhat more restrictive but easy to enforce a Two Phase Locking and Strict 2PL Locks implement the notions of con ict directly 0 The lock manager keeps track of the locks issued 0 Deadlocks may arise can either be prevented or detected Recovery Motivation o Atomicity o Transactions may abort Rollback o Durability 0 What if DBMS stops running Causes oz Desired state after system restarts T1 amp T3 should be durable T2 T4 amp T5 should be aborted effects not seen crash T1 Commit I T2 39l It I T3 omml I T4 39 I T5 Handling Failures 0 System crashes in the middle of a transaction T partial effects of T were written to disk 0 How do we undo T atomicity 0 System crashes right after a transaction T commits not all effects of T were written to disk 0 How do we complete T durability 4262009 Luke Huan Univ of Kansas 20 Na39I39ve approach 0 Force When a transaction commits all writes of this transaction must be re ected on disk 0 Without force if system crashes right after T commits effects of T will be lost a Problem Lots of random writes hurt performance a No steal Writes of a transaction can only be ushed to disk at commit time 0 With steal if system crashes before T commits but after some writes of T have been ushed to disk there is no way to undo these writes r Problem Holding on to all dirty blocks requires lots of memory 4262009 Luke Huan Univ of Kansas 21 Logging 0 Log 0 Sequence of log records recording all changes made to the database 0 Written to stable storage eg disk during normal operation I Used in recovery 0 Hey one change turns into two bad for performance 0 But writes are sequential append to the end of log a Can use dedicated disks to improve performance 4262009 Luke Huan Univ of Kansas 22 Undoredo logging rules Record values before and after each modi cation h Ti X oldvalue0fX newvalue0fX i A transaction TI is committed when its commit log record h T commit i is written to disk Writeahead logging WAL Before X is modi ed on disk the log record pertaining to X must be ushed 0 Without WAL system might crash afterX 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 ushed to disk anytime since undo information is logged 4262009 Luke Huan Univ of Kansas 23 Undoredo logging example T1 balance transfer of 100 from A to B readA a a a 100 writeA a readB 19 b 100 writeB b commit ltT1 startgt ltT1 A 800 700gt ltT1 B 400 500gt ltT1 commitgt Steal can ush before commit No force can ush after commit Moogestriction on when memogubloygig canshould be ushed 24 Summary 0 Goal 0 Support Concurrency with Isolation Protocol Isolation Recover ability Deadlock Starvation 2PL Strict 2PL Strict 2PL with priority 4262009 Luke Huan Univ of Kansas 25 Summary o Concurrency control a Serial schedule no interleaving o Con ictserializable schedule no cycles in the precedence graph equivalent to a serial schedule 0 2PL guarantees a con ictserializable schedule a Strict 2PL also guarantees recoverability 0 Recovery undoredo logging with fuzzy checkpointing a Normal operation writeahead logging no force steal a Recovery rst redo forward and then undo backword 4262009 Luke Huan Univ of Kansas 26
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'