iKen BirmanCornell University. CS5410 Fall 2008. Virtual Synchronyy A powerful programming model! y Key idea: equate “group” with “data abstraction”y Each group implements some objecty An application can belong to many groupsVi l h i h id i dlyVirtual synchrony is the associated consistency model:y Process groups with state transfer, automated fault detection and membership reportingdetection and membership reportingy Ordered reliable multicast, in several flavorsy Extremely good performancey g py Assumes that the membership oracle is availableWhy “virtual” synchrony?y What would a synchronous execution look like?y In what ways is a “virtual” synchrony execution not the hisame thing?A synchronous ex ecutionpqGMSqrsstuu With true synchrony executions run in genuine lock-stepgenuine lockstep.  GMS treated as a membership oracleVirtual Synchrony at a glancepqGMSqrsstuy With virtual synchrony executions only look “lock step” to the applicationulock step to the applicationVirtual Synchrony at a glancepqGMSqrsstuu We use the weakest (hence fastest) form of communication possiblecommunication possiblef/c/abcast, flush...y Last week we saw how the GMS could support protocols that have various forms of orderingO i i h “i id ” h GMSyOne option is to run them “inside” the GMSy But suppose that we use the GMS to manage membership of processes other than the GMS serversmembership of processes other than the GMS serversy This is easy do to! Our protocols didn’t “need” to run inside the GMS per‐se!y Group runs “outboard” and protocols send messages directly between the membersGMS ild l if h i hyGMS involved only if the group view changesChances to “weaken” orderingy For example, imagine a data replication object with variables “inside”, and suppose that any conflicting updates are synchronized using some conflicting updates are synchronized using some form of lockingy Multicast sender will have mutual exclusiony Hence simply because we used locks, cbcast delivers conflicting updates in order they were performed!yIf our system ever does see concurrent multicasts yIf our system ever does see concurrent multicasts… they must not have conflicted. So it won’ t matter if cbcast delivers them in different orders at different recipients!Causally ordered updatesy Each thread corresponds to a different lock2GMSpr251st1342y The “group” is best visualized as a kind of object that has a replica associated with each proc essp py Within it, red “events” never conflict with blue!Strong to weak…y Definition: a multicast is safe, also called dynamically uniform, if:If b dli i h li i l yIf any group member delivers it to the application layer, then every group member will do so, unless it failsyAnd this is true even if the first delive ries are in And this is true even if the first delive ries are in processes that faily Our fbcast and cbcast and abcast protocols from last week were not safe! y They delivered “early” and hence if the first processes to deliver copies failed the event might be lostdeliver copies failed, the event might be lostStrong to weaky A safe/dynamically uniform protocol needs two phasesy Phase 1: Deliver a copy to at least a majority of the b f th t i Rii t kldmembers of the current view. Recipients acknowledgey … but instead of delivering to the application layer, they retain these copies in bufferspy Phase 2: Sender dete cts that a majority have a copy, tells recipients that now they can delivery Much slower… but now a failure can’t erase a multicast.y Same ordering options existIn gener al?y Start by thinking in terms of safe abcast (== gbcast!)y Then replace “safe” (dynamic uniformity) protocols ih dd li h iblwith a standard multicast when possibley Weaken ordering, replacing abcast with cbcastWk li bih fbyWeaken even more, replacing cbcast with fbcastMore tricks of the tradey Multicast primitives usually can support replies!y No replies: the multicast is asynchronousy One reply: like an anycast –all receiv e, but any one reply will suffice (first one wins if several reply…)yC replies: for a constant C (rarely supported)yC replies: for a constant C (rarely supported)y ALL replies: wait for every group member to replyy Failure: treated as a “null reply”y Want speed? Ask for as few replies as possible!Why “virtual” synchrony?y The user sees what looks like a synchronous executiony Simplifies the developer’s tasky But the actual execution is rather concurrent and asynchronousyMaximizes performanceyMaximizes performancey Reduces risk that lock‐step execution will trigger correlated failuresCorrelated failuresy Observation: virtual synchrony makes these less likely!yRecall that many programs are buggyRecall that many programs are buggyy Often these are Heisenbugs (order sensitive)y With lock‐step execution each group member sees group eents in identical ordergroup events in identical ordery So all die in unisonyWith virtual synchrony orders differyyy So an order‐sensitive bug might only kill one group member!Programming with groupsy Many systems just have one groupy E.g. replicated bank serversCl t ii hi hl li bl yCluster mimics one highly reliable servery But we can also use groups at finer granularityyEg to replicate a shared data structureyE.g. to replicate a shared data structurey Now one process might belong to many groupsy A further reason that different processes might see p gdifferent inputs and event ordersEmbedding groups into “tools”y We can design a groups API:y pg_join(), pg_leave (), cbcast()…y But we can also use groups to build other higher level mechanismsyDistributed algorithms like snapshotyDistributed algorithms, like snapshoty Fault‐tolerant request executionyPublish‐subscribePublishsubscribeDistributed algorithmsy Processes that might participate join an appropriate groupN h i i il ld li lyNow the group view gives a simple leader election ruley Everyone sees the same members, in the same order, ranked by when they joinedranked by when they joinedy Leader can be, e.g., the “oldest” processDistributed algorithmsy A group can easily solve consensusy Leader multicasts: “what’s your input”?yAll reply: “Mine is 0. Mine is 1”y Initiator picks the most common value and multicasts that: the “decision value”that: the