Loading...
[Of course, Google Map is a hugely rich app. We could add many, many, requirements - traffic changing time estimate, multiple routes, real time navigation, satellite view, 360 camera view, nearby businesses. But remember, system design is a sprint, not a marathon. Start with simple requirements.]
This estimation is quite rough, but it seems fair to conclude that graphs representing roads would be in the range of GBs to tens of GBs, likely to fit in one server.
route(start_location, destination_location)
-> This returns list of roads to take, and ETA.
[Simple API is OK! The complexity of this problem is in data modeling and path finding. We don't have to overthink API.]
[Mid-level deep dive topic. It is critical to talk about these for this problem.]
Graph Representation
To run a path-finding algorithm, e.g, A* algorithm, we will represent the map as a directed graph.
Each node presents an intersection.
Each edge represents the road from a node to another, with weights representing the distance, average travel time, and real time traffic information.
Grids
Putting all the roads in the Globe into one big graph, and running a path finding algorithm, would be very inefficient.
If we divide the Globe into grids, for example, 5 mile * 5 mile squares, it would be much easier.
For example, if the source and destination are in two neighboring grids, we can limit the path-finding algorithms to these two grids, plus surrounding grids in case there are no good direct route between the two grids. This significantly reduces the path finding search space.
Layers of Grids
Even with the grids approach, a long distance travel would still require an inefficient path finding computation. For example, to map a route from San Francisco to New York City, it would have to visit so many small roads in so many grids.
In the real world, though, drivers usually do not take local roads for many miles. Instead, they would take local roads to a highway intersection, take highways until they reach an intersection near the destination, then take load roads.
To achieve this kind of path finding, we can have layered graphs. Perhaps in three layers: (1) local, small roads, (2) larger streets typically within a city, and (3) highways.
Database Choice
Road graphs must be stored in some permanent storage. Routing Service reads this data, stores it in memory, and runs path finding algorithm on it.
Because the storage size is GBs to tens of GBs, and it does not change rapidly, RDB would be a good choice. This would allow us to take advantage of rich features of RDBs if necessary, e.g., relational queries, secondary indices, strong consistency, etc.
It is a simple high-level design. The complexity is in Routing Service itself.
Client (e.g. using a map app on a mobile phone) sends route() request to API Gateway.
API Gateway forwards the request to Routing Service.
Routing Service uses the grid data from Database to find the shortest paths and return.
Routing Service uses cache to store some already computed paths.
[Senior level deep dive]
Path Finding
We need to pick a good path finding algorithm. Let's take a look at two common algorithms: Dijkstra and A*.
We can select a reasonable heuristic function, e.g., Euclidean distance between a node and the destination location. We can refine the heuristic function as users travel, because we get the real data on how long it took the users to travel from the node to the destination.
Contraction Hierarchies (CH)
Even with A*, it would still be inefficient and slow to try to find a path that spans across many grids, e.g., an inter-city trip.
Contraction Hierarchies (CH) solves this by creating a higher level graph. It contracts smaller roads and focuses on larger roads, such as highways. Because the higher level graph has fewer nodes and edges, path finding (such as with A*) on it would be more efficient.
A real life example would be:
A driver drives from a local road to a big intersection. This is doing A* using the original graph.
A* on a higher level graph provides a path between big intersection 1 (which is close to the start) to big intersection 2 (which is close to the destination). CH provides this higher level graph.
The driver then takes a local road from intersection 2 to the destination. Again doing A* using the original graph.
Estimated Time of Arrival
Once the shortest paths are built, it is straightforward to sum up estimated time from each edge to compute the ETA of the whole route.
See Path Finding discussion above for the trade offs between Dijkstra and A* algorithms.
Caching
Many people travel using this system (1B DAU!). Many would travel on the same route. We do not need to compute shortest paths every time user requests that route.
We can easily cache this in a cache system such as Redis.
Cache key would be: (start_node, end_node)
Cache object would include: (route, ETA)
This would drastically improve the amount of computation we have to spend in path finding.
Real Time Traffic
In this design, we did not include real time traffic in consideration. It would be a very useful addition. We do not want to send a user to a particular route, thinking it's usually a good path, only to find out it has a terrible traffic jam right now.
Real time traffic information can be obtained by location updates from this system's users. If we find some edges are taking much longer than usual, we can indicate that in the graph, and re-run the path finding algorithm for the routes that include this edge.