CS514 Intermediate Course in Operating Systems Professor Ken Birman Vivek Vishnumurthy TA Recap Our recipe for group communication Group membership We solved this by building a fault tolerant group membership service Everyone who uses it sees the same group views in the same order When it makes a mistake about a failure we just terminate the unfortunate victim Fault tolerant view synchronous multicast Ordering mechanisms Ordering The missing element Our fault tolerant protocol was FIFO ordered messages from a single sender are delivered in the order they were sent even if someone crashes View synchronous everyone receives a given message in the same group view This is the protocol we called fbcast But we identified other options cbcast If cbcast a cbcast b deliver a before b at common destinations abcast Even if a and b are concurrent deliver in some agreed order at common destinations gbcast Deliver this message like a new group view agreed order w r t multicasts of all other flavors Can we implement them First look at cbcast Recall that this property was like fbcast The issue concerns the meaning of a single sender With fbcast a single sender is a single process With cbcast we think about a single causal thread of events that can span many processes For example p asks q to send a then asks r to send b So a b but a happens at q and b happens at r Single updater If p is the only update source the need is a bit like the TCP fifo ordering 1 p 2 3 4 r s t fbcast is a good choice for this case Causally ordered updates Events occur on a causal thread but multicasts have different senders 2 p r s t 5 3 1 4 Reminder Who needs it The issue is that with Web Services and CORBA you might not even know that you are invoking a remote object If it does a multicast for you that event seems like something you did but may have been issued by some other process If we use cbcast messages will be delivered in the order they were sent Causally ordered updates Events occur on a causal thread Perhaps p invoked Now we re a back T gets in another request This one butremote multicasts have different operation process p The came remote from p indirectly via s but implemented operation by some has the returned idea The process T finishes corresponding whatever theis exactly the same P is senders other object here and p resumes really running a single causal thread to that object is involved t and and 2operation 5 computing thattoweaves through the system while doing sendsthe a response operation the various objects and hence it sent invoker a multicast Now visiting t waits for 3 requests the processes that own them other p r s t 1 4 How to implement it Within a single group the easiest option is to include a vector timestamp in the header of the message Only increment the VT when sending Send these labeled messages with fbcast Delay a received message if a causally prior message hasn t been seen yet Causally ordered updates p r s t Example messages from p and s arrive out of order at t VT b 1 0 0 1 c is early VT c 1 0 1 1 but VT t 0 0 0 1 clearly we are VT c When b one arrives we can deliver missing message from s 1 0 1 1 both it and message c in order VT a 0 0 0 1 Causally ordered updates This works even with multiple causal threads 2 p 5 1 r 3 s t 1 4 2 Concurrent messages might be delivered to different receivers in different orders Example green 4 and red 1 are concurrent Causally ordered updates Sorting based on vector timestamp 1 0 0 1 p 1 1 1 1 2 1 1 3 r s t 0 0 0 1 1 0 1 1 1 0 1 2 1 1 1 3 In this run everything can be delivered immediately on arrival Causally ordered updates Suppose p s message 1 0 0 1 is delayed 1 0 0 1 p 1 1 1 1 2 1 1 3 r s t 0 0 0 1 1 0 1 1 1 0 1 2 1 1 1 3 When t receives message 1 0 1 1 t can see that one message from p is late and can delay deliver of s s message until p s prior message arrives Other uses for cbcast The protocol is very helpful in systems that use locking for synchronization Gaining a lock gives some process mutual exclusion Then it can send updates to the locked variable or replicated data Cbcast will maintain the update order Cost of cbcast This protocol is very cheap It requires one phase to get the data from the sender to the receiver Receiver can deliver instantly Same cost as an IP multicast or a set of UDP sends Imposes a small header and a small garbage collection overhead Nobody is likely to notice And we can often omit or compress the header Better and better Suppose some process sends a bunch of small updates using fbcast or cbcast Pack them into a single bigger message Benefit message costs are dominated by the system call and almost unrelated to size at least until we get big enough to require fragmentation Causally ordered updates A bursty application Can pack into one large message and amortize overheads p r s t Screaming performance This type of packing can give incredible performance Sender is able to send a small message then move on to the next task like sending a TCP message without waiting for it to get through Sender s platform packs them together Receiver unpacks on arrival Can send hundreds of thousands of asynchronous updates per second in this mode Snapshots with cbcast Send two rounds of cbcast Round 1 Start a snapshot Round 2 Done Receivers make a checkpoint And they start recording incoming messages Then say OK They send back their checkpoints and logs Thought question why does this work What about abcast Abcast puts messages into a single agreed upon order even if two multicasts are sent concurrently fbcast and cbcast can deliver messages in different orders at different receivers Notice that this disordered delivery wouldn t matter in the cases we discussed Many options Literature has at least a dozen abcast protocols and some are causal too Easiest just uses a token To send an abcast either pass it to the token holder or request the token Token holder can increment a counter and put it in header of message Only need the counter if token can move Delay a message until it can be delivered in order What about gbcast This is a very costly protocol Must be ordered wrt all other event types including fbcast cbcast abcast view changes other gbcasts Used to change a security key or even modify the protocol stack at runtime Like changing the engines on …
View Full Document
Unlocking...