Requirements of Google Maps' Design
Understand the requirements to design a maps application like Google Maps.
Requirements
Before we start requirements, let’s clarify that we will design a system like Google Maps by picking a few key features because actual Google Maps is feature-rich and complex.
Let’s list the functional and non-functional requirements of the system under design.
Functional requirements
The functional requirements of our system are as follows.
- Identify the current location: Users should be able to approximate their current location (latitude and longitude in decimal values) on the world map.
- Recommend the fastest route: Given the source and destination (place names in text), the system should recommend the optimal route by distance and time, depending on the type of transportation.
- Give directions: Once the user has chosen the route, the system should list directions in text format, where each item in the list guides the user to turn or continue in a specific direction to reach the destination.
Non-functional requirements
The non-functional requirements of our system are as follows.
- Availability: The system should be highly available.
- Scalability: It should be scalable because both individuals and other enterprise applications like Uber and Lyft use Google Maps to find appropriate routes.
- Less response time: It shouldn’t take more than two or three seconds to calculate the
ETA Estimated Time of Arrival - Accuracy: The ETA we predict should not deviate too much from the actual travel time.
Note: We’re not getting into the details of how we get the data on roads and layout. Government agencies provide maps, and in some places, Google itself drives mapping vehicles to find roads and their intersection points. Road networks are modeled with a graph data structure, where intersection points are the vertices, and the roads between intersections are the weighted edges.
Challenges
Some of the challenges that we need to focus on while designing a system like Google Maps are below:
- Scalability: Serving millions of queries for different routes in a second, given a graph with billions of nodes and edges spanning over 194 countries, requires robust scalability measures. A simple approach, given the latitude and longitude of the source and destination, would be to apply an algorithm like Dijkstra to find the shortest path between the source and the destination. However, this approach wouldn’t scale well for billions of users sending millions of queries per second. This is because running any path-finding algorithm on a graph with billions of nodes running a million times per second is inefficient in terms of time and cost, ultimately leading to a bad user experience. Therefore, our solution needs to find alternative techniques to scale well.
- ETA computation: In an ideal situation with empty roads, it’s straightforward to compute ETA using the distance and the speed of the vehicle we want to ride on. However, we cannot ignore factors like the amount of traffic on the roads and road conditions, which affect the ETA directly. For example, a road under construction, collisions, and rush hours all might slow down traffic. Quantifying the factors above to design our system is not trivial. Therefore, we’ll, categorize the factors above in terms of traffic load to complete our design.
Resource estimation
Let’s estimate the total number of servers, storage, and bandwidth required by the system.
Number of servers estimation
To estimate the number of servers, we need to know the number of daily active users of Google Maps. Let’s assume that we have 32 million daily active users of Google Maps. Considering our assumption of using daily active users as a proxy for the number of requests per second, we get 32 million requests per second. Then, we use the following formula to calculate the number of servers:
Using 64,000 as an estimated RPS a server can handle from "Back-of-the-envelope Calculations" section, the required servers are estimated as follows:
Storage estimation
Google Maps is essentially a system with a one-time storage requirement. The road data from many countries has already been added, which is over ...