YT YouTube2Text

YouTube2Text → Transcripts → Basic System Design for Uber or Lyft | System Design Interview Prep

Basic System Design for Uber or Lyft | System Design Interview Prep — Transcript

by Interview Pen · 3,727 words · 511 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00So today we're going to be learning how
0:01to build a ride sharing service
0:03something like Uber or Lyft some basic
0:06requirements for something like this is
0:07the writer needs to be able to pick a
0:09point on a map and they need to be able
0:11to view the ETA and the price at that
0:13time once they're ready to call the ride
0:15they need to be able to pay the rider
0:16needs to be able to be matched to a
0:18driver and then the driver needs to be
0:19able to accept the ride and finally the
0:21rider needs to receive information about
0:23the driver such as their type of their
0:25car so they can recognize them and then
0:27the driver's location needs to be sent
0:29to the rider in real time so taking a
0:30look at how we're going to structure a
0:32system like this we of course need the
0:34drivers and the Riders and we need a
0:36database to store all the information
0:37about them and the trips that they're
0:39making and then taking a look at our
0:41requirements there's some other services
0:42that we're going to need first things
0:44first we're going to need a map so that
0:45we can serve maps to the user we're
0:48going to need a service that knows the
0:50ETA so we need a ride service that can
0:52calculate the ETA and has information
0:54about the locations of every driver
0:56we're going to need a pricing service
0:58which is going to calculate the price
0:59pricing based on load the writer is
1:01going to need to pay for their ride so
1:03we need a payment service and the
1:04drivers and riders need to be matched
1:06together so we'll introduce a service
1:07that can handle that putting this all
1:09together if each service was responsible
1:11for sending updates to every other
1:13service that needed information about it
1:15this would be pretty difficult to do and
1:17you can see just by the lines I'm
1:19drawing that this gets pretty messy this
1:21tightly couples all of our systems so
1:22for example when a rider requests a ride
1:24it would need to go out to the matching
1:26service to get matched to a driver go
1:28out to the pricing service so the
1:30pricing service can update its price by
1:31load it would need to update that in the
1:33database and then when the driver
1:35approves it would need to send that
1:36approval to the rider and to the ride
1:38service etc etc etc and this is pretty
1:41difficult to maintain if you're enjoying
1:42this video we have plenty more awesome
1:44data structure algorithm and system
1:46design explanations on interviewpen.com
1:48you can ask us any questions you have
1:50about any kind of topics surrounding
1:52data structures and algorithms and
1:53system design we released two to four
1:55videos a week you can run your code you
1:57can talk to a personalized AI teaching
1:58assistant and yeah the size pretty great
2:00anyway enjoy the video so in order to
2:02solve these issues we're going to
2:03introduce an event bus the event bus can
2:05be implemented just with Kafka and
2:07essentially what it's going to do is
2:09take information about our Riders and
2:11our drivers and any real-time updates
2:13that they make and then any service that
2:15needs access to that information can
2:17just subscribe to the event bus and get
2:19that data so this makes things a lot
2:20cleaner and much easier to maintain as
2:23we're building out each of these systems
2:24so now that we know what sort of
2:26problems we're solving and the high
2:27level structure of this system let's
2:30take a look into each one of these
2:31issues and see how we can solve this
2:33problem so first let's take a look at
2:35our Rider and our driver apis so a
2:37couple of things that we need to
2:38consider when we're building these out
2:39is we need to be able to handle a very
2:41large number of users accessing these
2:43apis there's going to be a lot of users
2:45on our platform and each one of them is
2:47going to be making multiple requests to
2:49these apis every single time they make a
2:51trip so we need to be able to handle
2:53that load to do that we're going to
2:54introduce a load balancer in front of
2:56each of these apis and then we can
2:57horizontally distribute our API onto
2:59multiple notes the next thing to
3:01consider is that there's a lot of
3:02real-time data going on here so for
3:04example the driver needs to update the
3:07location and the rider needs to receive
3:08updates about that location change in
3:11real time so one option for this would
3:12of course be HTTP polling so the writer
3:14could simply go out to our API say every
3:17two seconds and then once the driver
3:19updates the location the writer would
3:21eventually receive that update this
3:22introduces a couple of problems the
3:24first one is there's latency on the
3:26rider's side so the driver updates the
3:28location we now have to wait two seconds
3:30for the next time the rider pulls the
3:32API in order to get that location update
3:34and the other problem that's perhaps
3:35more important is that this introduces a
3:37huge amount of load on our Rider API
3:39because now every single user that's
3:41using our app now has to pull this API
3:44every two seconds we have to scale this
3:45API to be huge in order to handle that
3:48amount of load so a much more scalable
3:49solution to this problem would be to use
3:51web sockets websockets enables our Rider
3:53app to maintain a persistent connection
3:55with our API and the API can actually
3:57push data back down to the app this
3:59means that when the driver updates their
4:00location for example the rider can
4:02simply receive that update immediately
4:04by pushing the data to the app so taking
4:07a look back at our high level overview
4:08we can see we've swapped out our API for
4:11our completed solution so now let's take
4:13a look at the next piece of the puzzle
4:15which is the database there's a few
4:16things that our database needs to hold I
4:18used to hold information about the
4:20driver and the rider so they can see
4:21their own information and also
4:23information about each other once
4:24they've been matched and we also need
4:26information about each trip so drivers
4:28and Riders will likely want to see their
4:29own trip history and we need to be able
4:31to use this record in order to
4:33coordinate things like matching a driver
4:35to a rider or coordinating a pickup
4:37location so for every user we need a
4:39phone number and a name of course and
4:42we'll also need an email and a password
4:43hash that we can use to identify the
4:45user when logging them in for a rider
4:47we'll of course need payment information
4:48so that they can quickly pay for their
4:50ride and on the driver's side we'll need
4:52the ride type so for example Uber has
4:54uberX and Uber black so we need to be
4:56able to know which designation this
4:58driver is so we can specify the price
5:00and we also need information about their
5:02car so that the rider can identify them
5:04and finally we need the last known
5:06location of the driver so that when the
5:08rider opens the app they can immediately
5:10see that last location on a map then for
5:13each trip we need the rider ID and
5:15Driver ID that that trip has been
5:17assigned to we need the price and the
5:19location and destination of the trip
5:20along with a date we'll also need the
5:22ride type so we can assign the rider the
5:25correct driver and we'll also want to
5:27include a status that says whether the
5:28drive is in progress canceled completed
5:31waiting for a driver Etc so I start here
5:34things that we'll need to query by so of
5:36course a driver will need to see its own
5:38information and the writer will also
5:40need to be able to see its own
5:41information furthermore for a trip we'll
5:43want to be able to find the trips that
5:45are associated with a specific driver or
5:46a specific Rider we'll also want to be
5:48able to look up status but only in the
5:50context of a specific driver or Rider ID
5:53so for example a common query pattern
5:55would be show me all of the in-progress
5:57trips associated with this driver so
5:59let's take a look at how we'll actually
6:00structure our database given that
6:02information it's important to know that
6:03this is going to be a very high traffic
6:05database drivers and writers are going
6:07to be constantly updating this data as
6:09their ride progresses and furthermore
6:11the driver is going to be sending
6:12frequent location updates that need to
6:15be persisted to the database every
6:16couple of seconds so it's really
6:18important that we scale our database
6:19horizontally and the easiest way to do
6:21that is with sharding the way sharding
6:23works is essentially that we can split
6:25our data onto multiple nodes and each
6:27node can hold a subset of the data in
6:29order to determine which node our data
6:31is actually stored on we can use a Shard
6:33key when you're looking for a Shard key
6:34it's important to have high cardinality
6:36and low frequency and that allows the
6:38data to be efficiently split across
6:39multiple partitions so for our trips and
6:42for our drivers and Riders we'll use ID
6:44and since this is a unique identifier
6:46for the trip or driver or Rider this
6:49satisfies both of these requirements
6:50furthermore this allows us to quickly
6:52look up a record by ID because looking
6:55at the ID we can immediately determine
6:57which of these nodes the data is on and
6:59look up their record very quickly
7:00however we still need to search for
7:03driver ID and writer ID on our trip so
7:05in order to do that we're going to
7:06introduce a global index the global
7:08index is essentially just another
7:10Charlotte database where each record
7:11contains the ID that we're going to
7:14index on and a reference to the main
7:17table so for these two Global indexes
7:19we'll have one that's sharded by driver
7:22ID and one that's started by Rider ID
7:24and then within each of these partitions
7:25we can actually sort the data by the
7:27status and that will allow us to quickly
7:29look up by status so to give an example
7:32if we're looking for in-progress trips
7:34with a specific driver ID we can use
7:36that driver ID to immediately determine
7:38which node the data is stored on and
7:40then since the data is sorted within
7:42that partition we can then find the
7:44records with a specific status very
7:46quickly let's take a look back at our
7:47high level overview again we can see
7:49that our database is now including our
7:51trips database our writer database and
7:53our driver database along with the
7:55indexes that we need to efficiently
7:56access that data now taking a look at
7:58the next piece of the puzzle we we can
8:00look at the map and payments
8:01infrastructure and see how those will
8:02work first let's take a look at the map
8:04there's a few key jobs that the map
8:06needs to perform the first one is it of
8:07course these just serve map images to
8:09the user it needs to perform geocoding
8:12which means it's converting a street
8:13address into a latitude and longitude
8:15that will allow our users to actually
8:17look up a location that they're going to
8:19drive to without having to enter a
8:21specific latitude and longitude for that
8:23location and we also need to be able to
8:24get directions and that will allow our
8:26drivers to pick up our Riders and know
8:28where to go now we could build our own
8:30map service however there's a bunch of
8:33other services out there that already do
8:35this such as mapbox and Google Maps so
8:37we'll just use one of those for this
8:38example taking a look at our payments
8:39infrastructure the writer of course
8:41needs to pay for their rides the driver
8:42needs to get paid and in order to do
8:44this we could again build our own
8:46payments infrastructure or we could
8:47simply use one of many solutions out
8:49there such as stripe if you're
8:50unfamiliar with stripe the way that it
8:52works is a user can push a payment to
8:55stripe and then once the payment
8:56finishes processing stripe will call a
8:58web hook that we set setup so in our
9:00situation the user is going to pay for
9:02their ride stripe will send an update to
9:04this web hook and then our web hook will
9:05add an event to our Kafka event queue so
9:08that we can continue processing the ride
9:10so looking at this entire thing in
9:12context we can see that we're using
9:13mapbox for our map service and we can
9:15see that stripe and our web hook are
9:17then pushing information to our Kafka
9:19event bus you'll notice that all of
9:21these services are attached to the
9:23client side of our Rider and drivers and
9:26that's because stripe and mapbox are
9:27both designed to interact directly with
9:29a client for the map of course there's
9:30no authorization necessary because it's
9:32all it's doing is serving map tiles and
9:35looking up locations and for stripe any
9:37processing that we'll do to make sure
9:39that the user paid the right amount for
9:41example will be done within this web
9:42hook so the next problem we need to
9:44solve is the pricing model so pricing
9:46for Uber for example varies by demand
9:48they call this surge pricing at Uber the
9:51way it works is essentially if there's
9:53higher demand in an area for example a
9:55concert just ended and 200 people are
9:58all trying to call an Uber were from the
10:00same location they're actually going to
10:01increase the price in order to take
10:03advantage of the higher demand so in
10:04order to actually calculate price in
10:06this situation we need information about
10:08demand and processing every trip in
10:10batch would be far too slow for us so
10:12let's take a look at how we can
10:13Implement a streaming pipeline to make
10:15this actually work so our price API of
10:17course needs to be able to get
10:18information about demand and we're going
10:20to store that demand in a redis
10:22in-memory database so we can access it
10:24very quickly then in order to get the
10:25demand data into redis we're going to
10:27use spark spark if you're unfamiliar is
10:29a distributed data analytics engine and
10:32it essentially allows you to take in a
10:33data set and then perform various
10:35queries on it such as filtering sorting
10:38aggregating grouping and joining things
10:40together if you've ever used the pandas
10:43python Library spark is a lot like that
10:45except that it allows jobs to be
10:46distributed across a bunch of workers so
10:48the way we're going to use spark is with
10:50a separate feature that it has called
10:52structured streaming structured
10:53streaming allows spark to subscribe to a
10:56Kafka event bus and then whenever it
10:58receives an event it will process that
11:00in a streaming fashion and then push the
11:03resulting data to some other data source
11:05so for our example we'll have ride
11:07requests that are an event in our Kafka
11:09event bus spark will subscribe to those
11:11events aggregate them based on time and
11:13location and push them to this redis
11:15database so taking a look at our whole
11:17solution now we can see that spark is
11:20now subscribed to our Kafka event bus we
11:22can see that our drivers can now access
11:25this price API to get access to the
11:28calculated price given the load and our
11:31drivers can now access the pricing API
11:33which will calculate the price based on
11:35load so now let's finally take a look at
11:37the last piece which is the rides and
11:39matching services so for rides there's a
11:41couple of very simple things that it
11:42needs to do it needs to efficiently find
11:44drivers in a given area and it needs to
11:47calculate the ETA for the ETA that's a
11:49pretty simple problem we just need some
11:51sort of service that can make that
11:52calculation we could either build our
11:54own service that takes into account
11:55demand and other characteristics about
11:57the driver or we could simply use mapbox
12:00or Google Maps like we showed in the map
12:02service for driver locations however
12:04this is an interesting problem we don't
12:06know the exact location of the driver
12:08we're looking for we only know that we
12:09want to find one that's in some radius
12:11of where the rider is so we can't just
12:14index based on the exact location we
12:16need some way to index off of an area so
12:18to do that we're going to use an
12:20algorithm that Uber developed called H3
12:22and what H3 does is it splits the world
12:25into a bunch of hexagonal areas and it
12:27assigns an ID to each one of these cells
12:30then it groups all of the drivers into
12:32these cells so we can efficiently look
12:34up a specific cell and all the drivers
12:37within it there's a couple of
12:38interesting points about cell IDs first
12:40one is that they can be calculated from
12:41longitude and latitude so if I'm a
12:43writer here I can see that I'm in cell D
12:45and I can efficiently look up that cell
12:47another interesting point is that one
12:49sale ID can be used to calculate
12:51adjacent cell IDs so if I'm in cell D I
12:53can look up all the other cells around
12:55it based on that so if I'm a writer
12:57located here I can simply look up all
13:00seven of these hexagons then I can draw
13:02a circle around me and I can find all of
13:05the rides that are within that radius
13:07then using the ETA service that we have
13:10here we can look up the ETA for each one
13:12of those and find out which one is
13:13closest to us now taking a look at how
13:15we actually match a rider to a driver we
13:18simply need to subscribe to the event
13:19that a rider requests a ride and then
13:21once that happens we can find the
13:23closest driver using our ride service
13:25that we just talked about and then we
13:26need to tell the driver API to either
13:28accept or decline the ride if they
13:30accept we need to notify the rider who
13:32can then look up information about the
13:34driver and the driver needs to get
13:36directions to the pickup location and if
13:38the request is declined we need to
13:39Simply repeat this whole process for the
13:41next closest driver so taking a look at
13:42our entire system here we can see that
13:44we have all of the parts completed let's
13:45just do another quick overview of
13:47everything that happens when we're using
13:49this system a driver is going to be able
13:51to use a map to find a specific location
13:53they can then go out and they can find
13:55the price at that given location and
13:57they can use this ride server us to find
14:00the ETA and then once they're ready they
14:02can pay using stripe and they can be
14:04matched to a driver using the matching
14:06service all of this data will be
14:07persisted to this database to be looked
14:09up later and real-time updates about the
14:11driver's location can be sent to the
14:13rider through this event bus so this is
14:15a working solution but there's a ton of
14:17ways that we can dig deeper and find
14:19better ways to optimize and make this
14:21whole system more efficient so a couple
14:23of things that we didn't look into in
14:24this video but you're certainly welcome
14:26to dig into yourself if you're curious
14:27first one is math we didn't really do
14:30any math to see how much we need to
14:32scale all of our systems but there's
14:34there's certainly some numbers that can
14:36be crunched if you're curious about how
14:38this scales we also didn't discuss
14:40redundancy but that's a very important
14:41consideration we need to make sure that
14:43if any one of these pieces fails that
14:45our drivers and Riders can continue
14:47riding and if the rider can safely get
14:49to their destination in the event of any
14:51system failures some other interesting
14:53things to take a look at are algorithms
14:54for calculating an ETA we mentioned that
14:56it would be possible to build our own
14:58ETA service that take takes into account
14:59various other characteristics about a
15:01driver so looking into the algorithms
15:03that services like uber and Lyft use to
15:05actually do that would be very
15:07interesting another thing that's really
15:08important for companies like uber is
15:10data analytics so having some sort of
15:12pipeline setup that can persist data to
15:15some sort of data warehouse and allow
15:16employees to analyze the data and make
15:19optimizations to this system is super
15:21important we also talked about sharding
15:23our database of driver locations but
15:25there's a lot of algorithms that can be
15:26used to make sure that the data is
15:28geographically located close to where
15:30the user is going to be requesting it
15:32from and that cells that are close to
15:34each other are actually located in nodes
15:36that are close to each other there's a
15:37ton of other ways that you can dig in
15:38and find different ways to optimize and
15:40make the solution better and I certainly
15:42invite you to do so if you enjoyed that
15:43video you can get a lot more content
15:45just like this on interviewpen.com WE
15:48publish two to four videos a week really
15:49it's just an arbitrary number it's
15:51whenever I can sit down and do a video
15:53because these videos take a whole day to
15:55do and we're always online to answer any
15:57questions you may have join our Discord
15:59join our newsletter the blueprint where
16:01you can get more weekly data structure
16:03and algorithm and system design kind of
16:04topics and subscribe and like this video
16:07if you actually like this video and it
16:08helped you and also tell a friend that
16:10we exist that's all

About this transcript

This page contains the full transcript of Basic System Design for Uber or Lyft | System Design Interview Prep by Interview Pen, generated from the public captions YouTube serves with the video. The transcript has 3,727 words across 511 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.