1CS677: Distributed OSComputer ScienceLecture 13, page 1Last Class: Canonical Problems• Election algorithms– Bully algorithm– Ring algorithm• Distributed synchronization and mutual exclusionCS677: Distributed OSComputer ScienceLecture 13, page 2Today: More on Transactions• Distributed transactions• Implementation issues– Workspaces– Writeahead logs• Concurrency control– Two phase locks– Time stamps2CS677: Distributed OSComputer ScienceLecture 13, page 3Transactions•Transactions provide higher levelmechanism for atomicity ofprocessing in distributed systems– Have their origins in databases•Banking example: Threeaccounts A:$100, B:$200, C:$300– Client 1: transfer $4 from A to B– Client 2: transfer $3 from C to B•Result can be inconsistent unlesscertain properties are imposed onthe accessesWrite B:$203Read B: $200Write B:$204Read B: $200Write C:$297Read C: $300Write A: $96Read A: $100Client 2Client 1CS677: Distributed OSComputer ScienceLecture 13, page 4ACID Properties•Atomic: all or nothing•Consistent: transaction takessystem from one consistent state toanother•Isolated: Immediate effects arenot visible to other (serializable)•Durable: Changes are permanentonce transaction completes(commits)Read B: $204Write C:$297Write B:$207Read C: $300Write B:$204Read B: $200Write A: $96Read A: $100Client 2Client 13CS677: Distributed OSComputer ScienceLecture 13, page 5Transaction PrimitivesExample: airline reservationBegin_transactionif(reserve(NY,Paris)==full) Abort_transactionif(reserve(Paris,Athens)==full)Abort_transactionif(reserve(Athens,Delhi)==full) Abort_transactionEnd_transactionWrite data to a file, a table, or otherwiseWRITERead data from a file, a table, or otherwiseREADKill the transaction and restore the old valuesABORT_TRANSACTIONTerminate the transaction and try to commitEND_TRANSACTIONMake the start of a transactionBEGIN_TRANSACTIONDescriptionPrimitiveCS677: Distributed OSComputer ScienceLecture 13, page 6Distributed Transactionsa) A nested transactionb) A distributed transaction4CS677: Distributed OSComputer ScienceLecture 13, page 7Implementation: Private Workspace• Each transaction get copies of all files, objects• Can optimize for reads by not making copies• Can optimize for writes by copying only what is required• Commit requires making local workspace globalCS677: Distributed OSComputer ScienceLecture 13, page 8Option 2: Write-ahead Logs• In-place updates: transaction makes changes directly to allfiles/objects• Write-ahead log: prior to making change, transaction writes to logon stable storage– Transaction ID, block number, original value, new value• Force logs on commit• If abort, read log records and undo changes [rollback]• Log can be used to rerun transaction after failure• Both workspaces and logs work for distributed transactions• Commit needs to be atomic [will return to this issue in Ch. 7]5CS677: Distributed OSComputer ScienceLecture 13, page 9Writeahead Log Example• a) A transaction• b) – d) The log before each statement is executedLog[x = 0 / 1][y = 0/2][x = 1/4] (d)Log[x = 0 / 1][y = 0/2] (c)Log[x = 0 / 1] (b)x = 0;y = 0;BEGIN_TRANSACTION; x = x + 1; y = y + 2 x = y * y;END_TRANSACTION; (a)CS677: Distributed OSComputer ScienceLecture 13, page 10Concurrency Control• Goal: Allow several transactions to be executingsimultaneously such that– Collection of manipulated data item is left in a consistent state• Achieve consistency by ensuring data items are accessedin an specific order– Final result should be same as if each transaction ransequentially• Concurrency control can implemented in a layered fashion6CS677: Distributed OSComputer ScienceLecture 13, page 11Concurrency Control Implementation• General organization of managers for handling transactions.CS677: Distributed OSComputer ScienceLecture 13, page 12Distributed Concurrency Control• General organization ofmanagers for handlingdistributed transactions.7CS677: Distributed OSComputer ScienceLecture 13, page 13Serializability• Key idea: properly schedule conflicting operations• Conflict possible if at least one operation is write– Read-write conflict– Write-write conflictBEGIN_TRANSACTION x = 0; x = x + 3;END_TRANSACTION (c)BEGIN_TRANSACTION x = 0; x = x + 2;END_TRANSACTION (b)BEGIN_TRANSACTION x = 0; x = x + 1;END_TRANSACTION (a)Illegalx = 0; x = 0; x = x + 1; x = 0; x = x + 2; x = x + 3;Schedule 3Legalx = 0; x = 0; x = x + 1; x = x + 2; x = 0; x = x + 3;Schedule 2Legalx = 0; x = x + 1; x = 0; x = x + 2; x = 0; x = x + 3Schedule 1CS677: Distributed OSComputer ScienceLecture 13, page 14Optimistic Concurrency Control• Transaction does what it wants and validates changes prior tocommit– Check if files/objects have been changed by committed transactions sincethey were opened– Insight: conflicts are rare, so works well most of the time• Works well with private workspaces• Advantage:– Deadlock free– Maximum parallelism• Disadvantage:– Rerun transaction if aborts– Probability of conflict rises substantially at high loads• Not used widely8CS677: Distributed OSComputer ScienceLecture 13, page 15Two-phase Locking• Widely used concurrency control technique• Scheduler acquires all necessary locks in growing phase,releases locks in shrinking phase– Check if operation on data item x conflicts with existing locks• If so, delay transaction. If not, grant a lock on x– Never release a lock until data manager finishes operation on x– One a lock is released, no further locks can be granted• Problem: deadlock possible– Example: acquiring two locks in different order• Distributed 2PL versus centralized 2PLCS677: Distributed OSComputer ScienceLecture 13, page 16Two-Phase Locking• Two-phase locking.9CS677: Distributed OSComputer ScienceLecture 13, page 17Strict Two-Phase Locking• Strict two-phase locking.CS677: Distributed OSComputer ScienceLecture 13, page 18Timestamp-based Concurrency Control• Each transaction Ti is given timestamp ts(Ti)• If Ti wants to do an operation that conflicts with Tj– Abort Ti if ts(Ti) < ts(Tj)• When a transaction aborts, it must restart with a new(larger) time stamp• Two values for each data item x– Max-rts(x): max time stamp of a transaction that read x– Max-wts(x): max time stamp of a transaction that wrote x10CS677: Distributed OSComputer ScienceLecture 13, page 19Reads and