Design Google Maps: Routing, Tiles & ETA System Design

"Design Google Maps" is a favourite question at Google, Uber, Ola, Swiggy and logistics companies because it mixes classic algorithms with heavy infrastructure. A candidate who only draws boxes misses the routing problem; a candidate who only talks about Dijkstra misses tiles, traffic and scale. You need both.

The question is too big to cover fully in 45 minutes, so the first thing a strong candidate does is split it into subsystems and agree with the interviewer which ones to go deep on. This guide covers all of them so you can go deep wherever you are steered.

Step 1: Requirements

Functional

• Map display: pan and zoom a map of the world, with roads, labels, buildings and points of interest.
• Routing: given origin and destination, return the best route (fastest by default) with alternatives, for car, two-wheeler, walking and transit.
• ETA: estimated travel time considering current and predicted traffic.
• Turn-by-turn navigation: track the user, give instructions, reroute when they deviate or traffic changes.
• Live traffic layer: colour roads green/orange/red.
• Offline maps: download a region and navigate without connectivity.
• Out of scope unless asked: place search and reviews (see proximity service design), Street View, business listings.

Non-functional

• Map tiles load fast enough that panning feels instant: tens of milliseconds from cache.
• Route queries return in well under a second, including alternatives.
• ETA accuracy matters more than raw speed; users and businesses (cab and delivery apps) plan around it.
• High availability: navigation is used while driving; graceful degradation to cached data and offline routing.
• Location data is sensitive: anonymise and minimise.

Step 2: Capacity Estimates

These are interview assumptions, not Google's real numbers, which are not public at this granularity.

Three conclusions fall out. Tile serving is a CDN problem: hundreds of thousands of requests per second of static, cacheable content. Routing is a CPU and memory problem: ~17k queries per second, each of which must be fast on a huge graph. Traffic ingestion is a streaming problem: a million location events per second to aggregate continuously. For the general technique behind these numbers, see back-of-the-envelope estimation.

Step 3: API Design

GET  /tiles/v1/{style}/{z}/{x}/{y}.mvt?ver=2026-10-01
     -> vector tile (protobuf), Cache-Control: public, max-age=604800, immutable

GET  /route/v1?origin=12.9756,77.6050&destination=12.9352,77.6245
              &mode=two_wheeler&depart_at=now&alternatives=2
     -> { routes: [ { polyline: "encoded...", distance_m: 6120, eta_s: 1260,
                      eta_range_s: [1080, 1500], legs: [...], steps: [...],
                      traffic_spans: [...] } ] }

POST /nav/v1/sessions              { route_id, device_id }   -> { session_id }
POST /nav/v1/sessions/{id}/pings   [ {lat, lng, ts, speed, bearing, accuracy_m}, ... ]
     -> { on_route: true, eta_s: 1180, reroute: null | { new route } }

GET  /offline/v1/regions/{region_id}/manifest?have=2026-09-01
     -> { version, full_package_url, diff_url, size_bytes }

Note the tile URL includes a data version. Tiles become immutable per version, so they can be cached for a week or more; publishing new map data changes the version rather than invalidating billions of cached objects. Location pings are batched (several pings per request) to save battery and radio wake-ups.

Step 4: High-Level Architecture

The left and top are offline: building tiles and preprocessing the graph from map data, run in batch whenever map data changes. The bottom is online: serving routes, ingesting pings and turning them into traffic, which feeds back into routing. Keeping these separate is the main architectural idea.

Deep Dive 1: Map Tiles and the Tile Pyramid

The world is projected onto a square using Web Mercator and cut into a pyramid. At zoom level z there are 2^z × 2^z tiles, each conventionally 256 (or 512) pixels square. Zoom 0 is one tile showing the whole world; zoom 18 shows individual buildings.

Tile addressing: from latitude/longitude to z/x/y

import math


