Computer Computer Science Science 425 425 Distributed Distributed Systems Systems Fall Fall 2009 2009 Lecture 24 Transactions with Replication Reading Section 15 5 Klara Nahrstedt Acknowledgement Acknowledgement The slides during this semester are based on ideas and material from the following sources Slides prepared by Professors M Harandi J Hou I Gupta N Vaidya Y Ch Hu S Mitra Slides from Professor S Gosh s course at University o Iowa Administrative Administrative MP3 posted Deadline December 7 Monday pre competition Top five groups will be selected for final demonstration on Tuuesday December 8 Demonstration Signup Sheets for Monday 12 7 will be made available Main Demonstration in front of the Qualcomm Representative will be on Tuesday December 8 afternoon details will be announced HW4 posted Deadline December 1 2009 Tuesday Plan Plan for for Today Today Gossiping Architecture Review Transactions on replicated objects Communication via 2PC Protocol for Replicated objects no failures Primary copy replication approach Read one write all replication approach Available copies replication approach Replications under failures RM failure Network partition Quorum based approaches A A Gossip Gossip Replica Replica Manager Manager Other replica managers Gossip messages Replica timestamp Replica log Replica manager Timestamp table Value timestamp Replica timestamp Update log Stable Value updates Executed operation table Updates OperationID Update FE FE Prev Update Update Operations Operations Each update request u contains The update operation u op The FE s timestamp u prev A unique id that the FE generates u id Upon receipt of an update request the RM i Check if u has been processed by looking up u id in the executed operation table and in the update log and executed operation table If not increment the i th element in the replica timestamp by 1 to keep track of the number of updates directly received from FEs Place a record for the update in the RM s log logRecord i ts u op u prev u id where ts is derived from u prev by replacing u prev s ith element by the ith element of its replica timestamp Return ts back to the FE which merges it with its timestamp Update Update Operation Operation Cont d Cont d The stability condition for an update u is u prev valueTS i e All the updates on which this update depends have already been applied to the value When the update operation u becomes stable the RM does the following value apply value u op valueTS merge valueTS ts update the value timestamp executed executed U u id update the executed operation table Exchange Exchange of of Gossiping Gossiping Messages Messages A gossip message m consists of the log of the RM m log and the replica timestamp m ts Replica timestamp contains info about non stable updates An RM that receives a gossip message has three tasks 1 Merge the arriving log with its own Let replicaTS denote the recipient RM s replica timestamp A record r in m log is added to the recipient s log unless r ts replicaTS replicaTS merge replicaTS m ts 2 Apply any updates that have become stable but not been executed stable updates in the arrived log may cause some pending updates become stable 3 Garbage collect Eliminate records from the log and the executed operation table when it is known that the updates have been applied everywhere Query Query Operations Operations A query request q contains the operation q op and the timestamp q prev sent by the FE Let valueTS denote the RM s value timestamp then q can be applied if q prev valueTS The RM keeps q on a hold back queue until the condition is fulfilled If valueTs is 2 5 5 and q prev is 2 4 6 then one update from RM3 is missing Once the query is applied the RM returns new valueTS to the FE along with the value and the FE merges new with its timestamp Selecting Selecting Gossip Gossip Partners Partners The frequency with which RMs send gossip messages depends on the application Policy for choosing a partner to exchange gossip with Random policies choose a partner randomly perhaps with weighted probabilities Deterministic policies a RM can examine its timestamp table and choose the RM that is the furthest behind in the updates it has received Topological policies arrange the RMs into an overlay graph Choose graph edges based on small round trip times RTTs e g ring or Chord Each has its own merits and drawbacks The ring topology produces relatively little communication but is subject to high transmission latencies since gossip has to traverse several RMs Example Network News Transport Protocol NNTP uses gossip communication Your updates to class cs425 are spread among News servers using the gossip protocol Gives probabilistically reliable and fast dissemination of data with very low background bandwidth Analogous to the spread of gossip in society Examples Examples of of Highly Highly Available Available Services Services Bayou Replicated database with weaker guarantees than sequential consistency Uses gossip timestamps and concept of anti entropy Anti Entropy Anti entropy protocols for repairing replicated data which operate by comparing replicas and reconciling differences Complete anti entropy CAE Reconcile all inconsistent states Selective anti entropy SAE Selectively reconcile inconsistent states Coda Provides high availability in spite of disconnected operation e g roving and transiently disconnected laptops Based on AFS Aims to provide Constant data availability Transactions Transactions on on Replicated Replicated Data Data Client front end Client front end U T deposit B 3 getBalance A B Replica managers Replica managers A A A B B B One One Copy Copy Serialization 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 Coordination Coordination in in PrimaryPrimaryBackup Backup Communication Replication Replication Service ServiceView Synchronous in the group of RMs Coordinator join Participant Primary RM Client Front End T B Backup Replication Manager B Replication Manager B Backup Replication Manager B Backup Replication Manager Replication Service Interface
View Full Document
Unlocking...