{small lecturenumber - hepage :} Previously on cs682: Causal delivery{small lecturenumber - hepage :} Previously on cs682: Vector clocks{small lecturenumber - hepage :} Previously on cs682: Vector Clock example{small lecturenumber - hepage :} Previously on cs682: Consensus{small lecturenumber - hepage :} Replication{small lecturenumber - hepage :} Why is replication useful?{small lecturenumber - hepage :} Why is replication useful?{small lecturenumber - hepage :} Client-side replication{small lecturenumber - hepage :} Fault tolerance{small lecturenumber - hepage :} Outline{small lecturenumber - hepage :} Client Requirements{small lecturenumber - hepage :} System Model{small lecturenumber - hepage :} Fault tolerance example{small lecturenumber - hepage :} Correctness{small lecturenumber - hepage :} Passive Replication{small lecturenumber - hepage :} Passive Replication{small lecturenumber - hepage :} Passive Replication{small lecturenumber - hepage :} Group Communication{small lecturenumber - hepage :} Group membership{small lecturenumber - hepage :} View-synchronous communication{small lecturenumber - hepage :} View-synchronous communication{small lecturenumber - hepage :} Comments on passive replication{small lecturenumber - hepage :} Failures{small lecturenumber - hepage :} Active Replication{small lecturenumber - hepage :} Active Replication{small lecturenumber - hepage :} Active Replication{small lecturenumber - hepage :} Active replication{small lecturenumber - hepage :} Failures{small lecturenumber - hepage :} Lazy Replication{small lecturenumber - hepage :} Lazy Replication{small lecturenumber - hepage :} Lazy Replication{small lecturenumber - hepage :} Lazy Replication{small lecturenumber - hepage :} Coordinating with lazy replication{small lecturenumber - hepage :} Querying with lazy replication{small lecturenumber - hepage :} Updating with lazy replication{small lecturenumber - hepage :} Updating with lazy replication{small lecturenumber - hepage :} Gossiping{small lecturenumber - hepage :} Gossiping{small lecturenumber - hepage :} Comments on lazy replication{small lecturenumber - hepage :} Failures{small lecturenumber - hepage :} SummaryDistributed Software DevelopmentReplicationChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment 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), thendeliver(m1) → (m2) when different processes are sending m1and 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, TS(m)) for receive; thenV C(e)[i] = V C[i] + 1•On receive, the vector clock takes the max on acomponent-by-component basis, then updates the local clock.Department of Computer Science — University of San Francisco8-4: Previously on cs682: Vector Clock examplep1p2p3(1,0,0)(0,1,0)(0,0,1)(2,1,0)(1,0,2)(1,0,3)(1,0,4)(3,1,3)(1,2,4)(4,1,3)(4,3,4)(1,0,5) (5,1,6)(5,1,3) (6,1,3)Department of Computer Science — University of San Francisco – p. 4/??8-5: Previously on cs682: Consensus•If we don’t have reliable communication, consensus isimpossible, even without failures.•With reliable communication, we can solve consensus for crashfailures.•In asynchronous systems, it is impossible to guarantee that wewill reach consensus, even in the presence of a single crashfailure.•This means that we can’t do:◦Asynchronous Byzantine generals◦Asynchronous totally ordered multicastDepartment of Computer Science — University of San Francisco – p. 5/??8-6: Replication•Replication is the maintenance of copies of data at multiplecomputers.•Enhances a service by providing:◦Fault tolerance◦Improved performance◦Increased availability◦Information redundanceDepartment of Computer Science — University of San Francisco8-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 howmany 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 agiven time period, and we want 99.9% availability, we need atleast 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 Francisco8-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 ofa given number of faults.•Similar to availability, but a coordination element is alsorequired.•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 Francisco8-13: System ModelClientClientFrontEndFrontEndRMRMRMRM•Clients interact with replicamanagers via a front end.•Front end hides replicationfrom the client.•Front end may interact withall replica managers,
View Full Document
Unlocking...