← System Design Simulator

Google Maps System Design Interview Question

By Rahul Kumar · Senior Software Engineer · Updated · 10 components · 3 operations ·Source: Alex Xu, System Design Interview Vol 2, Chapter 3

Problem: Design a web-scale map service that renders tiled maps, searches places, and computes routes from A to B.

Overview

Google Maps is the canonical consumer geo product and, underneath the slick UI, a stack of four distinct services glued together: a tile server that paints the basemap, a place search service that turns typed strings into coordinates, a routing service that produces turn-by-turn directions, and a traffic and ETA service that keeps those routes honest. Each one has its own data model, its own hot path, and its own scaling story, which is why a single 'design Google Maps' interview can take an entire hour. The tile server is read-mostly and absurdly cacheable; routing is compute-heavy and benefits from pre-processed graph contractions; place search is a classic autocomplete problem with spatial bias. This SEO supplement expands the widget with Java sketches for a tile server endpoint, a bidirectional Dijkstra routing skeleton, and a trie-backed place autocomplete service so the core mechanics are concrete.

Google Maps — Interactive Simulator

Runs fully client-side in your browser; no sign-up. Or open full screen →

Launch the interactive walkthrough for Google Maps — animated architecture diagram, step-by-step flow with real payloads, component swap, and a discrete-event stress simulator.

Summary

A read-heavy geospatial system dominated by three very different workloads: (1) map tile fetches — billions of tiny immutable PNG/vector requests that belong on a CDN, (2) place autocomplete — low-latency prefix search out of Elasticsearch, and (3) routing — CPU-heavy graph traversal over the road network, accelerated with Contraction Hierarchies so 1000 km queries finish in <100ms. The dominant design choice is pushing the tile workload all the way to the CDN edge (99%+ cache hit) so the origin sees only rare misses; the main tradeoff is that map updates take hours to propagate globally as tiles are re-rendered and purged. Sized for ~1B MAU and ~10M route requests/day.

Requirements

Functional

Non-functional

Capacity Assumptions

Back-of-Envelope Estimates

High-level architecture

