设计谷歌地图应用

难度: hard

设计一个类似于谷歌地图的应用程序。这个应用应能计算基于目的地的最佳路径以及到达目的地所需的时间。

Solution

System requirements

Functional:

  1. Map Display:
  2. The application should display maps with various zoom levels, allowing users to view locations, roads, and geographical features.
  3. Users should be able to pan and zoom the map to explore different areas.
  4. Search and Navigation:
  5. Users should be able to enter a destination address or point of interest.
  6. The system should provide suggestions for addresses or points of interest as the user types.
  7. Users should be able to get directions from their current location to the entered destination.
  8. Route Planning:
  9. The application should calculate the best possible route considering factors like distance, traffic conditions, and user preferences.
  10. Users should have the option to choose between multiple routes if available.
  11. The system should provide estimated travel time for each route.
  12. Real-Time Traffic Information:
  13. The system should provide real-time traffic updates and suggest alternate routes if there are traffic jams or accidents.
  14. Users should have the option to enable or disable real-time traffic updates.
  15. Turn-by-Turn Navigation:
  16. Users should receive step-by-step directions while navigating, including voice guidance.
  17. The system should provide timely instructions for turns, lane changes, and other maneuvers.
  18. Estimated Time of Arrival (ETA):
  19. The application should provide users with an estimated time of arrival based on current traffic conditions and chosen route.
  20. Multiple Transportation Modes:
  21. Users should have the option to choose between driving, walking, cycling, or public transportation modes.
  22. The system should adjust route suggestions based on the selected transportation mode.
  23. Offline Maps:
  24. Users should be able to download maps for offline use in areas with poor or no internet connectivity.
  25. The application should provide regular updates for offline maps to ensure accuracy.

Non-Functional:

  1. Performance:
  2. The system should provide fast response times for map rendering, route calculation, and navigation instructions.
  3. The application should be capable of handling a large number of concurrent users without significant performance degradation.
  4. Reliability:
  5. The system should be highly reliable, with minimal downtime or service interruptions.
  6. It should gracefully handle errors and unexpected events, such as loss of GPS signal or network connectivity issues.
  7. Usability:
  8. The user interface should be intuitive and easy to use, catering to users of all levels of technical expertise.
  9. Navigation instructions should be clear and concise, ensuring that users can easily follow directions.
  10. Scalability:
  11. The system should be scalable to accommodate an increasing number of users and data volume.
  12. It should be able to handle peak loads during rush hours or special events without performance degradation.
  13. Security:
  14. User data, including location information, should be securely stored and transmitted.
  15. The application should implement authentication and authorization mechanisms to protect user privacy and prevent unauthorized access.
  16. Accessibility:
  17. The application should comply with accessibility standards to ensure that users with disabilities can use it effectively.
  18. Features such as voice-guided navigation should be accessible to users with visual impairments.
  19. Compatibility:
  20. The application should be compatible with a wide range of devices and operating systems, including smartphones, tablets, and desktop computers.
  21. It should support popular web browsers and mobile platforms such as iOS and Android.

Capacity estimation

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.

API design

  1. Map Display API:
  2. Description: This API will retrieve and display maps for the specified location.
  3. Input: Latitude and longitude coordinates or an address.
  4. Output: Map image or interactive map interface.
  5. Route Calculation API:
  6. Description: This API will calculate the best route between two points based on various factors such as traffic conditions and user preferences.
  7. Input: Starting and ending coordinates or addresses, transportation mode (driving, walking, cycling, public transit).
  8. Output: List of waypoints or coordinates for the optimal route, including distance, estimated travel time, and any alternate routes.
  9. Traffic Information API:
  10. Description: This API will provide real-time traffic updates and suggest alternate routes to avoid congestion.
  11. Input: Current location coordinates or an address.
  12. Output: Traffic conditions along the specified route, including congestion levels, accidents, and road closures.
  13. Navigation Guidance API:
  14. Description: This API will provide turn-by-turn navigation instructions for a given route.
  15. Input: List of waypoints or coordinates for the route, transportation mode.
  16. Output: Step-by-step navigation instructions, including directions, distances, and estimated arrival time, possibly delivered as text or voice-guided instructions.
  17. Search Places API:
  18. Description: This API will allow users to search for places of interest or addresses.
  19. Input: Search query (e.g., restaurant, gas station, museum), location coordinates or address.
  20. Output: List of relevant places matching the search query, including names, addresses, and possibly ratings or reviews.
  21. Offline Maps API:
  22. Description: This API will enable users to download maps for offline use.
  23. Input: Area to be downloaded (specified by bounding box or region).
  24. Output: Downloaded map tiles or map data files for offline storage and navigation.
  25. Geocoding API:
  26. Description: The Geocoding API allows developers to convert addresses to geographic coordinates (latitude and longitude) and vice versa.
  27. Input:
  28. For address to coordinates conversion: The address or place name to be geocoded.
  29. For coordinates to address conversion: The latitude and longitude coordinates.
  30. Output:
  31. For address to coordinates conversion: The corresponding latitude and longitude coordinates.
  32. For coordinates to address conversion: The formatted address or place name corresponding to the provided coordinates.

