ฝัง
- เผยแพร่เมื่อ 18 พ.ค. 2020
- This is a solution for System Design Interview Question where you need to design a Map + Navigation application like Google Maps.
This problem has been asked by a lot of companies like Google, Amazon, Flipkart, Walmart Labs to name a few.
Prerequisites:
How to select the right Database for a Large Scale System: • Database Design Tips |...
Summary of this video: www.codekarle.com/system-desi...
Architecture diagram: github.com/codekarle/system-d...
Author: / sandeep1904
If you like this video, please help us grow by sharing this video with your friends on Facebook, connections on LinkedIn and anyone who can benefit from this.
PS: This is not the real architecture of Google Maps or any other similar service. This is my take on how I would answer that problem.
#codekarle #systemdesign #googlemaps #googlemapssystemdesign #system #design #interview #faang #maps
I reckon this will become the best system design channel in youtube. Keep up the good work !
Thanks for the motivation! Do share it with your friends to help us get there 🙂
I second this. This is by far the best system design video I watched on youtube.
true
Exactly.
No doubt about that.
This is brilliant but Im kinda surprised you didnt mention quad trees. They are the standard way to solve problems like this.
I banged the first AWS interview and Meta interview in one go. Thanks for the detailed explanation! Not sure if you are active anymore, but you deserve lot more followers than what you have.
how is it going now?
While preparing for interviews for experienced level, one can agree that system design level is the deciding round many times. I also used to struggle in these rounds and hence searched hell lot of resources to understand the concept but nowhere found satisfying result. This is the only channel where I started seeing patterns in designs, role of different components, out of the box solutions and no-fancy/complex components/logic.
Designs explained are so simple that after going through few designs, any one can start creating boxes and understand flows between them while approaching to a new problem.
Thanks Prateek!
The whole idea of this channel is to propose simple solutions to complex real world problems :)
Do spread the word about the channel among your connections! It helps :)
This is the level of details that helps in real interviews. Thanks!
Discussion around - Disputed areas, last bit of inferences like pub goers are social etc..was icing on the cake!!!
Thanks for keeping the explanations simple. I have seen some videos where people just bombard with jargons reducing interest.
This was on its way to become the best sys design channel on TH-cam but why did you stop making videos? All other channels just have scattered information and no clarity of thought. Can you start making videos again and cover more systems asked in interviews? It will be of great help to budding software engineers!
It was an awesome video. Thank you very much!
Some friendly suggestions:
1. Data models could be added (KV stores, data size, replication and sharding)
2. Instead of specific technology names, generic names could be used. "Queue" instead of Kafka, "NoSQL database" instead of Cassandra
3. Geospatial index could be mentioned
Yeah, true, that could be done :)
@@codeKarle why Cassandra is chosen in this scenario. It is column based databases? why not document db kind of db is used?
I have watched quite a lot of system design videos from different sources, and this by far, exceeds most of them in technical depth and breadth. It's not too academic and neither too complex, well done! I am recommending this channel to my peers.
After 2 years, still an amazing video!
Very smart to include discussion of disputed areas in this video
Great Effort to put all the complex pieces together. As we all agree google maps is one of the complex designs in the world and you have done justice to explain this is best possible way. Great Effort.
Very comprehensive!!
Liked the "Summary of this video" too.
The best video on this topic I found so far
Loved your approach about calculating distances ..
Thanks for the amazing series. I would just recommend going with simple design problems to start with and increment the complexity for beginners. Thanks
You are pretty smart! Thank you for your videos. I am learning it out of curiosity
Thanks!! Happy that the videos are helping you
This is a very solid 1-hr content!
Thanks for the video. Could you comment a little bit on the schema of the Cassandra tables storing segments/distances between exit points of segments? Also, how come you didn't consider using a graph database such as Neo4j? (I don't know much about it at all, but I would think it is designed specifically for a usecase like this?)
This is an awesome system design video given the scope and difficulty of the problem. One suggestion I had was to also add link of slides or screenshots of the diagram drawn at different stages of the video :)
Your all videos are awesome.
This was a really awesome video. The first 40 min. were gem
Awesome. Very well explained.
I have a question on the design: Shouldn't we use some kind of graph database (say, Neo4j for example) to store the graph instead of Cassandra?
Quality content as always. But plz do something about your audio.
Questions about the algorithms being chosen:
a) In the initial few minutes the presenter mentions Bellman-Ford. Isnt that quite inefficient unless you are trying to look for negative cycles?
b) Later he mentions Djistkra'a algorithm. Isn't the A* algorithm better as you don't need to evaluate all paths. Additionally, the heuristic could be dynamic based on traffic patterns. My thoughts were you could use A* for finding cost to go to different entry / exit points from inside for lowest level of granularity and then use the same A* algorithm to evaluate cost between different entry / exit points (like intra city travel)
Great video. My question would be regarding what does the data look like which we are storing in Cassandra. For almost all of the storage data you have chosen Cassandra but other factors like data access pattern and what sort of queries will be used on that data should also be considered. It would be great if you can elaborate more on that as well.
Very strong presentation. Actually the best what I have seen about this topic. Appreciate.
Awesome explaination ...
This channel will become a boom ...
This was an amazing explanation!!! I request you to please post a video about LinkedIn System Design as well. Good Work!!!
Thanks!!
That would be almost the same design as Facebook, since both have the same feature set like posts, likes, comments, share, etc. Only the Jobs thing is different, but if we can skip that, I would recommend to watch the Facebook System Design video here: th-cam.com/video/9-hjBGxuiEs/w-d-xo.html
Amazing bro, I like it, keep it up 👍
Super explanation of a very complex system. Thank you
woah!!! awesome work, keep doing that
Thanks for the kind words!! Do share it with your friends :)
Thanks for an informative video, Sandeep. Could you also please include the reasoning behind going with specific db choices, external services like hadoop etc instead of a different competitive service?
Awesome work you are doing. I would like if you can do small videos covering topics like SQL/ NoSQL, Micrososervices, Kafka Messaging Queue etc.
Great suggestion! We'll do that too
Excellent content! One of the best explanation of Google map design ever. But there are too many adds, it would be great if that can be reduced.
Great job! Thank you
Thanks for this awesome video. Next would like some LLD videos too.
Very well explained !!
Thank you for the detailed explanation of the overview architecture. Can you go in-depth for the upcoming vides of the bottlenecks faced while designing DB/ CAP principles tradeoffs i.e. C/A depending on the requirements/product
Sure, well try to do that
Thank you, quite insightful
Superb explanation!
I love the content! Could you please make video about databases and streaming systems?
Amazing content
Amazing work!.. Thank you! So this idea of Exit points on Segments and cutting through exit points to reach destination from source is your own? or is there some reference?
While I did come up with this approach myself, I can't claim that I am the only one who has designed it using this idea, but till the time of recording, I haven't come across anyone else using the same approach.
I believe Google would be doing something more optimal than this.
Nice Sandeep. Hope to see more content from you, but scoped to 35 min. But this one was informative to every minute and a nice write up!
Mega Segments: Are you meaning to say that in creating a route from Bengaluru to Mumbai, the constituencies or taluks along the way don't matter in that " outer layer" of computation because those have been reduced to a point (Sholapur or Kolhapur) in that layer where we apply the algorithm? This means something like min of a sum ~= generally a sum of minimums, which avoids end-to-end (massive, over) computation for little to no gain (in fact losing computation time, storage). O(nlogn) is >> O(mlogm) + O(klogk) + .. where m,k are < n (may add up to n). I didn't mean to get into maths, but that is what we are looking at in breaking a continuous spectrum of points to discrete points for each outer layer. Is this about accurate?
I don't see you use spatial database like quadtree. What is your opinion?
So long the Djikstra's algorithm is applied between cities, it picks up the best cached routes for the exit points of the cities of Sholapur or Kolhapur.
Thank you for Sharing
Thank you for google map . Didn't find any other video on this topic. u did a wonderful job.🙂
Thanks you :)
Let us know what other videos you'd like to see
@@codeKarle google search 🙂
@@nikitasinghchauhan6239 that would be live soon!!
Very nice explanation. Content is really good. This kind of content is not there anywhere on the internet. Can you please make a video on how distributed message queue works?
It would be interesting to tackle not so common system design interview questions also.
For example, about TinyURL there are a lot of system design videos already.
It would be challenging to see a system design video about Google Photos for example and how do they manage to provide "unlimited" storage space for Pixel users (at least).
Those are coming soon
@@codeKarle will you be producing more content ?
you channel name should be DesignKarle instead 😛
Thanks you. Nice explanation
Thank you for the helpful tutorial. qq: why are you using Cassandra for the Graph Processing service? shouldn't you be using a graph DB like Neo4j? As far as I know, Cassandra is a wide-column DB, not a graph DB.
Really good video, all parameters considered 👍
This can be further extended to series of parts. Especially, I am little more interested in the creation of segment, underlying data model of it, persistence logic, and updating the segments. When to increase the current segment range? When to break the current segment range to smaller segments?
Sorry if this sounds basic, but I'm new to system design and still learning. Can you explain why you didn't save which user is linked to which WebSocket handler at 41:35 in the video? You mentioned polling for this info, but where does it come from exactly? Is it from the WebSocket handler itself?
By the way, great video! 🙌 I really learned a lot from it and appreciate your work!
Good video. One suggestion : you could add a section on how search works in google maps. Chinese restaurants near me or best 5 star hotels near bus stop?
Perfect!
Websocket handler/manager is primarly required in the navigation flow not while collecting the lat/lon of users. what do you think ?
How does this approach (considering exits) help in reducing time complexity on the whole, as we are internally applying floyd-warshall for each segment to get the minimum distance between exits of every segment in between and then using this information to build a graph?
wah mza aagya subbed
super。learning new knowledge，ilove it
excellent one
Sandeep Kaul Sir ,all your videos are extremely useful for design preparation. if possible please speak little slow or pause for some seconds. Thanks in advance.
Awesome Video. One question though - shouldn't each segment have separate exit and entry point though? There can be scenarios where exit is allowed(one-way) but not entry. In that case, we would have to maintain exit and entry points for each segment and mega-segment.
Thanks a lot for your work! I believe the word you're looking for is "cell" (5:56)
Firstly thanks for this lovely channel. The explanations are so good.
I have a doubt: Can Map Service have a Cache so that if multiple people are asking for same location it doesnt need to ask for route to Graph Processing service?
do you keep a ETA heap for each segment? Not sure how you can efficiently bubble up when a road condition is changed.
Awesome and details content. Can you make a video about distributed scheduler ?
Hi, thanks for this awesome video.
I have a question around the the design. So at around @31:45 you talk about is the weight of any edge changes, we need to update the cache, and recursively bubble up the results. I want to confirm, if you are a) re-running the shortest path algo again in that segment to evaluate distance between all nodes, or b) just updating the current shortest path with increased value. I think option a) is the correct one. You take the example - if the time take for an edge increases from 10s to 15s, we increase the time taken for route by 5s and then bubble it up. (Which sounds like option b).
I could be wrong here but I see two variations :
1. Increase in travel time on one of the roads : We can recompute only the paths which used this road since only these would be affected.
2. Decrease in travel time on one of the roads : We can recompute the matrix of all entry and exit points. Doing so on each update would be too expensive, so probably we can wait for a batch of updates.
can you please explain why you are using Cassandra as a persistent storage for the graph service?
Can we use any graph db for the purpose like neo4J?
very good content, but the audio is a torture.
Thank You
Very informative and abstract; given its very challenging design question. Could have broken into 2-3 videos on realtime route algorithm, pre-processing routes, analytics just to justify each of them individually. Also, some points on choosing right datastore and rationale behind each. Wonderful job though :)
yes, trying this 2-3 videos thing in the next one, hopefully we'll be able to make it easy for people to correlate things across videos :)
For Datastores, you can look at this: th-cam.com/video/cODCpXtPHbQ/w-d-xo.html
Great work. It will be great if you can put some content about Google Doc and git design.
Sure, but that might take a while to be live :)
Thanks!
Good Explanation.. Good Job !..
Que: How Zoom Aggragate video streaming in One UI (on Zoom Client)?
quite good content
Thanks for the video.. 1. If the user changes from the route suggested how the re-route will be calculated and made visible ? Which particular service will be responsible for it?
I am watching your tutorials one by one on daily basis, wishing all good for you with upcoming videos. I request you to do a video on Slack
But how do you identify what all segments you should consider to calculate distance between two points? You traverse through entire graph or say max 10 segments from each direction?
So spark streaming is consuming as well as writing back to kafka? or are we going to create a different kafka for that?
Really amazing work! Can you please explain: when an user makes Get call to the API and google returns response. Return response is that GET or POST. What format does that data/response flow? Is it binary?
Thanks!! Ideally that would be a Get request, with start and end point details like Lat Long, and a preference if they want to minimize the distance or the time. In the response the server would send back ETA, Distance and then the lat longs of some points in the best route. The response format could be anything. to keep it simple I would keep a simple json there.
great video, i think a little more details on the database schema would have helped more to some readers. At least now i know how google works/worked hypothetically :)
🎯 Key Takeaways for quick navigation:
00:02 🗺️ Navigation app design like Google Maps requires route, distance, and time info.
00:57 🔌 System design should be pluggable for easy addition of features like traffic, weather, etc.
02:22 🌐 The system needs to handle high availability, good accuracy, and reasonable speed.
03:50 📈 Massive scale: Billions of user requests, millions of companies using the platform.
04:18 🛣️ Building a navigation app is challenging due to vast road data and unpredictable attributes affecting ETA.
22:14 🗺️ Mega-Segment approach: Dividing the map into Mega-Segments containing exit points, simplifying navigation across large areas.
24:32 ⏲️ Weight calculation: Factors like distance, ETA, and average speed influence weights; traffic and weather are attributes, not weights.
27:19 🚗 Traffic data: Utilizing real-time user data for traffic; data is normally distributed, allowing prediction within confidence intervals.
30:05 🔄 Dynamic updates: Changing ETA due to traffic/weather; cascading updates through segments and Mega-Segments when weights change significantly.
39:33 📊 System architecture: Overview of user location tracking, data processing, and updates to enhance map service.
45:32 📍 Hotspot Identifier: Identifying areas with increased activity using location data, enabling better traffic prediction and navigation.
46:32 🚗 Vehicle Identifier: Analyzing location pings to determine the type of vehicle (e.g., car, bus, two-wheeler) and enhance navigation insights.
49:20 🗺️ Area Search Service: Converts location search into lat/long, aiding navigation and route calculation.
50:44 🛤️ Map Service & Navigation Tracking: Handling user navigation, course correction, and analyzing user journeys to improve recommendations.
57:22 ⏰ ETA Accuracy & Analytics: Monitoring accuracy of estimated travel times, analyzing route preferences, and inferring user profiles based on location data.
Made with HARPA AI
Hi, can anyone help with this question: System design question to design a heatmap. user can input any range of times (in minutes) and I want to be able to see the density of drivers on the map color coded You don't have to worry about the actual color coding part (assume you have some UI that will take in the count input and do the coloring for you).
God level sir!
What is the data schema for the Cassandra that is attached to the Graph Processing Service?
I wish you had gone through the design from component by component, as the meat of this video was about "segments", usually system design interviews dont happen that way.
I wonder if a video about stock trading systems can be made?
On the Disputed Areas- what if user see the map from some other country? how do google decide boundaries?
can i recommend to talk the 2nd half before the 1st half. I realized the 2nd half is much more valuable. Also can you add some concrete examples during the explanation?
Sure, I can add the examples in the future ones. Editing now if really hard, so we'll try to keep the important parts before in the next ones :)
Can you please explain how did u come up with this design? What resources did you follow?
I didn't understand the difference between theoretically calculated road and cached or real roads? Could you explain?
Can you please make a video of how payment systems work? Say Design Square or Design Visa.
Do we really need web socket connection just to collect location info... shouldn't we have web socket only when user is actively using google map. Secondly, if user is not running google map application, will the application be still running somewhere in background to send location?
When to use Cassandra ? and when to use hadoop ?
any differences ?
Can you make a video on spark streaming ?
Could we use zookeeper instead of web socket manager?
Are we expected to solve this completely for a typical SDE-2 role having 3 years experience ? because this was a lot to digest for me.
Not all of it, but a good portion of it. For an SDE-2, you could skip out analytics and the big data portion completely, and still get a positive feedback. All of it would be required in-case you are applying for an Architect role.