Design Google Maps: The System Behind Real-Time Global Navigation

Here's what everyone gets wrong: Google Maps doesn't compute your route from scratch. That would take seconds, not milliseconds. The secret is a precomputed hierarchy that shortcuts the entire graph. If you think it's just Dijkstra on OpenStreetMap data, you're missing the entire production playbook. The real challenge isn't the algorithm — it's the data. 20 petabytes of map data, updated in real-time from satellites, street view cars, and user reports. One stale road closure and you reroute an entire city into gridlock. By the end of this, you'll understand the architecture that serves 1 billion monthly active users with sub-100ms routing queries. You'll know how they handle traffic spikes during earthquakes, how they version map data without downtime, and why your GPS sometimes thinks you're in a river.

Why Tiles? The Map as a Distributed Cache

Before tiles, maps were monolithic images. Every zoom level required a new image. Google Maps popularized the tile grid: each tile is a 256x256 PNG at a specific zoom level. The key insight: tiles are immutable and cacheable. A tile for zoom level 12 at coordinates (1234,567) never changes unless the underlying map data changes. This allows aggressive CDN caching. The tile server just stitches vector data into PNGs on the fly, but the real magic is the tile pyramid: precompute tiles for popular zoom levels and serve from blob storage. For zoom levels 0-10, tiles are static. For 11-20, they're generated on demand and cached. The failure mode: a tile stampede when a new map version is deployed. All CDN caches invalidate simultaneously, and the tile server gets hammered. Mitigation: staggered cache invalidation and pre-warming.

// io.thecodeforge — System Design tutorial

// Simplified tile server logic
class TileServer {
    // Cache: LRU with 10k entries per node
    private final Cache<TileKey, byte[]> tileCache = CacheBuilder.newBuilder()
        .maximumSize(10000)
        .expireAfterWrite(1, TimeUnit.HOURS)
        .build();

    public byte[] getTile(int zoom, int x, int y) {
        TileKey key = new TileKey(zoom, x, y);
        byte[] cached = tileCache.getIfPresent(key);
        if (cached != null) return cached;

        // Check blob storage (e.g., GCS) with CDN fallback
        byte[] tile = blobStorage.get(key);
        if (tile == null) {
            tile = renderTile(zoom, x, y); // expensive
            blobStorage.put(key, tile);
        }
        tileCache.put(key, tile);
        return tile;
    }
}

Geocoding: From Address to Lat/Lng in Milliseconds

Geocoding is the reverse of what most people think. You don't parse the address and look up coordinates. You tokenize the address into a hierarchy: country, state, city, street, number. Each level is a key in a sorted string table (SSTable). The trick: use a trie for prefix matching. When someone types '1600 Amphitheatre Parkway', the system returns candidates in O(k) time where k is address length. The gotcha: ambiguous addresses. 'Main Street' exists in 1000 cities. The system uses geohash of the user's IP to bias results. The failure mode: a geocoding query that matches millions of results (e.g., '1' in Manhattan). The fix: limit results to 5 and require more specificity.

// io.thecodeforge — System Design tutorial

// Simplified geocoding with trie
class Geocoder {
    private final TrieNode root = new TrieNode();

    public List<GeoResult> geocode(String address) {
        // Tokenize and traverse trie
        String[] tokens = address.toLowerCase().split(",\\s*|\\s+");
        TrieNode node = root;
        for (String token : tokens) {
            node = node.children.get(token);
            if (node == null) return Collections.emptyList();
        }
        // Return top 5 results by population bias
        return node.results.stream()
            .sorted(Comparator.comparingInt(r -> -r.population))
            .limit(5)
            .collect(Collectors.toList());
    }
}

Routing: The Contraction Hierarchy Secret

Dijkstra on a graph with 500 million nodes is too slow. Google uses Contraction Hierarchies (CH). The idea: precompute 'shortcuts' between important nodes (highways, intersections). During query, you run bidirectional Dijkstra on the contracted graph. The result: sub-millisecond routing for long distances. The trade-off: precomputation takes hours and must be updated when roads change. The gotcha: CH doesn't handle real-time traffic well. Traffic changes edge weights, invalidating shortcuts. Solution: run CH on the static graph, then apply traffic as a post-processing penalty. This is why traffic-aware routes are slightly slower to compute.

// io.thecodeforge — System Design tutorial

// Simplified CH-based router
class Router {
    private final Graph contractedGraph; // precomputed

    public Route computeRoute(Node from, Node to, TrafficModel traffic) {
        // Bidirectional Dijkstra on contracted graph
        PriorityQueue<Node> forwardQueue = new PriorityQueue<>();
        PriorityQueue<Node> backwardQueue = new PriorityQueue<>();
        // ... standard bidirectional Dijkstra
        // After path found, apply traffic penalties
        return applyTraffic(path, traffic);
    }