def latlng_to_tile(lat: float, lng: float, z: int) -> tuple:
    n = 2 ** z
    x = int((lng + 180.0) / 360.0 * n)
    lat_rad = math.radians(lat)
    y = int((1.0 - math.asinh(math.tan(lat_rad)) / math.pi) / 2.0 * n)
    return x, y


print(latlng_to_tile(12.9756, 77.6050, 15))   # MG Road, Bengaluru -> (23447, 15192)
print(latlng_to_tile(28.6139, 77.2090, 12))   # New Delhi           -> (2926, 1707)

public final class Tiles {
    public static int[] latLngToTile(double lat, double lng, int z) {
        double n = Math.pow(2, z);
        int x = (int) Math.floor((lng + 180.0) / 360.0 * n);
        double latRad = Math.toRadians(lat);
        double asinh = Math.log(Math.tan(latRad) + 1.0 / Math.cos(latRad));
        int y = (int) Math.floor((1.0 - asinh / Math.PI) / 2.0 * n);
        return new int[] { x, y };
    }

    public static void main(String[] args) {
        int[] t = latLngToTile(12.9756, 77.6050, 15);
        System.out.println(t[0] + "/" + t[1]);   // 23447/15192
    }
}

At zoom 15 near Bengaluru, one 256-pixel tile spans about 1.2 km and each pixel is about 4.7 m (ground resolution is 40,075 km × cos(latitude) / 2^z / 256). A phone screen shows roughly 15–30 tiles at once, and panning fetches only the new edge tiles.

Raster vs vector tiles

Modern apps use vector tiles for the base map. Tiles are generated offline by a tile builder that clips features to each tile, simplifies geometry for the zoom level (no need for every curve of a road at zoom 8) and drops features that are not visible at that zoom.

Storing and serving 90 billion tiles

• Ocean and empty land produce identical tiles. Store one copy and point duplicates at it via a hash, cutting storage dramatically.
• Pre-render popular zooms, render rare ones on demand. Low zooms (0–12) are few and requested by everyone, so pre-generate them. Deep zoom tiles in sparse regions can be generated lazily on first request and cached.
• Overzooming: beyond a maximum data zoom (say 16), the client scales the z16 vector tile instead of fetching z17–z21 tiles, because vector geometry stays sharp.
• Cache layers: device disk cache, then CDN edge (very high hit rate since tiles are immutable per version), then object storage origin.
• Dynamic layers like traffic are separate, small, short-TTL overlay tiles (or per-route traffic spans), never baked into the base map.

Deep Dive 2: The Road Graph and Graph Partitioning

For routing, the map is a directed weighted graph: nodes are intersections, edges are road segments. Edges are directed because of one-way streets. Each edge carries length, road class, speed limit, restrictions (no trucks, toll, two-wheeler only), and a travel-time weight that changes with traffic. Turn restrictions ("no right turn here") are modelled either with turn tables at nodes or by building an edge-based graph where turns are edges.

A global routable graph has hundreds of millions of nodes and edges. Two things make it tractable:

1. Compress degree-2 chains. A curving road with 40 shape points but no junctions becomes one edge with a polyline attached. The graph keeps only real decision points.
2. Partition. Split the graph into cells using a graph partitioner (tools like METIS, KaHIP or PUNCH) that minimises the number of edges crossing cell boundaries. Road networks partition beautifully along rivers, mountains and highways, so cells have few boundary nodes. Repeat recursively to get a multi-level hierarchy.

Partitioning serves two purposes: it enables fast routing algorithms (next section), and it lets you shard the routing service. A routing server for India loads the India graph into RAM; most trips start and end in the same region, and cross-region trips use the higher-level overlay graph of boundary nodes. Sharding by geography mirrors how ride-hailing systems shard by city.

Deep Dive 3: Routing with A* and Contraction Hierarchies

Dijkstra's algorithm finds shortest paths with non-negative weights in O((V + E) log V) using a binary heap (a refresher is in shortest path algorithms explained). The problem is not correctness, it is that Dijkstra expands in all directions. For a 1,000 km trip it settles millions of nodes, which takes far too long at 17,000 queries per second.

