Cloud computing systems today, whether open-source or used inside companies, are built using a common set of core techniques, algorithms, and design philosophies – all centered around distributed systems. Learn about such fundamental distributed computing "concepts" for cloud computing. Some of these concepts include: clouds, MapReduce, key-value/NoSQL stores, classical distributed algorithms, widely-used distributed algorithms, scalability, trending areas, and much, much more! Know how these systems work from the inside out. Get your hands dirty using these concepts with provided homework exercises. In the programming assignments, implement some of these concepts in template code (programs) provided in the C++ programming language. Prior experience with C++ is required. The course also features interviews with leading researchers and managers, from both industry and academia.
2.5. Virtual Synchrony
Loading...
來自 University of Illinois at Urbana-Champaign 的課程
Cloud Computing Concepts, Part 1
694 個評分
從本節課中
Week 5: Classical Distributed Algorithms
Lesson 1: This module covers how to calculate a distributed snapshot, leveraging causality again to circumvent the synchronization problem. Lesson 2: This lecture teaches how to order multicasts in any distributed system. Algorithms for assigning timestamp tags to multicasts using various flavors of ordering – FIFO, Causal, and Total – are covered. The module also covers virtual synchrony, a paradigm that combines reliable multicasts with membership views. Lesson 3: Consensus is one of the most important problems in a distributed system, enabling multiple machines to agree. This module uses Paxos, one of the most popular consensus solutions used in the industry today. Paxos is not perfect because consensus cannot be solved completely – an optional lecture presents the famous FLP proof of impossibility of consensus.
與講師見面
Indranil GuptaProfessor
Department of Computer Science
[MUSIC]
So in this lecture we're going to look at how to combine a membership protocol or
failure introduction along with a Multicast.
This is often and
very popularly implemented in an abstraction known as virtual synchrony.
Virtual synchrony also known as view synchrony attempts to preserve multicast
ordering and reliability in spite of failures of what happened in the system.
It combines a membership protocol with a multicast protocol.
Systems that implemented virtual synchrony or
view synchrony, such as Isis from Cornell University have been used in
many important scenarios including the New York Stock Exchange,
the French Air Traffic Control System, and the Swiss Stock Exchange.
Virtual synchrony or view synchrony has an important concept known as Views.
Each process maintains a membership list and
you've seen how membership protocols work earlier in the course.
This membership list is called a View.
An update to the membership list is called a View Change.
For instance, if a process joins, this may be reflected in the view and
that would be a View Change.
If a process leaves or
a process fails then those would be reflected in the view as well.
That would be a View Change.
Multiple changes may be made to a view and that would
just count as a single View Change if those changes are made simultaneously.
So for instance.
A process P1 might be added to the view and
simultaneously process P2 might be drop from the view.
That would just be a single view change where both those updates were done
simultaneously.
Virtual synchrony or views synchrony guarantees that all the view
changes are delivered in the same order at all the correct processes in the group.
So for instance if a correct process P1 receives views,
which are somewhat like the following.
The first view has only itself, P1.
The second view has itself along with two other processes, P1, P3.
The next view only has P1 or P2, P3 was dropped.
And the next view has P1, P2 and P4, where P4 was added.
Then any of the correct process also received the same sequence of view changes
after it joins the group.
So, for instance, if you construct P2 and the views it receives,
P2's first view would be P1, P2, P3, because that's when it joins the group.
But after that, its next view would be P1, P2.
It would have to be the same as the next view that P1 got.
And then the third view that P2 reviews would also be the same as
P1's next view which will be P1, P2, P4 over here.
That is the same as P1's, our next view as well.
In other words, as long as you can see only the correct process in the group
of the sequence of view changes that they receive is in fact
the same as all the other current processes in the group.
When the process fails, then you stop considering it.
But as long as the process is alive, all the views that it receives
are in fact in the same order as the other correct process in the system.
Now the times at which the views are delivered at the processes might be
different at different process, but the ordering is the same.
So again, here the insistence is on the ordering of them being the same.
In other words, the views being totally audited in all of the processes, but
they may of course be delivered at different physical times.
And this is why it is somewhat known as virtual synchrony, but
we'll come back to the name later on.
So that's about abuse.
What about the multicasts that are sent out among the processes in the group?
Now a multicast M is said to be delivered in a view V at a process Pi If and
only if Pi receives the view V.
And then before Pi delivers the next view after V, it delivers multicast M.
because in other words multicast M is delivered in between view V and
the next view that follows V.
Then M is said to be delivered in the view V.
In other words, what we are saying is that when M is delivered
view V was the membership list at the process Pi.
Now multisynchronicity requires that the set of multicasts delivered in
a given view is the same set of multicasts at all the correct processes that
are in that view.
This says that suppose the view consists of
to P3 then the set of multicasts received at P1 in that same view
is the same the set of multicasts received P2 in the same view.
In other words, what happens in a view stays in that view.
It does not go outside that view.
Okay, this is a good rule of thumb to remember virtual synchrony by.
He also required the sender of the mutlicast message to believe to that
view otherwise it would make sense for a multicast to be received.
Within a view when the sender is not a part of the view itself.
And what this means is that, if a process Pi does not deliver a multicast M in view
V, while other processes in the view V delivered multicast M in that same view,
V, then Pi will be forcibly removed from the next view delivered.
After we've add these other processes.
So, yo have to go with what he rest of the group is doing otherwise you might be
forcibly removed from that group if you don't satisfy group.
So, let's see a few examples that are both correct from the and also incorrect
form the viewpoint of So here's our first example with process P1, P2, P3, and P4.
The first view that all of them deliver consists of all four processes, so
that's our group.
Then P1 sends out a multicast message M1, P2 sends out a multicast message M2,
P4 sends out a multicast message M3, but P4 crashes after that.
Because P4 crashes, the next view that is delivered at P1, P2, P3, the remaining
members in the group Consists of only P1, P2, P3, and that's fine, okay?
Now the message M1 is delivered in the first view,
which causes all the four processes.
M2 is also delivered in the first view.
M2 is not delivered in P4, but that's fine because P4 crashed anyway.
Now the message M3 from P4 is also delivered at P1, P2, P3 as well as P4 and
it is delivered in the same view that consists of all the four processes.
Okay, so satisfies virtual synchrony.
This particular run over here.
However if I make a small change which is that a P3 delivers the second view
first and only then delivers the multicast n one from p one.
This would not satisfy virtual synchrony because what happens in the view
does not stay in the view.
In other words m1 is delivered by p2 in the earlier view but
delivered at p3 in the second view.
And that does not satisfy virtual synchrony.
This satisfies virtual synchrony, where P3 is forced out of the group, and
only P1 and P2 are left in the group.
And the set of multicast messages of P1 and
P2 received in the old first view are identical.
Okay, this satisfies virtual synchrony.
Here's another example of a route that does not satisfy virtual synchrony.
Why does it not satisfy virtual synchrony?
Well Notice here that we have the modech
as message m2 that is received at process p1 but is not received at process p3.
But p3 was is a part of the next view so
in other words this is a multi pass message m that is not
completely reliably delivered inside the group inside the old view.
Okay so this does not satisfy virtual synchrony.
This satisfies virtual synchrony here because M2 is in fact not delivered at any
of the members in the group in the old view.
It's not delivered at P2 either, and this has virtual synchrony because essentially
M2 as a multicast was never sent out, so never delivered at all in the group.
Does not satisfy what you need here you notice that the multi-cache text message,
m1 and m2 willing to the correct view, and the older view in all across but
m3 is delivered in the next view at process v1 and process v2.
And it's delivered in all view process p3,
because this does not satisfy virtual synchrony.
You might think that moving this view ahead now satisfied both virtual synchrony
because [INAUDIBLE] at all the other processes in the system and
all the current processes but
this [INAUDIBLE] because by the time the semantic [INAUDIBLE] is delivered.
The view does not include the sender p 4 of that multicast message anymore, and
so because p 4 is not part of the second view delivered at the correct processes,
the run that I'm showing here is also
not correct as far as virtual synchrony is concerned.
And finally here is an example where dropped by the system and
it's not able to tolerate any of the processes of the group and
this satisfies of course virtual synchrony because what happens in
the view stays in the view and before it has crashed.
So, virtual synchrony or virtual synchronous systems implement membership
protocols in the form of views, and also multicasts in terms of reliability, and
they want to ensure reliability within each view.
If you want to implement ordering in a virtual synchronous system you can do that
too because ordering is orthogonal to reliability, so
you can have a Virtually synchronous system that implements FIFO.
Or a virtually synchronous system that implements causal ordering, or
one that implements total ordering, or one that has a hybrid ordering scheme.
Now the name virtual synchrony comes about, or came about because it's part of
running on top of an asynchronous network with unpredictable delays and failures.
The order of membership changes and
multicasts that each process sees is the same at all the other processes.
If you use a total ordering protocol, even if it's a hybrid total ordering protocol,
then all the processes see the event in the system
happening in the same order as all the other processes in the system
as long as the processes that you're talking about are the correct processes.
Okay, so instead of landing on top of an asynchronous
network the view the processes behave are able to behave as if they're
running on top of a synchronous system where all the membership changes and
all the multi-cast messages are delivered in the same order.
But then actually the question should arise whether or not such an abstraction
could be used to implement a protocol that solves the consensus problem.
And the answer to this is no because virtually synchronous systems are still
susceptible to what is known as partitioning.
This may happen due to inaccurate failure detections because a process may be
mistakenly detected they will be removed from the group
Also processes may be forcibly removed from groups.
So an example of partitioning is shown on this slide, where initially,
all the four processes, P1, P2, P3, and P4 are a part of the view.
But subsequently, even though P4 is the only one that crashes, the view has become
partitioned where P1 considers only itself to be a part of the view.
And P2 and P3 are different view which consider only themselves to be a part
of the membership list.
So P1 is partitioned away from P23, and such partitions can happen in a virtually
synchronous system and this is the feature that prevents socially synchronous or
view synchronous systems from implementing consensus on top of them.
So, that wraps of our discussion of Multicast.
Multicast is an important building block for cloud computing systems that has been
so far many use to it systems for many decades.
Depending on the application need,
you can implement either a flavor of Multicast Ordering.
As far as your application requires level Multicast Ordering.
If you don't care about efficiency then you can implement
the Multicast Ordering Reliability.
Protocol that we saw or there are other radians of
multicache library protocols that we have discussed as well in this course.
And if you need something really,
really strong then you can implement virtual synchrony or real synchrony.
In fact there are many real systems out there that use these forms of multicast
in terms of their ordering that are and even a devotedly synchronize of framework.
[MUSIC]
