Design maps, routing and ETA

A national maps service answers about 174,000 tile requests a second at its peak and takes in 400,000 speed reports a second, yet a route across 50 million road segments must come back within 300 ms. To design maps for a country, you build three systems that share one map database.

Tiles draw the map: squares at every zoom level, built ahead of time and served from a CDN, so a phone downloads only the squares on its screen. Routing finds the fastest path through a graph of junctions and road segments, preprocessed once so that a query touches only a few hundred junctions. The ETA, the estimated time of arrival, adds up the route’s segments at the speeds phones report now and the speeds usual for the hour each is reached, then applies corrections learned from finished trips. Whoever has to design maps needs all three.

About 174,000 tiles a second, and 400,000 probe points

Settle the scope first, writing down each assumption:

• Which journeys? Driving, two-wheelers and walking in one country of about 3 million km², turn by turn.
• Who calls it? 60 million daily users, and partner services, such as ride matching, that ask for many arrival times at once.
• How fresh? A jam or a closed road reaches routes within minutes, a new road the tiles within a day.
• How fast? A tile within 100 ms from the edgeedge (CDN): One of a content delivery network's servers, placed close to users. The user's connection ends at the edge, which answers from its cache or fetches the response from the origin. More in “The life of a web request, hop by hop” and a route within 300 ms, at the 99th percentilep99 (99th percentile): The latency within which 99 % of requests finish, so the slowest 1 % take longer. Tail latency is read from such high percentiles, because an average hides the slowest requests. More in “Latency, throughput and percentiles”.
• How good? Most arrival times within 10 %, with no steady lean towards early or late.

So the service draws the map, geocodes, routes and predicts arrival times from live speed reports, and keeps serving its last good data when a pipeline fails. A common starting point is OpenStreetMap data, under the Open Database License: a product must credit OpenStreetMap and its contributors, and a database built from the data may be shared only under the same licence (OpenStreetMap). Its community tile servers may block heavy use and allow no offline use, so an app this size runs its own tile pipeline (OpenStreetMap Foundation).

Two facts shape the design. Tiles carry the most traffic but cache perfectly, because a tile is the same for everyone. The heavy writing is the probe stream: 400,000 reports a second become one speed per segment every minute.

DAY_SECONDS = 86_400


def tile_requests_per_second(daily_users, views_each, tiles_per_view, peak_factor):
    """Tile requests a second in the busiest hour."""
    # Replace this line with your code.
    return 0


def edge_gbit_per_second(tiles_per_second, kb_per_tile):
    """Gbit/s the edge sends for that many tiles a second."""
    # Replace this line with your code.
    return 0


def vector_tileset_gb(area_km2, tile_km2, kb_per_tile):
    """GB for a vector tile set of the area, every zoom included."""
    # Replace this line with your code.
    return 0


def probe_points_per_second(phones, seconds_between):
    """Speed reports a second from navigating phones."""
    # Replace this line with your code.
    return 0

import math

from sizing import edge_gbit_per_second, probe_points_per_second, tile_requests_per_second, vector_tileset_gb


def near(actual, expected):
    """Within 10%, as an estimate should be."""
    return math.isclose(actual, expected, rel_tol=0.10)


def test_tiles_at_peak():
    """every view's tiles spread over the day, times the peak factor"""
    assert near(tile_requests_per_second(60_000_000, 5, 20, 2.5), 173_611)
    assert near(tile_requests_per_second(5_000_000, 3, 12, 3), 6_250)


def test_edge_bandwidth():
    """tiles times bytes, in gigabits"""
    assert near(edge_gbit_per_second(173_611, 25), 34.7)
    assert near(edge_gbit_per_second(6_250, 40), 2.0)


def test_tileset_storage():
    """the deepest zoom's tiles, a third more for the zooms above, times the bytes"""
    assert near(vector_tileset_gb(3_000_000, 5.29, 25), 18.9)
    assert near(vector_tileset_gb(50_000, 4.0, 30), 0.5)


def test_probe_stream():
    """one report per phone every few seconds"""
    assert near(probe_points_per_second(2_000_000, 5), 400_000)
    assert near(probe_points_per_second(300_000, 4), 75_000)

The first design: tiles, routes and speeds

The phone takes tiles from the CDN, which fetches misses from tile storage. Route and arrival-time requests pass the API gateway, whose geocoder turns addresses into points, to routing servers holding the road graph in memory. Phones send probe points to the traffic pipeline, which publishes speeds every minute. Builders turn map edits into changed tiles and new graphs. Follow one phone through it:

The questions this design must answer:

• Raster or vector tiles? Raster tiles are images drawn on the server; vector tilesMap tiles that carry shapes such as roads, rivers and labels as coordinates instead of an image, so the phone or browser draws and styles the map itself. carry shapes that the phone draws and styles itself.
• Which search? Dijkstra explores outward from the start in order of travel time; A* steers it towards the target with a lower bound.
• Contraction hierarchies: preprocessing adds shortcut edges, so a hierarchyA road graph prepared once by adding shortcut edges in an order of importance, so that a route query searches from both ends only towards more important junctions. query only climbs from both ends towards more important roads.
• Multi-level Dijkstra: times across nested cells of the graph are precomputed, so new speeds apply cell by cell.
• ETA: probe speeds for the next few minutes, usual speeds for later segments, and corrections for waits at junctions.
• Addresses: PIN codes, landmarks and DIGIPINIndia Post's open grid code that names a small square of the map; a geocoder uses it beside the PIN code, the locality and landmarks. grid codes turn an Indian address into a point.

Vector tiles stop at zoom 14 and cache better than raster tiles Pro: opens with a Pro, Premium or Ultimate pass