Previously on cs682: Causal delivery Previously on cs682: Logical clocks Logical clock example Vector clocks Previously on cs682: Vector Clock example Previously on cs682: Consensus Replication Why is replication useful? Why is replication useful? Client-side replication Fault tolerance Outline Client Requirements System Model Fault tolerance example Correctness Passive Replication Passive Replication Passive Replication Group Communication Group membership View-synchronous communication View-synchronous communication Comments on passive replication Failures Active Replication Active Replication Active Replication Active replication Failures Lazy Replication Lazy Replication Lazy Replication Lazy Replication Coordinating with lazy replication Querying with lazy replication Updating with lazy replication Updating with lazy replication Gossiping Gossiping Comments on lazy replication Failures SummaryDistributed SoftwareDevelopmentReplicationChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment of Computer Science — University of San Francisco – p. 1/??Previously on cs682: Causal delivery•causal delivery says that if send(m1) → send(m2), thendeliver(m1) → (m2) when different processes are sendingm1and m2.•We can get causal delivery in synchronous systems usinglogical clocks.Department of Computer Science — University of San Francisco – p. 2/??Previously on cs682: Logical clocks•Each process maintains a logical clock. (LC).•Each message m contains a timestamp indicating the logicalclock of the sending process.•After each event, the logical clock f or a process is updatedas follows:•LC(e) = LC + 1 if e is a local or send event.•LC(e) = max(LC, T S(m)) + 1 if e = receive(m).•The LC is updated to be greater than both the previousclock and the timestamp.Department of Computer Science — University of San Francisco – p. 3/??Logical clock examplep1p2p311122 3445565767Department of Computer Science — University of San Francisco – p. 4/??Vector clocks•Vector clocks are an extension of logical clocks.•One logical clock per process.•Provides causal delivery with asynchronous communication.•Update rule:•LC(e)[i] = V C[i] + 1 for send and internal.•V C(e) = max(V C, T S(m)) for receive; thenV C(e)[i] = V C[i] + 1•On receive, the vector clock takes the max on acomponent-by - c omponent basis, then updates the localclock.Department of Computer Science — University of San Francisco – p. 5/??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. 6/??Previously on cs682: Consensus•If we don’t have reliable communication, consensus isimpossible, ev en without failures.•With reliable communication, we can solve consensus forcrash failures.•In asynchronous systems, it is impossible to guarantee thatwe will reach consensus, even in the presence of a singlecrash failure.•This means that we can’t do:•Asynchronous B yzantine generals•Asynchronous totally ordered multicastDepartment of Computer Science — University of San Francisco – p. 7/??Replication•Replication is the maintenance of copies of data at multiplecomputers.•Enhances a service by providing:•Fault tolerance•Improved pe rformance•Increased availability•Information redundanceDepartment of Computer Science — University of San Francisco – p. 8/??Why is replication useful?•Increased performance.•By moving data clo ser to a client, latency is reduced.•Web caching, proxy servers are an ex ample of this.•Performance is improved most effectively with immutabledata.•If the client is going to change the data and send itback, performance gains are reduced.Department of Computer Science — University of San Francisco – p. 9/??Why is replication useful?•Increased availability.•Many services need to be highly available•Replication provides a way of overco ming server failures.•If a server will fail with probability p, then we can determinehow many servers are needed to prov ide a given level ofservice:•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, weneed at least 4 replicas.Department of Computer Science — University of San Francisco – p. 10/??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 so f tware.Department of Computer Science — University of San Francisco – p. 11/??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 presenceof a given number of faults.•Similar to availability, but a coordination element is alsorequired.•We may also want to ensure ag ainst corruption of data.Department of Computer Science — University of San Francisco – p. 12/??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. 13/??Client Requirements•Single logical c opy.•Multiple physical copies.•Consistency•The details of this will depend on the application.Department of Computer Science — University of San Francisco – p. 14/??System ModelClientClientFrontEndFrontEndRMRMRMRM•Clients interact withreplica managers v ia afront end.•Front end hidesreplication from the client.•Front end may interactwith all replica managers,or just a subset.•Replica managers interactto e nsure c onsistency.Department of Computer Science — University of San Francisco – p. 15/??Fault tolerance example•Consider this example:•We have a bank with two re plicated servers: a user’sfront end may connect to either one.•First, a user updates acco unt A via server 1 to contain$10.•Next, the user transfers $ 5 from A to account B viaserver 2.•Server 1 fails before data is propagated.•The bank manager logs into server 2 and sees thataccount A has a balance of 0 and account B has abalance of $5.•Problem: ev e n though the transfer happened after thedepo sit, it is the only o peration
View Full Document
Unlocking...