2.3. NTP

Loading...

來自 University of Illinois at Urbana-Champaign 的課程

Cloud Computing Concepts, Part 1

578 個評分

University of Illinois at Urbana-Champaign

Cloud Computing Concepts, Part 1

578 個評分

課程 1（共 6 門，Specialization Cloud Computing）

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.

從本節課中

Week 4: Key-Value Stores, Time, and Ordering

Lesson 1: This module motivates and teaches the design of key-value/NoSQL storage/database systems. We cover the design of two major industry systems: Apache Cassandra and HBase. We also cover the famous CAP theorem. Lesson 2: Distributed systems are asynchronous, which makes clocks at different machines hard to synchronize. This module first covers various clock synchronization algorithms, and then covers ways of tagging events with causal timestamps that avoid synchronizing clocks. These classical algorithms were invented decades ago, yet are used widely in today’s cloud systems.

2.1. Introduction and Basics10:54

2.2. Cristian's Algorithm5:50

2.4. Lamport Timestamps14:35

2.5. Vector Clocks12:01

與講師見面

Indranil Gupta
Professor
Department of Computer Science

In this lecture, we'll be looking at one of the standards

for synchronizing clocks in the internet.

The standard is called NTP.

NTP stands for Network Time Protocol.

Uh, here the NTP servers, which are managed,

are organized in a tree structure.

Uh, I'm showing the tree structure here with, uh,

the root of the tree or the primary server,

uh, being shown here.

That's the one, uh, that has a UDC time added.

There are secondary servers that are, uh, the children

of the primary, uh, server.

And, uh, that synchronize directly

with the primary server.

Then there are tertiary servers which synchronize

with their corresponding parent,

uh, at the secondary server level.

Your client might be one of the work statio-

might be one of the leaves in this, uh, tree,

and I'm showing one particular client over here.

So essentially, each node in the tree here synchronizes

with its parent in the tree.

How does it synchronize?

Well here is how the NTP protocol works

and then we'll look at how it sets the clock

over the next few slides.

So a child, uh, sends a message to the parent saying,

"Hey, let's start the protocol, I wanna synchronize my clock."

The message, uh, uh, uh, sent by the parent in response

is called message 1.

Uh, the parent 1 respon-uh,

records the time at which it sends the message.

This time is ts1 over here,

and then the child when it receives the message 1,

it records its receive time as tr1.

Notice that these times are set according to the local clocks

at the corresponding processes.

So ts1 is according to the parent's local clock

and tr1 is according to the child's local clock,

which of course are not synchronized.

Uh, the child then sends back a response message, message 2.

Records its sent time as ts2, according to its own clock.

And when the parent receives a response, it, uh, marks,

uh, the response received time

as tr2 according to its own clock.

Finally, the parent sends over the values

of, uh, ts1 and tr2 to child,

uh, and then the child uses all these four values:

ts1, tr1, ts2, and tr2 to set its clock.

How does it set its clock?

Let's, uh, look at it.

So why is this particular offset used by the child

to set its clock?

Why this particular funky equation?

So let's calculate the actual error, uh, uh,

due to this particular protocol.

Suppose the real offset, the real clock offset

between the child and the parent is, uh, oreal.

We don't know what oreal is, but let's say its oreal.

This means that the child is ahead of the parent by oreal

and the parent is ahead of the child by -oreal,

or it's behind the child by oreal.

Now, the value of oreal might actually be negative

over here, right?

So, uh, these two statements

would still be true in this case.

Uh, suppose the one-way latency of message 1 is L1,

and similarly, the one-way latency for message 2 is L2.

We don't know the values for L1 and L2,

just because the clocks are not synchronized,

and this means that it's gonna be, uh, hard, if not impossible,

to measure the one-way transmission latency.

However, we can write down the equations

based on these variables.

So the receive time of message 1, tr1

equals the transmit si-uh, the send time of the message 1

plus its, um, uh, uh, latency,

uh, uh, message delay plus the clock offset, oreal.

Similarly, the receive time of message 2 is, uh,

equal to its send time plus the message latency L2

minus, uh, the clock delay, because th-this message

is going in the opposite direction as message 1.

So, using these two equations now,

you can subtract the second equation from the first

and this gives you, uh, this equation for oreal.

You can solve, uh, for, uh, for oreal.

Uh, and oreal turns out to be this particular, uh, equation

over when you massage the terms.

And, uh, this first term is in fact the same

as, uh, the value of o that you see up here

at the title, uh, part of this slide.

And this means that the second part

in fact now becomes the error

because now, uh, the difference between oreal and o

is bounded by, uh, (L2-L1)/2,

and this is of course less than

the |(L2+L1)/2|,

and this is in fact the round-trip time.

So this means that the error,

uh, in, uh, this particular algorithm, NTP algorithm,

is bounded by the round-trip time,

um, uh, or at least half of the round trip time

in this particular case.

Okay, so this is justification for actually using

this particular value o to set, uh, the clock.

However, we still have a non-zero error.

We just can't seem to get rid of this error;

it always seems to depend on the round-trip time.

Uh, whenever you have a non-zero round-trip time it seems like,

uh, the error is about half of the round trip time.

So the question arises, um, uh, since it's getting so hard

to synchronize clocks,

why can't we just not synchronize clocks

and instead go directly to the root of the problem,

which is that we want to assign time stamps

to, uh, uh, uh, the, uh, events that happen

in a distributed system

and do this without synchronizing clocks?

We'll see how to do this in the next lecture.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2018 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取