DOC PREVIEW
USF CS 682 - Replication

This preview shows page 1-2-3-20-21-40-41-42 out of 42 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Distributed Software Development Replication Chris Brooks Department of Computer Science University of San Francisco Department of Computer Science University of San Francisco p 1 8 2 Previously on cs682 Causal delivery causal delivery says that if send m1 send m2 then deliver m1 m2 when different processes are sending m1 and m2 Logical clocks aren t enough to give us causal delivery Department of Computer Science University of San Francisco p 2 8 3 Previously on cs682 Vector clocks Solution keep a logical clock for each process these are stored in a vector V C Assumes number of processes in known and fixed Update rule V C e i V C i 1 for send and internal V C e max V C T S m for receive then V C e i V C i 1 On receive the vector clock takes the max on a component by component basis then updates the local clock Department of Computer Science University of San Francisco p 3 8 4 Previously on cs682 Vector Clock example 1 0 0 2 1 0 p1 3 1 3 4 1 3 5 1 3 6 1 3 1 2 4 p2 4 3 4 0 1 0 p3 0 0 1 1 0 2 1 0 3 1 0 4 1 0 5 5 1 6 Department of Computer Science University of San Francisco p 4 8 5 Previously on cs682 Consensus If we don t have reliable communication consensus is impossible even without failures With reliable communication we can solve consensus for crash failures In asynchronous systems it is impossible to guarantee that we will reach consensus even in the presence of a single crash failure This means that we can t do Asynchronous Byzantine generals Asynchronous totally ordered multicast Department of Computer Science University of San Francisco p 5 8 6 Replication Replication is the maintenance of copies of data at multiple computers Enhances a service by providing Fault tolerance Improved performance Increased availability Information redundance Department of Computer Science University of San Francisco p 6 8 7 Why is replication useful Increased performance By moving data closer to a client latency is reduced Web caching proxy servers are an example of this Performance is improved most effectively with immutable data If the client is going to change the data and send it back performance gains are reduced Department of Computer Science University of San Francisco p 7 8 8 Why is replication useful Increased availability Many services need to be highly available Replication provides a way of overcoming server failures If a server will fail with probability p then we can determine how many servers are needed to provide a given level of service Avail 1 pn For example if a server has a 5 chance of failure i i d over a given time period and we want 99 9 availability we need at least 4 replicas Department of Computer Science University of San Francisco p 8 8 9 Client side replication Note that replication is not limited to servers Multiple clients may need to replicate data Shared code or documents being edited Meeting scheduling Conferencing or whiteboard software Department of Computer Science University of San Francisco p 9 8 10 Fault tolerance Highly available data may not be correct data For example in the presence of network outages Fault tolerance guarantees correct behavior in the presence of a given number of faults Similar to availability but a coordination element is also required We may also want to ensure against corruption of data Department of Computer Science University of San Francisco p 10 8 11 Outline Passive Replication What problems must be solved for this Active Replication What problems must be solved for this Lazy Replication What problems must be solved for this Department of Computer Science University of San Francisco p 11 8 12 Client Requirements Single logical copy Multiple physical copies Consistency The details of this will depend on the application Department of Computer Science University of San Francisco p 12 8 13 System Model Clients interact with replica managers via a front end Client Front end hides replication Front End RM from the client RM RM Client Front End RM Front end may interact with all replica managers or just a subset Replica managers interact to ensure consistency Department of Computer Science University of San Francisco p 13 8 14 Fault tolerance example Consider this example We have a bank with two replicated servers a user s front end may connect to either one First a user updates account A via server 1 to contain 10 Next the user transfers 5 from A to account B via server 2 Server 1 fails before data is propagated The bank manager logs into server 2 and sees that account A has a balance of 0 and account B has a balance of 5 Problem even though the transfer happened after the deposit it is the only operation seen Department of Computer Science University of San Francisco p 14 8 15 Correctness This example violates sequential consistency Sequential consistency says that Interleaving operations across servers produces a sequence that is consistent with a correct copy of the objects The global order is consistent with the local order in which each client executed its operations This is very much like our definition of causality Department of Computer Science University of San Francisco p 15 8 16 Passive Replication Passive replication uses a single replica manager Other replica managers act Client Front End as backups or slaves Backup RM Backup RM Client Front End Primary RM Backup RM Primary manager executes operations and sends copies of updated data to backups If primary fails a new one is elected Department of Computer Science University of San Francisco p 16 8 17 Passive Replication Sequence of events 1 Front end issues a request to primary 2 Primary takes requests in FIFO order Checks to see if request has already been serviced If so re send response 3 Execute request and store response 4 If data is updated send updates to all backups All backups acknowledge 5 Response is sent to client Department of Computer Science University of San Francisco p 17 8 18 Passive Replication A question How do we communicate updates to all backups Recall that we want to be able to tolerate primary crashes before during and after updating Department of Computer Science University of San Francisco p 18 8 19 Group Communication Updating replicas is a group communication problem If groups can change dynamically then a group membership service is needed This keeps track of the processes that are currently in a group Department of Computer Science University of San Francisco p 19 8 20 Group membership A group membership process needs to Provide an


View Full Document

USF CS 682 - Replication

Documents in this Course
Load more
Download 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 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 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?