# Requirements of Google Maps' Design

### Requirements <a href="#requirements-0" id="requirements-0"></a>

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 <a href="#functional-requirements-1" id="functional-requirements-1"></a>

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.

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2F2MKj63Sfk3tr0g48Gc2M%2FScreenshot%202023-09-03%20at%2011.42.29%20AM.png?alt=media&#x26;token=e714397f-0e18-4cfd-bbc9-23a98ef6970e" alt=""><figcaption></figcaption></figure>

#### Non-functional requirements <a href="#non-functional-requirements-0" id="non-functional-requirements-0"></a>

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 and the route, given the source and the destination points.
* **Accuracy**: The ETA we predict should not deviate too much from the actual travel time.

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2Fb7gsd9XWJhhkBqShrsfD%2FScreenshot%202023-09-03%20at%2011.42.54%20AM.png?alt=media&#x26;token=f5da9363-bd91-4a1d-a5f0-d0791326b30b" alt=""><figcaption></figcaption></figure>

**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 <a href="#challenges-0" id="challenges-0"></a>

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.

A graph spanning the whole world network

* **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.

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2FDesE2TjnKzyrkJmYddvr%2FScreenshot%202023-09-03%20at%2011.43.09%20AM.png?alt=media&#x26;token=6865138c-e48d-4b50-a38d-d20bc1078237" alt=""><figcaption></figcaption></figure>

### Resource estimation <a href="#resource-estimation-0" id="resource-estimation-0"></a>

Let’s estimate the total number of servers, storage, and bandwidth required by the system.

#### Number of servers estimation <a href="#number-of-servers-estimation-1" id="number-of-servers-estimation-1"></a>

To estimate the number of servers, we need to know how many daily active users are using Google Maps and how many requests per second a single Google Maps server can handle. We assume the following numbers:

* Daily active users who use Google Maps: 32 million (about 1 billion monthly users).
* Number of requests a single server can handle per second: 8,000.

The number of servers required has been calculated using the below formula:

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2FIttiIT3fBfxxONgyD8b0%2FScreenshot%202023-09-03%20at%2011.43.42%20AM.png?alt=media&#x26;token=2d9a486f-ff21-4403-b65a-f877cb90add7" alt=""><figcaption></figcaption></figure>

#### Storage estimation <a href="#storage-estimation-0" id="storage-estimation-0"></a>

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 20 petabytes as of 2022. Since there are minimal changes on the road networks, the daily storage requirement is going to be negligible for Google Maps. Also, short-term changes in the road network is a small amount of data as compared to the full network data. Therefore, our storage needs don’t change rapidly.

#### Bandwidth estimation <a href="#bandwidth-estimation-0" id="bandwidth-estimation-0"></a>

As a standard practice, we have to estimate the bandwidth required for the incoming and outgoing traffic of our system. Most of the bandwidth requirements for Google Maps are due to requests sent by users. Therefore, we’ve devised the following formula to calculate bandwidth:

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2FBoDNnkxYPVuX7osLbqSt%2FScreenshot%202023-09-03%20at%2011.44.16%20AM.png?alt=media&#x26;token=926b1b40-2f35-42b4-86e7-0415f09cb573" alt=""><figcaption></figcaption></figure>

**Incoming traffic**

To estimate the incoming query traffic bandwidth, we assume the following numbers:

* Maximum number of requests by a single user per day: 50.
* Request size (source and destination): 200 Bytes.

Using the assumptions above, we can estimate the total number of requests per second on Google Maps using the following formula:

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2Fziu4RfcCtpwrpAE51S4R%2FScreenshot%202023-09-03%20at%2011.44.45%20AM.png?alt=media&#x26;token=d7ac8baa-bd0b-49de-8465-e57077505029" alt=""><figcaption></figcaption></figure>

We can calculate the incoming query traffic bandwidth required by Google Maps by inserting the request per second calculated above and the size of each request in the aforementioned bandwidth formula.

**Bandwidth Required for Incoming Query Traffic**

| No. of requests per second | Request size (Bytes) | Bandwidth (Mb/s) |
| -------------------------- | -------------------- | ---------------- |
| 18518                      | 200                  | f29.63           |

**Outgoing traffic**

Outgoing application traffic will include the response that the server generates for the user when they make a navigation request. The response consists of visuals and textual content, and typically includes the route shown on the map, estimated time, distance, and more detail about each step in the route. We assume the following numbers to estimate the outgoing traffic bandwidth:

* Total requests per second (calculated above): 18,518.
* Response size: 2 MB + 5 KB = 2005 KB.
  * Size of visual data on average: 2 MB.
  * Size of textual data on average: 5 KB.

We can calculate the bandwidth required for outgoing traffic using the same formula.

**Bandwidth Required for the Outgoing Application Traffic**

| No. of requests per second | Response size (KB) | Bandwidth (Gb/s) |
| -------------------------- | ------------------ | ---------------- |
| 18518                      | 2005               | f297.03          |

Show Detailed CalculationsSummarizing the bandwidth requirements for Google Maps

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2F7jlpwEiX7c62gWMe91KW%2FScreenshot%202023-09-03%20at%2011.45.36%20AM.png?alt=media&#x26;token=3a077f80-3c7e-44a5-92f4-4779608f842a" alt=""><figcaption></figcaption></figure>

### Building blocks we will use <a href="#building-blocks-we-will-use-0" id="building-blocks-we-will-use-0"></a>

Now that we’ve completed our estimates of resources required, let’s identify the building blocks that will be an integral part of our design for the Google Maps system. Below, we have the key building blocks:

<figure><img src="https://1055613405-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MlQzjDKRh_AaQvZflWz%2Fuploads%2FZvn8DWicEN2wlHuOKXav%2FScreenshot%202023-09-03%20at%2011.46.46%20AM.png?alt=media&#x26;token=571bf9ad-e1e0-4bac-8222-9e7babc894df" alt=""><figcaption></figcaption></figure>

* [**Load balancers**](https://ylbbak99.gitbook.io/grokking-modern-system-design-interview/load-balancers/introduction-to-load-balancers) are necessary to distribute user requests among different servers and services.
* [**Databases**](https://ylbbak99.gitbook.io/grokking-modern-system-design-interview/databases/introduction-to-databases) are required to store data in the form of a graph along with metadata information.
* [**Distributed search**](https://ylbbak99.gitbook.io/grokking-modern-system-design-interview/distributed-search/system-design-the-distributed-search) is needed to search different places on the map.
* [**A pub-sub system**](https://ylbbak99.gitbook.io/grokking-modern-system-design-interview/pub-sub/system-design-the-pub-sub-abstraction) is required for generating and responding to important events during navigation and notifying the corresponding services.
* [**A key-value store**](https://ylbbak99.gitbook.io/grokking-modern-system-design-interview/key-value-store/system-design-the-key-value-store) is also used to store some metadata information.

Besides the building blocks mentioned above, other components will also be required for designing our maps system. These components will be discussed in the design lessons. We are now ready to explore the system and API design of Google Maps.
