The Genius System Behind the Uber App’s Real-Time Map — Transcript

Full transcript

1. 0:00We've all done it. You open the Uber
2. 0:01app, enter your location and desired
3. 0:03destination, and then click a button to
4. 0:04get a ride. From this point on, two
5. 0:07things happen. On the one hand, your
6. 0:09location as the rider is shared with
7. 0:11Uber. And on the other hand, nearby
8. 0:13drivers positions are shared with you.
9. 0:15And what seems like such a simple thing
10. 0:17comes with massive complexities on
11. 0:19Uber's end to make this system work
12. 0:21fluently for hundred millions of users.
13. 0:24How does the Uber app on back end really
14. 0:26achieve to update it so fluently for
15. 0:28this many drivers even in bad network
16. 0:30conditions? Let's take a look. Uber must
17. 0:32keep millions of driver devices, rider
18. 0:35devices, and backend services in sync in
19. 0:37near real time. And originally, Uber
20. 0:39stick to an approach that ended up
21. 0:41getting them into huge problems. Back
22. 0:43then, they've actually implemented a
23. 0:44polling based approach where the app
24. 0:46simply asks the server for new data. So
25. 0:48in a simple loop, the client has asked
26. 0:50the server things like, "Hey, are there
27. 0:52new locations for nearby drivers? Are
28. 0:53there new locations? Are there new
29. 0:55locations?" So this was Uber going full
30. 0:57founders mode. But it was clear that
31. 0:59this approach won't scale. On the one
32. 1:01hand, every polling request made that
33. 1:03way that does not result in new data for
34. 1:06the client is in the end unnecessary
35. 1:07load for the server. It also drains a
36. 1:09lot of battery. It comes with a lot of
37. 1:11overhead because every polling request
38. 1:13adds additional headers to the request.
39. 1:15And what this has led to at some point
40. 1:17is that 80% of network requests made to
41. 1:19Uber server from the app were polling
42. 1:21calls. It has also made the cold startup
43. 1:24time of the app skyrocket because
44. 1:26multiple concurrent polling calls were
45. 1:28competing which prevented the app from
46. 1:30rendering UI because the data came from
47. 1:32the polling calls. And as a result of
48. 1:33these polling problems, Uber has moved
49. 1:35to a pushbased communication approach.
50. 1:38So instead of the client asking for new
51. 1:40data, the server now pushes it to the
52. 1:43client once it's available. And for that
53. 1:45they've created ramen. Okay, not
54. 1:47actually instant noodles. Ramen stands
55. 1:50for realtime asynchronous messaging
56. 1:52network. And in theory this works much
57. 1:55better, but still comes with challenges.
58. 1:58So now instead of the client blindly
59. 1:59asking for new data, they needed logic
60. 2:02deciding when to push, what to push, and
61. 2:05how to push that data to the client. And
62. 2:07for a scaling infrastructure, they
63. 2:09decided to separate these three
64. 2:11responsibilities. First of all, they've
65. 2:13introduced Firewall, which is a micros
66. 2:15service responsible for the decision
67. 2:16behind when to push. So, it's really
68. 2:19just a service that listens to all kinds
69. 2:20of different events and then decides if
70. 2:22it's worth pushing an update to the
71. 2:23client. So, these events could be a user
72. 2:26requesting a ride. This could be a
73. 2:28driver accepting a ride. It could be a
74. 2:30new location of a rider or a driver. And
75. 2:32while locations may change very
76. 2:34frequently, not every little change
77. 2:36definitely has to be sent. So Fireball
78. 2:37may compare a new location with a
79. 2:39previous one and only send the new one
80. 2:41if it has changed enough, for example.
81. 2:43[music] And when Fireball then decides
82. 2:45that a push should happen, it takes this
83. 2:47information and it sends it to Uber's
84. 2:48API gateway. This gateway now has the
85. 2:51purpose to take a look at that minimal
86. 2:53push data and gather the entire data
87. 2:55necessary for the client. For example,
88. 2:57the users locale, the operating system
89. 2:59they use, and so on. Finally, the client
90. 3:01then connects directly to the ramen
91. 3:03server, which pushes the determine
92. 3:05payload to the client. How does Ramen
93. 3:07actually work internally? Well,
94. 3:08originally it was built on top of SS.
95. 3:11So, server sent events and ramen is in
96. 3:13the end just a protocol, a technology
97. 3:15built on top of that that makes sure
98. 3:17that at least once delivery is
99. 3:18guaranteed. So that events being pushed
100. 3:20to the client will definitely also
101. 3:21arrive there. Nowadays, however, they've
102. 3:23migrated it to use gRPC as it allows
103. 3:26sending messages from both client and
104. 3:28server. So, it's not just a pushbased
105. 3:30approach anymore where just the server
106. 3:31can push data to the client at any time,
107. 3:33but the client can also share data with
108. 3:35the server that way. So this
109. 3:36infrastructure now allows Uber to push
110. 3:38data to clients efficiently. However,
111. 3:40there was still a big challenge. Uber in
112. 3:42the end receives realtime updates for
113. 3:44millions of locations around the world
114. 3:47every minute. So how do you actually
115. 3:49send just the locations a specific
116. 3:51client cares about? So exactly those of
117. 3:54nearby drivers of that client app? One
118. 3:56approach you may think could work is to
119. 3:57simply take a look at the riders
120. 3:58position and then calculate the distance
121. 4:00to all drivers positions to only show
122. 4:02those in a given [music] radius. But as
123. 4:04you can imagine, at high scale,
124. 4:06calculating millions of distances for
125. 4:08millions of active riders results in
126. 4:10unmanageable load for the server. So
127. 4:12instead, Uber actually came up with a
128. 4:15much much more genius approach called
129. 4:17spatial partitioning. And the idea
130. 4:19behind that is really to take a
131. 4:20geographic space and then divide it into
132. 4:22smaller regions where we can then take a
133. 4:24driver's position and map it to a clear
134. 4:26region. since this way we don't have to
135. 4:29calculate millions of distances anymore
136. 4:31but just check which drivers are in our
137. 4:33region and the ones around it. Splitting
138. 4:36up the world into squares however has a
139. 4:38major problem and it is that squares
140. 4:41don't have the same distance to all the
141. 4:43neighbors which can lead to what we call
142. 4:44corner bias since squares diagonal to
143. 4:47the one you're looking at are further
144. 4:49away than squares to the top of it or to
145. 4:51the left and right. Wouldn't it be much
146. 4:53better if we could simply query nearby
147. 4:55drivers based on at least an approximate
148. 4:57radius? And that is why Uber has created
149. 4:59H3, which is an open-source hexagonal
150. 5:02spatial index. So instead of dividing
151. 5:04the world into squares, it divides it
152. 5:06into a honeycom of hexagons, each really
153. 5:09having the same distance to all of its
154. 5:11neighbors. So given any GPS coordinate,
155. 5:13H3 computes which hexagon it's in, and
156. 5:16then returns that H3 index. And instead
157. 5:18of computing distances for every driver,
158. 5:20you instead ask for the so-called K
159. 5:22ring. So those hex's within K steps of
160. 5:25your rider cell. So for example, if K is
161. 5:28equal to one, then that includes the
162. 5:29first layer of neighbors making up seven
163. 5:31cells in total. If K is equal to two,
164. 5:33then the second layer of neighbors is
165. 5:35also included. And this new system
166. 5:37effectively brings down the time
167. 5:39complexity from O of N where N could
168. 5:42literally be millions of active drivers
169. 5:44to O of K^ squ plus O of M where K is
170. 5:48the radius and M is the number of nearby
171. 5:50drivers.
172. 5:51So this means if there are 100 nearby
173. 5:53drivers, Uber now only has to iterate
174. 5:55over those 100 drivers instead of
175. 5:57possibly millions. And the genius thing
176. 5:59behind this new strategy is not just
177. 6:02that it can be used for finding nearby
178. 6:04drivers, but actually for so so much
179. 6:06more that is important to Uber. [music]
180. 6:08For example, to create dynamic pricing
181. 6:10zones for predicting the estimated time
182. 6:12of arrival or for things like
183. 6:14forecasting demand. And now that spatial
184. 6:17index helps Uber to really optimize load
185. 6:19on the server side since when receiving
186. 6:21a rider's location, the server can now
187. 6:22look up nearby drivers positions much
188. 6:24faster and therefore give the client a
189. 6:26faster response. This however is only
190. 6:28one side of the metal. Especially with a
191. 6:30mobile app, you can't count on its
192. 6:32internet connection being super stable
193. 6:34at all times. And in the case of a ride
194. 6:36sharing app like Uber, it's completely
195. 6:37expected that most people using it
196. 6:39aren't at home and therefore likely
197. 6:41won't connect via stable Wi-Fi
198. 6:42connection, but much more likely a
199. 6:44cellular one. So, how did Uber's
200. 6:46engineers optimize the mobile app to run
201. 6:48super smoothly even under bad network
202. 6:51conditions? And here there are two
203. 6:52things that have to be looked at. First
204. 6:54of all, how do we actually minimize the
205. 6:56network latency between mobile app and
206. 6:58server? And second, how do we make sure
207. 7:02the app still feels fluent even when not
208. 7:04receiving many GPS updates? Let's start
209. 7:06with keeping network traffic fast. Here,
210. 7:09Uber actually sticks to so-called edge
211. 7:10servers. And those are really nothing
212. 7:12else than hundreds, if not thousands of
213. 7:14servers spread around the globe where
214. 7:16each server is responsible for nearby
215. 7:18users. So instead of a user in Berlin
216. 7:21talking to a server in California, Uber
217. 7:23instead uses service relatively close,
218. 7:25for example, in Frankfurt. And these
219. 7:26edge servers then not only serve as a
220. 7:28primary entry point for requests for
221. 7:30nearby drivers and users, but also cache
222. 7:32all kinds of relevant data, so data
223. 7:34access is even faster. And when
224. 7:36considering a typical 4G connection,
225. 7:38this change alone can result in requests
226. 7:40being approximately 100 milliseconds
227. 7:42faster when talking to a closed local
228. 7:44server versus one that is 10,000 km
229. 7:47away. However, even with closed servers,
230. 7:49there is no guarantee that new location
231. 7:51data arrives reliably at the same
232. 7:52intervals. [music]
233. 7:53In mobile apps, you in the end always
234. 7:55need to account for connection drops at
235. 7:57any time. So, let's imagine the Uber app
236. 7:59now receives three location updates from
237. 8:00a driver over the period of 20 seconds.
238. 8:03Our goal is now to not make the location
239. 8:05jump from one coordinate to another when
240. 8:07a new location is received from the
241. 8:08server. So instead, we need a way to
242. 8:10take a look at a few known locations and
243. 8:12use that information to kind of predict
244. 8:14what is likely the new current location
245. 8:16of the driver, even if it doesn't send a
246. 8:19new one. And for that, Uber uses what we
247. 8:21call that reckoning, which really tries
248. 8:23to predict where the driver should be if
249. 8:26they kept the last known speed and
250. 8:28direction. This is then used in
251. 8:29combination with so-called Kelman
252. 8:31filters, which combines these predicted
253. 8:33coordinates with real measured
254. 8:34coordinates. [music] And that's in the
255. 8:36end what makes the car marker move
256. 8:38around smoothly even when a new measured
257. 8:40coordinate is quite different than the
258. 8:41last predicted one. But I actually also
259. 8:43have something for the conspiracy
260. 8:44theorists among you. There are actually
261. 8:46claims and discussions about Uber
262. 8:48showing fake cars in the mobile app.
263. 8:50cars that don't even exist. Because if
264. 8:52we think about it, for cars that don't
265. 8:54even exist, [music]
266. 8:55you obviously don't have to listen to
267. 8:57serverside location updates, and you
268. 8:59could also artificially make more
269. 9:01drivers appear to riders to not show
270. 9:03them a dead area, which may make them
271. 9:04open a competitor's app. This phenomenon
272. 9:06of phantom cars is however something
273. 9:08that Uber denies. But what this shows is
274. 9:10that most simple looking interfaces
275. 9:12often have the most complex back ends,
276. 9:14especially when things really have to
277. 9:16scale. And with this video, I really
278. 9:17tried something new here and a lot of
279. 9:19work went into this video and that is
280. 9:21why I need your feedback here. Is there
281. 9:23anything that wasn't clear? Uh would you
282. 9:24like to see more such videos every now
283. 9:26and then? And if so, which app would you
284. 9:28like me to take a look at next? So, if
285. 9:30mobile development and especially with
286. 9:31cotton is a thing for you, then
287. 9:33subscribe for all kinds of in-depth
288. 9:35tutorials about that. Thanks so much for
289. 9:37watching. I will see you back in the
290. 9:38next one. Have an amazing rest of your
291. 9:39week. Bye-bye.