The map UI is really four APIs talking to one shell. The tile path is the cheapest: vector tiles are rendered offline from OSM plus proprietary data into protobuf PBF blobs, stored in immutable object storage keyed by (style, z, x, y), and pushed to a global CDN. A TileServer instance only serves as a fallback when the CDN misses, typically adding a signed URL and stamping a cache header. The place search path fronts an Elasticsearch or custom inverted index with a trie cache for prefix completions; queries are re-ranked by geographic prior (distance from the user's viewport centroid) and click popularity. The routing path is the heaviest. The world road graph is partitioned into cells (typically country or sub-country) with contraction hierarchies pre-computed offline, so at query time a bidirectional Dijkstra or A* runs on a sparse overlay graph in tens of milliseconds rather than the hour it would take on the raw graph. Live traffic is a separate stream: a fleet of GPS probes feeds speed tiles into a Traffic Service that writes edge-weight deltas into a Redis layer that the router consults on every query. Everything is regional, and cross-region routes stitch together via a gateway graph whose edges are country-border crossings. Observability tracks CDN hit ratio per zoom level, router edge-relaxations per query, and autocomplete index staleness, all surfaced on a Google-Maps-team Grafana board during major event launches.

Architecture Components (10)

Operations Walked Through (3)

Implementation

TileServer endpoint by (z, x, y)
@RestController
public class TileController {
    private final TileStore store;

    @GetMapping("/tiles/{style}/{z}/{x}/{y}.pbf")
    public ResponseEntity<byte[]> vectorTile(
            @PathVariable String style,
            @PathVariable int z,
            @PathVariable int x,
            @PathVariable int y) {
        if (z < 0 || z > 22) return ResponseEntity.badRequest().build();
        long max = 1L << z;
        if (x < 0 || x >= max || y < 0 || y >= max) {
            return ResponseEntity.badRequest().build();
        }
        byte[] tile = store.get(style, z, x, y);
        if (tile == null) return ResponseEntity.notFound().build();
        return ResponseEntity.ok()
            .header("Content-Type", "application/x-protobuf")
            .header("Content-Encoding", "gzip")
            .header("Cache-Control", "public, max-age=86400, immutable")
            .header("ETag", store.version(style))
            .body(tile);
    }
}
Bidirectional Dijkstra skeleton
public class BidirectionalDijkstra {
    private final Graph graph;

    public Route shortestPath(long source, long target) {
        Map<Long, Double> distF = new HashMap<>();
        Map<Long, Double> distB = new HashMap<>();
        PriorityQueue<Entry> forward = new PriorityQueue<>();
        PriorityQueue<Entry> backward = new PriorityQueue<>();
        forward.add(new Entry(source, 0));
        backward.add(new Entry(target, 0));
        distF.put(source, 0.0);
        distB.put(target, 0.0);
        double best = Double.POSITIVE_INFINITY;
        long meeting = -1;
        while (!forward.isEmpty() && !backward.isEmpty()) {
            if (forward.peek().cost + backward.peek().cost >= best) break;
            Entry f = forward.poll();
            for (Edge e : graph.outgoing(f.node)) {
                double nd = f.cost + e.weight();
                if (nd < distF.getOrDefault(e.to(), Double.POSITIVE_INFINITY)) {
                    distF.put(e.to(), nd);
                    forward.add(new Entry(e.to(), nd));
                    if (distB.containsKey(e.to()) && nd + distB.get(e.to()) < best) {
                        best = nd + distB.get(e.to());
                        meeting = e.to();
                    }
                }
            }
            Entry b = backward.poll();
            for (Edge e : graph.incoming(b.node)) {
                double nd = b.cost + e.weight();
                if (nd < distB.getOrDefault(e.from(), Double.POSITIVE_INFINITY)) {
                    distB.put(e.from(), nd);
                    backward.add(new Entry(e.from(), nd));
                    if (distF.containsKey(e.from()) && nd + distF.get(e.from()) < best) {
                        best = nd + distF.get(e.from());
                        meeting = e.from();
                    }
                }
            }
        }
        return graph.reconstruct(source, target, meeting, distF, distB);
    }

    record Entry(long node, double cost) implements Comparable<Entry> {
        public int compareTo(Entry o) { return Double.compare(cost, o.cost); }
    }
}
Trie-backed place autocomplete endpoint
public class PlaceTrie {
    static class Node {
        Map<Character, Node> next = new HashMap<>();
        List<Place> topK = new ArrayList<>(); // pre-scored top results
    }
    private final Node root = new Node();

    public void index(String name, Place p) {
        Node cur = root;
        for (char c : name.toLowerCase().toCharArray()) {
            cur = cur.next.computeIfAbsent(c, k -> new Node());
            insertTopK(cur.topK, p, 10);
        }
    }

    public List<Place> prefix(String q) {
        Node cur = root;
        for (char c : q.toLowerCase().toCharArray()) {
            cur = cur.next.get(c);
            if (cur == null) return List.of();
        }
        return cur.topK;
    }

    private void insertTopK(List<Place> list, Place p, int k) {
        list.add(p);
        list.sort(Comparator.comparingDouble(Place::score).reversed());
        if (list.size() > k) list.remove(list.size() - 1);
    }
}

@RestController
public class PlaceController {
    private final PlaceTrie trie;
    private final ViewportRanker ranker;

    @GetMapping("/places/autocomplete")
    public List<Place> autocomplete(
            @RequestParam String q,
            @RequestParam double lat,
            @RequestParam double lon) {
        List<Place> candidates = trie.prefix(q);
        return ranker.rerank(candidates, lat, lon);
    }
}

Key design decisions & trade-offs

Interview follow-ups

Related