Practical ReplicationPurposes of ReplicationProblems with ReplicationThe Costs and Limits of Availability for Replicated ServicesContinuous Consistency ModelMetrics of ConsistencyExample of Numerical and Order ErrorDeriving tight upper bound on availabilityUpper bound as a function of Numerical error and stalenessUpper bound as a function of order errorSerialization orderWhat can we get from this?Numerical Error BoundOrder Error BoundEffects of Replication ScaleThe Dangers of Replication and a SolutionHow does replication models affect deadlock/reconciliation ratesEager ReplicationLazy Group ReplicationSlide 20Lazy Master ReplicationNon-Transactional SchemesTwo-tier systemSlide 24Slide 25ExampleSlide 27Two-tier systemPractical ReplicationPurposes of ReplicationImprove AvailabilityReplicated databases can be accessed even if several replicas are unavailableImprove PerformanceReplicas can be geographically diverse, with closest replica serving each clientProblems with ReplicationConsistency of the replicated dataMany applications require consistency regardless of which replica is read from or inserted intoConsistency is expensiveSome replication schemes will reduce update availabilityOthers require reconciliation after inconsistency occursPerformance may suffer as agreement across replicas may be necessaryThe Costs and Limits of Availability for Replicated ServicesConsistency vs. AvailabilityMany applications don’t need strong consistencyCan specify a maximum deviationConsistency don’t need to be sacrificed during normal operationOnly perform tradeoff when failure occursTypically two choices of consistencyStrong consistencyLow availability, high data accuracyWeak consistencyHigh availability, low accuracy (lots of conflicts and stale access)Continuous Consistency ModelA spectrum of different levels of consistencyDynamically adapt consistency bounds in response to environmental changesContinuous Consistency ModelMetrics of ConsistencyThree categories of errors in consistency at a replicaNumerical error The total number of writes accepted by the system but not seen by the replicaStalenessDifference between current time and the acceptance time of the oldest write not seen locallyOrder errorNumber of writes that have not established their commit order at the local replicaExample of Numerical and Order ErrorDeriving tight upper bound on availabilityWant to derive a tight upper bound on the Availservice based on a given level of consistency, workload, and faultloadAvailservice  F(consistency, workload, faultload)Upper bound helps evaluate existing consistency protocolsReveal inherent impact of consistency on availabilityOptimize existing consistency protocolsQuestions:Must determine which write to accept or rejectAccepting all writes that do not violate consistency may preclude acceptance of a larger number of write in the futureDetermine when and where to propagate writesWrite propagation decreases numerical error but can increase order errorMust decide serialization orderCan affect the order errorUpper bound as a function of Numerical error and stalenessQuestions on write propagationWhen and where to propagate writesSimply propagate writes to all replicas whenever possible – Aggressive write propagationAlways help reduce both numerical error and stalenessQuestions on write acceptanceMust perform a exhaustive search on all possible sets of accepted writesTo maximize availability and ensure numerical and staleness bounds are not violatedSearch space can be reduced by collapsing all writes in an interval to a single logical writeDue to Aggressive write propagationUpper bound as a function of order errorTo commit a write, a replica must see all preceding writes in the global serialization orderMust determine the global serialization orderFactorial number of serialization orderSearch space can be reducedCausal orderSerialization orders compatible with causal orderCluster orderWrites accepted by the same partition during a particular interval cluster togetherSerialization orderExample:Suppose Replica 1 receives transaction W1 and W2 and Replica 2 receives W3 and W4CausalS = W1W2W3W4 better than S’ = W2W1W3W4Whenever W2 can be committed using S’, the replica must bave already seen W1 and thus can also commit W2 in S. The same is true for W1, W3, W4ClusterOnly 2 possible clustersS = W1W2W3W4 and W3W4W1W2Intuition is that it does not expedite write commitment on any replica if the writes accepted by the same partition during a particular interval are allowed to split into multiple sections in the serialization orderCluster has smallest search spaceWhat can we get from this?Modify an existing protocol with ideas from proofEach replica ensure that the error bound on other replicas are not violatedReplica may push writes to other replicas before accepting a new writeAdded aggressive write propagationAnalyze other protocols for order errorPrimary copy protocolA write is committed when it reaches the primary replicaSerialization order is the write order as seen by primary replicaGolding’s algorithmEach write assigned a logical timestamp that determines serialization orderEach replica maintains a version vector to determine whether it has seen all writes with time less than tPulls in writes from other replicas to advance version vectorVotingOrder is determining by voting of membersIs there anything else other than Aggressive Write Propagation that we can get from this proof?Numerical Error BoundAs predicted, aggressive write propagation improves availabilityAlso increases the number of messages requiredRemoves the optimization of combining multiple updates to amortize communication costsPacket header overhead, packet boundaries, ramping up to the bottleneck bandwidth in TCPOrder Error Bound Aggressive Voting also performs wellBase voting is awfulLazy replication can cause each replica to casts a vote for a different uncommitted writeEach replica must collect votes from all replicas to determine winner and any unknown vote can be the deciding oneAggressive ensures most votes for the same uncommitted writeOnly need to contact a subset of nodesEffects of Replication ScaleAdding more replicas Reduces