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.1. Multicast Ordering
Loading...
来自 University of Illinois at Urbana-Champaign 的课程
Cloud Computing Concepts, Part 1
594 个评分
从本节课中
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
Hi there.
In this, uh, series of lectures,
uh, we'll be discussing
the distributed computing problem known as multicast,
which is very widely used as a building block
in, uh, many of the cloud computing systems today.
Uh, in this lecture today
we'll be discussing the ordering property of, uh, multicast.
So multicast, again, in a nutshell,
uh, is a message that needs to be sent out
in a group of, uh, processes.
Um, uh, these processes are running at internet-based hosts.
Uh, for instance, here I have a group of processes,
each denoted by a circle.
A-a red circle, a red process, has some piece of information
that needs to be sent out to all the other processes
in that, uh, group.
Uh, this is only one multicast message.
There might be multiple, uh, multicast messages
that are being sent out by that sender one after another
uh, and also multiple senders in the group
might be, uh, trying to send multicast messages,
uh, to the other processes in the group.
So, uh, multicast in a nutshell is a message sent to a group
of, uh, processes, a selected group.
A broadcast, on the other hand,
is a message that is sent to all the processes anywhere,
uh, in the system and in fact anywhere in the world.
Broadcasts are also very widely used,
um, uh, but of course broadcasts can be pretty expensive,
uh, because, uh, processes that don't, uh, really,
uh, have any interest in the message
might also receive the multicast message
or the broadcast message.
A unicast message is, uh, the most common kind of message
that we have seen, uh, so far in this course.
Essentially it's a point-to-point message;
there is one sender process and one receiver process.
Uh, in terms of, uh, uh, this terminology, the multicast
has, uh, one sender and, uh, multiple receivers per message.
The broadcast has one sender
and everyone else as a receiver for that one message.
So here in this lecture we'll focus on, uh, multicasts only,
which are messages sent out to a group of processes.
So who uses the multicast?
It's a widely used building block
by many cloud computing systems.
For instance, key value stores like Cassandra,
which are storage systems, and database systems,
use multicast internally.
For instance, a given key
might have multiple replica servers
which are replicating the values for that key.
So in that case, uh, the writes and reads that are sent
to that key from, uh, any client will then be multicast
inside the group so that all the replicas are up to date
and reflect the same values
for the key at any point of time.
You don't want to send the values for that key
to other servers beyond the replica group
because they are not interested in that particular,
uh, key itself.
Also, these systems use membership information, uh,
such as, uh, gossip-style,
uh, membership, uh, protocols in these systems,
and essentially, uh, membership, uh, information
requires information about joins, leaves and failures
of processes to be multicast out
within a group of servers
that are running that storage system.
Uh, multicasts are also used in user facing scenarios,
so for instance online scoreboards of sporting events
such as ESPN, French Open tennis the FIFA World Cup,
essentially have each of the clients, uh,
be subscribed to certain topics,
and essentially whenever there is an update for a topic,
such as an update to a score for a match,
that update is multicast out to all the clients,
all the browsers out there in the world
that are interested in this particular update.
So that's a multicast being used in a user, uh, facing scenario.
Multicast is also used in
the floor of, uh, stock exchanges
and air traffic control systems.
For instance, on the floor of a stock exchange,
the group might be the set of broker computers,
and whenever there is a trade on any one of the broker computers,
it's then sent out the other broker computers on the floor.
This ensures all the broker computers are up to date
at all points of time and are reflecting the latest updates
and stock trades on the floor.
Multicast is also used in high-frequency trading
among the servers
that are trying to do high-frequency trading,
and here it's fairly important for the multicasts to be fast,
uh, as well as reliable as well.
In the air traffic control system,
all the air traffic controllers are seeing a picture of the sky,
and you want all the, hm, pictures
to be consistent with each other.
You don't want one air traffic controller,
uh, seeing a slightly stale or outdated picture,
and so any update done
by one air traffic controller's computer is then multicast out
to the group of other air traffic controllers' computers.
So you see two things, eh, emerging from here.
One is you need reliable multicast;
you want all the processes
in the group to receive the multicast.
And the second one is you need to worry about ordering;
you want, uh, all the multicasts to be received,
uh, in the same somewhat consistent order
at all the processes in the group.
So let's look at the FIFO ordering first.
Uh, in FIFO ordering,
essentially multicasts from each sender
are received in, uh, the same order that they are sent
at all receivers.
This means that if two multicasts are sent
by, uh, these same sender, they're of course sent
in an order depending on that senders um, uh, timeline
and the sender's clock,
and they need to be delivered in exactly that order
at all the receivers in the group.
However, if two multicasts are from different senders,
then we don't really care about
which order they're delivered in.
Uh, some multicasts, uh, some processes might deliver
those two multicasts from different senders in one order,
and, uh, other receivers might deliver them
in the opposite order,
and that's fine as far as FIFO ordering is concerned.
So a little bit more formally, if a correct process,
uh, issues or sends a-a multicast,
uh, m to a group g,
uh, and then sends a multicast m' to the same group g,
then every correct process that delivers,
uh, the second message m' would already have delivered m.
In other words, you are saying that, um, you deliver m'
only after you have delivered m.
And notice that here we're talking about correct processes,
which means that we're talking about, uh, non-faulty processes.
This accounts for, uh, failures, if processes fail,
then we don't necessarily know what they did,
and so we don't want to worry about them.
We a, uh, we only want to make sure
that processes that have not failed,
uh, follow, uh, the particular, uh, ordering guarantee
that we are trying to provide.
So as an example, here is a timeline.
Again, here we have four processes; P1, P2, P3, P4.
Time runs from left to right,
and you notice that there are multiple multicasts
being sent out, so process P1 sends out multicast,
uh, 1 over here, shown as, uh, M1:1.
Process P1 also sends out a second multicast, M1:2.
Uh, process P3 sends out a multicast M3:1.
And so you'll notice here that because M1:1 and M1:2
are multicasts sent by processes-process P1,
which is the sender, in that order,
they need to be delivered in exactly that order
at all the recipient processes.
So P2 delivers M1:1 first, uh,
and only then does it deliver M1:2.
Similarly, P3 delivers M1:1 first,
and only then does it deliver M1:2.
Similarly for P4 as well.
However, as far as M1:2, sent by process P1
and M3:1 sent by process P3 are concerned,
they are sent by different senders,
so FIFO doesn't worry about them.
In fact, they can be delivered in opposite orders
at, uh, different, uh, process.
So P2, for instance, delivers M3:1 first,
while P4 delivers M1:2 first, and that's fine.
This still obeys FIFO ordering
because we are only bothered about, uh, the messages
that originate from the same sender.
Here, if, uh, P3 had sent a second message M3:2,
say over here,
then that should have been delivered, uh, after M3:1
at all the recipient processes.
So let's look at the next flavor,
which is known as causal ordering.
Uh, this is an extension of, uh, FIFO ordering.
Uh, in this, um, kind of ordering,
multicasts whose send events are causally related
must be received in the same causality-obeying order
at all receivers.
What this is trying to tell you is that if two multicast sends
are, uh, related in the-by a causal path,
so if the multicast send of one message m,
uh, causally happened before the multicast,
uh, uh, the send of the multicast mech-message m',
uh, then m must be delivered before m' at all receivers.
If two message sends, m and m', are not causally related,
meaning that their send events do not have a causal path
between them, then, well, all bets are off,
and, uh, it's not necessarily required
that their multicasts be delivered in the same order.
They can in fact be flipped at different processes.
Formally, uh, if a multicast message m is sent to a group g,
and the multicast send event causally happens before,
this is Lamport's happens-before relationship over here,
shown by the horizontal arrow,
if that causally happens before the multicast send event
of another message m', a multicast message m',
then any correct process that delivers m'
would already have delivered m.
In other words, you deliver m first,
and only then can you deliver m'.
So let's look at an example again with our timeline
of four processes P1 through P4.
This is a slightly different set of multicast messages
from the earlier example you saw.
Here, process P1 sends out a multicast message M1:1,
uh, which is received by process P2 along with other receivers,
but then subsequently P2 sends out a multicast message M2:1.
Now, because the multicast message M1:1 was received by P2
before it sent out its multicast message M2:1,
the send event of M1:1 happens before the send event of M2:1,
and so we want those two multicasts to be received
in the same order at all the other processes
in, uh, the system.
Similarly, M1:1 is received by P3 before P3 sends outs it-
sends out its first multicast M3:1,
and so M1:1 happens before M3:1,
and we wanna make sure
that those two messages are delivered
in that causality-obeying order at all the recipients.
Of course, M3:1 happens before M3:2
because, uh, causality implo-implies FIFO ordering,
and so these messages M3:1 and M3:2 are also delivered
in that same order at all receivers, okay?
So that-that obeys FIFO ordering,
and since M1:1 happens before M3:1,
and transitively M1:1 happens before M3:2,
we want the delivery order to be, uh, obeying that ordering
which is M1:1 first, then M3:1, and then M3:2.
You can verify for yourself that this ordering
is in fact, uh, obeyed by-at all the processes
in this example.
Now let's look at two messages here: M2:1 sent by process P2,
and M3:1 sent by process P3.
There is no causal path in between these two send events,
so these two send events are in fact, uh, concurrent events,
and so their delivery, uh, may be in different orders
at different processes.
So for instance, P1 delivers M2:1 first, while P4 delivers
M3:1 first, and only then M2:1.
And this is fine; this obeys causal-causal ordering,
because concurrent send events may be ordered in any, uh, order
at different recipients.
The only thing that you're trying to guarantee here is that
if two send events are causally related,
then they are in fact delivered
in the causality-obeying- obeying order at all recipients.
So let's compare a little bit, uh, the causal ordering
that we just saw with the FIFO ordering which we saw before.
Causal ordering that is satisfied by multicast protocol
implies that that multicast protocol
also satisfies FIFO ordering.
Why is this true?
Well, um, consider a multicast protocol
that satisfies causal ordering.
If two multicasts, M and M' are sent
by the same-same sender process P,
and M was sent before M', then, um, it's true
that M happened before M', because time progresses
only linearly at, uh, the sender process, uh, P,
and so because the multicast protocol
already satisfies causal ordering,
it must be true that M is delivered first,
and only then is M' delivered.
Okay, this means that a multicast protocol
that implements causal ordering
will automatically obey FIFO ordering.
However, the reverse is not true.
If I give you a multicast protocol
that obeys FIFO ordering,
it may not obey causal ordering,
because FIFO ordering does not worry about,
uh, multicast sends, uh-uh, from different, uh, processes,
even if they are causally related.
Why prefer causal ordering at all?
Uh, well, causal ordering is pretty intuitive,
and therefore it is
actually used in several, uh, scenarios, uh,
whether multicast or not.
For instance, you might have a group of, uh, friends
on a social network, one of the more popular social networks,
choose your own.
Uh, if a friend sees your message m,
say you post a message m,
uh, and, uh, your friend then posts a response,
uh, comment m' to it,
you want your other friends to be seeing m,
uh, before they see m'.
If they see m' first before they see m,
then the comment doesn't necessarily make sense to them,
because it is a-it is in the context of the message m.
Uh, so, uh, before-because m happens before m',
you want their delivery orders at the other, uh, processes
in the group-which in this case are your other friends,
uh, or rather your common friends
between you and the posting other friend,
uh, to see, um, m first and only then m'.
However, if, uh, two friends, uh, post m" and n" concurrently,
and these are concurrent send events,
then they can be seen in any order,
and that's still fine.
A variety of systems implement,
uh, this kind of causal ordering.
This includes social networks, uh, bulletin boards,
uh, including, uh, news groups and, um, uh, posts
on the news servers,
uh, and comments on websites, and so on and so forth.
Finally we come to our third flavor of ordering,
which is total ordering.
Total ordering is sometimes called as atomic, uh, broadcast.
Unlike FIFO and causal ordering,
uh, the definition of this total ordering
doesn't necessarily pay any attention
to the order in which multicasts are sent.
What it is into-instead trying to guarantee
is that all the receivers
receive all the multicasts in the same order.
Uh, notice that I'm not saying anything about the order
in which they are sent.
All I am saying is that if a correct process P
delivers the message m- multicast message m,
before another multicast message m',
independent of what the senders did,
then any other correct process in the system P',
uh, that delivers m' would already have delivered m.
In other words, what we are saying is that if any process,
uh, delivers message m before m',
then every other correct process in the group
will also be, uh, delivering message m before, uh, m'.
So here is an example of, uh, total ordering.
Again, this is, uh, the same example from before.
Here, uh, we wanna make sure that all the multicasts,
uh, sent here,
the four multicasts that are sent in this particular run,
are delivered in the same order at all the processes.
So for instance, at P1, M1:1 is delivered first,
then M2:1 is delivered,
then M3:1 is delivered,
and then M3:2 is delivered.
Now we we need to make sure that all the other processes
deliver these four multicast in exactly that order,
so M1:1 first, then M2:1, then M3:1, and then M3:2.
Let's look at P2.
P2 delivers M1:1 first, then M2:1, then M3:1, and then M3:2.
So far so good.
Then, uh, P3 delivers M1:1 first,
then it needs to deliver M2:1,
but, uh, M2:1 has not yet been received
when M3:1 is being sent out,
so the, uh, delivery of M3:1 at P3 itself
needs to wait until M2:1 is delivered,
and then M3:1 can be delivered,
and finally M3:2 is delivered.
This delivery order at P3 obeys, uh, the total ordering.
Finally, at P4, M1:1 is delivered first,
then M2:1 is delivered,
then M3:1, and finally M3:2 is delivered,
and this satisfies total ordering
because all the other processes,
ah, in-all the processes in the group
deliver their multicasts,
ah, deliver all the multicasts in the same order,
uh, as all the other processes in the group.
Now this of course means just that some processes like P3
may need to d-delay the delivery of, uh, the multicast messages,
perhaps even at the sending process
of that particular multicast.
Okay, so those are the three flavors we have seen.
Uh, those are not the only three flavors possible.
Um, since FIFO and causal ordering, uh, uh,
look at this, uh, the sending order,
and total ordering looks at the receiving order,
they are orthogonal,
and so we have the possibility of hybrid protocols.
You could have a FIFO total hybrid, uh, protocol
for multicast ordering,
which satisfies both FIFO ordering and total ordering.
In other words, this protocol would give you a total order
for multicast messages that obeys the, uh,
FIFO ordering ordering of multicast sends.
A causal-total hybrid protocol is also possible
for multicast ordering,
which obeys both, uh, causal as well as total ordering.
This means that you have a total ordering
of, uh, multicast messages
which, uh, also obeys the, uh, causality.
Notice that causal-total ordering would mean, uh,
that um, even concurrent events, um, concurrent multicast sends,
are in fact ordered the same way
at all the processes in the group,
uh, but because they are concurrent,
we don't really care which order it is.
Any order is fine as long as it's consistent.
Uh, multicast sends that are causally related are of course,
uh, delivered in the causality-obeying order
at all the processes in the group.
Uh, so we have discussed so far what the ordering mean,
what the flavors are.
Uh, in the next lecture we'll discuss how to im-
how to implement each of these, uh, orderings.