A*: point the search at the destination

A* orders the priority queue by f(n) = g(n) + h(n), where g is the cost so far and h is a lower-bound estimate of the remaining cost. For distance, use straight-line (haversine) distance; for travel time, straight-line distance divided by the maximum speed on the network. If h never overestimates (admissible) and is consistent, A* returns the optimal route while expanding fewer nodes.

import heapq
import math

coords = {"A": (0, 0), "B": (2, 0), "C": (1, 2), "D": (4, 1), "E": (3, 3), "F": (6, 2)}
edges = [("A", "B", 2.0), ("A", "C", 2.5), ("B", "C", 3.0), ("B", "D", 2.5),
         ("C", "E", 2.5), ("D", "E", 2.5), ("D", "F", 2.5), ("E", "F", 3.5)]

graph = {n: [] for n in coords}
for u, v, w in edges:            # two-way roads for this toy example
    graph[u].append((v, w))
    graph[v].append((u, w))


def h(n, goal):
    (x1, y1), (x2, y2) = coords[n], coords[goal]
    return math.hypot(x1 - x2, y1 - y2)   # straight line never overestimates here


def a_star(src, dst):
    g = {src: 0.0}
    parent = {src: None}
    pq = [(h(src, dst), src)]
    settled = set()
    while pq:
        f, u = heapq.heappop(pq)
        if u in settled:
            continue
        settled.add(u)
        if u == dst:
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return g[dst], path[::-1]
        for v, w in graph[u]:
            ng = g[u] + w
            if ng < g.get(v, math.inf):
                g[v] = ng
                parent[v] = u
                heapq.heappush(pq, (ng + h(v, dst), v))
    return math.inf, []


print(a_star("A", "F"))   # (7.0, ['A', 'B', 'D', 'F'])

import java.util.*;

public class AStar {
    record Edge(int to, double w) {}

    static double[][] xy = { {0,0}, {2,0}, {1,2}, {4,1}, {3,3}, {6,2} };   // A..F
    static List<List<Edge>> g = new ArrayList<>();

    static void road(int u, int v, double w) {
        g.get(u).add(new Edge(v, w));
        g.get(v).add(new Edge(u, w));
    }

    static double h(int n, int goal) {
        return Math.hypot(xy[n][0] - xy[goal][0], xy[n][1] - xy[goal][1]);
    }

    static List<Integer> route(int src, int dst) {
        double[] dist = new double[xy.length];
        int[] parent = new int[xy.length];
        Arrays.fill(dist, Double.POSITIVE_INFINITY);
        Arrays.fill(parent, -1);
        boolean[] settled = new boolean[xy.length];
        PriorityQueue<double[]> pq = new PriorityQueue<>(Comparator.comparingDouble(a -> a[0]));
        dist[src] = 0;
        pq.add(new double[] { h(src, dst), src });
        while (!pq.isEmpty()) {
            int u = (int) pq.poll()[1];
            if (settled[u]) continue;
            settled[u] = true;
            if (u == dst) break;
            for (Edge e : g.get(u)) {
                double nd = dist[u] + e.w();
                if (nd < dist[e.to()]) {
                    dist[e.to()] = nd;
                    parent[e.to()] = u;
                    pq.add(new double[] { nd + h(e.to(), dst), e.to() });
                }
            }
        }
        LinkedList<Integer> path = new LinkedList<>();
        for (int v = dst; v != -1; v = parent[v]) path.addFirst(v);
        System.out.println("cost=" + dist[dst]);
        return path;
    }

    public static void main(String[] args) {
        for (int i = 0; i < xy.length; i++) g.add(new ArrayList<>());
        road(0,1,2.0); road(0,2,2.5); road(1,2,3.0); road(1,3,2.5);
        road(2,4,2.5); road(3,4,2.5); road(3,5,2.5); road(4,5,3.5);
        System.out.println(route(0, 5));   // cost=7.0, [0, 1, 3, 5] = A-B-D-F
    }
}

