Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
PROFESSOR
And welcome back. We're finally here. MapReduce — very exciting to be the first one to explain this to you if you haven't seen it before. So MapReduce is an abstraction.
It's very simple. I say simple, compared to what we used to have to do before MapReduce phase, data parallel programming model designed for scalability and fault tolerance. The key here is fault tolerance.
If you're operating on not just cores — cores don't fail for the most part. But boy, when you go to machines, and those machines live in other countries, they fail.
The network goes down. Things happen. I can't just farm it out to 1,000 different machines and hope that all 1,000 — and expect — I hope that all 1,000.
But I expect that all 1,000 will come back with no trouble without failing at some level. Many things could happen.
Especially when you increase the number of machines to a big number, you're going to have some problems. Not usually the same in the case of cores.
So there's a little bit less worry about fault tolerance there, but certainly the case when you go to multi-machine and distribute — we call this distributed computing, by the way.
Again, pioneered by Google. And regularly, they're processing 25 petabytes — pretty incredible, petabytes of data per day. There's a new open source project. I shouldn't say so new.
There was an open source project that was new a couple of years ago, Hadoop, used by Yahoo, Facebook, Amazon, and many people. And this is a Java-based framework.
We love Hadoop for what it does. What's it used for? Well, Google uses its MapReduce framework for lots and lots of things.
They've got to build your indices to be able to handle Google Search, clustering articles for Google News, machine translation, street maps.
How do you do all that street maps and multi-layer and be able to handle the zoom factor in all of those?
Yahoo search for Yahoo, spam detection is a big one, Facebook, data mining, ad optimization, spam detection.
Many things that fall into the model of, as you can imagine, a mapping phase and a reduction phase. And we'll talk about what those are in a moment.
Here's an example of something that they used to use MapReduce for at Facebook. This used to be available. No longer available, but the Facebook Lexicon.
I think Google has something as well, where you can type in a word and you can see when correlating events used to happen. So when are people searching for different things?
So here's a funny thing of people saying "party tonight" and "hangover." And so here's "party tonight" and "hangover." "Party tonight" is in yellow, "hangover" is in blue.
And you notice the hangovers often follow, often peak, right behind the "party tonight." It's just people typing things. When is this happening, and this is like the frequency of that.
And by the way, when are the parties happening? Can you see? Oh, there's a pretty big party. When, oh I don't know.
Halloween party, New Year's Eve party. Maybe holidays — Christmas, Kwanzaa, Hanukkah, all happening here, but distributed.
So there, but, boy, everybody seems to party on Halloween and New Year's, and not a thing in February, March or April.
So it sounds like we need to introduce more national holidays in those days to just distribute out the parties. Here's the design goal.
By the way, this initially came out of work that Jeffrey Dean and Sanjay Ghemawat did at Google years ago. They wrote a famous paper, one of the most downloaded papers in systems, since 2004.
This is, like, 16 years ago as of this video. The idea is it's scalable to really massive data volumes, thousands of machines. Each machine might have multi-core within them, tens of thousands of disks.
It's a lot of data. You can imagine processing in all of that, cost efficiency.
So one of the things they've learned — we'll talk about this in the warehouse scale computing lecture, is they didn't buy the highest-end machines. They went with commodity machines.
They said value per dollar, cycles per dollar, processing cycles per dollar is cheaper if you go with commodity machines.
The value of volume really helps, rather than, well, let's buy the highest-end — crazy, high-end gamer machine with liquid cooling, and blah, blah, blah.
Per dollar, that actually isn't so — if you didn't have one game, I want to play it. For one system, I'll have the best thing for my 8K screen.
Maybe that's a good value, but not when you try to compute massive amounts of data. Compute processing per dollar, that's not the right call. A commodity machine is interesting.
And they actually started building their own, which is very interesting. Commodity network. This is the thing. Fault tolerance — how do you deal with fault tolerance?
Well, all you do is resend it. This is what happens on the internet as well. If I send a packet and I don't get an ACK back, I just send it again.
That's what we learned in the internet, and that's what TCP/IP is doing for you. TCP really is doing that work for you.
Here, what we'll just do is re-send that request step, but probably not to the same machine. Probably send it to somebody else. But we handle fault tolerance by just re-execution.
Just send it out again. Send the request out. I broke it up into 1,000 pieces, and 999 came back. One didn't?
Well, I'll send it to somebody else. And by the way, maybe there's a time-out earlier than that.
Rather than to wait till all 999 came back, and then send the thousands back out, maybe say, you know what? I'm going to give up on you early.
Send it out so that it can all come back in the same time, and I don't have to wait for that. And we find it very easy and fun to use.
And we've had some assignments in lower division to do this, and we're excited to share this with you as well. We've linked to the Dean paper. We call it the Dean Ghemawat paper.
We've linked that on the 61C page, so please do check that out. Here's a typical cluster. You've got each machine. We call them nodes.
Each node might have a disk local to it, hanging right off of it. And that's a reasonable thing to do. There's a rack switch that connects these all.
We'll talk about server rack and array in the next lecture.
But for here, they're all connected via a switch, which is able to take a request and be able to know which computer to talk to and which it came from, where is it going.
Like a router in some sense. And there's an aggregation switch, which is doing the same thing. But the difference is you have different bandwidth requirements.
Once you get to more and more central command, it's almost like plumbing. When you have a plumbing from your house, the pipes are really small. Once it gets in your neighborhood, it's much bigger.
It's from the city, it's massive. If you go to Los Angeles, they have this overflow. Not the — I'm sure the sewer is large and massive as well.
But if you think about handling flooding, you have a little teeny flood — this happens a lot in the Bay Area and very flat locations, certainly in Los Angeles.
Oh, here's my neighborhood. There's a little ditch to handle flood, and that's fine.
And then once it gets to the main area, there's this massive, I think, probably 20 lanes wide of a flow where the water's finally going to the ocean.
Same idea here. Once you get away from each node higher up in the hierarchy, if you will, these switches have to be very fast, much higher end.
And they have an 8-gigabit connection network here across them.
So you end up having much more expensive — and we'll talk about the cost here, much more expensive switches and connections at the higher level, because you're handling larger channels of data.
This is for everybody in maybe the whole array. So some of the numbers we have here are 40 nodes in a rack, maybe up to 4,000 nodes in a cluster.
So you might hear the first cluster here. And again, 1 gigabit per second bandwidth within the rack, and then eight out of the rack. And the node specs, this is a lower-end machine.
This is, like, a couple of years old, but [INAUDIBLE] faster. Computers, as you saw, aren't getting that much faster.
So maybe eight 2-gigahertz cores, 8 gigs of RAM — probably that's 16 or 32 by now, and four disks each, about 4 terabytes.
So this is a fun slide, because one of the things we've been doing in CS 10 and 61A, a little bit in 61B, but not as much, is to share with you the benefits of the programming paradigm, known as the functional programming paradigm.
If you think in a functional way, where your job is to have a block that has an inputs and outputs, and doesn't have any side effect, then you're going to be able to work with this MapReduce model a little bit easier.
So we've been trying to teach MapReduce. We actually teach MapReduce, the idea of a map and a reduce in a non-majors class. Very rarely is that happening.
So I think Berkeley's really leading the way nationally in terms of bringing some of these parallel and distributed computing ideas into the lower division, and even in this case into our non-majors class, which by the way is being shared with 1,000 high schools all around the world.
At least we've had 1,000 teachers go through our professional development in BJC. So that means these ideas are getting out there into the winds. Here's the model.
Map says do a function over a set of data. That's it. So I want to square all those numbers, 1, 20, 3, and 10.
So here's a little picture on the bottom to show what's happening. So I'm first applying the map. But what that does is, map says take a function.
It's usually a monadic function, a function of one argument. Here in this simple case, it's a function of one argument, takes every number, and it's going to square it.
So it's applying that function to everybody, returning a new list, not mutating the list. It's not it's an immutable list.
Returning a new list in which every element has had that function applied to it.
So if I square every element of the list, 1, 20, 3, and 10, I get 1, 400, 9, and 100. And now I say combine with plus.
And combine with, again, it's below the level of abstraction of how that works. Is it left-associated, right-associatd, tree-wise? Hopefully, it's a tree structure.
But that's being combined, and that's usually a dyadic function — two inputs, one output, and it's a smusher together. And so here, I'm just adding them up. So here's an example.
Here, 1 and 400 get added together to give you 401. 9 and 100 gives you 109. And then eventually, that's 510. So we're hoping like a tree model for that.
Who knows how reduction happens? Again, who knows how the mapping happens? Maybe you tell me, oh, Dan, I only have two worker bees, two cores, two machines to help you.
Well, I don't care. This is just going to work. If I have two, this will be split up. One machine might do these two, one machine might be these two.
I don't know. Maybe there was four. This list could also be in the billions. Who knows how big that list is?
So we're rarely going to have a billion worker bees working totaled cores in your available set. So at some point, it says, well, apply it out, and then come back.
And then keep working on more of that until you're all done. But from the user's point of view, I don't care. This is the beauty of this abstraction.
From the user's point of view, I don't care. So at the end of the day, I get 510.
By the way there's only two data types here — the data type of the input and the data type of the output here. And this is thinking about domain and range here.
This can be done in Scheme. We used to teach us in Scheme all the time. This is a Scheme model. Those of you who have taken 61A know this.
And So map and reduce come — by the way, we call it combine. We call it map and combine in CS 10.
In 61A, we teach Scheme, and map and reduce are part of that. And so here's map square over the list, 1, 20, 3, and 10, and then you reduce plus over that.
How beautiful and tight that is. Python, it's a little bit more syntax for it, but not much more. We have to import the reduce method from functools library.
Then I have to define the plus function a little bit. And then I'm going to define a square function. I can obviously use a lambda here, and you'll see it a little later.
We're going to use a lambda when we do the Spark stuff. But here's exactly the same thing in Python. Reduce of plus over map of square of this, and automatically I get 510.
Really, really clean. So this is a simplified version of MapReduce. It gets a little more complicated on the next slide. So let's actually get into it.
In the full MapReduce programming model that Dean et al presented is an intermediate step. It's the step between the map and the reduction phase.
And that intermediate step has a key value pairing. You know about key value pairing from Python and from any key value model that you've seen before. So here's how Map works.
Map takes your data.
I key in a value, and it's going to process the input key value pair, slicing data into shards, which are distributed to workers. And that produces intermediate pairs.
So these itty-bitty pairs are set up by key, and then they are sorted by key. Every shared key, all the data for a shared key, is sent to one machine.
You're going to see in the next slide, this will all become clear. That machine — that Omni machine has all data — had that same key.
So the key is the way that you're tagging the data in some way to distribute it across those machines.
Because the system says, whatever the keys you have, I will coordinate it sorted by the keys. So the intermediate stage is there.
So you're using the keys, in some sense, not to just add more data, not to add more cruft to your data input data, but to distribute it across nicely.
You get to determine what the key assignment is. And that distributes it nicely, so you get some control over how it distributes in the reduction phase.
And then everybody just attaches the key in a parallel way. Then it's sorted by key across machines.
And then every machine gets all the data for a particular key, and then processes all the data using your reducer. And this is a reducer.
That's it, and it produces a set of merged output. Usually just one value is right here. So here's an example.
The bread and butter problem we have every time when we're looking at a new programming language is "Hello, World."
If you [INAUDIBLE] say my system solves all two-person abstract strategy games, we'd say "Solve Tic-Tac-Toe."
If you were to say, I have this great system that lets you do parallel computing easier, we say to you "Show me WordCount." WordCount has become the problem we go to.
It's the go-to bread and butter problem — the "Hello, World," if you will, of parallel and distributed systems. WordCount says the following. I've got a corpus of text.
Maybe it's all Shakespeare's work, maybe it's the Gutenberg Bible, maybe it's all of the Hillary emails. Who knows what it is?
And I want to be able to, for WordCount, count the number of words. For every unique word, I want to count the occurrences of it. That's all I'm doing.
So if I give you "I do, I learn," I want to get out I. There's two "I's," one "do," and one "learn" here. And so what this is going to do is to tag.
Remember, I told you the output of map is this key value pair list.
So what it's going to do is tag it with the key is the word itself, split it by words, the word itself. And the value is going to be the number 1.
So essentially, for every word that comes in, I just slap on a 1 to the side of it.
And the key, by the way, is going to be the word and the value is going to be the number 1. And it passes it on to the next stage.
Then that sorting stage is going to sort things. There's going to be a machine for each of those keys. So the keys are "I," "do," and "learn."
There's going to be a machine whose job it is to just add up those values, here the number 1, for all the I's." There is a machine adding up all the values.
Here is the number 1 again for the do and here's 1 for "learn." So it would be an "I," a "do," and a "learn" machine. And each of them does the reducer.
What's the reducer say? Well, look at this.
Set result to 1 for each value, for each v in the intermediate values — this is the intermediate level, the intermediate values, I accumulated in some result variable.
And I emit the result as a string. That's it. The data is on a distributed file system. This means that data isn't in memory.
The data is on files. And those files, who knows what they are? They're on the distributed network, so they're not just a local to me. You think, oh, it's always my local disk.
It's not the case. You want a distributed file system, which means they live out there in "the cloud" in quotes. So this is my favorite example. Here's the code for map and reduce.
And I've got a file of just utterances.
Ah ah er is in the first file, file 2 is blank, ah is in the third file, if and or are in the fourth file, or an uh in the fifth file, or, and ah and if.
What does the mapper do? It returns a key and a value pair for each of these guys. So it says I'm going to process this.
By the way, there's no reason it has to process everything. In the mapper, it could go through and decide to not emit some things. What I'm saying is for each word, it emits that.
You could say for each word that is not er, and therefore you'd take er away. So you can do some filtering in there as well. It's your call.
I mean, you're running this code. My point is, you're only emitting things you want to emit. Here, it's emitting everything because it's for each w, and w is admitting everything.
But you could imagine it being a filtering step in here if you wanted that. So think about, as you're thinking, oh, I might do this problem, but I need to do some filtering.
Here's where the filter would happen where you don't emit things you don't want to emit. So now all I've done is attached one to all these guys.
Now I have a 1 at the end of every single key. The key, again, are all the words. This is this phase I talked about — the group-by key phase.
That says they're going to be a machine attached to every key. The keys are now the five unique words ah, er, if, or, or uh. And what is the reducer?
Then all those values are sent to the reducer. What does the reducer say? Basically, it says add them all up — add all the numbers up, whatever the values.
Sometimes, it ignores the keys. I don't care what the output key is. But for each of these guys, all I'm going to do is output a 4. It emits a string.
And so what comes out of this is, in a way, it's a dictionary.
Think about this as the outputted value of the whole system here is every machine says, well, I was the machine assigned to ah, and my value is 4.
So it's ah:4 Well, mine was the machine doing er, and I only saw one of them. So I'm er:1. So that's the idea.
The output is, in a way, of this whole system of — that was the goal.
The goal of the whole problem was WordCount — was return a dictionary of where the keys are the words, every unique word.
And the value is the number of occurrences they occurred in the original thing. Well, that's what's happening here. This is the output.
If you turn your head sideways, this is key down here and value up there. That's it, and that's your output of the word count. Very simple. Doesn't seem that hard.
So mapper, all it does is slap a 1 at the end of it. And reducer says, well, I got all the 1's. What do I do with them?
Add them all up. So it's really reduce plus. Key is attach 1. The reducer is just plus.
It's all I'm doing. That's it. So that is word count. Pretty clean.
How does this work? Well, let's say the corpus is not just four files, but a ton of files. Maybe it's a huge directory. Maybe it's a lot.
How does this work? Well, this is very clever. This is the part that's the system engineering part of it that really is quite brilliant.
And by the way, not all maps take the same time. Sometimes, the map task, maybe the file you're given is a much larger file than everybody else.
You're going to be doing more work than anybody else does. So not all maps take the same amount of time.
In my simplification, in my simple example of map of square, square takes the same amount of time for every number you're going to be given, except perhaps if you have big numbers, and the numbers actually are stored as a string.
But for now, you think that's a bad model. Really, maps can take variable amount of time as reducers can take it variable amounts of time.
Who knows how many of those 1's I had to add up in that model?
So there's a lead. We call it, I guess, a master controller, which assigns the map and reduce tasks to these worker servers. There's all these servers. It's like worker bees, if you will.
As soon as a map task finishes, that server can be re-assigned a new task. So this particular worker was only assigned map task. This particular worker was only assigned a map task as well.
This worker can be assigned read tasks because it's reading 1, meaning what is this doing? This guy says, well, when that's done, I can start reading those values in and be waiting for it.
And I also need to know why I need to be reading this one. So this is also reading for that when that comes in, and then I'm reading for this one.
So when they're all done, now I can start my reduction task. So why wait till they're all done? It's very clever to think about this to start its reduction.
So this is saying, look, these workers are the mapper workers, these are the reducer workers — that it's not always the case.
Basically, once map 1 finishes, I'm telling the system, hey, I'm available for more work. Maybe I'm the job. Maybe this becomes me. I mean, it's drawn this way to make this diagram clear.
But it could be that this worker 1 is assigned to do that read, and then it's going to be waiting and reading. Then basically this could be up here is what I'm saying.
It doesn't have to be like, oh, worker 1 is only mapping and worker 2 is only mapping ever. Basically, they go back into the pool of workers, and the jobs are just out there.
So there's a queue of jobs that need to be processed, like you got to start reducer. You've got to start the next mapper. There may be many more mappers than just three here.
So it could be that you're heterogeneous in that sense. I'm a worker bee and I was doing some mapping, and then I'll do some reducing, and maybe there's some more mapping to be done.
I finish that reducing, and there's more mapping to be done there. Who knows what that is, was done? And by the way, what typically happens is it's not just one map and one reduction.
You tip it. I read the paper, I found what happens is, there could be a map reduction here that feeds into another map reduction, to feeds into another.
So there's this whole series of map reduction, not just one. It's just one problem. It's all they have to know.
There might be several phases of it and doing phase 1, phase 2, phase 3, and you just continue to process the machine.
And it's really fun to watch There's a dashboard that you can see how things are processing. It's very neat to see.
So I encourage you to take a look at that if you ever get this working.
The reduction task begins as soon as all the data shuffles finish, when we get our shufflings around and finally there.
Because in this problem as before, that last mapper might contribute a 1 to your reduction. So here in this particular problem, you can't do any reduction until you've finished all the mapping.
So I might have implied that you could start reducing before the mapping is done.
In this particular case, I certainly can't start adding up my 1's until all the guys that are going to be 1's feed into my machine and that's done.
So in this particular model, you have to wait till all of the maps get done before I can even start thinking about the reduction. But you can start reading their values certainly.
That's a nice thing. Here's a thing, I mentioned this before. If a worker doesn't respond — network failure, disk failure, hardware failure, memory failure, it could be a lot of failures.
I just reassign the task if a worker dies. That's important. This is the amount of Java code that does that same word count.
If we look here in detail what is happening, here it's saying I'm outputting the value and a ONE. This is the actual code for this.
And here, here's my sum of 0, and I'm sum plus equal that value. It's a little bit more complicated, but essentially, that's what we were doing before. And that's the Java code for it.
That's it. So there's WordCount, folks. And by the way, most of this is just setup. We're just setting these things up here in this early part of it.
That's it. Pretty exciting. WordCount is a really nice example, and MapReduce is a very, very powerful paradigm.
The next lecture, we're going to talk about maybe there's a cleaner, lighter-weight way than when I'm looking at maybe 35 lines of code. Maybe there's a little tighter way of doing that in Spark.
We'll see that then. Take care.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.