Loading...
Data Storage:
Map Data: Estimated at 1 Petabyte (PB).
Traffic Data: Hundreds of TB daily.
Assuming 500 TB/day, 500 TB * 365 days = 182,500 TB annually.
POI (Point of Interest) Data: Estimated over 100 TB.
Server Resources:
Processing Power: Handling billions of user requests and real-time updates requires massive computational power.
Memory and Storage:
Each server needs sufficient memory and local storage to handle tasks efficiently.
Server specifications vary based on their purpose (rendering, routing, search).
Network Bandwidth:
User Requests:
Billions of requests daily for map tiles, navigation, and POI searches.
Assuming an average of 10 TB of data transferred per request, 10 TB * 1 billion requests = 10,000,000 TB or 10,000 PB of daily bandwidth.
Overall Capacity:
Data Storage: Potentially several Exabytes (EB).
1 EB = 1,000 PB
Servers: Millions globally.
Network Bandwidth: Massive, spanning multiple continents.
For various operations, the APIs use common HTTP methods like GET, POST, and PUT:
A distributed database architecture is used by Google Maps to provide scalability and reliability. For real-time analytics, they might use Bigtable on Google Cloud, and for structured data, they might use Cloud SQL, a relational database.
Our system should be highly scalable. It should employ a number of strategies, such as the following, to manage numerous concurrent users and requests:
Below is the flow for user searching for a place, setting route for that place and then searcing for new places along the way.
Geocoding is the process of converting addresses to geographic coordinates. For instance, “1600 Amphitheatre Parkway, Mountain View, CA” is geocoded to a latitude/longitude pair of (latitude 37.423021, longitude -122.083739).
In the other direction, the conversion from the latitude/longitude pair to the actual human-readable address is called reverse geocoding.
Geohashing is an encoding system that encodes a geographic area into a short string of letters and digits. At its core, it depicts the earth as a flattened surface and recursively divides the grids into sub-grids, which can be square or rectangular. We represent each grid with a string of numbers between 0 to 3 that are created recursively.
Using Quad Trees
For our solution, we can use quad trees to store the geo hashes. Quad trees are hierarchical data structures used to represent spatial data. They recursively partition a space into four equal quadrants until each quadrant contains a manageable number of data points or reaches a specified depth. In the context of map rendering and storage using geohashing, quad trees can play a crucial role in efficiently organizing and querying spatial data.
Here's how quad trees can be used for storing geohash data in the context of Google Maps:
Road data processing for navigation algorithms
Most routing algorithms are variations of Dijkstra’s or A* pathfinding algorithms. It is important to note is that all these algorithms operate on a graph data structure, where intersections are nodes and roads are edges of the graph.
The pathfinding performance for most of these algorithms is extremely sensitive to the size of the graph. Representing the entire world of road networks as a single graph would consume too much memory and is likely too large for any of these algorithms to run efficiently. The graph needs to be broken up into manageable units for these algorithms to work at our design scale.
One way to break up road networks around the world is very similar to the tiling concept we discussed for map rendering. For each grid, we convert the roads within the grid into a small graph data structure that consists of the nodes (intersections) and edges (roads) inside the geographical area covered by the grid.
By breaking up road networks into routing tiles that can be loaded on demand, the routing algorithms can significantly reduce memory consumption and improve pathfinding performance by only consuming a small subset of the routing tiles at a time, and only loading additional tiles as needed.
Hierarchical routing tiles
Efficient navigation routing also requires having road data at the right level of detail. For example, for cross country routing, it would be slow to run the routing algorithm against a highly detailed set of street-level routing tiles. The graph stitched together from these detailed routing tiles would likely be too large and consume too much memory.
There are typically three sets of routing tiles with different levels of detail. At the most detailed level, the routing tiles are small and contain only local roads. At the next level, the tiles are bigger and contain only arterial roads connecting districts together. At the lowest level of detail, the tiles cover large areas and contain only major highways connecting cities and states together. At each level, there could be edges connecting to tiles at a different zoom level. For example, for a freeway entrance from local street A to freeway F, there would be a reference from the node (street A) in the small tile to the node (freeway F) in the big tile.
Map Rendering
The world’s map is projected into a huge 2D map image. It is broken down into small image blocks called “tiles” (see below). Now when the user zooms into the map we can serve a pre-generated set of map tiles at each zoom level. The map tiles are static, with each tile covering a fixed rectangular grid using a subdivision scheme like geohashing. Each tile is therefore represented by its geohash. In other words, there is a unique geohash associated with each grid. When a client needs a map tile, it first determines the map tile collection to use based on its zoom level. It then computes the map tile URL by converting its location to the geohash at the appropriate zoom level. These static, pre-generated images are served by a CDN
User location data is valuable. We use it to update our road data and routing tiles. We also use it to build a database of live and historical traffic data. This location data is also consumed by multiple data stream processing services to update the map data.
For user location data, we need a database that can handle the write-heavy workload well and can be horizontally scaled. Cassandra could be a good candidate.
ETA service
Once the route planner receives a list of possible shortest paths, it calls the ETA service for each possible route and gets a time estimate. For this, the ETA service uses machine learning to predict the ETAs based on the current traffic and historical data.
One of the challenges here is that we not only need to have real-time traffic data but also to predict how the traffic will look like in 10 or 20 minutes.
Shortest-path service
The shortest-path service receives the origin and the destination in lat/lng pairs and returns the top-k shortest paths without considering traffic or current conditions. This computation only depends on the structure of the roads. Here, caching the routes could be beneficial because the graph rarely changes.
The shortest-path service runs a variation of A* pathfinding algorithms against the routing tiles in object storage. Here is an overview:
Explain any trade offs you have made and why you made certain tech choices...
Try to discuss as many failure scenarios/bottlenecks as possible.
For our design, we have considered quad-trees, in reality the system might be using a more efficient data structure to create the maps. we can further explore concepts like oct-trees and similar data structures.