[CS61C FA20] Lecture 36.2 - MapReduce, Spark: Request-Level and Data-Level Parallelism — Transcript

Full transcript

1. 0:00and welcome back our next video is going
2. 0:03to talk about request level and data
3. 0:04level parallelism
4. 0:06you've seen this picture before we've we
5. 0:08keep revisiting it as we
6. 0:10continue to share the wonders of
7. 0:12parallelism in all its different
8. 0:13manifestations
9. 0:15today we're going to talk about two
10. 0:16elements one is the top most parallelism
11. 0:18which is parallel requests top level
12. 0:20idea that i'm going to search for cats
13. 0:22on a computer and how that works at the
14. 0:24top level we're also going to talk about
15. 0:26a model of computation called mapreduce
16. 0:29in which if i kind of think
17. 0:30functionally about my data i can think
18. 0:32of it by saying
19. 0:34i've got a array of a million numbers
20. 0:37i wouldn't mind being able to just say
21. 0:40add them all up however square them all
22. 0:42and then add them all up and i can think
23. 0:44of that
24. 0:45the abstraction allows us to be able to
25. 0:47deal with it from the programmatic
26. 0:48standpoint to just say square them all
27. 0:52done no loop square them all so i'm
28. 0:55thinking about
29. 0:56doing of some more than one data at a
30. 0:59time and up until now
31. 1:00you've thought about well that just
32. 1:01means semdi that means you're operating
33. 1:02on four vectors
34. 1:03four float you know a vector that's
35. 1:05wider maybe four floats wide and you say
36. 1:07add
37. 1:08that with another vector at the same
38. 1:10time that's what we used to think about
39. 1:11that box
40. 1:12but now we're going to think about that
41. 1:13box in an abstraction point of view
42. 1:15that that computation of squaring a
43. 1:18million numbers
44. 1:19could happen by me farming that out to a
45. 1:21million computers
46. 1:22or a million cores there's some models
47. 1:24where you have a million cores on one
48. 1:26computer
49. 1:27i farm it out somehow it gets
50. 1:30each one of these guys grabs a number is
51. 1:33it a core is it a computer who cares
52. 1:35each element each worker element will
53. 1:36grab the number square it and return it
54. 1:38instantly
55. 1:39and it all somehow magically comes back
56. 1:40to it so you can still think this this
57. 1:42kind of new abstraction allows you to
58. 1:44think in that model
59. 1:45where i was adding four i just said add
60. 1:48four vectors so i
61. 1:49even though i have four floats and i'm
62. 1:50adding to another to another flow i'm
63. 1:51just adding a vector to another vector
64. 1:53and it's really four floats being added
65. 1:54all at once that's really wonderful
66. 1:56the same idea in the abstraction idea of
67. 1:59working with parallel data pretty neat
68. 2:00so
69. 2:00we're going to talk about some very
70. 2:01powerful abstractions in this series of
71. 2:03lectures
72. 2:05so what's request level parallelism if
73. 2:07you've ever thought about what web
74. 2:08servers have to handle
75. 2:09this is request level parallelism um
76. 2:11just hundreds or thousands of requests a
77. 2:13second and when that
78. 2:15that number exceeds what the machine can
79. 2:17handle it becomes a distributed
80. 2:19a ddos attack it becomes an attack that
81. 2:21the system is now
82. 2:22pinned just trying to breathe and trying
83. 2:24to move around and just enough
84. 2:26enough denial of service uh requests you
85. 2:29can make a denial of service
86. 2:30attack and distribute this with a lot of
87. 2:32computers all focusing on one server
88. 2:34by making it try to deal with that so
89. 2:36when it's in this comfort zone that's
90. 2:37what we're talking about but you can
91. 2:38exceed that to get to this and you'll
92. 2:40learn about this in 161 a denial of
93. 2:42service attack
94. 2:43so imagine you're a server and your job
95. 2:46is to just
96. 2:46you know react to requests and you can
97. 2:48make it by the way it's really fun to
98. 2:50make your own web server
99. 2:50i encourage you to think about that make
100. 2:52a web server that serves some
101. 2:53interesting data maybe you have a
102. 2:54some sensor that's doing something fun
103. 2:56or taking a picture or doing something i
104. 2:57don't know
105. 2:58measuring something in your house how
106. 2:59much a plant grows and make a server
107. 3:01that'll be able to respond to an attack
108. 3:03onto it
109. 3:03respond to request and give the data
110. 3:05here's how big the plant has grown today
111. 3:06or
112. 3:07here's what my camera is seeing play
113. 3:08with that it's fun to explore that now
114. 3:10that you're all kind of becoming more
115. 3:11more fluent computer scientist and
116. 3:12and hackers and simpsons play with that
117. 3:14it'd be fun to do
118. 3:16so each of these requests is largely
119. 3:18independent if you were to release your
120. 3:19plant growing
121. 3:20uh data service to the world you might
122. 3:23have people all around the world
123. 3:24and even for you know from the space
124. 3:27station
125. 3:28hitting your server asking for i want to
126. 3:30know how tall that plant is right
127. 3:32now kind of exciting but one of the
128. 3:35elements of this is all these requests
129. 3:36are mostly independent
130. 3:37and maybe it's you know one person you
131. 3:39know hitting it a lot because they want
132. 3:41to
133. 3:41chart a graph and so they're hitting it
134. 3:42maybe your service also lets you query
135. 3:44past growth values and so you've you've
136. 3:46made a little table and so you're able
137. 3:48to get the current growth value maybe
138. 3:49past ones so maybe someone's going
139. 3:51sweeping through all the valid dates and
140. 3:53kind of hitting years a lot but most of
141. 3:54the time they're largely independent
142. 3:57most of the time these are reading from
143. 3:59large databases or large data
144. 4:01data centers some some way you're
145. 4:03collecting and serving data again you'll
146. 4:05learn this in cs186
147. 4:06if you ever wanted to learn about how to
148. 4:07build one of these uh officially but you
149. 4:09can
150. 4:10probably roll your own pretty easily as
151. 4:12well
152. 4:13they rarely involve it it says strictly
153. 4:15uh read write data sharing or
154. 4:17synchronization across requests so
155. 4:18mostly these are just
156. 4:19lots of lots of these requests happening
157. 4:21at once and mostly their reads mostly
158. 4:23their read sometimes they're rights but
159. 4:24mostly their reads
160. 4:26if you're handling a piazza who handles
161. 4:28piazza think about all the services you
162. 4:30use that are
163. 4:31read write you know facebook piazza i'm
164. 4:33editing something and i want it to be
165. 4:34stored and seen be seen around the world
166. 4:36um that cloud software which we'll learn
167. 4:40a little bit about how the how how cloud
168. 4:42warehouse scale computing works another
169. 4:44lecture
170. 4:44um certainly there are if you have new
171. 4:47web services you're not just read-only
172. 4:48you're
173. 4:49able to interact in a social media way
174. 4:50so that's important too and obviously
175. 4:51there are rights there as well
176. 4:54the competition is easily partitioned
177. 4:55within a request and across different
178. 4:57requests so
179. 4:58these things you know each one can be an
180. 5:00atomic request now
181. 5:01a person says type this new in and hit
182. 5:02edit and by the way you might have seen
183. 5:04this
184. 5:04before where two people are editing the
185. 5:06same piazza post and they'll say oh
186. 5:07there's a conflict because both of you
187. 5:09are trying to hit the same thing there's
188. 5:10got to be a way to handle these
189. 5:11in a way a race condition who's who gets
190. 5:13to write it first and piazza does a nice
191. 5:15way
192. 5:15that has a night just a nice job so it's
193. 5:17been bringing it already if ever there's
194. 5:19a question on an exam
195. 5:20and many of the tas try to answer the
196. 5:21question i'll get that i've gotten that
197. 5:22several times this semester
198. 5:24so this software still has to be able to
199. 5:25resilient to that kind of a thing as
200. 5:26well
201. 5:28here's an example of google's query
202. 5:30serving architecture
203. 5:31you hit the google uh web server and the
204. 5:34first thing it does is do a spell
205. 5:36checker and grab some ads
206. 5:38i mean the ads are the most important
207. 5:39thing from google's point of view
208. 5:40because that's where the monetization is
209. 5:42you search for i want to find the best
210. 5:44shoes in berkeley
211. 5:45well you bet bet your bet your bottom
212. 5:48dollar that somebody
213. 5:49who sells shoes around berkeley is
214. 5:52is it would be incentivized to pay
215. 5:55google so that
216. 5:56their possible research you know return
217. 5:59uh um or the link to their to their
218. 6:02company
219. 6:03shows up very early uh and there's a
220. 6:05there's a whole way that i if i if i
221. 6:06really need to
222. 6:07you know my my funders have told me i
223. 6:09need to ramp up my sales because of
224. 6:12something
225. 6:12and so i'm gonna pay google a little bit
226. 6:14more money so it's more prominent or it
227. 6:15comes up in
228. 6:16even you know farther away searches even
229. 6:18how about sneakers well i've never had
230. 6:20to pay to get into the sneakers there so
231. 6:21ad serving is
232. 6:22really important there it first has to
233. 6:24go and look up its index it's already
234. 6:26built
235. 6:26by the way many people naively think
236. 6:28that when you type something it then
237. 6:30starts to search the web it doesn't at
238. 6:31all it's been crawling the web
239. 6:32continuously
240. 6:33building a huge index a huge
241. 6:37index database um and so it knows where
242. 6:40the documents might live this index
243. 6:42servers
244. 6:42by the way notice that they're in
245. 6:43parallel this this is drawn that way to
246. 6:45indicate
247. 6:46that there are a lot of these guys um
248. 6:48there's no way that this is hitting one
249. 6:50really fast machine this is hitting a
250. 6:52lot of machines and they're coming back
251. 6:53and it's being
252. 6:54aggregated so kind of the interesting
253. 6:56part is what's happening here how is it
254. 6:58being aggregated
255. 6:59through those all requests coming back
256. 7:01in so here's your
257. 7:03page and i got okay great and i'm going
258. 7:04to grab a document and click on this and
259. 7:06i might the document might get fred from
260. 7:07there as well and returned as well
261. 7:09so exciting that google certainly has an
262. 7:11architecture that has
263. 7:12a front page it's doing spell checking
264. 7:15it's serving it sad that's a really big
265. 7:17deal
266. 7:17um bringing up its index to find out
267. 7:19what the what the list is of your
268. 7:21of your possible links to there as well
269. 7:23as documents that's being stored and
270. 7:24being
271. 7:25informed to feed the index servers as
272. 7:28well
273. 7:30data level parallelism you've seen a
274. 7:31little bit before there's data in memory
275. 7:33you've got a little bit you've got an
276. 7:34array and i want to be able to
277. 7:36attack this with um all the cores i have
278. 7:39to attack and so that's very very common
279. 7:42what you haven't seen so much of that
280. 7:43we're going to introduce in these series
281. 7:44of lectures is data across many disks
282. 7:46i've got this massive we call this big
283. 7:48data i've got this so big data's so big
284. 7:49i can't fit it in memory i have to fit
285. 7:51in a disc i can read a portion into
286. 7:52memory and work with it but that's the
287. 7:53biggest i can do it
288. 7:54so how would you be able to even if the
289. 7:56not just in one disk
290. 7:58one big let's say raid disk you don't
291. 8:00know what rate is yet but one big
292. 8:02set of disks on my computer that looks
293. 8:04as maybe one virtual disk but actually
294. 8:06as many disks as an abstraction
295. 8:08but no it's so big that it can't even
296. 8:09fit in one disk it has to fit on many
297. 8:11disks and maybe those things live in the
298. 8:13disks live in the cloud so that's called
299. 8:15cloud storage
300. 8:16how would you boy it would be nice it'd
301. 8:18be sure nice if we had an abstraction to
302. 8:20be able to
303. 8:20type some commands and have it be able
304. 8:22to work over those disks
305. 8:24that's we're going to teach in these
306. 8:25next series of lectures matt produces
307. 8:26this wonderfully powerful idea
308. 8:29um an abstraction a software
309. 8:31infrastructure and open source software
310. 8:32infrastructure now thankfully
311. 8:34that we can all play with all experiment
312. 8:35with that lets you work across many many
313. 8:37disks
314. 8:38it's a file to file model it's very very
315. 8:40exciting
316. 8:41so today's lecture and series of
317. 8:43lectures is about
318. 8:44mapreduce and an implementation of that
319. 8:47which is really
320. 8:47quite clever called spark as well so
321. 8:49we'll see the next couple of lectures
322. 8:50and we'll see you there