Asynchronous Replication and BayouAsynchronous ReplicationSynchronous ReplicationGrapevine and Clearinghouse (Xerox)Epidemic AlgorithmsHow to Ensure That Replicas ConvergeIssues and Techniques for Weak ReplicationBayou BasicsClocksUpdate OrderingCausalityCausality: ExampleLogical ClocksLogical Clocks: ExampleWhich Updates to Propagate?Flooding and the Prefix PropertyCausality and ReconciliationCausality and Updates: ExampleMotivation for Vector ClocksVector ClocksVector Clocks: ExampleVector Clocks and CausalityReconciliation with Vector ClocksThe Prefix Property and ReconciliationWhen to Discard or Stabilize Updates?The Need for Propagating AcknowledgementsMatrix ClocksPropagating Acknowledgment StampsGolding’s TSAE ProtocolAck Vectors in TSAE: ExampleThe Trouble With Ack VectorsCommitting Updates in BayouReconciliation with CSNsBayou Update Logs: ExampleUpdate Log with Commitment: ExampleDiscarding Updates in BayouReconciliation with Update Log TruncationReconciling a Lagging ServerThat Pesky “O-Vector”Reconciliation Using Transportable MediaQuestions About BayouWrite Conflicts in Optimistic ReplicationDetecting Update Conflicts: Traditional ViewExample: CodaVersion Vectors in CodaUpdate Conflicts: the Bayou ApproachApplication-Specific ReconciliationHandling Update Conflicts in BayouAsynchronous Replication and BayouAsynchronous Replication and BayouJeff ChaseCPS 212, Fall 2000Asynchronous ReplicationAsynchronous Replicationclient BIdea: build available/scalable information services with read-any-write-any replication and a weak consistency model.- no denial of service during transient network partitions- supports massive replication without massive overhead- “ideal for the Internet and mobile computing” [Golding92]Problems: replicas may be out of date, may accept conflicting writes, and may receive updates in different orders.client Cclient Aasynchronous statepropagationreplica Breplica Areplica CSynchronous ReplicationSynchronous Replicationclient AProblem: low concurrency, low availability, and high response times.Partial Solution: Allow writes to any N replicas (a quorum of size N). To be safe, reads must also request data from a quorum of replicas.Basic scheme: connect each client (or front-end) with every replica: writes go to all replicas, but client can read from any replica (read-one-write-all replication).client BHow to ensure that each replicasees updates in the “right” order?replicasGrapevine and Clearinghouse (Xerox)Grapevine and Clearinghouse (Xerox)Weakly consistent replication was used in earlier work at Xerox PARC:•Grapevine and Clearinghouse name servicesUpdates were propagated by unreliable multicast (“direct mail”).•Periodic anti-entropy exchanges among replicas ensure that they eventually converge, even if updates are lost.Arbitrary pairs of replicas periodically establish contact and resolve all differences between their databases.Various mechanisms (e.g., MD5 digests and update logs) reduce the volume of data exchanged in the common case. Deletions handled as a special case via “death certificates” recording the delete operation as an update.Epidemic AlgorithmsEpidemic AlgorithmsPARC developed a family of weak update protocols based on a disease metaphor (epidemic algorithms [Demers et. al. OSR 1/88]):•Each replica periodically “touches” a selected “susceptible” peer site and “infects” it with updates.Transfer every update known to the carrier but not the victim.Partner selection is randomized using a variety of heuristics.•Theory shows that the epidemic will eventually the entire population (assuming it is connected).Probability that replicas that have not yet converged decreases exponentially with time.Heuristics (e.g., push vs. pull) affect traffic load and the expected time-to-convergence.How to Ensure That Replicas ConvergeHow to Ensure That Replicas Converge1. Using any form of epidemic (randomized) anti-entropy, all updates will (eventually) be known to all replicas.2. Imposing a global order on updates guarantees that all sites (eventually) apply the same updates in the same order.3. Assuming conflict detection is deterministic, all sites will detect the same conflicts.Write conflicts cannot (generally) be detected when a site accepts a write; they appear when updates are applied.3. Assuming conflict resolution is deterministic, all sites will resolve all conflicts in exactly the same way.Issues and Techniques for Weak ReplicationIssues and Techniques for Weak Replication1. How should replicas choose partners for anti-entropy exchanges?Topology-aware choices minimize bandwidth demand by “flooding”, but randomized choices survive transient link failures.2. How to impose a global ordering on updates?logical clocks and delayed delivery (or delayed commitment) of updates3. How to integrate new updates with existing database state?Propagate updates rather than state, but how to detect and reconcile conflicting updates? Bayou: user-defined checks and merge rules. 4. How to determine which updates to propagate to a peer on each anti-entropy exchange?vector clocks or vector timestamps5. When can a site safely commit or stabilize received updates?receiver acknowledgement by vector clocks (TSAE protocol)Bayou BasicsBayou Basics1. Highly available, weak replication for mobile clients.Beware: every device is a “server”... let’s call ‘em sites.2. Update conflicts are detected/resolved by rules specified by the application and transmitted with the update.interpreted dependency checks and merge procedures3. Stale or tentative data may be observed by the client, but may mutate later.The client is aware that some updates have not yet been confirmed.“An inconsistent database is marginally less useful than a consistent one.”ClocksClocks1. physical clocksProtocols to control drift exist, but physical clock timestamps cannot assign an ordering to “nearly concurrent” events.2. logical clocksSimple timestamps guaranteed to respect causality: “A’s current time is later than the timestamp of any event A knows about, no matter where it happened or who told A about it.”3. vector clocksOrder(N) timestamps that say exactly what A knows about events on B, even if A heard it from C.4. matrix clocksOrder(N2) timestamps that say what A knows about what B knows about events on C.Acknowledgement vectors: an O(N) approximation to matrix clocks.Update OrderingUpdate OrderingProblem: how to ensure that all sites