1 00:00:06,010 --> 00:00:09,097 Okay last time we talked about map reduce, and gave the abstraction and went 2 00:00:09,097 --> 00:00:12,380 through some examples and we ended up on this slide which is, maybe the first time 3 00:00:12,380 --> 00:00:15,565 we've seen pseudo-code or any kind of code that actually implements these map 4 00:00:15,565 --> 00:00:22,080 and reduce functions, and so I asked you to just sort of take a look at this. 5 00:00:22,080 --> 00:00:26,238 actually the end of the last segment there are a couple of changes, mistakes 6 00:00:26,238 --> 00:00:30,081 that I fixed in this slide so you can compare the two to see if you can figure 7 00:00:30,081 --> 00:00:35,450 out what the mistakes are and why I changed them. 8 00:00:35,450 --> 00:00:40,280 So, let's walk through this. So what is this code? 9 00:00:40,280 --> 00:00:43,584 Do well as I sort of gave away last time, this implements this word count 10 00:00:43,584 --> 00:00:47,112 application that we went through schematically you know with cartoons and 11 00:00:47,112 --> 00:00:52,278 you know this is the psuedo code that actually implements that. 12 00:00:52,278 --> 00:00:58,100 Or you know an example of pseudo code that could be that could implement that. 13 00:00:58,100 --> 00:01:01,300 You can't execute this code since it is just Pseudo-code. 14 00:01:01,300 --> 00:01:05,290 So, what are we looking at here? Well, the input, as we said, the data 15 00:01:05,290 --> 00:01:08,440 model of MapReduce is key value pairs and so, the input is going to be a big set of 16 00:01:08,440 --> 00:01:12,431 key value pairs. And the Map function is going to operate 17 00:01:12,431 --> 00:01:16,853 on one of these key value pairs. And in this case, the key is the document 18 00:01:16,853 --> 00:01:20,140 name and the value is the document contents. 19 00:01:20,140 --> 00:01:24,156 So it could be a big string. Right it's maybe it comes from PDF file 20 00:01:24,156 --> 00:01:28,940 or a text file, or a webpage or whatever. Okay, and so this code is pretty simple. 21 00:01:28,940 --> 00:01:32,524 It says well for each word w in the input value, so this sort of assumes some how 22 00:01:32,524 --> 00:01:35,884 you can iterate over all the words in the, in the input value in the text of 23 00:01:35,884 --> 00:01:40,539 the document, without really specifying how. 24 00:01:41,590 --> 00:01:45,840 Then emit a key value pair where the key is this first element. 25 00:01:45,840 --> 00:01:49,340 Which is the word and the value is the number one. 26 00:01:54,490 --> 00:01:57,907 Okay, then, the majic shuffle phase takes over. 27 00:02:00,630 --> 00:02:04,290 And groups all the key value pairs that have, that share the same key into a 28 00:02:04,290 --> 00:02:07,790 single group. And so all the occurrences of a 29 00:02:07,790 --> 00:02:13,099 particular word will show up as a group. And how that group is represented is as a 30 00:02:13,099 --> 00:02:16,494 key along with. What we've called here an iterator, over 31 00:02:16,494 --> 00:02:19,487 the intermediate values. And if you're not familiar with the term 32 00:02:19,487 --> 00:02:22,910 iterator, you can think of it as just a collection of values. 33 00:02:22,910 --> 00:02:25,030 Okay. So as an example here we have the word. 34 00:02:28,430 --> 00:02:31,120 You know, the map function will produce, pairs like this. 35 00:02:34,100 --> 00:02:36,708 Every time it sees the word history in any document it'll produce this. 36 00:02:36,708 --> 00:02:42,980 And then finally, on the reduced side you'll have the word history here. 37 00:02:46,550 --> 00:02:54,870 And a sequence of, number ones. Okay. 38 00:02:54,870 --> 00:03:00,712 And so what is this code do? Well, it initializes the final result to 39 00:03:00,712 --> 00:03:04,137 zero. And it says, for each value in this list 40 00:03:04,137 --> 00:03:08,630 of intermediate values, add that value to the result. 41 00:03:08,630 --> 00:03:12,225 And so here we just add them all up. And then finally, we admit a final key 42 00:03:12,225 --> 00:03:15,292 value pair which is the intermediate key, the word itself. 43 00:03:15,292 --> 00:03:20,205 In the final result. And so maybe the output here is, you 44 00:03:20,205 --> 00:03:24,423 know, history 25. And we walk through this a couple 45 00:03:24,423 --> 00:03:27,100 different times. I hope this is pretty clear by now. 46 00:03:27,100 --> 00:03:32,690 Now, I calim that without changing this reduce function at all You could make a 47 00:03:32,690 --> 00:03:37,936 change to this map function and get a significantly faster algorithm for 48 00:03:37,936 --> 00:03:45,026 computing this. So I want you to think for a second how 49 00:03:45,026 --> 00:03:56,637 that might be done. So the thing to look at here is that, oh 50 00:03:56,637 --> 00:04:04,120 goodness We're emitting a key value pair. Let me stop resting my hand on this. 51 00:04:04,120 --> 00:04:07,888 We're emitting a key value pair 1s for every occurrence of a particular word. 52 00:04:07,888 --> 00:04:17,290 And each one of these key value pairs has to be shuffled across the network. 53 00:04:17,290 --> 00:04:21,528 And sent to the, sent to the reducer. So if we see the word, history, 25 times 54 00:04:21,528 --> 00:04:25,964 in a single document. We're going to emit 25 key value pairs 55 00:04:25,964 --> 00:04:28,462 for that word. And they're all going to be grouped up by 56 00:04:28,462 --> 00:04:31,644 the shuffle phase. But we have access to the entire document 57 00:04:31,644 --> 00:04:35,180 here in the map. In the, in this map function. 58 00:04:35,180 --> 00:04:39,030 So why not precount all the occurrences of those words. 59 00:04:39,030 --> 00:04:52,680 And produce a different key value pair. Right? 60 00:04:52,680 --> 00:04:55,865 Which means the word history appeared 25 times in this particular document on 61 00:04:55,865 --> 00:05:02,100 processing. And so now actually I meant to say 25. 62 00:05:02,100 --> 00:05:04,974 Sorry, that's confusing. That's confusing, I didn't mean to make 63 00:05:04,974 --> 00:05:09,070 this the same number as this. this is, you know, in our previous 64 00:05:09,070 --> 00:05:12,790 formulation of this problem, it turned out that we, we are, we said that the 65 00:05:12,790 --> 00:05:16,870 word history appeared 25 times across all documents, and I shouldn't use the same 66 00:05:16,870 --> 00:05:20,890 number up here, because that's, that's That's pretty confusing so let me change 67 00:05:20,890 --> 00:05:24,370 so here we say that the word history appears 5 times in this particular 68 00:05:24,370 --> 00:05:31,870 document, and it appears other times in other documents. 69 00:05:31,870 --> 00:05:35,610 Okay. So now we have only one key value pair 70 00:05:35,610 --> 00:05:42,018 emerging from this document. For the word history as opposed to five 71 00:05:42,018 --> 00:05:45,037 different ones. And overall, across all the documents, 72 00:05:45,037 --> 00:05:48,872 across all the computers being applied to this problem, that's a significant 73 00:05:48,872 --> 00:05:51,110 savings. Okay. 74 00:05:51,110 --> 00:05:54,374 And then, you know double check to make sure you don't have to change this code 75 00:05:54,374 --> 00:05:57,638 here, but you, know, you, hopefully it's clear that you don't because you're 76 00:05:57,638 --> 00:06:02,886 adding the total value into the result. And so here, instead of adding the number 77 00:06:02,886 --> 00:06:07,078 one, 25, or sorry, five times. Well sorry 25 times I guess in the, in 78 00:06:07,078 --> 00:06:13,530 the reduced side. Your adding it some number fewer times. 79 00:06:13,530 --> 00:06:19,480 Right, you're adding 5 plus 10 plus plus 3 plus 4 and so on to get 25. 80 00:06:19,480 --> 00:06:23,490 Okay, so this loop it is valuated fewer times. 81 00:06:23,490 --> 00:06:26,724 Okay, So the reason I want to go through that example is To demonstrate that, you 82 00:06:26,724 --> 00:06:29,970 know. There, there's two things. 83 00:06:29,970 --> 00:06:33,442 One is to try to think in terms of map reduce and think about how you can cast a 84 00:06:33,442 --> 00:06:36,970 problem as operating on a bunch of chunks. 85 00:06:38,410 --> 00:06:42,940 Emitting keys to, to define groups and then operating on those groups. 86 00:06:42,940 --> 00:06:46,558 But also that you know, you actually have a lot of control over the performance of 87 00:06:46,558 --> 00:06:51,390 these algorithms by just modifying the map and reduced functions. 88 00:06:51,390 --> 00:06:53,658 Alright, so even though you aren't working on the system internals you only 89 00:06:53,658 --> 00:06:56,870 have these two points of control. You can actually get very different 90 00:06:56,870 --> 00:07:00,420 algorithms, very different behavior and different amount of intermediate results 91 00:07:00,420 --> 00:07:04,700 being created and so on. Just when these two, two functions. 92 00:07:04,700 --> 00:07:07,556 And so you want to get a feel for not just how to express it in map reduce 93 00:07:07,556 --> 00:07:12,480 naively, but also get a feel for how to do things reasonably efficiently. 94 00:07:12,480 --> 00:07:15,496 And in fact, this example sort of demonstrates one of the things you're 95 00:07:15,496 --> 00:07:19,032 going to be looking for is the bottleneck often, not always, is the amount of data 96 00:07:19,032 --> 00:07:23,305 going across the network. And so if you can reduce the. 97 00:07:23,305 --> 00:07:27,494 amount of output produced by the mappers, especially in terms of number of key 98 00:07:27,494 --> 00:07:32,650 value pairs. You'll tend to improve performance, again 99 00:07:32,650 --> 00:07:36,540 not always. And we'll see some more examples of this. 100 00:07:36,540 --> 00:07:39,570 Okay. So I'm going to s, stop there, and in the 101 00:07:39,570 --> 00:07:46,008 next segment we'll go through a variation of this problem. 102 00:07:46,008 --> 00:07:49,110 That cha, that has similar characteristics. 103 00:07:49,110 --> 00:07:51,846 But really just to drive home how to design these ma, ma, map produced 104 00:07:51,846 --> 00:07:54,541 algorithms on slightly variant problems.