Dry run: A* vs Dijkstra from A to F

C (f = 2.5 + 5.0 = 7.5) and E were pushed but never settled. Dijkstra would settle A, B, C, D, E and then F: six nodes instead of four. On a real road network the saving grows with distance, but A* alone is still not enough for cross-country routes, because the heuristic is weak (roads are rarely straight and speeds vary hugely).

Contraction hierarchies (CH)

CH, introduced by Geisberger and colleagues in 2008, preprocesses the graph so queries become tiny:

1. Order nodes by importance. Local residential intersections are unimportant; highway junctions are important. Heuristics such as "edge difference" (shortcuts added minus edges removed) pick the order.
2. Contract nodes in that order. Remove node v; for each pair of neighbours u, w where the shortest u→w path went through v, add a shortcut edge u→w with the combined weight.
3. Query bidirectionally, only upwards. Run Dijkstra forward from the source and backward from the target, each relaxing only edges to more important nodes. The two searches meet near the top of the hierarchy (on a highway, intuitively). Shortcuts are unpacked recursively to recover the real path.

Published experiments on continental road networks report CH queries settling only hundreds of nodes and answering in well under a millisecond, versus seconds for plain Dijkstra. The catch: preprocessing takes minutes and depends on the weights. If travel times change every minute because of traffic, you cannot re-contract the whole graph every minute.

Making it work with live traffic: partition-based routing

Customizable Route Planning (CRP, Delling et al., developed at Microsoft Research for Bing Maps) and Customizable Contraction Hierarchies split preprocessing into two phases:

• Metric-independent phase (slow, rare): partition the graph into multi-level cells, or compute a weight-independent node order. Only redone when the road network itself changes.
• Customization phase (fast, frequent): given new edge weights, recompute shortest distances between boundary nodes of each cell. It parallelises across cells and only cells whose edges changed need recomputation, so it can run every minute or so.

Queries then run a bidirectional Dijkstra that uses the full detail graph only inside the source and target cells and jumps across the rest of the map using precomputed boundary-to-boundary "clique" edges. This is the design to describe when the interviewer asks "how do you include live traffic?"

Alternatives and personalisation

Alternative routes are usually found with the "via-node" or "plateau" method: candidate routes that share little with the best route, are not much longer (say, within 25%) and have no silly detours. Mode-specific routing (two-wheelers in Indian cities can use lanes cars cannot, trucks have restrictions) uses separate edge attributes and sometimes a separate preprocessed graph per mode.

Deep Dive 4: Live Traffic from GPS Probes

Phones with location sharing and navigation sessions act as moving traffic sensors. The pipeline turns a million pings per second into a speed per road segment.

1. Ingest. Navigation service authenticates batched pings and writes them to Kafka partitioned by geographic cell (for example an S2 or H3 cell ID) so one consumer sees all pings for nearby roads.
2. Anonymise. Replace device IDs with rotating trip pseudonyms and trim the first and last few hundred metres of every trip, which would otherwise reveal homes and workplaces.
3. Map matching. GPS is noisy (5–20 m, worse between tall buildings), so a ping near a flyover could belong to the road above or below. Hidden Markov Model map matching (Newson and Krumm, 2009) picks the most likely sequence of segments using both distance from ping to road and plausibility of the transitions between consecutive pings.
4. Speed estimation. For each matched pair of pings, compute travel time on the traversed segments. A stream processor (Flink, Kafka Streams) aggregates per segment over sliding windows (for example the last 5 minutes), using medians to reject outliers like a car parked at a tea stall.
5. Blend with history. Segments with few probes fall back to historical speed for that time of week. A typical blend weights live data by the number and freshness of observations.
6. Publish. Write segment speeds to a traffic store (a key-value store keyed by segment ID, with in-memory replicas on routing servers), push them to CRP customization and regenerate traffic overlay tiles.

