Concurrency ControlConflict Serializable SchedulesExampleDependency GraphReview: Strict 2PLTwo-Phase Locking (2PL)View SerializabilityLock ManagementDeadlocksDeadlock PreventionDeadlock DetectionDeadlock Detection (Continued)Multiple-Granularity LocksSolution: New Lock Modes, ProtocolMultiple Granularity Lock ProtocolExamplesDynamic DatabasesThe ProblemIndex LockingPredicate LockingLocking in B+ TreesTwo Useful ObservationsA Simple Tree Locking AlgorithmSlide 24A Better Tree Locking Algorithm (See Bayer-Schkolnick paper)Slide 26Even Better AlgorithmHybrid AlgorithmOptimistic CC (Kung-Robinson)Kung-Robinson ModelValidationTest 1Test 2Test 3Applying Tests 1 & 2: Serial ValidationComments on Serial ValidationSerial Validation (Contd.)Overheads in Optimistic CC``Optimistic’’ 2PLTimestamp CCWhen Xact T wants to read Object OWhen Xact T wants to Write Object OTimestamp CC and RecoverabilityMultiversion Timestamp CCMultiversion CC (Contd.)Reader XactWriter XactTransaction Support in SQL-92SummarySummary (Contd.)Slide 51Slide 521Concurrency ControlChapter 172Conflict Serializable SchedulesTwo schedules are conflict equivalent if:Involve the same actions of the same transactionsEvery pair of conflicting actions is ordered the same waySchedule S is conflict serializable if S is conflict equivalent to some serial schedule3ExampleA schedule that is not conflict serializable:The cycle in the graph reveals the problem. The output of T1 depends on T2, and vice-versa.T1: R(A), W(A), R(B), W(B)T2: R(A), W(A), R(B), W(B)T1 T2ABDependency graph4Dependency GraphDependency graph: One node per Xact; edge from Ti to Tj if Tj reads/writes an object last written by Ti.Theorem: Schedule is conflict serializable if and only if its dependency graph is acyclic5Review: Strict 2PLStrict Two-phase Locking (Strict 2PL) Protocol:Each Xact must obtain a S (shared) lock on object before reading, and an X (exclusive) lock on object before writing.All locks held by a transaction are released when the transaction completes If an Xact holds an X lock on an object, no other Xact can get a lock (S or X) on that object.Strict 2PL allows only schedules whose precedence graph is acyclic6Two-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.7View SerializabilitySchedules S1 and S2 are view equivalent if:If Ti reads initial value of A in S1, then Ti also reads initial value of A in S2If Ti reads value of A written by Tj in S1, then Ti also reads value of A written by Tj in S2If Ti writes final value of A in S1, then Ti also writes final value of A in S2T1: R(A) W(A)T2: W(A)T3: W(A)T1: R(A),W(A)T2: W(A)T3: W(A)8Lock 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 lock9DeadlocksDeadlock: Cycle of transactions waiting for locks to be released by each other.Two ways of dealing with deadlocks:Deadlock preventionDeadlock detection10Deadlock PreventionAssign 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 waitsIf a transaction re-starts, make sure it has its original timestamp11Deadlock DetectionCreate 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 graph12Deadlock Detection (Continued)Example: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 T2T3 T313Multiple-Granularity LocksHard to decide what granularity to lock (tuples vs. pages vs. tables).Shouldn’t have to decide!Data “containers” are nested: TuplesTablesPagesDatabasecontains14Solution: New Lock Modes, ProtocolAllow Xacts to lock at each level, but with a special protocol using new “intention” locks:Before locking an item, Xact 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 15Multiple Granularity Lock ProtocolEach Xact 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 Xact 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.Must release locks in bottom-up order.Protocol is correct in that it is equivalent to directly settinglocks at the leaf levels of the hierarchy.16ExamplesT1 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 to decide which.--IS IX--ISIX S XSX 17Dynamic DatabasesIf we relax the assumption that the DB is a fixed collection of objects, even Strict 2PL will not assure serializability: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 deletes oldest sailor with rating = 2 (and, say, age = 80), and commits.T1 now locks all pages containing sailor records with rating = 2, and finds oldest (say, age = 63).No consistent DB state where T1 is “correct”!18The ProblemT1 implicitly assumes that it has locked the set of all sailor records with rating = 1.Assumption only holds if no sailor records are added while T1 is executing!Need some mechanism to enforce this assumption. (Index
View Full Document