Concurrency Control IIAdministriviaReviewReview: AnomaliesReview: Anomalies (cont)Review: Anomalies (cont.)Review: Precedence GraphsReview: Schedule CharacteristicsLocking approaches to ConcurrencyReview: Locking IssuesSubject for TodayMultiple-Granularity LocksMultiple-Granularity Locks (cont)Solution: New Lock Modes, ProtocolMultiple Granularity Lock ProtocolMulti-Granularity ExampleMulti-Granularity Example 2Multi-Granularity Example 3Multi-Granularity Example 4Multi-Granularity Example 5Multi-Granularity NotesLocking in B+ TreesTwo Useful ObservationsA Simple Tree Locking AlgorithmExampleA Better Tree Locking Algorithm (See Bayer-Schkolnick paper)Slide 27Even 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 XactSummarySummary (Contd.)Slide 51Slide 52Concurrency Control IIR &G - Chapter 19Lecture 22Smile, it is the key that fits the lock of everybody's heart. Anthony J. D'Angelo, The College Blue BookAdministrivia•No Class next Tuesday, November 11•Guest Lecture on Data Mining next Thursday–Peruse chapter 26 in the book–Lecture material will be used for extra credit question(s) on the final•Homework 4:Review•We want DBMSs to have ACID properties•These properties supported by:–Transactions: unit of atomicity–Log: information to undo/redo transactions–Scheduler: limit reads/writes of Xactions to:•reduce anomalies•enhance concurency•Scheduling–A serial execution of transactions is safe but slow–Try to find schedules equivalent to serial execution–One solution for serializable schedules is 2PL•Reading Uncommitted Data (“WR”, dirty reads):•Unrepeatable Reads (“RW” Conflicts):•Overwriting Uncommitted Data (“WW”, lost update):Review: AnomaliesT1: R(A), W(A), R(B), W(B), AbortT2: R(A), W(A), CT1: R(A), R(A), W(A), CT2: R(A), W(A), CT1: W(A), W(B), CT2: W(A), W(B), CReview: Anomalies (cont)•If DBMS changes during transaction, result may not reflect consistent DBMS state•E.g., Consider T1 – “Find oldest sailor for each rating”–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).Review: Anomalies (cont.)•Some anomalies might be acceptable sometimes•SQL 92 supports different “Isolation Levels” for a transaction (Lost Update not allowed at any level)NoNoNoSerializableMaybeNoNoRepeatable ReadsMaybeMaybeNoRead CommittedMaybeMaybeMaybeRead UncommittedPhantom ProblemUnrepeatable ReadDirtyReadIsolation LevelReview: Precedence Graphs•Anomolies can be related to “conflicts”–2 Xacts accessing same object, at least one write•Precedence graphs show conflicts•Cycle in precedence graph indicates anomalyT1: R(A), R(A), W(A), CT2: R(A), W(A), CT1 T2AADependency graphReview: Schedule Characteristics•Want schedule to optimize concurrecy vs anomaly•Many criteria to evaluate schedulesLocking approaches to Concurrency•2PL ensures “conflict serializability”•Strict 2PL also ensures recoverability2PLStrict 2PLReview: Locking Issues•When a transaction needs a lock, it either...–blocks until the lock is available–or aborts, starts again later•Locking has significant overhead•Locking approaches are subject to Deadlock–must either prevent or detect deadlock•Locking also subject to Convoys–With pre-emptive multitasking, transaction with lock may be pre-empted many times to allow blocked transactions to execute, but they get no work done–Chain of block Xactions called a ConvoySubject for Today•What should we lock?–We assume tuples so far, but that can be expensive!–If we do table locks, that’s too conservative–Multi-granularity locking•Locking in indexes–don’t want to lock a B-tree root for a whole transaction!–actually do non-2PL “latches” in B-trees•CC w/out locking–“optimistic” concurrency control–“timestamp” and multi-version concurrency control–locking usually better, thoughMultiple-Granularity Locks•Hard to decide what granularity to lock (tuples vs. pages vs. tables).•Shouldn’t have to make same decision for all transactions!•Data “containers” are nested: TuplesTablesPagesDatabasecontainsMultiple-Granularity Locks (cont)•Idea: –need locks of different granularity, sometimes need to lock >1 table.–if transaction wants to rewrite entire DBMS, get X lock on DBMS.–if transaction wants to rewrite entire Table, get X lock on Table–if transaction wants to read entire Table, get S lock on Table–etc.–but, how to ensure that one transaction doesn’t lock DBMS while another locks a Table?TuplesTablesPagesDatabasecontainsSolution: New Lock Modes, Protocol•Allow Xacts to lock at each level, but with a special protocol using new “intention” locks.•Still need S and X locks, but before locking an item, Xact must have proper intension locks on all its ancestors in the granularity hierarchy.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 Multiple Granularity Lock Protocol•Each 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.Multi-Granularity Example•Rules–Each Xact starts from the root of the hierarchy.–To get S or IS lock, must hold IS or IX on parent.–To get X or IX or SIX, must hold IX or SIX on parent.–Must release locks in bottom-up order.Tuple 1Sailor TablePage 1DatabasePage 2Tuple 2 Tuple 4Tuple 3T1 wants to
View Full Document
Unlocking...