4.1.2 Pregel - Part 1

Loading...

来自 University of Illinois at Urbana-Champaign 的课程

Cloud Computing Applications, Part 2: Big Data and Applications in the Cloud

147 个评分

University of Illinois at Urbana-Champaign

Cloud Computing Applications, Part 2: Big Data and Applications in the Cloud

147 个评分

课程 4（共 6 门，Specialization Cloud Computing）

Welcome to the Cloud Computing Applications course, the second part of a two-course series designed to give you a comprehensive view on the world of Cloud Computing and Big Data! In this second course we continue Cloud Computing Applications by exploring how the Cloud opens up data analytics of huge volumes of data that are static or streamed at high velocity and represent an enormous variety of information. Cloud applications and data analytics represent a disruptive change in the ways that society is informed by, and uses information. We start the first week by introducing some major systems for data analysis including Spark and the major frameworks and distributions of analytics applications including Hortonworks, Cloudera, and MapR. By the middle of week one we introduce the HDFS distributed and robust file system that is used in many applications like Hadoop and finish week one by exploring the powerful MapReduce programming model and how distributed operating systems like YARN and Mesos support a flexible and scalable environment for Big Data analytics. In week two, our course introduces large scale data storage and the difficulties and problems of consensus in enormous stores that use quantities of processors, memories and disks. We discuss eventual consistency, ACID, and BASE and the consensus algorithms used in data centers including Paxos and Zookeeper. Our course presents Distributed Key-Value Stores and in memory databases like Redis used in data centers for performance. Next we present NOSQL Databases. We visit HBase, the scalable, low latency database that supports database operations in applications that use Hadoop. Then again we show how Spark SQL can program SQL queries on huge data. We finish up week two with a presentation on Distributed Publish/Subscribe systems using Kafka, a distributed log messaging system that is finding wide use in connecting Big Data and streaming applications together to form complex systems. Week three moves to fast data real-time streaming and introduces Storm technology that is used widely in industries such as Yahoo. We continue with Spark Streaming, Lambda and Kappa architectures, and a presentation of the Streaming Ecosystem. Week four focuses on Graph Processing, Machine Learning, and Deep Learning. We introduce the ideas of graph processing and present Pregel, Giraph, and Spark GraphX. Then we move to machine learning with examples from Mahout and Spark. Kmeans, Naive Bayes, and fpm are given as examples. Spark ML and Mllib continue the theme of programmability and application construction. The last topic we cover in week four introduces Deep Learning technologies including Theano, Tensor Flow, CNTK, MXnet, and Caffe on Spark.

从本节课中

Module 4: Graph Processing and Machine Learning

In this module, we discuss the applications of Big Data. In particular, we focus on two topics: graph processing, where massive graphs (such as the web graph) are processed for information, and machine learning, where massive amounts of data are used to train models such as clustering algorithms and frequent pattern mining. We also introduce you to deep learning, where large data sets are used to train neural networks with effective results.

4.1.1 Graph Processing22:34

4.1.2 Pregel - Part 17:21

4.1.3 Pregel - Part 211:00

4.1.4 Pregel - Part 36:13

4.1.5 Giraph Introduction6:46

4.1.6 Giraph Example4:46

4.1.7 Spark GraphX15:25

与讲师见面

Reza Farivar
Data Engineering Manager at Capital One, Adjunct Research Assistant Professor of Computer Science
Department of Computer Science
Roy H. Campbell
Professor of Computer Science
Department of Computer Science

[SOUND] We're going to move on now to look at

graph processing and what infrastructure you need for that graph processing.

We've seen the need to do it, but how do you provide support for that?

There's two ways to go.

You can either have a super computer, providing your graph processing,

lots of memory, very high performance machines.

Or if you want to scale it to normal sizes, you're going to have to look for

a cloud solution with distribute processing.

It's in general, going to be more expensive to design this.

Unless we can find a way to map

graph processing onto a cheap cloud infrastructure.

The super computing approaches will be more expensive.

