System Design Interview: Design Uber w/ a Ex-Meta Staff Engineer
Вставка
- Опубліковано 5 чер 2024
- 00:00 - Intro
01:51 - The Approach
3:01 - Requirements
10:20 - Core Entities & APIs
20:47 - High Level Design
32:55 - Deep Dives
1:01:32 - Conclusion
A step-by-step breakdown of the popular FAANG+ system design interview question, Design Uber, which is asked at top companies like Meta, Google, Amazon, Microsoft, and more.
This question is most commonly asked in Google and Meta System Design Interviews in particular.
Evan, a former Meta Staff Engineer and current co-founder of Hello Interview, walks through the problem from the perspective of an interviewer who has asked it well over 50 times.
Resources:
1. Detailed write up of the problem: www.hellointerview.com/learn/...
2. System Design In a Hurry: www.hellointerview.com/learn/...
3. Excalidraw used in the video: link.excalidraw.com/l/56zGeHi...
4. Vote for the question you want us to do next: www.hellointerview.com/learn/...
5. Previous Video, Design Ticketmaster: • System Design Intervie...
Connect with me on LinkedIn: / evan-king-40072280
Preparing for your upcoming interviews and want to practice with top FAANG interviewers like Evan? Book a mock interview at www.hellointerview.com.
Good luck with your upcoming interviews!
This channel undoubtedly has the best and most realistic functioning system design videos. Evan, you should add a donate button.
what sets these videos apart from other system design interviews is that not only is your thought process thorough and well thought out, you give clear distinction between mid/senior/staff level answers which is insanely valuable
Junior-to-mid-level dev here, got my first system design interview coming up soon for a new gig. I feel so much more confident thanks to you! Please keep it up!
I am into system design from a couple of months now and Hello Interview has genuinely the best system design content hands down 🙌.
I think everyone has already left wondeful comments here but I cant stop myself from giving a huge shout-out for creating such helpful videos. It is so straightforward and cohesive to understand the flow of this problem. Really appreciate the hard work you are doing!
Thanks for taking the time to right this! Love hearing people are finding them valuable
Totally agree with you on the Back of the Envelope Estimation! I think it's such a waste of time. As you mentioned, it's always "oh it's a lot. I need to scale it". Well duh.
but I think majority of the interviewers will still want it and judge based on the calculations :P
Went through your channel's videos and oh boy! they are amazing. One big takeaway for me which you have clearly demonstrated "Keep it Simple". Got yourself a follower for life.
This is amazing, loved the style of videos, deep dives and what's expected at each level. Gives a whole new perspective. Would love to see more!
Please make more videos. I don't normally watch these long videos, but these videos are so informative and packed with knowledge of different domains. Thankyou.
Yes, this channel videos are the best I've found on System Design and is not even close! Please keep them coming!
Ethan, kudos to your great videos!! This is by far THE best design video for such complicated topic like designing Uber!
Hands down the best system design vid I've seen so far, been searching all over and this makes me feel like I actually have a step by step approach to doing this
I really love the presentation style, and the notes on leveling staff engineer vs mid level expectations, showing the "range" discussing the expectations. these are the best system design videos on the web right now.
I have never felt so engaged while watching any other design video. This is pure gold. Thanks you so much and keep up the good work!
Amazing stuff! Please keep adding more videos like this! Thanks!!
please make more of these video's they're top notch 🙏
you have the best system design videos! please make more, and thanks for this
Thank you very much for this. Much more concise than any of the materials I have seen thus far. I love that you call out the benchmarks as well so we can know what the standard is for this type of question.
Awesome! This helps a lot. Thanks so much Evan for these videos. ❤
liked, commented, subscribed. This channel has the potential to blow up and become a top-tier programming channel if you keep this up!
This is by far the best system design I have seen or read. Very elegant and the way you structured it makes more sense. I wonder though if the interviewer would adapt to such format when they are particularly expecting a certain format. Subscribed to the channel with notifications 🤝
One of the best systems design videos . Concepts are so well explained. Thank you!! I wish I found your site sooner. 😊
Fantastic content, please do more of these!
I can't wait to see more videos. Amazing job!
You structured it well.Doesn't feel like jumping between concepts. I am going use this template for answering. Thank you!
I normally don't comment on youtube videos but this is f*cking incredible. I'm literally building.a map-based social media application as a personal project and you opened my eyes about how these things can actually scale.
The structure and content of this video is immaculate. Well done.
This comment made my day! Good luck with the app, sounds cool!
Really good work. Very well explained parts and great visual representation as well. I had a mock interview recently and used the Ticketmaster example as template to form my response. Waiting for you to cover more common and some unique design problems
These videos are amazing, thank you so much for recording them! Really helpful!
Glad you’re enjoying them!
You are sending a clear message to us. Keep it simple, build the design from basic building blocks. Great video. Even if someone encounters a question, which they have not seen, this principle works.
Reg the question, I believe 1. Notification service design (talking about web sockets, long polling, SSE) might be value add 2. Also, driver matching algorithm (K Nearest neighbor etc.) can be expanded 3. How to scale DynamoDB -apply sharding on Rider can be also be added to data point
Agreed, all great actionable deep dives!
I am just starting to prepare for interviews and Uber was the first one I wanted to understand since the location based matching kept bugging my brain. After watching this, I am glad that I did. Learnt so many new things in this single video. Thank you.
Yes, please make more!
Thank you! Keep them coming :)
Great, great content! It's shocking how simple and focused your designs are compared to nearly any other system design resources.
I always wonder how it can be possible to write out/draw the designs I see elsewhere in 35 minutes and now I've watch your videos I've realized the answer is you don't need to.
Another awesome video, thanks a lot for doing this, please keep up the great work!!!
This is definitely the no cruft and zero nonsense system design video. Also, suggestions to optimize time is so valuable as I have seen many candidates waste their time on things which don't add up value at the role they are interviewing.
Way too common!
Absolutely a good video and explanations!
loved it, glad I found your channel out of blue while preparing.
Awesome! very well explained -- please make more!
I appreciate the longer videos and how you go into depth on the expectations for different level candidates. As a beginner to the system design world (planning to switch from a DE role), it helps to understand expectations and also see everything from a seasoned expert's point of view.
I first saw a few of your posts on reddit when researching what prep material to use for the system design interview. HelloInterview has helped me tremendously with gaining knowledge, helping with behavioral stories and also just in confidence! I've been reading Alex Xu's books alongside your content. Thank you!
Right on! This is awesome to hear. So glad you've been finding value :)
Same boat. Going through the book and working through these exercises/videos. Hope your prep is going well!
Tight, Tight, Tight!... great watched it three time and still getting new points. Kudos!
I really like the depth you cover in your videos. It is the depth and the presentation style that I really love. It is amazing to watch you present. Thank you for uploading and you have a new subscriber.
Sweet!
This Channel is an absolute gem, thank god I found it before my interview, hopefully this is going to help.
Good luck!
@@hello_interview Will update you in couple of days fingerCrossed 😆
@@hello_interview Passed the system design but did not pass overall, either way your interviews were extremely helpful.
Loved the content. I love the fact that you re-explain a lot of things from previous videos. 1 Small knit pick. At the end of the video where you talk about stale data cleanup (for driver who doesn't interact with ride request). You mention about using dynamo db TTL, I would actually stick to the redis way of doing it instead of using dynamo db, the ttl feature has a delay (it may also take upto 48 hrs for data to cleanup). OR we can switch to using SQL for primary DB with triggers.
Yup good call! A couple other folks have correctly made the same comment below :)
Thank you Sir, another great design video. Keep your excellent work.
Such Clarity. Much Wow.
Where were you, all my life?
🤗
This is phenomenal !!!
very informative. well explained. thank you!
echoing other comments: definitely one of the best system design videos I have seen on youtube 😍
Amazing video! I would love to see more from you.
Another one coming within the week!
Been watching youtube for at-least 10 years now, and this might be my first comment ever. This was really really helpful without any fluff. And the way you explain the entire design was just so fluent and coherent. I've got a couple of interviews lined up and found this just in time. Thanks a lot!!
Hell yah! Good luck in the interviews!
@@hello_interview Thanks man!
nice video. Thank you for creating this video. I learned a lot from watching it!
I have my final Amazon SDE 2 interview (4hr loop) next Thursday and your videos are definitely helping me up my system design game. Please upload 1 more video before then 🙏
how’d it go?
Your content is addictive!
Wow, another excellent video Evan, I'm really enjoying these videos, these are by far the best system design videos out there. Thanks for sharing your knowledge with us Evan! By the way, you had one small typo in one of your primary database tables, you ended up having two "Ride" tables, I assume one of them was meant to be "Rider". Again, excellent video, thanks Evan!
Good find! And glad you’re enjoying them :)
Nice advice on back of the envelope 👍
Love your thought process also includes why so its intuitive, and isolating out the specially difficult parts
35:36 good example of calculating only to optimize location DB# transactions. But I feel like this location DB is a core feature that should be discusssed even in HLD
love the video! the best one I have seen to talk about different level of candidates. I have a question around the consistency of driver ride match, the distributed lock with TTL solution:
1. what would happen if there is a network delay that the driver accept was not going through successfully within the TTL, so there was a new request sent to the driver later (while the driver actually have accepted the first one already from their phone):
my potential guess: we will invalid the accept from the driver for the previous one and notify the driver the first one was not matched successfully?
2. and maybe more complicated case, what about the case that the first ride was still not matched successfully with another driver? do we resend the request to that driver after it unlocks from the second matched ride?
Thank you I'm enjoying your videos! I'm subscribed since the first video.
request: You mentioned in a previous video that "you'd pass as long as you answer the common scalability/fault questions well". Would love a video for mid level that covers the most common principals and themes and what candidates miss or struggle with.
Good suggestion. Focused on these full breakdowns right now but some more targeted overviews in the future could make sense
@@hello_interview some mid-level content would be greatly appreciate!
Great work 👏👏 Thankyou
My first thought on correcting lingering driver "request_sent" status back to "available" is using a asynchronous queue. The message in the queue is configured to be delivered after 10s in the future, and the processor of the message will check the Driver database table and see if the status should be reverted back, e.g, if the "request_sent_timestamp" is older than 10s. The delay of this architecture is minimal compared to Cron job. It does require row level database transaction, because both the ride matching service and the queue processor can update the same row through read-modify-write.
Thank you for the great content.
Sequentially notifying drivers is not optimal for rapid response notification to riders. In my understanding multiple drivers are notified simultaneously and then in case of a driver conflict they are arbitrated. During the non-functional requirements stage it might be beneficial to identify "analytics and operational metrics" as possible items of interest. Custodians and stakeholders live off of these.
Thanks a lot for such a great case study, as a Product Manager I am increasingly seeing that it is expected from PMs to have detailed knowledge of System Design, if time permits could you also have some sort of side notes that a PM should have when designing systems? It will help if you could give details of how and what engineers discuss with PMs when designing systems. I believe it'll help with interview prep for both engineers and PMs. Thanks again for such golden content.
your videos are most realistic out there
Please upload more videos 😁
Another great video thank you!! When you're making these, would it be possible to move your cursor off of where you're typing? Sometimes it covers what you're typing so you can't see it until you move on to the next part. Not a huge deal but would be nice!! Literally the best system design videos out there so I'll watch even if the cursor covers the whole dang thing.
Already fixed in the most recent video and will continue to be fixed moving forward :)
You are amazing. Wish you are my interviewer I feel you really try to engage the interviewee
Great video!
From the perspective of Product Design, what are some potential areas we could deep dive into for the deep dive section of this interview?
Thank you not just from myself, but also on behalf of my interviewer who I would have bored to death if I didn't have this structured advice to follow. 🤣
Great video, I think both ride service and ride matching service should handle the similar traffic (during peak time both services should see spike) and I think it's a good idea to put queue before ride matching service, my question is do you think it's a good idea to put queue in front of ride matching service also and use notification to send data back to users? is there any downside of this approach?
Thank you for your work. I've watched a lot of system design videos but your content is definitely the most elegant. The amount of abstraction vs. depth seems perfect for actual interview settings.
Quick question about using Redis as a distributed lock. Would we have to explain how Redis can be used as a distributed lock during an actual interview? It almost seems too simple to be true .
Only to the level i do here. It is straight forward! Its just a global view of a driver's state, so just saying its a simple key value pair with TTL should be enough.
@@hello_interview Thank you!
awesome
Awesome video and neat , thanks !!
What drawing app do you use, I wud want to use same for my interviews
Excalidraw
Great walkthrough! Which diagram software do you use?
Excalidraw
I have two immature ideas and I don’t know if they are suitable:
1. Consider the database as a bottleneck. By dividing different service areas(such as cities or districts with smaller granularity than regions, but not necessarily deploying service in different data centers), real-time data like location and driver-lock could be sharded. Therefore, the database could handle more requests?
2. Consider scaling the Ride Service. Separate a Tracking Service from the Ride Service to handle location updates since there are so many interactions during riding. Keep Ride Service concentrating on ride-crud. But this way, the Tracking Service is pretty same as the Location Service?
Thanks a lot for making this. Very helpful. Could you plz do "Ad click aggregation" question?
Will add it to the list! You'll see it first in written form on www.hellointerview.com/learn/system-design/answer-keys/ticketmaster then can try to get to a video
This is a great channel, and what mock software do you use for these diagrams, designs, and so on.
Excalidraw
@@hello_interview Thanks very much
thank you for the great quality video again. What do you think about the race condition that might happen in the while loop, e.g driver 1 accept the ride, noCondition becomes False, but notification is sent to driver 2? does it sound too simple to handle the matching?
Great observation! Couple ways to handle it.
1) just accept that you will have a small set of instances where a driver accepts only to get a response saying "drive already taken" (not a great option, but worth discussing)
2) Add an additional state to track driver response. So you wait to proceed until either 10s or driver responded declining
3) Increase the wait time to 11 or so seconds to give some buffer.
1 & 3 are cheap, 2 is likely the best.
This was amazing, expecting more in future
Your content is absolutely the best. I'm subscribing to all your content. Got only one feedback though. Your huge cursor seems to be always on the current text that you are talking about. If possible when you are typing, have the cursor hidden would be great. Thanks.
Fixed in the latest and all future videos :)
Quick question if anyone is able to answer. In the solution for the "high demand to the ride matching service" a queue was introduced to avoid overloading.
Is this assuming that the connection from the clients to the gateway is long lived? If using HTTP then I assume there will be timeouts if the client doesn't receive a response?
Also, this is more implementation than design, but if NGINX was used as the L7 gateway I assume this would mean a lightweight service is needed to actually handle the request and put on the queue?
BTW - This video was absolutely fantastic 🎉
Good observation! I hand wave this a bit. The queue makes the request asynchronous and, thus, we respond via push notification. Real Uber likely opens a websocket or has some long polling at this point as you suggest.
Since the main write load on the DB is going to be the driver lock, couldn't this be moved into Redis? If Redis goes down we will lose the lock, but if Redis is down, we can't match the driver anyway because we don't know the location.
In a similar manner, there is a lot of read load from the server checking driver status during the matching process. Would it be feasible to do this entirely in memory as well? If the driver client sent status with each location ping, we will always have the driver status in memory. If Redis goes down, the status will be refreshed with the next location ping. If a match is requested between when Redis comes back up and the first ping is received, the drivers location won't be in the cache at all, and will therefore not be matched.
Amazing video again, i enjoyed the level of detail for every decision made. quick qs, is it the norm to always use microservice architecture?
It’s certainly the most common architecture in these interview. I have a write up on Design LeetCode at www.hellointerview.com/learn/system-design/answer-keys/leetcode which serves as a counter example
Great video. Thanks a lot for sharing this. Just one comment, is DynamoDb the best for the distribute lock? it does allow you to set a TTL but it does not give any guarantees of when the record will be removed. I think it was up to 48 hours after the expiration. Is this correct? We would need to filter out expired items which is fine but just something to keep in account.
Yah others commented the same. It wouldn’t be the best fit for this reason. Would opt for something like redis instead
Hi Evan, I have a question about the design. Once the system get a list of nearby drivers, how does it send notification to them(using a message queue?) and also how to know if the system should send the notification to next nearby driver and when to stop sending notification to next driver?
Amazing channel. Learned lot of concepts! Quick question, What happens when ride matching service sent multiple push notification to the riders and let's assume 2 of them clicked accept option.
As MongoDB doesn't support Transaction where 2 riders are trying to accept a ride. Please provide some insights.
Go into detail about this when talking about matching consistency. Checkout the deep dives for more info. We use a distributed lock to handle this.
Great work!
1. DynamoDB TTL does NOT work -> "Items with valid, expired TTL attributes may be deleted by the system at any time, typically within a few days of their expiration. You can still update the expired items that are pending deletion, including changing or removing their TTL attributes."
2. You have ride matching service and location service both talking to the Location DB which is a bad practice, ideally every request to location DB would flow through the location service.
3. Why do we need a lock here? Why can't the TTL be on the location DB? When ride matching service find driver's nearby it can check the TTL field of each driver and decide whether or not to send notification to that driver. If you worry about consistency issue, you can add a version field to avoid 2 RMS trying to lock the same driver.
The location DB would have a TTL for freshness, but that does not solve the problem here of ensuring we don't send the same driver multiple requests
For #3, if we are using Redis cluster because we can't handle the load on a single leader instance due to the very high rate of location writes, that likely means we're partitioning the data geographically. Since Redis can't handle cross-slot queries we'd want it to be geographical because we want to see drivers close to a given location with a single query most of the time.
But that makes using the same Redis index for locking problematic. What if the driver drives across a shard boundary and their location updates start going to a different node? There's probably going to be some time period when the driver could be on two different Redis nodes. Then they could be sent ride requests from multiple riders at the same time who locked in two different places.
The usage pattern for locking is quite different. Firstly, the TPS is going to be way lower, since it only happens when we try to book a ride with a driver and not every few seconds for every active driver. We could probably handle the load on a single node. Secondly, the lock doesn't really depend on location at all, so if we did need to shard, it can be sharded consistently for a given driverId.
I am wondering if another tradeoff between quadtree and geohash could be how can it be partitioned, geohash naturally easier for paritioning as they are in string, and closer string likely closer locations; while quadtree in tree structure, they cannot be stored in different node with the parent - child relationship (correct me if I am wrong) -> which means if there are a lot of locations we need to store, geohash will also works better.
Yah this is largely true, though many complications arise when you need to scatter gather across partitions when a region exists on a boundary.
Thanks again for the great content Evan
One question though is how would a rider cancel the ride after they waited too long and still no match? One solution i can think of is to add rider status and change from “requested ride” to “idle” , and have the ride matching service to check the status . but then it will add more load to the other service and the db. What would u suggest?
Realistically once you add multiple back and fourth options you'd open a persistent connection. Pretty sure that is what Uber does. But your suggestion is great in the context of a interview where we deign a simplified version. I would update the Ride to cancelled and check that in each place before we proceed with the matching process.
Hello,
I thoroughly enjoyed watching this video! The detailed explanation of tradeoffs was incredibly helpful, and I appreciate the time you took to delve into them. Please don't mind the length of the tutorial as you're taking time to going into tradeoffs in a great details.
I have a small suggestion for improvement: Could you possibly move the cursor away when writing on the board? Sometimes it obscures the text you're typing, making it a bit difficult to follow along.
Regarding the while loop discussion, I understand that calling the database at the beginning of each iteration might lead to potential bottlenecks. Have you considered any optimizations or improvements in this regard?
Also another question: how does the rider know that a driver has accepterd the request? A simple push notification would have been nice to mention. The PATCH request is simply initiating the matching process as I understand from the video.
Overall, this was a fantastic video, and I look forward to seeing more content from you. Keep up the great work!
Best,
Totally agree on the cursor, will fix next go around. Still getting the hang of the video production side of things :)
For the while loop, you can cache the ride status which would help a lot. You're right I didn't cover the rider update. Couple ways to do that, polling, persistent connection, or push notification. Each with their own pros and cons.
Great video! Very well explained!
I have a question - Isn't load balancing and routing same thing?
Similar but not the same. Load balancing distributes traffic amongst a set of horizontally scaled severs. Routing determines which, micro services in this case, to send the traffic to based on the request.
Thank you for high quality videos! One question I have - probably more related to ticket master question though, can you help me understand what's the main difference between Redis pub-sub vs Kafka pub-sub and when we should choose one over another? Thank you and appreciate your insights!
Realistically, in 99% of interviews it doesn't matter, just choosing pub-sub correctly is enough. The main differences are around how they handle unsubscribing and their durability guarantees.
Great Videos!
One question regarding the distributed locking solution--does the DynamoDB TTL work for this feature? Their documentation seems to imply they clean up expired TTLs on the order of days afterwards rather than more tightly like the problem may require.
Would something like a select ... for update in postgres work to lock the rows and then rollback the transaction after a timeout defined in the ride booking service?
You'd want to avoid that approach as its going to keep the transaction open, occupying a write thread. The number of these could grow quickly. For DynamoDB, I'm pretty sure that is just clean up. When you query for that row it won't be there, even though it technically still exists on disk.
@@hello_interviewGood point about the transaction threads being an issue!
I tried this out in DynamoDB, and it seems like the expired rows can be returned by reads until they are cleaned up asynchronously (which took a few minutes for my test table).
It looks like Cassandra offers a similar TTL feature that does treat the expired values as removed for reads.
Excellent video! Subscribed to you channel!:D
QQ
1. Why did you go ahead with a DynamoDB based Primary DB and not MySQL? Yes, it would be easier to scale DynamoDB but would we really need that level of scale for the Primary DB? Would the TPS be as high as that of the location DB?
Only pro I can think of would be that it would be easier to change schema in NoSQL.
PS: Would be great to move your cursor while discussing a point. :)
Big +1 on cursor, will fix next video :)
Re DDB vs MySQL, the real answer here is "it doesn't really matter." Checkout this quick right up for more on my opinion here: www.hellointerview.com/learn/system-design/in-a-hurry/key-technologies#core-database
Very good approach. Great content. But I am curious why there is no mention of Websockets (bi-directional). I see while loop might go infinite if there is no driver accepted/available. In case of surges, do we send all near by drivers into while loop and ask for accept/deny but lock on single driver? I thought we might need to limit few drivers in this while loop since the accept rate high. How do we send drivers about demand areas/locations to find riders? So that drivers will roam around to find the ride requests.
You'd have meaningful limits here. Limits to the search time (1 minute) and limits to number of drivers considered (both by distance and total driver count). For the websockets and your last question, these are all considerations when designing a real uber-like product, but in a interview you have 35 minutes so need to choose what matters most, hence why those don't come up.
Thanks Evan! What tool are you using for diagrams?
Excaldiraw!
Wouldn't it be good to consider use of a Messaging Queue like Kafka for communicating between services?
Where inter-service communication are you concerned about?
Great video I am wondering would it make sense to use a websocket for the Users because we want them to keep us informed on the location and we want to let them know when I ride is available? That way we would want to keep communication with drivers without using many rest operation? Or would it be to many open connections to maintain during surges? Also is it now relevant to discuss alternatives to redis like valkey due to license changes?
Totally! Just too much scope to get to in this video but you are correct that that is a reasonable approach and is likely what Uber does. To that point, you'd compare user location to the map and trigger security escalations if they deviated significantly.
@@hello_interview Regarding redis, meh, probably too soon to panic there but no hard in bringing it up.
Can you use redis distributed lock if you need to scale up redis?
Yah! Realistically you'd have an instance per geo which would handle scaling, but you can also have a cluster. Note, Martin famously has some strong opinions here: martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
These are valid, but a bit academic in my opinion.
Thank you for explaining in depth. But, can you please share if we are using redis, queue or dynamo db. How much knowldge do we need related to them as they are very vast and interviewers can deep dives them as well?
Please share opinions
This totally depends on your level. If more junior, then not a ton. If senior or staff, then you should have at least a decent understanding with the ability to go deep in a handful of, but not all, technologies.
how will quad tree or geohashing work for matching? on your image of quadtrees it might be the case that one of red dots is closer to the green one than to other red dots.
Also it took this well prepared guy who didn't think twice on anything 45 minutes to finish first deep dive. at amazon they will give you 35 minutes in total for a system design.