Class Note for CMPSCI 645 at UMass(7)
Class Note for CMPSCI 645 at UMass(7)
Popular in Course
Popular in Department
This 39 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 17 views.
Reviews for Class Note for CMPSCI 645 at UMass(7)
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
Concurrency Control CMPSCI 645 Apr 3 2008 Slide content adapted from Ramakrishnan amp Gehrke Zack Ives Review the ACID Properties 4 Particularly important ensuring ACID properties I Atomicity each operation looks atomic to the user I Consistency each operation in isolation keeps the database in a consistent state this is the responsibility of the user I Isolation should be able to understand what s going on by considering each separate transaction independently I Durability updates stay in the DBMS Review properties of schedules 3 Serializable schedule A schedule that is equivalent to some serial execution of the transactions I Con ictserializability I Viewserializability rt Recoverable schedule if Tj reads data written by Ti then Ti commits before Tj commits rt Cascadeless schedule if Tj reads data written by Ti then Ti commits before read operation of Tj Today 3 Enforcing desirable schedules I Lockbased 39 Strict 2PL 2PL Phantoms 0 Index locking I Weak consistency in SQL LockBased Concurrency Control 3 DBMS must ensure I only serializable recoverable schedules are allowed I No actions of committed trans lost while undoing aborted trans 00 Lock associated with some object I shared or exclusive oz Locking protocol set of rules to be followed by each transaction to ensure good properties Lock Compatibility Matrix Locks on a data item are granted based on a lock compatibility matrix Mode of Data Item None Shared Exclusive Shared Y Y N Request mode Exclusive Y N N When a transaction requests a lock it must wait block until the lock is granted Transaction performing locking T1 10ckXA RA WA unlockA 10ckSB RB unlockB TwoPhase Locking ZPL 00 TwoPhase Locking Protocol Each Xact must obtain a S shared lock on object before reading and an X exclusive lock on object before writing A transaction can not request additional locks once it releases any locks o growing phase o shrinking phase Strict Two Phase Locking Strict ZPL 3 Strict Twophase Locking Strict ZPL Protocol Each Xact must obtain a S shared lock on object before reading and an X exclusive lock on object before writing A transaction can not request additional locks once it releases any locks o growing phase o shrinking phase All X exclusive locks acquired by a transaction must be held until commit Not admissible under ZPL T1 T2 RA WA RA WA RB WB Commit RB WB Commit 10 Lockbased protocols 0 2PL ensures conflict serializability I Transactions can be ordered by their end of growing phase called lock point I A 2PL schedule is equivalent to the serial schedule where transactions ordered by lock point order 3 Strict 2PL ensures conflict serializable and cascadeless schedules I Writers hold an X lock until they commit Schedule following strict ZPL T1 T2 5A RA 5A RA XB mm mm Commlt XC RC WC Commlt 12 Lock Management 9 4 Lock and unlock requests are handled by the lock manager 9 4 Lock table entry for an object Number of transactions currently holding a lock Type of lock held shared or exclusive Pointer to queue of lock requests 4 Locking and unlocking have to be atomic operations 4 Lock upgrade transaction that holds a shared locllt can be upgraded to hold an exclusive locllt Deadlocks 3 Deadlock Cycle of transactions waiting for locks to be released by each other 00 Tend to be rare in practice oz Two ways of dealing with deadlocks Deadlock prevention Deadlock detection Deadlock T1 T2 XA granted X03 granted X03 queued XA queued 3 Deadlock must be prevented or avoided 15 Deadlock Detection 3 Create a waitsfor graph Nodes are transactions There is an edge from Ti t0 Tj if Ti is waiting for Tj to release a lock add edge when queueing a lock request remove edge when granting lock request oz Periodically Check for cycles in the waitsfor graph Deadlock Detectzon Contmued T1 T2 T3 T4 SA RA X03 W03 SB SC RC XC X03 XA Deadlock Prevention 3 Assign priorities based on timestamps Assume 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 oz If a transaction restarts make sure it has its original timestamp Performance of Locking 3 Lockbased schemes resolve con icting schedules by blocking and aborting I in practice few deadlocks and relatively few aborts I most of penalty from blocking 00 To increase throughput I lock smallest objects possible I reduce time locks are held I reduce hotspots 19 What should we lock T1 T2 SELECT Srating MNSage UPDATE FROM Sailors S SailorsName Rating Age WHERE Srating 8 VALUES Joe 8 33 oz T1 Slock on Sailors T2 Xlock on Sailors 3 T1 Slock on all rows with rating8 T2 X lock on Joe s tuple 20 Phantom oz T1 quotFind oldest sailor for each of the rating levels 1 and 2 I T1 locllts all pages containing sailor records with rating 1 and finds oldest sailor say age 71 3 T2 Insert new sailor rating1 age96 oz T2 Deletes oldest sailor with rating 2 and say age 80 and commits oz T1 now locllts all pages containing sailor records with rating 2 and finds oldest say age 63 21 The Problem 3 T1 implicitly assumes that it has locked the set of all sailor records with rating 1 I Assumption only holds if no sailor records are added while T1 is executing I Need some mechanism to enforce this assumption Index locking and predicate locking oz Example shows that con ict serializability guarantees serializability only if the set of objects is fixed 9 Strict 2PL will not assure serializability The Phantom Problem Phantom problem A transaction retrieves a collection of tuples and sees different results even though it did not modify the tuples itself I Conceptually rnust lock all possible rows I Can lock entire table I Better use index locking 23 Index Locking 3 If there is an index on the rating field using Alternative 2 T1 should lock the index pag containing the data entries with rating 1 I If there are no records with rating 1 T1 must lock the index page where such a data entry would be if it existed 3 If there is no suitable index T1 must lock all pages and lock the file table to prevent new pages from being added to ensure that no new records with rating 1 are added Predicate Locking 3 Grant lock on all records that satisfy some logical predicate e g age gt 2salary 3 Index locking is a special case of predicate locking for which an index supports efficient implementation of the predicate lock oz In general predicate locking has a lot of locking overhead Locking in B Trees oz How can we efficiently locllt a particular leaf node 3 One solution Ignore the tree structure just lock pages while traversing the tree following 2PL 0 This has terrible performance I Root node and many higher level nodes become bottlenecks because every tree access begins at the root Two Useful Observations oz Higher levels of the tree only direct searches for leaf pages 0 For inserts a node on a path from root to modified leaf must be locked X mode of course only if a split can propagate up to it from the modified leaf Similar point holds wrt deletes 3 We can exploit these observations to design efficient locking protocols that guarantee serializability even though they violate ZPL A Simple Tree Locking Algorithm 3 Search Start at root and go down repeatedly S lock child then unlock parent oz Insert Delete Start at root and go down obtaining X locks as needed Once child is locked check if it is m I If child is safe release all locks on ancestors 3 Safe node Node such that changes will not propagate up beyond this node I Inserts Node is not full I Deletes Node is not halfempty ROOT Example g I Do I A 1 Search 38 2 Insert 45 IB IFfnc G H I D E I Transaction support in SQL 3 Transaction automatically started for SELECT UPDATE CREATE oz Transaction ends with COMMIT or ROLLBACK abort oz SQL 99 supports SAVEPOINTs which are simple nested transactions 30 Specify isolation level I General rules of thumb wrt isolation I Fully serializable isolation is more expensive than no isolation 0 We can t do as many things concurrently or we have to undo them frequently 3 For performance we generally want to specify the most relaxed isolation level that s acceptable I Note that we re slightly violating a correctness constraint to get performance 31 Specifying isolation level in SQL SET TRANSACTION READ WRITE READ ONLY ISOLATION LEVEL LEVEL LEVEL SERIALIZABLE REPEATABLE READ READ COMMITTED J Less 39So39at39on READ UNCOMMITED The default isolation level is SERIALIZABLE Locks sets of objects avoids phantoms 32 REPEATABLE READ oz T reads only changes made by committed transactions 3 No value read written by T is changed by another transaction until T completes 00 Phantoms possible inserts of qualifying tuples not avoided Locks only individual objects 33 READ COMMITTED oz T reads only changes made by committed transactions t No value read written by T is changed by another transaction until T completes rt Value read by T may be modified while T in progress oz Phantoms possible X locks on written objects held to end 8 looks on read objects but released immediately 34 READ UN C OMMI TTE D 3 Greatest exposure to other transactions oz Dirty reads possible oz Can t make changes must be READ ONLY 3 Does not obtain shared locks before reading I Thus no locks ever requested 35 Acceptable Dirty Read If we are just Checking availability of an airline seat a dirty read might be fine Why is that Reservation transaction EXEC SQL select occupied into 000 from Flights where Num 123 and date110399 and seat 23f if loco EXEC SQL update Flights set occupiedtrue where Num 123 and date110399 and seat 23f else noll user that seat is unavailable 36 Real systems 3 IBM DB2 Informix Microsoft SQL Server Sybase all use Strict PL or variants 3 Oracle use multiversion CC we didn t cover this oz All deal with deadlocks using waitsfor graph 37 Summary 3 There are several lockbased concurrency control schemes Strict 2PL 2PL Con icts between transactions can be detected in the dependency graph 3 The lock manager keeps track of the locks issued Deadlocks can either be prevented or detected 3 Na39ive locking strategies may have the phantom problem Summary Corlth 3 Index locking is common and affects performance significantly I Needed when accessing records Via index I Needed for locking logical sets of records index locking predicate locking 3 Treestructured indexes I Straightforward use of 2PL very inefficient 3 In practice better techniques now known do recordlevel rather than pagelevel locking
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'