Duke CPS 212 - Transactional Concurrency Control

Unformatted text preview:

Transactional Concurrency ControlTransactional Concurrency ControlTransactions: ACID PropertiesTransactions: ACID Properties“Full-blown” transactions guarantee four intertwined properties:• Atomicity. Transactions can never “partly commit”; their updates are applied “all or nothing”.The system guarantees this using logging, shadowing, distributed commit.• Consistency. Each transaction T transitions the dataset from one semantically consistent state to another.The application guarantees this by correctly marking transaction boundaries.• Independence/Isolation. All updates by T1 are either entirely visible to T2, or are not visible at all.Guaranteed through locking or timestamp-based concurrency control.• Durability. Updates made by T are “never” lost once T commits.The system guarantees this by writing updates to stable storage.Isolation and Serializability Isolation and Serializability Isolation/Independence means that actions are serializable.A schedule for a group of transactions is serializable iff its effect is the same as if they had executed in some serial order.Obvious approach: execute them in a serial order (slow).Transactions may be interleaved for concurrency, but this requirement constrains the allowable schedules:T1and T2may be arbitrarily interleaved only if there are no conflicts among their operations.• A transaction must not affect another that commits before it.• Intermediate effects of T are invisible to other transactions unless/until T commits, at which point they become visible.Some Examples of ConflictsSome Examples of ConflictsA conflict exists when two transactions access the same item, and at least one of the accesses is a write.1. lost update problemT: transfer $100 from A to C:R(A) W(A) R(C) W(C)S: transfer $100 from B to C:R(B) W(B) R(C) W(C)2. inconsistent retrievals problem(dirty reads violate consistency)T: transfer $100 from A to C:R(A) W(A) R(C) W(C)S: compute total balance for A and C: R(A) R(C) 3. nonrepeatable readsT: transfer $100 from A to C:R(A) W(A) R(C) W(C)S: check balance and withdraw $100 from A: R(A) R(A) W(A)Serializable SchedulesSerializable SchedulesA schedule is a partial ordering of operations for a set of transactions {T,S,...}, such that:• The operations of each xaction execute serially.• The schedule specifies an order for conflicting operations.Any two schedules for {T,S,...} that order the conflicting operations in the same way are equivalent.A schedule for {T,S,...} is serializable if it is equivalent to someserial schedule on {T,S,...}.There may be other serializable schedules on {T,S,...} that do not meet this condition, but if we enforce this condition we are safe.Conflict serializability: detect conflicting operations and enforce a serial-equivalent order.Legal Interleaved Schedules: ExamplesLegal Interleaved Schedules: ExamplesT < S1. avoid lost update problemT: transfer $100 from A to C: R(A) W(A) R(C) W(C)S: transfer $100 from B to C: R(B) W(B) R(C) W(C)2. avoid inconsistent retrievals problemT: transfer $100 from A to C:R(A) W(A) R(C) W(C)S: compute total balance for A and C: R(A) R(C) 3. avoid nonrepeatable readsT: transfer $100 from A to C R(A) W(A) R(C) W(C)S: check balance and withdraw $100 from A: R(A) R(A) W(A)Defining the Legal SchedulesDefining the Legal Schedules1. To be serializable, the conflicting operations of T and S must be ordered as if either T or S had executed first.We only care about the conflicting operations: everything else will take care of itself.2. Suppose T and S conflict over some shared item(s) x.3. In a serial schedule, T’s operations on x would appear before S’s, or vice versa....for every shared item x.As it turns out, this is true for all the operations, but again, we only care about the conflicting ones.4. A legal (conflict-serializable) interleaved schedule of T and Smust exhibit the same property.Either T or S “wins” in the race to x; serializability dictates that the “winner take all”.The Graph Test for SerializabilityThe Graph Test for SerializabilityTo determine if a schedule is serializable, make a directed graph:• Add a node for each committed transaction.• Add an arc from T to S if any equivalent serial schedule must order T before S.T must commit before S iff the schedule orders some operation of Tbefore some operation of S.The schedule only defines such an order for conflicting operations......so this means that a pair of accesses from T and S conflict over some item x, and the schedule says T “wins” the race to x. • The schedule is conflict-serializable if the graph has no cycles.(winner take all)T SACThe Graph Test: ExampleThe Graph Test: ExampleConsider two transactions T and S:T: transfer $100 from A to C: R(A) W(A) R(C) W(C)S: compute total balance for A and C: R(A) R(C)T: R(A) W(A) R(C) W(C)S: R(A) R(C)TSAC(S total balance gains $100.) T: R(A) W(A) R(C) W(C)S: R(A) R(C)TSC(S total balance loses $100.) ATransactional Concurrency ControlTransactional Concurrency ControlThree ways to ensure a serial-equivalent order on conflicts:• Option 1, execute transactions serially.“single shot” transactions• Option 2, pessimistic concurrency control: block T until transactions with conflicting operations are done.use locks for mutual exclusiontwo-phase locking (2PL) required for strict isolation• Option 3, optimistic concurrency control: proceed as if no conflicts will occur, and recover if constraints are violated.Repair the damage by rolling back (aborting) one of the conflicting transactions.• Option 4, hybrid timestamp ordering using versions.Pessimistic Concurrency ControlPessimistic Concurrency ControlPessimistic concurrency control uses locking to prevent illegal conflict orderings.avoid/reduce expensive rollbacks• Well-formed: acquire lock before accessing each data item.Concurrent transactions T and S race for locks on conflicting data items (say x and y)....Locks are often implicit, e.g., on first access to a data object/page.• No acquires after release: hold all locks at least until all needed locks have been acquired (2PL).growing phase vs. shrinking phase• Problem: possible deadlock.prevention vs. detection and recoveryWhy 2PL?Why 2PL?If transactions are well-formed, then an arc from T to S in the schedule graph indicates that T beat S to some lock.Neither


View Full Document

Duke CPS 212 - Transactional Concurrency Control

Download Transactional 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 Transactional 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 Transactional 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?