Virtual SynchronyA motivating exampleRequirements for a distributed system (or a replicated service)Requirements for a distributed system (or a replicated service)System as a set of groupsA process groupA model of a dynamic process groupThe lifecycle of a member (a replica)The Idea (Roughly)Slide 10Why another approach, though?A special class of applicationsDistributed trading systemWhat’s special about these systems?Differences (in a Nutshell)Back to virtual synchronyA process group: joining / leavingSlide 18A process group: hadling failuresCausal delivery and vector clocksWhat’s great about fbcast / cbcast ?Asynchronous pipeliningWhat’s to be careful with ?Why use causality?A migrating thread and FIFO analogySlide 26Causal vs. total orderingTotal ordering: atomic, synchronousWhy total ordering?Implementing totally ordered multicastAtomicity of failuresWhy atomicity of failures?Atomicity: message flushingA multi-phase failure-atomic protocolSimple toolsSimple replication: state machineUpdates with token-style lockingSlide 38Multiple locks on unrelated dataReplicated servicesSlide 41Other types of toolsComplaints (Cheriton / Skeen)At what level to apply causality?Slide 45OverheadsSlide 47Slide 48ConclusionsVirtual SynchronyKrzysztof [email protected] motivating exampleGENERALSSENSORSWEAPONnotificationsordersDANGERdetectionwell-coordinated response?????decisionmadeRequirements for a distributed system (or a replicated service)Consistent views across componentsE.g. vice-generals see the same events as the chief generalAgreement on what messages have been received or deliveredE.g. each general has same view of the world (consistent state)Replicas of the distributed service do not divergeE.g. everyone should have same view of membershipIf a component is unavailable, all others decide up or down togetherRequirements for a distributed system (or a replicated service)Consistent actionsE.g. generals don’t contradict each other (don’t issue conflicting orders)A single service may need to respond to a single requestResponses to independent requests may need to be consistentBut: Consistent  Same (same actions  determinism  no fault tolerance)System as a set of groupsclient-server groupspeer groupdiffusion groupmulticastinga decisioneventA process groupA notion of process groupMembers know each other, cooperateSuspected failures  group restructures itself, consistentlyA failed node is excluded, eventually learns of its failureA recovered node rejoinsA group maintains a consistent common stateConsistency refers only to membersMembership is a problem on its own... but it CAN be solvedA model of a dynamic process groupCRASHconsistent statemembership viewsJOINRECOVERconsistent statestate transfersABCDEFBCEThe lifecycle of a member (a replica)alive,but not ingroupdead or suspected to be deadin groupprocessingrequestsjointransfer state hereunjoinfail or just unreachablecome upassumed tabula rasa all information = lostThe Idea (Roughly)Take some membership protocol, or an external serviceGuarantee consistency in inductive mannerStart in an identical replicated stateApply any changesAtomically, that is either everywhere or nowhereIn the exact same order at all replicasConsistency of all actions / responses comes as a resultSame events seen:Rely on ordering + atomicity of failures and message deliveryThe Idea (Roughly)We achieve it by the following primitives:Lower-levelCreate / join / leave a groupMulticasting: FBCAST, CBCAST / ABCAST (the "CATOCS")Higher-levelDownload current state from the existing active replicasRequest / release locks (read-only / read-write)UpdateRead (locally)Why another approach, though?We have the whole range of other toolsTransactions: ACID; one-copy serializability with durabilityPaxos, Chandra-Toueg (FLP-syle consensus schemes)All kinds of locking schemes, e.g. two-phase locking (2PL)Virtual Synchrony is a point in the space of solutionsWhy are other tools not perfectSome are very slow: lots of messages, roundtrip latenciesSome limit asynchrony (e.g. transactions at commit time)Have us pay very high cost for freatures we may not needA special class of applicationsCommand / ControlJoint Battlespace Infosphere, telecommunications, Distribution / processing / filtering data streamsTrading system, air traffic control system, stock exchange, real-time data for banking, risk-managementReal-Time SystemsShop floor process control, medical decision support, power gridWhat do they have in common:A distributed, but coordinated processing and controlHighly-efficient, pipelined distributed data processingDistributed trading systemPricing DB’sHistorical DataAnalyticsCurrent PricingMarketDataFeedsLong-Haul WAN SpoolerTokyo, London, Zurich, ...Trader Clients1.2.3.Availability for historical dataLoad balancing and consistentmessage delivery for price distributionParallel execution for analyticsWhat’s special about these systems?Need high performance: we must weaken consistencyData is of different nature: more dynamicMore relevant online, in contextStoring it persistently often doesn’t make that much senseCommunication-orientedOnline progress: nobody cares about faulty nodesFaulty nodes can be rebootedRebooted nodes are just spare replicas in the common poolDifferences (in a Nutshell)Databases Command / Controlrelatively independent programs closely cooperating programs......organized into process groups consistent data;(external) strong consistencyweakened consistency; instead focus on making online progresspersistency, durable operations mostly replicated state and control infoone-copy serializability serializability w/o durability (nobody cares)atomicity of groups of operations atomicity of messages + causalityheavy-weight mechanisms; slow lightweight, stress on responsivenessrelationships in data relationships between actions and in the sequences of messagesmulti-phase protocols, ACKs etc. preferably one-way, pipelined processingBack to virtual synchronyOur plan:Group membershipOrdered multicast within group membership viewsDelivery of new views synchronized with multicastHigher-level primitivesA process group: joining / leavingABCDV1 = {A,B,C}request to joingroup membership protocolsending a new viewrequest to leaveV2 = {A,B,C,D}V3 =