Concurrency ControlTwo-Phase Locking (2PL)Lock ManagementDeadlocksSlide 11Deadlock Detection by WFGDeadlock Detection using WFGSlide 14Deadlock PreventionDeadlock Prevention using TimestampsPerformance IssuesMultiple-Granularity LocksSolution: New Lock ModesMultiple Granularity Lock ProtocolSlide 21Dynamic DatabasesThe Phantom ProblemIndex LockingPredicate LockingLocking in B+ TreesTwo Useful ObservationsA Simple Tree Locking AlgorithmSlide 30A Better Tree Locking AlgorithmSlide 32Slide 35Seen on actual product packagesOptimistic CC (Kung-Robinson)Kung-Robinson ModelValidationTest 1Test 2Test 3Slide 43Comments on Serial ValidationOverheads in Optimistic CC``Optimistic’’ 2PLSlide 48Break TimeTimestamp OrderingSlide 51Basic Timestamp OrderingWhen T wants to read Object OWhen T wants to Write Object OTimestamp CC and RecoverabilityExercise: Non-equivalence of 2PL and TORelationship between 2PL and TOSlide 58The Digital Michelangelo ProjectMulti-version Data ObjectsMulti-version Timestamp OrderingMultiversion Timestamp OrderingReader XactWriter XactSlide 67Slide 68SummarySummary (Contd.)Slide 71Slide 72Slide 73QoS Differentiation Example Image Compression1Concurrency ControlChapter 176Two-Phase Locking (2PL)Two-Phase Locking ProtocolEach 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. If an Xact holds an X lock on an object, no other Xact can get a lock (S or X) on that object.9Lock ManagementLock and unlock requests are handled by the lock managerLock table entry:Number of transactions currently holding a lockType of lock held (shared or exclusive)Pointer to queue of lock requestsLocking and unlocking have to be atomic operationsLock upgrade: transaction that holds a shared lock can be upgraded to hold an exclusive lock10DeadlocksDeadlock: Cycle of transactions waiting for locks to be released by each other.T1=r1(x)w1(y)C1; T2=r2(y)w2(x)C2How can a deadlock occur?Four conditions for deadlock:Mutual exclusionHold and waitNo preemptionCircular waitAre they necessary conditions, sufficient, or necessary and sufficient conditions?11DeadlocksThree ways of dealing with deadlocks:Deadlock detection and resolution Deadlock preventionDeadlock avoidanceDeadlock detectionTime-out: no detection, just guessingChances of aborting a transaction that is not involved in a deadlockWait-for graphPrecise detectionLarge overhead12Deadlock Detection by WFGCreate a waits-for graph:Nodes are transactionsThere is an edge from Ti to Tj if Ti is waiting for Tj to release a lockPeriodically check for cycles in the waits-for graph --- How often?13Deadlock Detection using WFGExample:T1: S(A), R(A), S(B)T2: X(B),W(B) X(C)T3: S(C), R(C) X(A)T4: X(B)T1 T2T4 T3T1 T2T4 T314DeadlocksThree ways of dealing with deadlocks:Deadlock detection and resolution Deadlock preventionDeadlock avoidanceDeadlock detectionTime-out: no detection, just guessingChances of aborting a transaction that is not involved in a deadlockWait-for graphPrecise detectionLarge overhead15Deadlock PreventionPriority-based scheme: allow Ti wait for Tj only if Ti has a higher priority than Tj. Otherwise, abort Ti.Deadlock is not possible. Why? If T1->T2-> … ->Tn->T1 in WFG, then P(T1)>P(T2) ..>P(Tn)>P(T1)Typically implemented by using timestamp -- Assign priorities based on timestamps.TimestampsA monotonically increasing numberFinite number of smaller timestampsPriority of T is the inverse of its timestamp. Why?16Deadlock Prevention using TimestampsAssign priorities based on timestamps. Assume Ti wants a lock that Tj holds. Two policies are possible:Wait-Die: It Ti has higher priority, Ti waits for Tj; otherwise Ti abortsWound-wait: If Ti has higher priority, Tj aborts; otherwise Ti waitsIn both cases, younger transaction is aborted. Why?If a transaction re-starts, make sure it has its original timestamp. Why?17Performance IssuesThrashingResource contentionData contention PolicyBlocking policy vs restart policyIf low resource contention but severe data contention -- which policy will perform better?Restart policy – surprising?Blocking is selfish, restarting is self-sacrificingImpact of granularity on performanceTree locking – why important?18Multiple-Granularity LocksWhy consider it?Database consists of tables, pages, tuples (records)Hard to decide what granularity to lock (tuples vs. pages vs. tables).Shouldn’t have to decide. How?Data “containers” are nested: TuplesTablesPagesDatabasecontains19Solution: New Lock ModesHow to ensure that a page is not locked if another T holds a conflicting lock on the table?Exploit hierarchical nature: lock at each level, using new “intention” locks.Before locking an item, T must set “intention locks” on all its ancestors.For unlock, go from specific to general (i.e., bottom-up).SIX mode: Like S & IX at the same time.--IS IX--ISIX S XSX 20Multiple Granularity Lock ProtocolEach T starts from the root of the hierarchy.To get S or IS lock on a node, must hold IS or IX on parent node.What if T holds SIX on parent? S on parent?To get X or IX or SIX on a node, must hold IX or SIX on parent node.When can a lock released? To ensure SR, multi-granularity locking must be used with 2PL, which dictates when a lock can be releasedMust release locks in bottom-up order.21ExampleT1 scans R, and updates a few tuples:T1 gets an SIX lock on R, then repeatedly gets an S lock on tuples of R, and occasionally upgrades to X on the tuples.T2 uses an index to read only part of R:T2 gets an IS lock on R, and repeatedly gets an S lock on tuples of R.T3 reads all of R:T3 gets an S lock on R. OR, T3 could behave like T2; can use lock escalation.--IS IX--ISIX S XSX 22Dynamic DatabasesIf we relax the assumption that the DB is a fixed collection of objects, even Strict 2PL will not assure serializability. Why?T1 locks all pages containing sailor records with rating = 1, and finds oldest sailor (say, age = 71).Next, T2 inserts a new sailor; rating = 1, age = 96.T2 also
View Full Document