1CS514: Intermediate Course in Operating SystemsProfessor Ken BirmanVivek Vishnumurthy: TAReminder: Group Communication Terminology: group create, view, join with state transfer, multicast, client-to-group communication This is the “dynamic” membership model: processes come & gopqrstuRecipe for a group communication system Back one pie shellBuild a service that can track group membership and report “view changes” Prepare 2 cups of basic pie fillingDevelop a simple fault-tolerant multicast protocol Add flavoring of your choiceExtend the multicast protocol to provide desired delivery ordering guarantees Fill pie shell, chill, and serveDesign an end-user “API” or “toolkit”. Clients will “serve themselves”, with various goals…Role of GMS We’ll add a new system service to our distributed system, like the Internet DNS but with a new role Its job is to track membership of groups To join a group a process will ask the GMS The GMS will also monitor members and can use this to drop them from a group And it will report membership changesGroup picture… with GMSpqrstuGMSP requests: I wish to join or create group “X”.GMS responds: Group X created with you as the only memberT to GMS: What is current membership for group X?GMS to T: X = {p} r joins…GMS notices that q has failed (or q decides to leave)Q joins, now X = {p,q}. Since p is the oldest prior member, it does a state transfer to qGroup membership service Runs on some sensible place, like the server hosting your DNS Takes as input: Process “join” events Process “leave” events Apparent failures Output: Membership views for group(s) to which those processes belong Seen by the protocol “library” that the group members are using for communication support2Issues? The service itselfneeds to be fault-tolerant Otherwise our entire system could be crippled by a single failure! So we’ll run two or three copies of it Hence Group Membership Service (GMS) must run some form of protocol (GMP)Group picture… with GMSpqrstGMSGroup picture… with GMSpqrstGMS0GMS1GMS2Let’s start by focusing on how GMS tracks its ownmembership. Since it can’t just ask the GMS to do this it needs to have a special protocol for this purpose. But only the GMS runs this special protocol, since other processes just rely on the GMS to do this jobIn fact it will end up using those reliable multicast protocols to replicate membership information for other groups that rely on itThe GMS is a group too. We’ll build it first and then will use it when building reliable multicast protocols.Approach We’ll assume that GMS has members {p,q,r} at time t Designate the “oldest” of these as the protocol “leader” To initiate a change in GMS membership, leader will run the GMP Others can’t run the GMP; they report events to the leaderGMP example Example: Initially, GMS consists of {p,q,r} Then q is believed to have crashedpqrFailure detection: may make mistakes Recall that failures are hard to distinguish from network delay So we accept risk of mistake If p is running a protocol to exclude q because “q has failed”, all processes that hear from p will cut channels to q Avoids “messages from the dead” q must rejoin to participate in GMS again3Basic GMP Someone reports that “q has failed” Leader (process p) runs a 2-phase commit protocol Announces a “proposed new GMS view” Excludes q, or might add some members who are joining, or could do both at once Waits until a majority of members of current view have voted “ok” Then commits the changeGMP example Proposes new view: {p,r} [-q] Needs majority consent: p itself, plus one more (“current” view had 3 members) Can add members at the same timepqrProposed V1= {p,r}V0= {p,q,r}OKCommit V1V1= {p,r}Special concerns? What if someone doesn’t respond? P can tolerate failures of a minority of members of the current view New first-round “overlaps” its commit: “Commit that q has left. Propose add s and drop r” P must wait if it can’t contact a majority Avoids risk of partitioningWhat if leader fails? Here we do a 3-phase protocol New leader identifies itself based on age ranking (oldest surviving process) It runs an inquiry phase “The adored leader has died. Did he say anything to you before passing away?” Note that this causes participants to cut connections to the adored previous leader Then run normal 2-phase protocol but “terminate”any interrupted view changes leader had initiatedGMP example New leader first sends an inquiry Then proposes new view: {r,s} [-p] Needs majority consent: q itself, plus one more (“current” view had 3 members) Again, can add members at the same timepqrProposed V1= {r,s}V0= {p,q,r}OKCommit V1V1= {r,s}Inquire [-p]OK: nothing was pendingProperties of GMP We end up with a single service shared by the entire system In fact every process can participate But more often we just designate a few processes and they run the GMP Typically the GMS runs the GMP and also uses replicated data to track membership of other groups4Use of GMS A process t, not in the GMS, wants to join group “Upson309_status” It sends a request to the GMS GMS updates the “membership of group Upson309_status” to add t Reports the new view to the current members of the group, and to t Begins to monitor t’s healthProcesses t and u “using” a GMS The GMS contains p, q, r (and later, s) Processes t and u want to form some other group, but use the GMS to manage membership on their behalfpqrstuWe have our pie shell Now we’ve got a group membership service that reports identical views to all members, tracks health Can we build a reliable multicast?Unreliable multicast Suppose that to send a multicast, a process just uses an unreliable protocol Perhaps IP multicast Perhaps UDP point-to-point Perhaps TCP … some messages might get dropped. If so it eventually finds out and resends them (various options for how to do it)Concerns if sender crashes Perhaps it sent some message and only one process has seen it We would prefer to ensure that All receivers, in “current view” Receive any messages that any receiver receives (unless the sender and all receivers crash, erasing evidence…)An
View Full Document