《數(shù)據(jù)庫系統(tǒng)》英文教學課件

《數(shù)據(jù)庫系統(tǒng)》英文教學課件,數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)庫,系統(tǒng),英文,教學,課件 Concurrency Control Part 2R&G-Chapter 17The sequel was far better than the original!-NobodyOutlineLast time:Theory:conflict serializability,view serializabilityTwo-phase locking(2PL)Strict 2PLDealing with deadlocks(prevention,detection)Today:“advanced”locking issuesLocking granularityOptimistic Concurrency ControlLocking GranularityHard to decide what granularity to lock(tuples vs.pages vs.tables).why?Multiple-Granularity LocksShouldnt have to make same decision for all transactions!Data“containers”are nested:TuplesTablesPagesDatabasecontainsSolution:New Lock Modes,ProtocolAllow 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.vIS Intent to get S lock(s)at finer granularity.vIX Intent to get X lock(s)at finer granularity.vSIX mode:Like S&IX at the same time.Why useful?TuplesTablesPagesDatabaseMultiple 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 S on parent?SIX 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.TuplesTablesPagesDatabaseLock Compatibility MatrixvIS Intent to get S lock(s)at finer granularity.vIX Intent to get X lock(s)at finer granularity.vSIX mode:Like S&IX at the same time.ISIXSIXISIXSIXSXSX-TuplesTablesPagesDatabaseExamples 2 level hierarchyT1 scans R,and updates a few tuples:T1 gets an SIX lock on R,then get X lock on tuples that are updated.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.Lock escalation dynamically asks for coarser-grained locks when too manylow level locks acquiredIS IXSIXISIXSIX SXSXTuplesTablesJust So Youre Aware:Indexes2PL on B+-tree pages is a rotten idea.Why?Instead,do short locks(latches)in a clever wayIdea:Upper levels of B+-tree just need to direct traffic correctly.Dont need to be serializably handled!Different tricks to exploit thisIncluding the“rightlink”trick you peeked at in GiSTNote:this is pretty complicated!Just So Youre Aware:PhantomsSuppose you query for sailors with rating between 10 and 20,using a B+-treeTuple-level locks in the Heap FileI insert a Sailor with rating 12You do your query againYikes!A phantom!Problem:Serializability assumed a static DB!What we want:lock the logical range 10-20Imagine that lock table!What is done:set locks in indexes cleverlyRoadmapSo far:Correctness criterion:serializabilityLock-based CC to enforce serializabilityStrict 2PLDeadlocksHierarchical LockingTree latchingPhantomsNext:Alternative CC mechanism:OptimisticOptimistic CC(Kung-Robinson)Locking is a conservative approach in which conflicts are prevented.Disadvantages:Lock management overhead.Deadlock detection/resolution.Lock contention for heavily used objects.Locking is“pessimistic”because it assumes that conflicts will happen.What if conflicts are rare?We might get better performance by not locking,and instead checking for conflicts at commit time.Kung-Robinson ModelXacts have three phases:READ:Xacts read from the database,but make changes to private copies of objects.VALIDATE:Check for conflicts.WRITE:Make local copies of changes public.RVWValidationIdea:test conditions that are sufficient to ensure that no conflict occurred.Each Xact assigned a numeric id.Just use a timestamp.Assigned at end of READ phase.ReadSet(Ti):Set of objects read by Xact Ti.WriteSet(Ti):Set of objects modified by Ti.Test 1For all i and j such that Ti Tj,check that Ti completes before Tj begins.TiTjRVWRVWTest 2For all i and j such that Ti Tj,check that:Ti completes before Tj begins its Write phase ANDWriteSet(Ti)ReadSet(Tj)is empty.TiTjRVWRVWDoes Tj read dirty data?Does Ti overwrite Tjs writes?Test 3For all i and j such that Ti Tj,check that:Ti completes Read phase before Tj does ANDWriteSet(Ti)ReadSet(Tj)is empty ANDWriteSet(Ti)WriteSet(Tj)is empty.TiTjRVWRVWDoes Tj read dirty data?Does Ti overwrite Tjs writes?Applying Tests 1&2:Serial ValidationTo validate Xact T:valid=true;/S=set of Xacts that committed after Begin(T)/(above defn implements Test 1)/The following is done in critical section else Restart Tstartof critical sectionend of critical sectionComments on Serial ValidationApplies Test 2,with T playing the role of Tj and each Xact in Ts(in turn)being Ti.Assignment of Xact id,validation,and the Write phase are inside a critical section!Nothing else goes on concurrently.So,no need to check for Test 3-cant happen.If Write phase is long,major drawback.Optimization for Read-only Xacts:Dont need critical section(because there is no Write phase).Overheads in Optimistic CCRecord xact activity in ReadSet and WriteSetBookkeeping overhead.Check for conflicts during validationCritical section can reduce concurrency.Private writes have to go somewhere arbitraryCan impact sequential I/Os on read&write.Restart xacts that fail validation.Work done so far is wasted;requires clean-up.Optimistic CC vs.LockingDespite its own overheads,Optimistic CC can be better if conflicts are rareSpecial case:mostly read-only xactsWhat about the case in which conflicts are not rare?The choice is less obvious Optimistic CC vs.Locking (for xacts that tend to conflict)Locking:Delay xacts involved in conflictsRestart xacts involved in deadlocksOptimistic CC:Delay other xacts during critical section(validation+write)Restart xacts involved in conflictsObservations:Locking tends to delay xacts longer(duration of X locks usually longer than critical section for validation+write)could decrease throughputOptimistic CC tends to restart xacts more often more“wasted”resources decreased throughput if resources are scarceRule of thumb:locking wins unless you have lots ofspare resources.E.g.distributed system.Just So Youve Heard of ThemTwo more CC techniquesTimestamp CCEach xact has a timestamp.It marks it on data it touches.Restart a xact if it tries to mess with a data item from“the future”.Multiversion CCAllow objects from many timestamps to coexist.Restart a transaction if it tries to“slip in a version”that should have been seen by somebody that ran previously.SummaryLocking,contHierarchical Locking a critical extension to 2PLTree latches a critical issue in practicePhantom handling important in practiceOptimistic CC using end-of-xact“validation”Good if:Read-dominated workloadSystem has lots of extra resourcesMost DBMSs use lockingOCC used in some distributed systems,since restart resources are cheap,latency of locks expensive.