    private Route applyTraffic(Route path, TrafficModel traffic) {
        for (Edge edge : path.edges) {
            double penalty = traffic.getDelay(edge.id); // seconds
            edge.cost += penalty;
        }
        return path;
    }
}

Real-Time Traffic: The Stream Processing Pipeline

Traffic data comes from three sources: 1) GPS pings from Android phones (anonymized), 2) road sensors, 3) incident reports. The pipeline ingests millions of events per second into Kafka. A stream processor (Apache Beam) aggregates events into 5-minute windows per road segment. The output is a 'speed' value for each segment. The challenge: handling sparse data. Rural roads may have zero pings. Solution: use historical baselines and interpolate from nearby segments. The failure mode: a traffic jam causes all phones to stop moving, reducing pings. The system interprets this as 'no traffic' and clears the jam. Fix: use a minimum ping threshold; if pings drop below threshold, fall back to historical data.

// io.thecodeforge — System Design tutorial

// Simplified traffic aggregation
Pipeline p = Pipeline.create();
p.apply("ReadPings", KafkaIO.read().withTopic("gps-pings"))
 .apply("Window", Window.into(FixedWindows.of(Duration.standardMinutes(5))))
 .apply("Aggregate", Mean.<String>perKey()) // key = road segment ID
 .apply("WriteTraffic", KafkaIO.write().withTopic("traffic-updates"));
p.run();

Map Data Versioning: How to Update Without Downtime

Map data changes daily: new roads, closed roads, changed speed limits. Google uses a versioned tile system. Each tile has a version number. When new data is published, tiles are regenerated with a new version. The client requests tiles with a version parameter. If the version is stale, the server returns a redirect to the new version. This allows gradual rollout: 1% of users see new map, then 10%, etc. The gotcha: version mismatch between tiles. A user might see a new tile for one area and an old tile for another, causing visual seams. Fix: version per region, not per tile. All tiles in a region share the same version.

// io.thecodeforge — System Design tutorial

// Versioned tile request
// Client request: GET /tile/12/1234/567?version=20240301
// Server response:
// If version matches current: 200 OK with tile
// If version is old: 302 Redirect to /tile/12/1234/567?version=20240315
class TileController {
    @GetMapping("/tile/{z}/{x}/{y}")
    public ResponseEntity<byte[]> getTile(
            @PathVariable int z, @PathVariable int x, @PathVariable int y,
            @RequestParam(defaultValue = "0") int version) {
        int currentVersion = versionManager.getCurrentVersion(z, x, y);
        if (version != currentVersion) {
            return ResponseEntity.status(HttpStatus.FOUND)
                .location(URI.create("/tile/" + z + "/" + x + "/" + y + "?version=" + currentVersion))
                .build();
        }
        byte[] tile = tileService.getTile(z, x, y);
        return ResponseEntity.ok(tile);
    }
}

Handling Traffic Spikes: The Super Bowl Problem

When a major event happens (earthquake, Super Bowl), traffic queries spike 100x. The routing service must not fall over. Solution: 1) Use a CDN for static assets (tiles). 2) For routing, use a queue with backpressure. If queue depth exceeds threshold, return cached routes for popular origins/destinations. 3) Degrade gracefully: disable traffic-aware routing during peak. The failure mode: the queue grows unbounded, causing OOM. Fix: bounded queue with rejection. Return HTTP 503 with Retry-After header. The client retries with exponential backoff.

// io.thecodeforge — System Design tutorial

// Bounded queue with backpressure
ExecutorService executor = new ThreadPoolExecutor(
    10, 100, 60, TimeUnit.SECONDS,
    new ArrayBlockingQueue<>(1000), // bounded queue
    new ThreadPoolExecutor.AbortPolicy() // reject if full
);

public CompletableFuture<Route> routeAsync(RouteRequest request) {
    return CompletableFuture.supplyAsync(() -> {
        if (executor.isShutdown()) throw new RejectedExecutionException();
        return router.computeRoute(request);
    }, executor);
}

When Not to Use This Architecture

If you're building a navigation app for a single city with <100k users, you don't need CH or distributed tile servers. A single PostGIS database with pgRouting and a tile server like TileServer GL will work fine. The Google Maps architecture is overkill for small scale. The cost of maintaining a CH precomputation pipeline and a Kafka-based traffic pipeline is justified only at planetary scale. For most startups, use Mapbox or OpenStreetMap with a managed service. Don't reinvent the wheel.