DOC PREVIEW
Berkeley COMPSCI 186 - Concurrency Control

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Concurrency ControlPart 2R&G - Chapter 17The sequel was far better thanthe original!-- NobodyOutline• Last time:– Theory: conflict serializability, view serializability– Two-phase locking (2PL)– Strict 2PL– Dealing with deadlocks (prevention, detection)• Today: “advanced” locking issues…– Locking granularity– Optimistic Concurrency ControlLocking Granularity• Hard to decide what granularity to lock(tuples vs. pages vs. tables).•why?Multiple-Granularity Locks• Shouldn’t have to make same decision for alltransactions!• Data “containers” are nested:TuplesTablesPagesDatabasecontainsSolution: New Lock Modes, Protocol• Allow Xacts to lock at each level, but with a specialprotocol using new “intention” locks:• Still need S and X locks, but before locking an item,Xact must have proper intension locks on all itsancestors in the granularity hierarchy. IS – Intent to get S lock(s) atfiner granularity. IX – Intent to get X lock(s)at finer granularity. SIX mode: Like S & IX atthe same time. Why useful?TuplesTablesPagesDatabaseMultiple 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 onparent 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 SIXon 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 Matrix IS – Intent to get S lock(s)at finer granularity. IX – Intent to get X lock(s)at finer granularity. SIX mode: Like S & IX atthe same time.IS IXSIXISIXSIXS XSX√√√ √ √-√√√------√---------TuplesTablesPagesDatabaseExamples – 2 level hierarchy• T1 scans R, and updates a few tuples:– T1 gets an SIX lock on R, then get X lock on tuples that areupdated.• T2 uses an index to read only part of R:– T2 gets an IS lock on R, and repeatedly gets an S lock ontuples of R.• T3 reads all of R:– T3 gets an S lock on R.– OR, T3 could behave like T2; canuse lock escalation to decide which.– Lock escalation dynamically asks forcoarser-grained locks when too manylow level locks acquiredIS IXSIXISIXSIX√√√√ √√S X√SX√√TuplesTablesJust So You’re Aware: Indexes• 2PL on B+-tree pages is a rotten idea.– Why?• Instead, do short locks (latches) in a cleverway– Idea: Upper levels of B+-tree just need to directtraffic correctly. Don’t need to be serializablyhandled!– Different tricks to exploit this• Note: this is pretty complicated!Just So You’re Aware: Phantoms• Suppose you query for sailors with ratingbetween 10 and 20, using a B+-tree– Tuple-level locks in the Heap File• I insert a Sailor with rating 12• You do your query again– Yikes! A phantom!– Problem: Serializability assumed a static DB!• What we want: lock the logica l range 10-20– Imagine that lock table!• What is done: set locks in indexes cleverlyRoadmap• So far:– Correctness criterion: serializability– Lock-based CC to enforce serializability• Strict 2PL• Deadlocks• Hierarchical Locking• Tree latching• Phantoms• Next:– Alternative CC mechanism: OptimisticOptimistic CC (Kung-Robinson)Locking is a conservative approach inwhich conflicts are prevented.• Disadvantages:– Lock management overhead.– Deadlock detection/resolution.– Lock contention for heavily used objects.• Locking is “pessimistic” because itassumes that conflicts will happen.• What if conflicts are rare?– We might get better performance by notlocking, and instead checking for conflictsat commit time.Kung-Robinson Model• Xacts have three phases:– READ: Xacts read from the database, butmake changes to private copies of objects.– VALIDATE: Check for conflicts.– WRITE: Make local copies of changespublic.R V WValidation•Idea: test conditions that are sufficient toensure 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 1• For all i and j such that Ti < Tj, check that Ticompletes before Tj begins.TiTjR V WR V WTest 2• For all i and j such that Ti < Tj, check that:– Ti completes before Tj begins its Write phase AND– WriteSet(Ti) ∩ ReadSet(Tj) is empty.TiTjR V WR V WDoes Tj read dirty data? Does Ti overwrite Tj’s writes?Test 3• For all i and j such that Ti < Tj, check that:– Ti completes Read phase before Tj does AND– WriteSet(Ti) ∩ ReadSet(Tj) is empty AND– WriteSet(Ti) ∩ WriteSet(Tj) is empty.TiTjR V WR V WDoes Tj read dirty data? Does Ti overwrite Tj’s writes?Applying Tests 1 & 2: Serial Validation• To 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< foreach Ts in S do { if ReadSet(T) intersects WriteSet(Ts) then valid = false; } if valid then { install updates; // Write phase Commit T } > else Restart Tstartofcriticalsectionend of critical sectionComments on Serial Validation• Applies Test 2, with T playing the role of Tj and eachXact in Ts (in turn) being Ti.• Assignment of Xact id, validation, and the Writephase are inside a critical section!– Nothing else goes on concurrently.– So, no need to check for Test 3 --- can’t happen.– If Write phase is long, major drawback.• Optimization for Read-only Xacts:– Don’t need critical section (because there is no Write phase).Overheads in Optimistic CC• Record xact activity in ReadSet and WriteSet– Bookkeeping overhead.• Check for conflicts during validation– Critical section can reduce concurrency.• Private writes have to go somewhere arbitrary– Can impact sequential I/Os on read & write.• Restart xacts that fail validation.– Work done so far is wasted; requires clean-up.Optimistic CC vs. Locking• Despite its own overheads, Optimistic CC canbe better if conflicts are rare– Special case: mostly read-only xacts• What about the case in which conflicts arenot rare?– The choice is less obvious …Optimistic CC vs. Locking(for xacts that tend to conflict)• Locking:– Delay xacts involved in conflicts– Restart xacts involved in deadlocks• Optimistic CC:– Delay other xacts during critical section


View Full Document

Berkeley COMPSCI 186 - Concurrency Control

Documents in this Course
Load more
Download Concurrency Control
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Concurrency Control and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Concurrency Control 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?