hey! incredible video as always. didn't fully understand the routing part of the video and checked the description for the article-- would appreciate it.
Hey Jordan! Thank you for consistently making these awesome videos and answering queries in comments. Want to clarify few things: 1. We want to update driver location every 3 sec. If we were to do that directly in geohash in-memory server, will it not be too many updates to be processed for each partition? Can potentially also result in re-partition or change in partition if lot of drivers go in/out of location. Grokking course is suggesting maintaining separate hash table server for each driver's old and new location and then update the main geoHash every 15 mins or may be less lets say 5mins. (which I guess we can do through kafka + spark streaming (to micro-batch) combination). What are your thoughts on that? One minor potential downside is driver has to maintain 2 websocket connections with matching server and this hashTable server. 2. Minor question - For secondary shard on userId hash range in geohash server, userId is customer requesting ride, right? And why not use consistent hashing instead of userId range partition?
1) Depends how big your partitions are :) . If you find that there are too many operations per partition, you should probably be using smaller partition sizes. Not sure why we would see lots of repartitioning if drivers change locations, it's just that the driver begins to connect to a different partition. I'm a bit confused on your description in part 1. Then you make it seem like the main geo hash server will only see location updates every 15 mins. Feel free to elaborate, when I have some more time I can go back to grokking and see what they said for myself. 2) That's correct, userId or driverId (we can call this entity id or something). As for using user id range, what benefit does that get us? At least with consistent hashing, we can ensure that if we change the number of partitions fewer keys have to be moved around in the re-balancing.
@@jordanhasnolife5163 Thanks for responding. 1. Yes smaller partitions can help. Repartitioning can happen for case where we are using dynamic partition to keep lets say 500 drivers per partition. So if a location becomes hot (due to some event may be) we might see more drivers there and our system might want to repartition in those cases. About grokking solution, they used separate hash table for getting driver location updates every 3 sec to prevent frequent updates in main geoHash server. But I also had this same confusion that the main server only gets update every 15 mins from this hash table. This might not be ideal if we want to show customers all available drivers. I was trying to see if there was a middle ground where we can avoid frequent updates to geoHash partitions but still serve sort of fresh data. I guess grokking solution can work if we reduce the sync time from 15 mins to may be 2 mins.
Hello Jordan! Thanks for all the content you provide, it is really insightful and I appreciate your work I have a question: why you never consider Dynamo DB as an option for storage? I ofter hear about Cassandra, MySQL, Redis, but never about Dynamo Are there some concerns with it from your perspective?
I don't talk about it as it isn't open source, so it's hard for me to speak about it's implementation under the hood. Plus, then you're locked into AWS.
Could anyone comment if they have been asked to compute the driver's exact route in an interview? Another great video Jordan, thanks! Looking forward to the Google Maps one
16:23 For later, as we are on "Finding a ride" part - I think we want to make it persistent-ish as soon as client and driver accept a drive up until the end of a drive. Maybe every Nth signal, but we have to have at least some o f it for user history/compliance/legal reasons.
For using viterbi algorithm's as well, can we avoid the cross partition computation, by having all the location pings go to the same db partition? we will be tracking path only when ride is in progress right? i.e only after trip id is created, driver and rider are matched. so we want persistant data from that point. so we start writing the location pings to db instead of just redis. and all those pings could be to the trips db, which can be partitioned by trip id (or rider id) but not geohash id.. So there is no scenario where state is stored across partition?
I don't think we can for the viterbi algorithm part. It would be nice to have all of the pings for a trip id go to the same node, however I need to know based on wherever I am, what the transition probability is that I end up at the road next to me. To get those, I'd have to make a ton of network calls to some sort of "transition probability service", which I think would take quite a bit longer and require more data sent over the network.
Regarding the trip distribution. When the service wait 5 seconds before sending the trip to the 2nd driver. It's gonna have to sort drivers again every 5 second and exclude the 1st driver. How does this work? I guess it's some kind of scoring system that will push the 1st driver down the rank.
hi Jordan, during the capacity estimation you mentioned that we receive around 15k ride requests per second and mentioned that "it's a lot". But i am surprised that you have chosen MySQL for such a high write heavy system. What about picking Cassandra here? (as it allows leader-less replication) to increased write throughput? We are not performing any reads on the db once its written, so I don't think we need strong consistency here. Please clarify. Thank you.
Also curious about the DB selection here. My understanding is we need some consistency to make sure the driver won't be matched to two ride -> maybe the reason for MySQL? But maybe Cassandra / Dynamo + a row lock would work for this level of consistency needed?
Yeah fair point, I think cassandra would be fine here. Typically, my main concern for cassandra is when we need really fast ingestion on a single partition (like a given chat for facebook messenger or something), whereas here I guess we could just add more MySQL partitions, but yeah Cassandra totally works fine. I wasn't too concerned with consistency here at the time, but this is a fair point too. Problem is, if we're not sharding by rider/driver ids for the trips table, it's hard to see if we already have an open trip. Maybe the best option would be to use a two phase commit or something to make sure to put down that a driver/rider has an active trip and this way we ensure that they don't double up. Then those tables can be sql and the trips table itself can be cassandra. Nice question!
I did not understand why you have to jump the websocket from 1 server to another server as the driver moves. we can have driver connect always to the same websocket server and the location is pinged through this websocket server onto redis. during redis writes we make sure driver id in old geohash partition is erased(could also have ttl for handling race conditions of not getting deleted) and new location in new partition is written
Sure but in your design now the server has to connect to each redispartition (of which there are many) via a websocket or poll it indefinitely as it also has to send driver locations back to all of the riders
I also found the websocket creation/deletion in this video and in the webcrawler video kind of odd. IMO, coordinating websockets connections based on the internal partition scheme couples the frontend a little too tightly to the backend. Just keeping a persistent websocket connection and handling the routing internally feels like a better separation of concerns. For example, you could use a Kafka queue to pipe top K driver matches computed in the backend to the websockets in the frontend. On the other hand, maybe connecting and disconnecting websockets is simpler and would give you lower latencies?? I have no idea.
Would there be a cache in front of the trips db? When the HMMs update the location of the ride periodically it’s also being read periodically. Wondering if that’s too many read and write requests for a mysql trips db?
you dont talk about costs in any of these videos. cost is a very imp. aspect which can redefine the entire solution. But good video, you bring new dimensions to my thought process.
If we are sharding based on Trips DB on trip id, who creates the unique trip IDs? Should there be a central service creating unique trip id? Or does the sharding needs to happen on something that is already existing, for example user id?
We could use a central service, but that could become a bottleneck. Could do something similar to tinyURL where you partition the servers by trip id, randomly choose a leader based on load or round robin or something, and then assign the id on the leader
Why does a rider need to be connected to a matching service close its location using the geohash loadbalancing ? I am quite confused. Can you please clarify
The server itself doesn't need to be physically near it's location but it should be responsible for the area of the map that the potential rider and all nearby drivers could connect to
When a driver clicks accept on a ride, we can basically just tell their client to temporarily stop sending location updates to the cache until we confirm the acceptance. On the front end, just don't allow them to click accept again while there is one outgoing. Technically, we could have some wild race condition where they click accept, it takes 20 seconds to go through, and in that time they somehow accept another. If you really needed to, you could either 1) Just let it happen, the second rider will get mad and cancel 2) Shard all driver rides to the same database node and perform a check that they don't have a ride in progress
The capacity is off. Uber only did about 500M trips globally lasts year. If you’re using localization to load balance you can optimize for a population. Like NYC which only does about 600k trips a day. You don’t need location checkins with the db on time scale, offload that to the client and only put it to the db on significant change in position. Most modern dbs can process Haversian requests natively. If you really wanted to build your own you could work with arc seconds to find plane intersections and plot from there. Ubers REST API code was dumped a few years back and it’s actually pretty simple. They have a lot of complexity around rate and surge 😮calculations. They do have some proprietary routing and gps accuracy systems that I’m not aware of. Good work.
Thanks! Interesting point with regards to the surge pricing. Definitely a combination there of demand as well as distance calculation. For these videos, agreed on the capacity being off, but in an interview, they can basically tell you any capacity that they want. But yeah mine was super crude lol
@@jordanhasnolife5163 Yea... I like your videos! You're on the right track. I have a couple of tips, 1. Don't boil the ocean. Lots of jrs try to exaggerate loads and over build systems, just make reasonable usage assumptions, marry that to good n-tier design that you can scale. Bandwidth and Hardware are cheap, refactoring isn't. 2. Stick to the Scope: You spent a lot of time on geocoding, gps location, etc. There are companies that make billions doing that. It's not in scope to build a routing or mapping engine, just say, "Here, i'll call x service to get the lon/lat, route, waypoints, etc." and then stick to the core of the app. Just my .03.
@@TheTacoReview Certainly not in scope to build them in reality, though for whatever reason certain companies do ask about it! Appreciate the feedback!
![ทัศนศึกษาโรงงานผลิตโค้ก [THAI/ENG SUB]](http://i.ytimg.com/vi/M9y-TJBNem0/mqdefault.jpg)
You don't need to apologize 😅 Your videos are top notch and I'm learning a lot! Keep it up man 👍🏽
48:10 Great use case for combo of LB, Ques, and processing nodes.
Great vid. One feedback. Please link the pre-watches/pre-req (like the geo spatial vid you mentioning) to easier discovery..
Love that there is this whole detailed section about finding the exact route and times but in reality we just use google distance matrix API LOL
Interview: tell me how to do an inorder binary search tree traversal
IRL: treetset.iterator().forEach
The DJ Khalad of system design. Just when I think the last problem you solved was your best yet you hit me with a, "And another one!"
Great Explanation as always.
hey! incredible video as always. didn't fully understand the routing part of the video and checked the description for the article-- would appreciate it.
highscalability.com/designing-uber/
Accidentally found this playlist and loving it. Kate's asking if Jordan can have a link to notes on these videos too?
Damn Kate needs to stop hitting me up I'm too busy with Sydney Sweeney these days. Tell her I'll post the notes once I'm done with the series though.
Hey Jordan! Thank you for consistently making these awesome videos and answering queries in comments. Want to clarify few things:
1. We want to update driver location every 3 sec. If we were to do that directly in geohash in-memory server, will it not be too many updates to be processed for each partition? Can potentially also result in re-partition or change in partition if lot of drivers go in/out of location.
Grokking course is suggesting maintaining separate hash table server for each driver's old and new location and then update the main geoHash every 15 mins or may be less lets say 5mins. (which I guess we can do through kafka + spark streaming (to micro-batch) combination). What are your thoughts on that?
One minor potential downside is driver has to maintain 2 websocket connections with matching server and this hashTable server.
2. Minor question - For secondary shard on userId hash range in geohash server, userId is customer requesting ride, right? And why not use consistent hashing instead of userId range partition?
1) Depends how big your partitions are :) . If you find that there are too many operations per partition, you should probably be using smaller partition sizes. Not sure why we would see lots of repartitioning if drivers change locations, it's just that the driver begins to connect to a different partition.
I'm a bit confused on your description in part 1. Then you make it seem like the main geo hash server will only see location updates every 15 mins. Feel free to elaborate, when I have some more time I can go back to grokking and see what they said for myself.
2) That's correct, userId or driverId (we can call this entity id or something). As for using user id range, what benefit does that get us? At least with consistent hashing, we can ensure that if we change the number of partitions fewer keys have to be moved around in the re-balancing.
@@jordanhasnolife5163 Thanks for responding.
1. Yes smaller partitions can help.
Repartitioning can happen for case where we are using dynamic partition to keep lets say 500 drivers per partition. So if a location becomes hot (due to some event may be) we might see more drivers there and our system might want to repartition in those cases.
About grokking solution, they used separate hash table for getting driver location updates every 3 sec to prevent frequent updates in main geoHash server. But I also had this same confusion that the main server only gets update every 15 mins from this hash table. This might not be ideal if we want to show customers all available drivers.
I was trying to see if there was a middle ground where we can avoid frequent updates to geoHash partitions but still serve sort of fresh data. I guess grokking solution can work if we reduce the sync time from 15 mins to may be 2 mins.
Hello Jordan!
Thanks for all the content you provide, it is really insightful and I appreciate your work
I have a question: why you never consider Dynamo DB as an option for storage? I ofter hear about Cassandra, MySQL, Redis, but never about Dynamo
Are there some concerns with it from your perspective?
I don't talk about it as it isn't open source, so it's hard for me to speak about it's implementation under the hood. Plus, then you're locked into AWS.
Gotcha, thanks
Could anyone comment if they have been asked to compute the driver's exact route in an interview? Another great video Jordan, thanks! Looking forward to the Google Maps one
Also interested in the above - I doubt it but I still think its a solid case study in stream processing
16:23 For later, as we are on "Finding a ride" part - I think we want to make it persistent-ish as soon as client and driver accept a drive up until the end of a drive. Maybe every Nth signal, but we have to have at least some o f it for user history/compliance/legal reasons.
Fair point!
Thank you man!
Clear and insightful video. However, i think it's inappropriate that you doxxed my wife's house ( Kate Upton ).
Sorry, to be fair everyone knows where she lives already...
For using viterbi algorithm's as well, can we avoid the cross partition computation, by having all the location pings go to the same db partition? we will be tracking path only when ride is in progress right? i.e only after trip id is created, driver and rider are matched. so we want persistant data from that point. so we start writing the location pings to db instead of just redis. and all those pings could be to the trips db, which can be partitioned by trip id (or rider id) but not geohash id.. So there is no scenario where state is stored across partition?
I don't think we can for the viterbi algorithm part. It would be nice to have all of the pings for a trip id go to the same node, however I need to know based on wherever I am, what the transition probability is that I end up at the road next to me. To get those, I'd have to make a ton of network calls to some sort of "transition probability service", which I think would take quite a bit longer and require more data sent over the network.
Regarding the trip distribution. When the service wait 5 seconds before sending the trip to the 2nd driver.
It's gonna have to sort drivers again every 5 second and exclude the 1st driver. How does this work?
I guess it's some kind of scoring system that will push the 1st driver down the rank.
Can just sort once and be stateful!
@@jordanhasnolife5163 Ah, I can store each trip in Redis with a list of sorted driver IDs that we keep popping each driver out.
hi Jordan, during the capacity estimation you mentioned that we receive around 15k ride requests per second and mentioned that "it's a lot". But i am surprised that you have chosen MySQL for such a high write heavy system. What about picking Cassandra here? (as it allows leader-less replication) to increased write throughput? We are not performing any reads on the db once its written, so I don't think we need strong consistency here. Please clarify. Thank you.
Also curious about the DB selection here. My understanding is we need some consistency to make sure the driver won't be matched to two ride -> maybe the reason for MySQL? But maybe Cassandra / Dynamo + a row lock would work for this level of consistency needed?
Yeah fair point, I think cassandra would be fine here. Typically, my main concern for cassandra is when we need really fast ingestion on a single partition (like a given chat for facebook messenger or something), whereas here I guess we could just add more MySQL partitions, but yeah Cassandra totally works fine.
I wasn't too concerned with consistency here at the time, but this is a fair point too. Problem is, if we're not sharding by rider/driver ids for the trips table, it's hard to see if we already have an open trip. Maybe the best option would be to use a two phase commit or something to make sure to put down that a driver/rider has an active trip and this way we ensure that they don't double up. Then those tables can be sql and the trips table itself can be cassandra.
Nice question!
I did not understand why you have to jump the websocket from 1 server to another server as the driver moves. we can have driver connect always to the same websocket server and the location is pinged through this websocket server onto redis. during redis writes we make sure driver id in old geohash partition is erased(could also have ttl for handling race conditions of not getting deleted) and new location in new partition is written
Sure but in your design now the server has to connect to each redispartition (of which there are many) via a websocket or poll it indefinitely as it also has to send driver locations back to all of the riders
I also found the websocket creation/deletion in this video and in the webcrawler video kind of odd. IMO, coordinating websockets connections based on the internal partition scheme couples the frontend a little too tightly to the backend. Just keeping a persistent websocket connection and handling the routing internally feels like a better separation of concerns. For example, you could use a Kafka queue to pipe top K driver matches computed in the backend to the websockets in the frontend.
On the other hand, maybe connecting and disconnecting websockets is simpler and would give you lower latencies?? I have no idea.
Why is the ClaimedTrips table is needed?
I think that just the Trips table with a driver_id column should do the job.
Sorry ClaimedTrips == Trips. I just called it that on one slide haha.
Would there be a cache in front of the trips db? When the HMMs update the location of the ride periodically it’s also being read periodically. Wondering if that’s too many read and write requests for a mysql trips db?
If you noticed that there was a ton of load on it I don't see why you couldn't add a cache.
@@jordanhasnolife5163 thanks very much!!!
you dont talk about costs in any of these videos. cost is a very imp. aspect which can redefine the entire solution. But good video, you bring new dimensions to my thought process.
Duplicate comment, responded to the last one lol
If we are sharding based on Trips DB on trip id, who creates the unique trip IDs? Should there be a central service creating unique trip id? Or does the sharding needs to happen on something that is already existing, for example user id?
We could use a central service, but that could become a bottleneck. Could do something similar to tinyURL where you partition the servers by trip id, randomly choose a leader based on load or round robin or something, and then assign the id on the leader
@@jordanhasnolife5163 That makes sense. Thanks for the clarification! Great videos :)
Why does a rider need to be connected to a matching service close its location using the geohash loadbalancing
? I am quite confused. Can you please clarify
The server itself doesn't need to be physically near it's location but it should be responsible for the area of the map that the potential rider and all nearby drivers could connect to
how to make sure that driver will not accept two requests concurrently? (Race condition on driver side)
When a driver clicks accept on a ride, we can basically just tell their client to temporarily stop sending location updates to the cache until we confirm the acceptance. On the front end, just don't allow them to click accept again while there is one outgoing. Technically, we could have some wild race condition where they click accept, it takes 20 seconds to go through, and in that time they somehow accept another. If you really needed to, you could either
1) Just let it happen, the second rider will get mad and cancel
2) Shard all driver rides to the same database node and perform a check that they don't have a ride in progress
what do i do if i dont understand alotta this
Watch the concepts series!
The capacity is off. Uber only did about 500M trips globally lasts year. If you’re using localization to load balance you can optimize for a population. Like NYC which only does about 600k trips a day.
You don’t need location checkins with the db on time scale, offload that to the client and only put it to the db on significant change in position.
Most modern dbs can process Haversian requests natively. If you really wanted to build your own you could work with arc seconds to find plane intersections and plot from there.
Ubers REST API code was dumped a few years back and it’s actually pretty simple. They have a lot of complexity around rate and surge 😮calculations.
They do have some proprietary routing and gps accuracy systems that I’m not aware of.
Good work.
Thanks! Interesting point with regards to the surge pricing. Definitely a combination there of demand as well as distance calculation.
For these videos, agreed on the capacity being off, but in an interview, they can basically tell you any capacity that they want. But yeah mine was super crude lol
@@jordanhasnolife5163 Yea... I like your videos! You're on the right track. I have a couple of tips, 1. Don't boil the ocean. Lots of jrs try to exaggerate loads and over build systems, just make reasonable usage assumptions, marry that to good n-tier design that you can scale. Bandwidth and Hardware are cheap, refactoring isn't. 2. Stick to the Scope: You spent a lot of time on geocoding, gps location, etc. There are companies that make billions doing that. It's not in scope to build a routing or mapping engine, just say, "Here, i'll call x service to get the lon/lat, route, waypoints, etc." and then stick to the core of the app. Just my .03.
@@TheTacoReview Certainly not in scope to build them in reality, though for whatever reason certain companies do ask about it!
Appreciate the feedback!