U of I CS 425 - Transactions with Replication

Unformatted text preview:

Computer Science 425 Distributed SystemsTransactions on Replicated DataOne Copy SerializationTwo Phase Commit Protocol For Replicated ObjectsPrimary Copy ReplicationRead One/Write All ReplicationAvailable Copies ReplicationAvailable Copies ApproachThe Impact of RM FailureLocal Validation (using Our Example)Network PartitionDealing with Network PartitionsQuorum ApproachesStatic QuorumsVoting with Static QuorumsQuorum Consensus ExamplesOptimistic Quorum ApproachesView-based QuorumView-based Quorum - detailsExample: View-based QuorumExample: View-based Quorum (cont’d)Summary 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 25-1Lecture 25-1Computer Science 425Distributed SystemsComputer Science 425Distributed SystemsLecture 25Transactions with ReplicationReading: Section 15.5 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 25-2Lecture 25-2Transactions on Replicated DataTransactions on Replicated DataBAClient + front endBB BAAgetBalance(A)Client + front endReplica managersReplica managersdeposit(B,3);UT 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 25-3Lecture 25-3One Copy SerializationOne Copy Serialization•In a non-replicated system, transactions appear to be performed one at a time in some order. This is achieved by ensuring a serially equivalent interleaving of transaction operations.•One-copy serializability: The effect of transactions performed by clients on replicated objects should be the same as if they had been performed one at a time on a single set of objects (i.e., 1 replica per object). –Equivalent to combining serial equivalence + replication transparency/consistency 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 25-4Lecture 25-4Two Phase Commit Protocol For Replicated ObjectsTwo Phase Commit Protocol For Replicated ObjectsTwo level nested 2PC•In the first phase, the coordinator sends the canCommit? command to the participants, each of which then passes it onto the other RMs involved (e.g., by using view synchronous communication) and collects their replies before replying to the coordinator.•In the second phase, the coordinator sends the doCommit or doAbort request, which is passed onto the members of the groups of RMs. 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 25-5Lecture 25-5Primary Copy ReplicationPrimary Copy Replication•For now, assume no crashes/failures•All the client requests are directed to a single primary RM.•Concurrency control is applied at the primary. •To commit a transaction, the primary communicates with the backup RMs and replies to the client.•View synchronous comm. gives  one-copy serializability•Disadvantage? Performance is low since primary RM is bottleneck. 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 25-6Lecture 25-6Read One/Write All ReplicationRead One/Write All Replication•An FE may communicate with any RM.•Every write operation must be performed at all of the RMs–Each contacted RM sets a write lock on the object. •A read operation can be performed at any single RM–A contacted RM sets a read lock on the object.•Consider pairs of conflicting operations of different transactions on the same object.–Any pair of write operations will require locks at all of the RMs  not allowed–A read operation and a write operation will require conflicting locks at some RM  not allowedOne-copy serializability is achieved.Disadvantage? Failures block the system (esp. writes). 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 25-7Lecture 25-7Available Copies ReplicationAvailable Copies Replication•A client’s read request on an object can be performed by any RM, but a client’s update request must be performed across all available (i.e., non-faulty) RMs in the group.•As long as the set of available RMs does not change, local concurrency control achieves one-copy serializability in the same way as in read-one/write-all replication. •May not be true if RMs fail and recover during conflicting transactions. 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 25-8Lecture 25-8Available Copies ApproachAvailable Copies ApproachAXClient + front endPBClient + front endReplica managersdeposit(A,3);UTdeposit(B,3);getBalance(B)getBalance(A)Replica managersYMBNAB 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 25-9Lecture 25-9The Impact of RM FailureThe Impact of RM Failure•Assume that (i) RM X fails just after T has performed getBalance; and (ii) RM N fails just after U has performed getBalance. Both failures occur before any of the deposit()s.•Subsequently, T’s deposit will be performed at RMs M and P, and U’s deposit will be performed at RM Y. •The concurrency control on A at RM X does not prevent transaction U from updating A at RM Y.•Solution: Must also serialize RM crashes and recoveries with respect to transactions. 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 25-10Lecture 25-10Local Validation (using Our Example)Local Validation (using Our Example)•From T’s perspective,–T has read from an object at X  X must have failed after T’s operation. –T observes the failure of N when it attempts to update the object B  N’s failure must be before T.–N fails  T reads object A at X; T writes objects B at M and P  T commits  X fails.•From U’s perspective,–X fails  U reads object B at N; U writes object A at Y  U commits  N fails.•At the time T tries to commit, –it first checks if N is still not available and if X, M and P are still available. Only then can T commit.–It then sees if the failure order is consistent with that of other transactions (T cannot commit if U has committed)–If T commits, U’s validation will fail because N has already failed.•Can be combined with 2PC. •Local validation may not work if partitions occur in the network 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 25-11Lecture 25-11Network PartitionNetwork PartitionClient + front endBwithdraw(B, 4)Client + front endReplica managersdeposit(B,3);UTNetworkpartitionBB B 2002, M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 25-12Lecture 25-12Dealing with Network PartitionsDealing with Network Partitions•During a partition, pairs of conflicting transactions may have been allowed to execute in different partitions. The only choice is to take corrective action after the network has recovered


View Full Document

U of I CS 425 - Transactions with Replication

Documents in this Course
Lecture 8

Lecture 8

23 pages

TIPS

TIPS

3 pages

The Grid

The Grid

41 pages

Lecture 4

Lecture 4

27 pages

Lecture 4

Lecture 4

20 pages

The Grid

The Grid

41 pages

LECTURE 5

LECTURE 5

25 pages

Multicast

Multicast

23 pages

LECTURE

LECTURE

34 pages

Load more
Download Transactions with Replication
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 Transactions with Replication 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 Transactions with Replication 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?