Deep Dive 5: ETA Prediction

A route found with current speeds is not the same as an accurate ETA. A 45-minute drive across Bengaluru starting at 5:30 pm will hit segments 30 minutes from now, when traffic will be different from what it is right now.

Layered ETA model

• Time-dependent segment speeds. For each segment, expected traversal time as a function of the time you will reach it: live speeds for the next few minutes, a blend of live and historical for the middle of the trip, mostly historical for far-future segments.
• Turn and junction costs. Right turns across traffic in India (left-hand driving), signals and U-turns add time that segment speeds miss.
• ML correction. A model trained on millions of completed trips predicts the residual error from features like route shape, time of day, weather, events and region. Google and DeepMind have published work on graph neural networks for ETA in Google Maps (2021), which model how traffic on neighbouring segments interacts.
• Uncertainty. Return a range, not just a point estimate. "18–24 min" is more honest than "21 min" on a volatile route.

Closing the loop

Every completed navigation session provides ground truth: predicted ETA versus actual arrival. Track error metrics (for example mean absolute percentage error) per city and time band, alert on regressions, and feed results into retraining. For businesses like food delivery, ETA error directly affects promises shown to customers; see how ETAs are used in Swiggy/Zomato system design.

Deep Dive 6: Turn-by-Turn Navigation and Rerouting

Navigation is mostly on the client. The device holds the route polyline, maneuvers and the tiles for the corridor, and it map-matches its own GPS locally to place the arrow on the road and trigger voice instructions. The server is involved for:

• Pings and ETA refresh. Every few seconds the client sends batched pings; the server returns an updated ETA and, if needed, a better route.
• Off-route detection. If local map matching puts the user on a segment not on the route for more than a few pings, the client requests a reroute from the current position and heading.
• Proactive rerouting. The server periodically re-runs the route for active sessions with fresh traffic. If a new route saves meaningfully (say more than 3–5 minutes or 10%), it offers it. Thresholds prevent "route flapping".
• Session state (current route, last position, ETA) lives in a fast store keyed by session ID so any navigation server can handle the next ping.

Network loss is normal in tunnels and highways. The client keeps navigating with the cached route and corridor tiles, queues pings and syncs when connectivity returns. The server never needs to be on the critical path for the next instruction.

Deep Dive 7: Offline Maps

Offline maps move a slice of the whole backend onto the phone.

Updates use diffs: the client sends its current version, the server returns a binary diff to the latest version if one exists, or the full package otherwise. Regions are defined by a fixed grid or administrative boundaries so packages can be precomputed once per data release and served from the CDN like tiles. When online again, the device prefers server routing with live traffic and uses offline data only as a fallback.

Bottlenecks and Trade-offs

Bottlenecks to call out: memory per routing server (keep graphs compact, use arrays not object graphs), hot regions during festivals or big matches (scale routing replicas per region), Kafka partition skew in dense cities (smaller cells in dense areas) and tile origin load on map data release (release gradually, pre-warm the CDN for popular zooms).

What Interviewers Look For

Common mistakes

• Saying "run Dijkstra on the map" and stopping there.
• Storing tiles in a relational database and serving them from app servers instead of object storage plus CDN.
• Treating GPS points as exact positions and skipping map matching.
• Claiming contraction hierarchies handle live traffic without saying how weights get updated.
• Computing ETA from current speeds only, ignoring how traffic will change during the trip.
• Ignoring privacy of location traces.

Follow-up questions to prepare

• "How would you support ride-hailing ETAs for millions of driver-to-rider pairs?" Many-to-many queries with bucket-based CH or matrix APIs, cached per area.
• "How do you add a newly built flyover?" Map data update, regional graph rebuild, new tile version, offline package diff.
• "Why is the ETA wrong during Diwali traffic?" Historical patterns are for normal weeks; special-event calendars and faster blending towards live data help.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.