Skip to main content

Google Maps

Google Maps is a web mapping service and navigation technology developed by Google. It provides a comprehensive map of the world that can be used to search for and locate places, view satellite imagery, and get directions between two or more points. Functional requirements for Google Maps:

  • Identify roads and routes: Google Maps uses satellite imagery and map data from various sources, including government sources, to display roads, highways, and other routes on its map. It can also onboard new routes as they become available, providing users with the most up-to-date information.
  • Distance and ETAs: Google Maps provides users with the ability to calculate the distance and estimated time of arrival (ETA) between two or more points. This information can be used for trip planning, optimizing delivery routes, and more.
  • Plugable: Google Maps can be integrated into other applications and websites, allowing developers to build custom mapping and location-based applications. This feature allows users to access Google Maps functionality within other platforms, making it a highly versatile and useful tool.

Non-functional requirements for Google Maps:

  • High availability: Google Maps must be available to users at all times, with minimal downtime. This is essential to ensure that users can access the service whenever they need it, whether for navigation or for trip planning.
  • Good accuracy: Google Maps must provide accurate and up-to-date information about roads, highways, and other routes. This includes accurate information about distances, ETAs, and turn-by-turn directions.
  • Performant: Google Maps must be fast and responsive, providing users with instant access to the information they need. This is critical to ensure that users can find the information they need quickly and easily.
  • Scale: Google Maps must be able to handle a large number of users, with the ability to scale to accommodate the needs of 1.2 billion monthly active users.
  • Support for businesses: Google Maps must be able to support the needs of the 6 million companies that use the software, providing them with the tools they need to optimize delivery routes, plan trips, and more.

Google Maps is a powerful tool for navigation, trip planning, and exploring the world around you. It provides detailed and up-to-date information about roads, highways, and other routes, enabling users to get from one place to another quickly and efficiently. To ensure the accuracy and performance of its services, Google Maps breaks down the world into smaller segments that are easier to manage and operate on. Each segment is defined by four points, forming a boundary that can be used to calculate the distance between two center points of two segments using Euclid distance and thus calculating the area distance between two segments.

Within each segment, location points (cities, any geo location) and roads are represented as directed graphs (directed since the edges in both ways for two points might have different weights, for example on time dimension if it takes more time to go from A to B, than from B to A), with edges representing the connections between two points and weighted based on various attributes such as distance, time, and other relevant information. To calculate the shortest path between each pair of points in one segment we can use Floyd-Warshall algorithm while we can use Dijkstra's algorithm to find the shortest path between two points that belong to two different segments. Note that path between segments is formed by following the path from exit points from each segment to it's neighbor until we find the destination point. If we have a request for a point that doesn't exist in the matrix of shortest paths for certain segment, we can find two closest points and use them for calculation (the total distance is distance between request point and closest point, and distance from our starting point to the closest point for destination). We use area distance (distance between two segments) to bound the Dijkstra algorithm (so that we don't take into consideration all the roads in the world), for example if we have 10km distance between segments we know that we only need to check 10 segments east-west or south-north and use their exit points to reach the destination segment. The interesting part is we have distance much larger than 10km, the Dijkstra would perfom poorly, so that's why we ensure granularity by combining multiple segments into a parent segment and then parent segments into another level and so on (we can run heuristics to see what level of granularity we need). Now each level represents segments which are much far way from each other, while for leaves of this tree hierarchy we will have 1-unit segments (e.g 1x1km square area). What happens if we change one road/edge inside one 1-unit segment? If the parent segment is using that road, we will have to update the leaf node, and then bubble up the calculation up to update the matrix (recalculate) the parent level shortest paths. It would be waste of resource if we would update and recalculate the shortest path for each change in the weight/dimensions, so we define a threshold (e.g. 30% of weights changed) and if cross the threshold a recalculation has to be done.

image

Let's break down the components used for designing the system:

  • Load Balancers - to uniformly distribute our load to WebSocket Handler and other services.
  • WebSocket Handlers - It keeps a bi-directional connection with a certain user, it sends an events each time there is a new message for the user it maps to, leading to message appearing on user device. We use to record current location in time for a user by communication to Location Service.
  • WebSocket Manager - This component manages the mapping of users to WebSockets. It sits in front of distributed cache (Redis) which store the mapping between users and websocket handlers.
  • Location Service store the current lat/long location of the user in certain point in a database, and also sends an event to Kafka for further processing (running Spark pipelines for example).
  • We use Spark and Hadoop to process massive amount of data and identify for example new roads, average speeds during certain days on certain roads.
  • Search Service is used to query the Elastic search service to get the best (fuzzy based) search result for certain query for a locations. It also propagates the event to Kafka where it can used to determine the most frequent location users are searching for.
  • Navigation Service is used to listen and send events to Kafka regarding user behavior on the road from source to destination, and can be used to send notification on the next turn or if we're diverging from the initial path.
  • Map Service is an interface users use to access functionalities of our system, it propagates the requests to Graph Service and it also listens to event for any update of the map (new road) coming from Kafka.
  • Traffic Service listens to event comming from Kafka regarding updates to traffic, which then it's propagated to Graph Service in order to update the weights of the edges/roads and possibly recalculate the shortest paths within segments or between them.
  • Graph Service is the central piece and orhestraction services communicating with Segment Service which gets/updates information about certain segments and distance between any pair. It store the information about the roads in database and uses them to calculate the shortest path, it also communicates with historical data (e.g. average speed on certain road for certain day). We also integrate with a third party service that sends event on any change in weather, traffic, contruction on roads and which push events to Graph Service to react to, which in return can update the weight of the roads and do the recalculation of the shortest paths.