1Transactional Concurrency ControlTransactional Concurrency ControlTransactions: ACID PropertiesTransactions: ACID Properties“Full-blown” transactions guarantee four intertwined properties:• Atomicity. Transactions can never “partly commit”; their updates areapplied “all or nothing”.The system guarantees this using logging, shadowing, distributed commit.• Consistency. Each transaction T transitions the dataset from onesemantically consistent state to another.The application guarantees this by correctly marking transaction boundaries.• Independence/Isolation. All updates by T1 are either entirely visibleto 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.2Isolation and SerializabilityIsolation and SerializabilityIsolation/Independence means that actions are serializable.A schedule for a group of transactions is serializable iff its effect isthe 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 thisrequirement constrains the allowable schedules:T1and T2may be arbitrarily interleaved only if there are noconflicts among their operations.• A transaction must not affect another that commits before it.• Intermediate effects of T are invisible to other transactionsunless/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)3Serializable SchedulesSerializable SchedulesA schedule is a partial ordering of operations for a set oftransactions {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 operationsin 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 notmeet this condition, but if we enforce this condition we are safe.Conflict serializability: detect conflicting operations and enforce aserial-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)4Defining the Legal SchedulesDefining the Legal Schedules1. To be serializable, the conflicting operations of T and S must beordered as if either T or S had executed first.We only care about the conflicting operations: everything elsewill 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, weonly 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 thatthe “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 mustorder 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 oversome 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 SAC5The 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:blockTuntiltransactions 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 noconflicts will occur, and recover if constraints are violated.Repair the damage by rolling back (aborting) one of theconflicting transactions.• Option 4, hybrid timestamp ordering using versions.6Pessimistic Concurrency ControlPessimistic Concurrency ControlPessimistic concurrency control uses locking to prevent illegalconflict orderings.avoid/reduce expensive rollbacks• Well-formed: acquire lock before accessing each data item.Concurrent transactions T and S race for locks on conflicting dataitems (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 allneeded 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 theschedule graph indicates that T beat S to some lock.Neither could access the shared item x without holding its lock.Read the arc as “T holds a resource needed by S”.2PL guarantees that the “winning” transaction T holds