So, natural question is can we actually use MapReduce, and would that work?

Well, it tends to be inefficient because the graph state must be

stored at each stage of the graph algorithm.

And each computational stage will produce much communication between the stages.

So, if you do a MapReduce and you do a MapReduce on all the vertices,

what's going to happen is, you're going to have to visit all of the data structures,

and it's going to be very expensive,

even if your algorithm doesn't actually change all the data structures.

And we'll see later that there's some algorithms that don't.

Single computer in a library approach, well, that's not very scalable, though it

works on a super computer up to some large extent, but once you reach out of memory,

once you lose, once can't fit your graph in the memory as we've seen, there's

lots of problems with graph processing that won't do that, then you have trouble.

So, if we're doing a shared memory system implementation on a super computer.

You do also have to worry about how you get fault-tolerance and

if the computation runs for a long while, and there's a chance that machines die,

how are you going to make sure that the computation will continue?

And one of the advantages of using distributed computing is that machines can

die and you can have backup pieces and

you can keep going even in those circumstances.

So, we're running into the area where we may not be able to do the computations we

want if we can't figure out how to map it on a distributed machine, and

maybe we don't need it as efficient.

Maybe what we will do is just use the massive approach to try and make

the computation work, provide the full tolerance and provide the computation.

And it won't be as efficient as we would really desire.

So, we are going to look at a parallel model again.

The BSP model is still going to be the valiant BSP model,

and it's still going to be the direction that we're going to take.

We're going to provide graphs and

often we're going to be sort of oriented towards a directed graph.

I'm going to show you Pregel.

Pregel was one of the first systems to do graph processing on a distributed system.

It was running to show how you could actually solve the problem.

What it's oriented towards, as you all have heard,

as you will have from the first lecture, is going to be vertex space.

We're going to do the computations around each vertex, and

each vertex makes sense of processing.

So you're going to move the computation forward by processing a particular vertex.

And we are going to keep repeating on all vertices that need

to be processed until every computation in each vertex votes to say, okay, I

have done what I have needed to do on this particular stage of the graph processing.

And once all of those vertices vote and

say, okay, that may not be all the vertices.

That could be a subset.

What we're going to do is to return back to directed graph

and allow yet another iteration.

Those iterations are going to be sort of like super steps in our method.

So, the primitives you will find in Pregel they deal with vertices, they treat

them as first class entities, meaning we will be programming with the vertices.

With this vertices, we're going to do this, this and this.

The edges aren't first class, they're incidental when we visit a vertex,

we're going to be talking about the edges.

And, we will be exploring what's on the edges,

what are the edges labeled, what are they connected to?

We will allow both vertices and

edges to be created and destroyed in the computation if we need to.

So, Pregel was based around C++, it has a C++ API.

It moves ahead with a set of supersteps.

Superstep, you look at the vertices, the application code using C++,

an object-oriented programming.

Subclasses, an abstract notion of an abstract class of vertex and

it writes a compute method for that vertex, and in that compute method,

you're going to say, we're taking into account all of the edges.

What do I want to do with this vertex?

You can set the vertex value.

You can set the outgoing edges values.

You can get them.

You can send and receive messages generally, and

you'll be reading messages sent to a particular vertex.

You can either do it from the previous step in Step S.

So, Superstep S minus one you can look at the edges or read the messages.

You can send messages to other vertices that will be received at superstep S+1.

And that way,

sort of allowing you to go from step to step computation to computation.

Each time you could be modifying a set of V, and

its outgoing edges and they'll be available to the next superstep.

So, the C++ API provides messaging.

It has a guaranteed message delivery order.

So it's like TCP.

Messages deliver exactly once.

So, you don't have to worry about failures of messages to get

through and you can send a message to any node in the system at all.

So, if you want it to wrap around or you want to have a broadcast or whatever,

it's fine.

If the destination doesn't exist, then, there's a user function will

be called to tell you that you've made an error and you need to fix the problem.

[MUSIC]

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

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

通过 App Store 下载

通过 Google Play 获取