For various operations, the APIs use common HTTP methods like GET, POST, and PUT:

  • GET: Get information, like directions or map tiles.
  • POST: Send in data, like user location updates or newly contributed points of interest.
  • PUT: Modify current information, like a company’s address or operating hours.

Database design

  • Map Data Database:
  • This database is required for storing unstructured or semi-structured data like terrain information, satellite imagery, and street-level imagery, it should support flexibility of schema design and scalability for handling large volumes of spatial data.
  • CAP Theorem Focus: Availability Focused - In the context of map data, it's crucial to ensure that the data is available for users to access at any given time, even in the face of network partitions or node failures.
  • Routing Database:
  • This database is required for querying complex relationships between road networks, traffic patterns, and road closures, allowing efficient route calculations and real-time traffic updates.
  • CAP Theorem Focus: Balanced - While availability is important for providing real-time route suggestions, consistency is also crucial to ensure accurate and reliable routing information.
  • Places Database:
  • a scalability and high availability database should be chosen here, making them suitable for storing and retrieving large volumes of unstructured or semi-structured data such as social media posts, restaurant reviews, and business listings associated with places.
  • CAP Theorem Focus: Availability Focused - The focus here is on ensuring that users can access place-related information quickly and reliably, even under high load conditions or network disruptions.
  • Real-time Data:
  • A database suitable for storing and processing real-time data streams from traffic sensors, weather stations, and social media platforms should be chosen.
  • CAP Theorem Focus: Availability Focused - Real-time data needs to be readily available for analysis and processing to provide up-to-date information to users, prioritizing availability over strict consistency.

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:

  • Load balancing:-multiple load balancers will be required to disperse traffic among several servers. This makes it possible for the system to manage even the highest traffic volume.
  • Replication:- Data is replicated by Google Maps among several servers. This contributes to maintaining high system availability and preventing data loss.
  • Caching:- Google Maps caches information that is accessed often. This lessens the strain on the database servers and enhances performance.

High-level design

  1. User Interface (UI):
  2. The user interface component provides the graphical interface for users to interact with the application, including map display, search functionality, and navigation controls.
  3. Technologies: HTML5, CSS, JavaScript (e.g., React, Angular), and mobile development frameworks for iOS and Android (e.g., Swift, Kotlin).
  4. Frontend Services:
  5. Frontend services handle user requests, manage sessions, and communicate with backend servers.
  6. Technologies: RESTful APIs, GraphQL for data fetching, WebSocket for real-time updates, and JavaScript frameworks for frontend development.
  7. Backend Services:
  8. Backend services manage data processing, storage, and business logic, including map rendering, route calculation, and traffic updates.
  9. Technologies: Microservices architecture, cloud computing platforms (e.g., AWS, Google Cloud Platform), serverless computing for scalability, and containerization (e.g., Docker, Kubernetes) for deployment.
  10. Maps Data Service:
  11. This component manages the storage and retrieval of map data, including terrain information, satellite imagery, street-level imagery, and POI (Points of Interest) data.
  12. Database Type: NoSQL databases like MongoDB or Cassandra for scalability and flexibility in handling large volumes of spatial data.
  13. Routing Service:
  14. The routing service calculates optimal routes based on factors such as distance, traffic conditions, and user preferences.
  15. Database Type: A combination of SQL and NoSQL databases may be used, depending on the specific requirements. For example, SQL databases for road network information and NoSQL databases for traffic patterns and real-time data.
  16. CAP Focus: Balanced approach focusing on availability and consistency, ensuring reliable and accurate route calculations.
  17. Places Service:
  18. The places service provides information about businesses, landmarks, and other points of interest, including social media posts, reviews, and business listings.
  19. Database Type: NoSQL databases like MongoDB or Elasticsearch for flexibility in storing and querying unstructured data such as social media posts and reviews.
  20. Real-Time Data Service:
  21. This component aggregates and processes real-time data sources such as traffic sensors, weather stations, and social media platforms to provide up-to-date information to users.
  22. Database Type: NoSQL databases like Cassandra for high availability and fast writes, suitable for handling large volumes of real-time data.
  23. Caching Layer:
  24. A caching layer improves performance by storing frequently accessed data, such as map tiles, route calculations, and POI information.
  25. Technologies: Memcached or Redis for in-memory caching, CDNs (Content Delivery Networks) for caching static assets like map tiles.
  26. Authentication and Authorization:
  27. Authentication and authorization components handle user authentication, access control, and session management to ensure secure access to the application.
  28. Technologies: OAuth 2.0 for authentication, JWT (JSON Web Tokens) for session management, and role-based access control (RBAC) for authorization.
  29. Monitoring and Logging:
  30. Monitoring and logging components track system performance, detect errors, and provide insights for troubleshooting and optimization.
  31. Technologies: Logging frameworks (e.g., Log4j, ELK stack), monitoring tools (e.g., Prometheus, Grafana), and error tracking platforms (e.g., Sentry, Rollbar).
