[CS61C FA20] Lecture 36.4 - MapReduce, Spark: Spark — Transcript

Full transcript

1. 0:00welcome back now we're going to teach
2. 0:02you spark
3. 0:03which is another way to think of the
4. 0:04mapreduce paradigm with a little bit
5. 0:07lighter weight touch in terms of how
6. 0:08much programming you have to do for it
7. 0:10so it's a fast and general engine for
8. 0:12large-scale data processing it came out
9. 0:14of uc berkeley
10. 0:15very excited about that and this is a
11. 0:17performance bar
12. 0:18that says running time on a particular
13. 0:20file
14. 0:21and spark is blowing out of water at a
15. 0:23factor of more than 100 times faster
16. 0:25and part of the reason for that is that
17. 0:27spark
18. 0:29does the work in memory map produce is
19. 0:31always about disk
20. 0:32disk in disk out so there's they say but
21. 0:35basically mapreduce says
22. 0:36we're dealing with such big data files
23. 0:38data sets that i can't do it in memory
24. 0:40i have to i mean i'm going to load it in
25. 0:41memory and do it but put it down
26. 0:43basically the kind of input output
27. 0:44characteristic is always based on disk
28. 0:46file in file out that's the idea you
29. 0:48write a file then you're done if it
30. 0:49crashes halfway through it leaves your
31. 0:50files written and
32. 0:51you can rest spark says well that's nice
33. 0:54but wouldn't it be nice if i could work
34. 0:56just in memory and just live in memory
35. 0:58not have to pay the 1000 time or more
36. 1:00performance penalty to go to disk
37. 1:03that's painful so spark has an advanced
38. 1:07execution engine that figures out what's
39. 1:09needed when
40. 1:10and it gives you just in time
41. 1:12computation it's quite quite clever it's
42. 1:14very it's lazy it's a lazy evaluation
43. 1:15model which is really nice
44. 1:16and as much as you can in memory
45. 1:18computing easy right applications in
46. 1:20java in scala or python we're going to
47. 1:22see the python example
48. 1:24and it offers very quite a few
49. 1:25high-level operations to make it very
50. 1:27easy and you can even interact with it
51. 1:28interactively
52. 1:29you can interface with interactively as
53. 1:31well as a batch processing way which is
54. 1:32how mapreduce is done
55. 1:34but the fact that you can play this
56. 1:35interactively is really very fun and
57. 1:36very exciting
58. 1:38so ladies and gentlemen let me show you
59. 1:41this is the java code i showed you in
60. 1:42the last lecture
61. 1:44this is the same word count
62. 1:48in spark in python file
63. 1:52i've loaded file there's a there's
64. 1:54another line above it which it says you
65. 1:55know what file is i've loaded file in
66. 1:56but the actual processing is
67. 1:58first i flat map by splitting my
68. 2:01document into words now i have as some
69. 2:04sense a list of words
70. 2:07i then map across that word
71. 2:10and one and i return now a list of word
72. 2:12and one
73. 2:14and i reduce by key remember the
74. 2:15reduction by key so this is rather than
75. 2:17having a shuffling phase
76. 2:19this is reduced by key and what that
77. 2:21says is
78. 2:22each of these worker elements is going
79. 2:26to get
80. 2:26again just the values of the same key
81. 2:29reduced by key means
82. 2:30each of those mach worker b's is only
83. 2:33going to get
84. 2:34all only get the values for a particular
85. 2:36key and what does it do with those two
86. 2:37values
87. 2:38it adds them up ladies and gentlemen
88. 2:42mic drop so not only are you 100 times
89. 2:44faster
90. 2:45but you can do in three lines what java
91. 2:47had to do in
92. 2:4945 lines pretty impressive so let's
93. 2:51actually play with it a little bit so
94. 2:53you can load this up i encourage you to
95. 2:54do this as well
96. 2:56this is i'm going to show you about what
97. 2:58um what flat map does i want
98. 3:00if you didn't know what flatmap does i
99. 3:01want to show explain them what it is and
100. 3:02why we knew we need that
101. 3:04so here's an example called neighbor
102. 3:05neighbor takes a number returns a list
103. 3:06of the number to the left
104. 3:08my number number to my right pretty easy
105. 3:10we start this by saying
106. 3:12sc spark context dot
107. 3:15paralyze range of five that says i'm
108. 3:18going to take
109. 3:19um the number zero through four
110. 3:21inclusive
111. 3:22and in some sense parallelize it load it
112. 3:24into its
113. 3:25uh rdd set into it into its the way it
114. 3:28stores data
115. 3:29into a parallel way it stores data okay
116. 3:31and call it r
117. 3:33now it's nothing's happened yet by the
118. 3:35way that didn't actually you know that
119. 3:37range i hope you know that the
120. 3:39difference between range
121. 3:41in python 2 versus python 3 is python 2
122. 3:45if you say range of a million it will
123. 3:47actually make a million list
124. 3:49and return it python 3 range says
125. 3:52yeah but what if you never use it that's
126. 3:54silly to make that million list range
127. 3:55but never use it so python 3
128. 3:57takes the lazy approach and returns a
129. 3:59promise here's range everything's a new
130. 4:01type called range of
131. 4:02i think it's called range of five range
132. 4:04zero five one maybe
133. 4:05and it says well that didn't do any work
134. 4:07it returns instantly
135. 4:09python two call range of a million and
136. 4:10see how long it takes call range of a
137. 4:12million on python three instantaneously
138. 4:14here's a promise for a range of a
139. 4:15million if you ever wanted them
140. 4:18and then if you say well let me iterate
141. 4:19well it's gonna one by one grab a value
142. 4:21from the range
143. 4:22hey range i need your next value range
144. 4:23okay here it is three
145. 4:25range i need a nice value here's four
146. 4:26that's how that works that's how lazy
147. 4:28evaluation works
148. 4:29same idea here in spark that range
149. 4:32didn't do any work so range returns a
150. 4:34promise that paralyzed into anywhere
151. 4:35because you never asked for it
152. 4:37only when you say collect are you saying
153. 4:39okay now you gotta
154. 4:40pay the piper where's your where's your
155. 4:42data
156. 4:43parallel says well where's the data who
157. 4:45recall it on oh range of five quick
158. 4:46range of five give some value range says
159. 4:48okay how much you need all of them great
160. 4:50and range will give you those values
161. 4:51only at that moment does range do any
162. 4:53work
163. 4:53and only that moment does the parallel
164. 4:55parallels do any work that's the idea
165. 4:56it's a very lazy system very clever that
166. 4:58way
167. 4:59it also means you might have delays like
168. 5:01there's like 20 commands like
169. 5:03why are they so fast yeah because
170. 5:04nothing's happened yet only when you say
171. 5:05collect
172. 5:06to say okay now i can do the work so
173. 5:07only on a collect we'll actually gather
174. 5:09this up and try to spit it back at you
175. 5:10it's really important idea that you
176. 5:11understand that
177. 5:12so now if i were to say r dot map of
178. 5:14neighbor it'd return
179. 5:16a list of five of these triplets right
180. 5:18the n minus one
181. 5:19n and n plus one but it wouldn't do it
182. 5:22until i say
183. 5:22collect if i just says r.map on neighbor
184. 5:25that's fine range could have been over
185. 5:2710 billion 100 billion
186. 5:29a trillion that r dot map of neighbor
187. 5:32would have instantly returned doing no
188. 5:33work
189. 5:33because it's not asked to produce
190. 5:34anything yet if you say collect it's
191. 5:36going to try to give it all and actually
192. 5:37try to
193. 5:38do its work so if i say art map neighbor
194. 5:40dot collect
195. 5:41it will give you that it will give you a
196. 5:42list of five sub lists
197. 5:45but i'm saying to myself i don't want
198. 5:46five sub i want one flat map i want one
199. 5:49flat list well that's what flatmap does
200. 5:53it's exactly the same idea as map except
201. 5:54it flattens whatever
202. 5:56sub-list came out of what map would have
203. 5:58given you it flattens those it's like it
204. 5:59appends them all together
205. 6:01so flat map returns the same thing as
206. 6:03map does except they're all flattened
207. 6:05does that make sense i teach you that
208. 6:07because we're going to see this as we
209. 6:08look at what word count does
210. 6:10when we play with word count we're going
211. 6:11to actually run let's do a slow motion
212. 6:13version of word count
213. 6:15in in in in spark so let's do this now
214. 6:18so here is word count in smart we saw
215. 6:20this already in one line where the
216. 6:21stephen colbert dropped his mic
217. 6:23but let's do a little bit slower this is
218. 6:25exactly the same data i showed you
219. 6:26before
220. 6:27literally to the to the to the letter
221. 6:29the same data these are the files
222. 6:33uh in the first one and then there's an
223. 6:36empty file on the second one that's just
224. 6:38all these are the same data before that
225. 6:39picture you saw earlier so the first
226. 6:41thing i say is
227. 6:42w for word count equals sc.text file i
228. 6:46give a text file
229. 6:47it then load that's like it's
230. 6:48parallelized but it's reading text files
231. 6:50rather than paralyzing a python
232. 6:52object first thing i say is
233. 6:56flat map again lambda line line dot
234. 6:58split and only if i say dot collectible
235. 7:01to print something out if i just did
236. 7:02that it wouldn't do normally give you
237. 7:03any output
238. 7:04but i say this and it gives me
239. 7:06essentially if it says i don't
240. 7:07what this what this flat map does again
241. 7:09it says i don't care what file this what
242. 7:11you came from
243. 7:11i want to just flatten you into one big
244. 7:13pool we call it a pool of words
245. 7:16okay one big pool of words so here we
246. 7:19are there's all the words i have
247. 7:21then i say flat map and by the way the
248. 7:22orange is the only thing that's new okay
249. 7:24so this this
250. 7:25all the white is the same i'm adding dot
251. 7:27map lambda word word of one
252. 7:29okay and what that's going to do is for
253. 7:31each of these words
254. 7:32i add i tag it one now that's new and
255. 7:34you've seen that before now three times
256. 7:36here
257. 7:36and now here's the key i add reduce by
258. 7:39key
259. 7:40lambda a b a plus b and this is
260. 7:42literally
261. 7:43i just copy and paste this yesterday
262. 7:44what you get from from
263. 7:46uh from spark and that's what you get er
264. 7:49and by the way these are in no no
265. 7:50particular order obviously they're not
266. 7:51alphabetized or anything but err is one
267. 7:53four oz two ifs uh three ors
268. 7:56and an uh that's my output
269. 8:00word count now i see i broke this into
270. 8:02pieces i probably could have done this
271. 8:03in one line i mean
272. 8:05you know this this sc.text file
273. 8:08is w i could have said that dot flat map
274. 8:11and then that dot
275. 8:13map and then that dot reduced by key the
276. 8:15same again one line like i showed you
277. 8:17before
278. 8:18pretty neat isn't that beautiful so
279. 8:20that's an example now you say well dan
280. 8:22is it faster
281. 8:23you sure did it in parallel while i did
282. 8:24this little thing that little baby thing
283. 8:26that's insanity check it
284. 8:27let's run this thing let's say i'm going
285. 8:28to crunch some numbers simulated
286. 8:29crunching a big number
287. 8:31i take a number n i'm going to be
288. 8:33chugging chugging chugging doing lots of
289. 8:34testing in here and bluebird
290. 8:36something it's going to take a long an
291. 8:37hour a long i mean five seconds i'm
292. 8:39saying
293. 8:40so i'm gonna actually say i'm gonna
294. 8:42sleep for five seconds and then return
295. 8:43the square of that number
296. 8:45so if i say crunch of ten it returns a
297. 8:48hundred
298. 8:49five seconds later by the way try this
299. 8:50yourself this trust me
300. 8:53if i then say map of crunch and range of
301. 8:56four so i'm going to square all the
302. 8:58elements from zero
303. 8:59zero through three um if i just say that
304. 9:01remember if i just say that what'll
305. 9:03happen is it'll say oh yeah i've
306. 9:04returned a map type
307. 9:05now i don't i want you to actually give
308. 9:06me the values so i have to say list that
309. 9:08to get the actual values
310. 9:09but it takes 20 seconds later there's
311. 9:11four elements there
312. 9:12four times five is 20 that's 20 seconds
313. 9:14later and that does take 20 seconds if
314. 9:15you time it
315. 9:17then i just for fun i say well let's try
316. 9:18it in sparks world
317. 9:20sc paralyze range of four fine
318. 9:25r dot map crunch collect
319. 9:28five seconds later five seconds later we
320. 9:31came up with that however so this is
321. 9:32like a little silly test
322. 9:34but now what's interesting is i have i
323. 9:36run this on an acorn machine
324. 9:38i would love to retest this and i want
325. 9:40you to play with this on your own
326. 9:41machines
327. 9:42please play with this to see well okay
328. 9:45how big can this be before
329. 9:48i only if i only have you know we know
330. 9:50we have hyper threading so maybe i have
331. 9:51eight cores that's 16 threads i can work
332. 9:53with
333. 9:54how how big is it before this stops
334. 9:57taking five seconds
335. 9:58so continue to change this the size of
336. 10:00this to see what happens and that's a
337. 10:02kind of a way to poke into your machine
338. 10:04and by the way when you instantiate
339. 10:05spark you can tell it how many
340. 10:07uh how many uh how many cores you want
341. 10:09to have how many parallel threads you
342. 10:10want to allow
343. 10:11so play with that play with that number
344. 10:13and see what happens as you change this
345. 10:14number to see if it's always five
346. 10:16seconds or when it when it gets
347. 10:17above five seconds but it's kind of neat
348. 10:18that this whole thing happened in five
349. 10:19seconds just as a standard check
350. 10:20to play with that so that's in this
351. 10:23lecture
352. 10:24fourth big idea that you've seen in this
353. 10:26course is parallelism we are hitting it
354. 10:28hard for many different ways in fact we
355. 10:29saw two of those ways
356. 10:31today data level parallelism and request
357. 10:33level parallelism
358. 10:34amdah's law is heartbreaking and
359. 10:36unfortunate but it's part of our reality
360. 10:38part as part of the by the way part of
361. 10:39the reality of not computer science this
362. 10:40is anything anything working in parallel
363. 10:42amdahl's law will affect that
364. 10:44and with again with infinite parallelism
365. 10:46speed up is one over s that's the
366. 10:47maximum
367. 10:48mapreduce is a wonderful abstraction
368. 10:51google uses it many many people yahoo
369. 10:53uses it uh
370. 10:54for for their big data processing uh it
371. 10:56is file based
372. 10:57spark does it even better and it's a
373. 11:00very fast growing
374. 11:01uh that the the number of developers
375. 11:04involved in spark is growing and by the
376. 11:06way
377. 11:07this makes you very marketable nudge
378. 11:09nudge wink wink say no more say no more
379. 11:11i encourage all of you to learn about
380. 11:12spark and be fluent in spark
381. 11:14play with play with it over the break
382. 11:16you add spark to this you say i can work
383. 11:18with big data
384. 11:19onto your resume you're you're looking
385. 11:21like a pretty good candidate
386. 11:23that's it we'll see at the next level
387. 11:24when we talk about cloud computing
388. 11:26pretty exciting
389. 11:27see you there