Continuous Consistency and AvailabilityConsistency in ReplicationStrong Consistency and Optimistic ConsistencyProblems with Binary ChoiceContinuous ConsistencyQuantifying ConsistencyApplications ?Trading Consistency for PerformanceThe Cost of Increased PerformanceModel vs. ProtocolDesigning a Continuous Consistency ModelDistributed Consensus and Leader ElectionGroup Membership ServiceContinuous Consistency SummaryWhat is Availability ?Perform-abilityAvailability of an Internet ServiceEffects of ReplicationLimitations of Strong ConsistencyEffects of Continuous ConsistencySlide 21Consistency Impact is InherentEffects of Consistency ProtocolAvailability OptimizationsSlide 25Retiring ReplicasAggressive Write PropagationEffects of Aggressive PropagationMore Aggressive PropagationAvailability of Other SystemsAvailability SummaryWhy can we easily approach the upper bound?Dual Effects of Replication Scale on AvailabilityOptimal Replication ScaleContinuous Consistency Continuous Consistency and Availabilityand AvailabilityHaifeng YuCPS 212 Fall 20022Consistency in ReplicationConsistency in ReplicationReplication comes with consistency cost:Reasons for replication: Better performance and availabilityclientclientclientserverserverserverReplication transforms client-server communication to server-server communication: •Decrease performance•Decrease availability3Strong Consistency and Optimistic ConsistencyStrong Consistency and Optimistic ConsistencyTraditionally, two choices for consistency level:•Strong consistency: Strictly “in sync”•Optimistic consistency: No guarantee at all•Associated tradeoffs with each modelAvailability / Performance /ScalabilityConsistencyOptimistic ConsistencyStrong Consistency4Problems with Binary ChoiceProblems with Binary ChoiceStrong consistency incurs prohibitive overheads for many WAN apps•Replication may even decrease performance, availability and scalability relative to a single server!Optimistic consistency provides no consistency guarantee at all•Resulting in upset users: Unbounded reservation conflicts•Potentially render the app unusable: If traffic data is more than 1 hour stale, probably of little useApplications cannot tune consistency level based on its environment•Need to adapt to client, service and network characteristics5Continuous ConsistencyContinuous ConsistencyConsistency is continuous rather than binary for many WAN apps •These apps can benefit from exploiting the consistency spectrum between strong and optimistic consistency.Availability / Performance /ScalabilityConsistencyOptimistic ConsistencyStrong ConsistencyConsistencyContinuous ConsistencyAvailability / Performance /Scalability6Quantifying ConsistencyQuantifying ConsistencyMany ways:•Staleness (TTL in web caching): Invalidate•Limit number of locally buffered writesbufferedupdatesTo OtherReplicas7Applications ?Applications ?Applications:•Web caching•Airline reservation•Distributed games•Shared editorNon-Applications:•Some scientific computing problems•Banking system•Any application that has binary outputApplication’s nature determines whether continuous consistency is applicable8Trading Consistency for PerformanceTrading Consistency for PerformanceAirline reservation: running at Berkeley, Utah, Duke010203040500% 50% 100%InconsistencyThroughput(updates/sec)StrongConsistencyOptimisticConsistency[Yu’02, TOCS]9The Cost of Increased PerformanceThe Cost of Increased PerformanceIncreased performance comes with a cost•Adaptively trade consistency for performance based on client, network, and service conditions0%5%10%15%20%25%0% 20% 40% 60% 80% 100%InconsistencyResv. Conflict Rate10Model vs. ProtocolModel vs. ProtocolContinuous consistency model is a spec.Protocol is anything that can enforce the spec. •Corollary: Strong consistency protocol is a protocol for any modelMany protocols for a specific model, some are good, others are not11Designing a Continuous Consistency ModelDesigning a Continuous Consistency ModelModel is a spec, thus quantifying consistency (in a bad way) is trivialOnly applications know its definition of consistency•Airline reservation vs. distributed gamesWhat is a “good” continuous consistency model?•Can be used by diverse apps•Practical12Distributed Consensus and Leader ElectionDistributed Consensus and Leader ElectionWhat does “continuous consistency” mean ?•Allow at most k decision values•Allow at most k leadersHelps overcome some impossibilities•Unique decision value requires ½ majority•K decision values allow any partition with 1/(k + 1) nodes to decide13Group Membership ServiceGroup Membership ServiceDef: Keep track of which nodes belong to which groupTraditionally, group membership only maintain a single group•Primary-partition membership services•Corresponds to strong consistencyRecently, partitionable membership services•Still active area of research•Corresponds to optimistic consistencyContinuous consistency:•Allow at most k groups•Again, helps overcome the ½ majority limitation14Continuous Consistency SummaryContinuous Consistency SummaryWAN replication needs dynamically tunable consistencyTradeoff between consistency and performanceHow to design a continuous consistency modelContinuous consistency in other contextNext: Availability15What is Availability ?What is Availability ?No well-accepted availability metric for Internet services“Uptime” metric can be misleading for Internet services•Server may be inaccessible because of network partitionAvailable: “present or ready for immediate use” •From Webster’s Collegiate Dictionary•What does “immediate” mean?•Time-outAvailability = (accepted accesses) / (submitted accesses)•Implicit time-out in the definition16Perform-abilityPerform-abilityUser satisfaction is not binary•What if a partial result is returned before time-out ?•What if the result is sent back after an hour, or a day ?•Availability is related to performancePerformability = reward function (quality and timeliness of result)Determining reward function is hard !17Availability of an Internet ServiceAvailability of an Internet ServiceWe use user-observed availability in our study:Availability = (accepted accesses) / (submitted accesses)Serverclient×2% [Chandra et.al.,USITS’01]reject due to server failure×0.1% [MS press