graph TD

    subgraph User_Interface
        A[User Interface] -- User Requests --> B[Frontend Services]
    end

    subgraph Backend_Services
        B -- Request Processing --> C[Backend Services]
    end

    subgraph Data_Services
        D[Maps Data Service] -- Data Retrieval --> H((Maps Data Database))
        E[Routing Service] -- Route Calculation --> I((Routing Database))
        F[Places Service] -- Places Information --> J((Places Database))
        G[Real-Time Data Service] -- Real-Time Data --> K((Real-Time Data))
        N((Caching Layer)) -. Cached Data .-> C
    end

    subgraph Authentication_Authorization
        C -- Authentication & Authorization --> L[Auth Service]
        L -- Secure Access --> P[User Database]
    end

    subgraph Monitoring_Logging
        C -- Monitoring & Logging --> M[Monitoring Service]
        M -- Logs & Metrics --> Q[Logging Database]
    end

    O[Real-Time Updates] --> B

Request flows

Below is the flow for user searching for a place, setting route for that place and then searcing for new places along the way.

Detailed component design

Geocoding​

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​

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:

  • Spatial Partitioning: Initially, the entire geographical area covered by Google Maps is represented as a single bounding box. This bounding box is divided into four equal quadrants, creating the root node of the quad tree.
  • Geohash Storage: Each geohash represents a rectangular area within the geographical space. When storing geohash data in a quad tree, each node in the quad tree corresponds to a bounding box that covers a specific region of the map. Geohashes falling within the bounds of each node are stored within that node.
  • Hierarchical Structure: As the quad tree grows, nodes are recursively subdivided into smaller quadrants until each node contains a manageable number of geohashes or reaches a maximum depth. This hierarchical structure allows for efficient querying of geohashes within specific regions of the map.
  • Spatial Indexing: Quad trees provide spatial indexing, enabling fast retrieval of geohashes based on their spatial proximity to a given location or bounding box. This indexing mechanism is crucial for tasks such as finding nearby points of interest, routing, and map rendering.
  • Range Queries: Quad trees facilitate range queries by efficiently identifying all geohashes within a specified geographic area. This capability is essential for tasks such as displaying map tiles, rendering map features, and retrieving spatial data for a given viewport.
  • Dynamic Updates: Quad trees support dynamic updates, allowing for efficient insertion, deletion, and modification of geohash data. This flexibility is vital for maintaining an up-to-date representation of the geographical space covered by Google Maps.

Using R-Trees

  • Structure: R-trees are hierarchical data structures used for indexing spatial data. Each node in an R-tree represents a bounding box that encompasses a group of spatial objects or data points.
  • Organization: R-trees organize spatial data in a balanced tree structure, where each node contains references to child nodes or spatial objects.
  • Spatial Queries: R-trees support efficient spatial queries such as range queries (searching for objects within a specified region) and nearest neighbor queries (finding the closest object to a given point).
  • Map Data Retrieval: In the context of Google Maps, R-trees can be used to index various spatial entities such as roads, points of interest (POIs), and geographic features. This allows for fast retrieval of map data based on user queries, such as finding nearby restaurants or displaying road segments within a specific area.
  • Performance: R-trees offer good performance for both insertion and query operations, making them suitable for real-time applications like Google Maps that require rapid spatial data retrieval.

Generally R-Trees are more preferred over quad-trees for the following reasons:

  1. Efficiency: R-trees are more efficient in terms of storage and query performance, especially for large-scale spatial datasets. They can handle overlapping and irregularly shaped spatial objects more effectively compared to quad-trees.
  2. Flexibility: R-trees can index multidimensional spatial data, making them suitable for applications beyond just 2D spatial indexing. They can handle data in higher dimensions, such as 3D spatial data (e.g., for modeling buildings or landscapes) or temporal data (e.g., tracking moving objects over time).
  3. Complex Queries: R-trees support a wider range of spatial queries, including range queries, nearest neighbor queries, and spatial joins, making them more versatile for complex spatial analysis tasks.
  4. Standardization: R-trees have been standardized (e.g., by the Open Geospatial Consortium) and are supported by many GIS libraries and databases, which makes them easier to implement and integrate into existing systems.

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​

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:

  • The algorithm receives the origin and destination in lat/lng pairs. The lat/lng pairs are converted to geohashes which are then used to load the start and end-points of routing tiles.
  • The algorithm starts from the origin routing tile, traverses the graph data structure, and hydrates additional neighboring tiles from the object store (or its local cache if it has loaded it before) as it expands the search area. It’s worth noting that there are connections from one level of tile to another covering the same area. This is how the algorithm could “enter” the bigger tiles containing only highways, for example. The algorithm continues to expand its search by hydrating more neighboring tiles (or tiles at different resolutions) as needed until a set of best routes is found.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

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.


得分: 8