Design Google Maps / Nearby Search - System Design

“Design Google Maps” sounds like it is about drawing a map. It is not. The map tiles are the easy, cacheable part. The interviewer is really asking two hard questions stacked on top of each other. First: there are hundreds of millions of places on Earth - restaurants, petrol pumps, ATMs, chemists - and a user standing on a street corner types “coffee” and wants the ten nearest open cafes, sorted, in under a second. How do you find “things near this point” out of a planet’s worth of static points without scanning the whole globe? Second: that same user then taps one of those cafes and asks for directions, and you have to compute the fastest route across a road graph with hundreds of millions of edges, weighted by live traffic, in a few hundred milliseconds. How do you plan a shortest path across a continent without running Dijkstra over the entire road network on every request?

Those two problems - proximity search over billions of static points and shortest-path routing with ETA over a planet-scale graph - are the spine of this design. They are different from the Uber problem (which is about millions of moving points and matching); here the places barely move but there are far more of them, and the routing engine is the star, not a service call you hand-wave away. Let me build both properly.

Functional Requirements (FR)

In scope:

• Nearby / proximity search. Given a user location (lat, lng) and a query (a category like “coffee” or “petrol”, or free text), return the nearest matching places ranked by distance, relevance, rating, and open-now status. This is the “Nearby” tab.
• Place details. Given a place ID, return its name, address, coordinates, category, hours, rating, photos reference, and popularity.
• Directions / routing. Given an origin and destination (and a travel mode - drive, walk, transit), return the fastest route as a road-following polyline, with turn-by-turn steps and a total distance.
• ETA. For a route, an estimated time of arrival that accounts for current live traffic and typical historical traffic for that time of day.
• Map tile serving. Serve the visual base map at multiple zoom levels as the user pans and zooms.
• Live traffic ingestion. Consume anonymized GPS traces from millions of phones already navigating, and turn them into per-road-segment speed estimates that feed ETA and routing.

Explicitly out of scope (say this so you own the scope):

• Turn-by-turn voice navigation and re-routing UI. The client-side navigation experience, voice prompts, and lane guidance are a client concern; I design the routing service that produces the route and the ETA.
• Street View, satellite imagery, and the map-tile rendering pipeline. I will treat rendered tiles as pre-generated static assets served from a CDN, and focus on the vector/road data behind them rather than the cartographic rendering.
• Place ingestion / data collection. How the places database gets populated (business submissions, imagery extraction, government data) is a separate data-engineering pipeline. I assume a curated Places dataset exists and design how it is indexed and queried.
• User accounts, reviews, and photo storage. Each is its own system; I consume rating and review_count as attributes of a place.

The decision that drives everything: this is a read-heavy geospatial system over a mostly-static, enormous dataset, with a compute-heavy routing engine bolted to a real-time traffic stream. Places do not change second to second (unlike drivers), so the geo-index can be built offline and heavily cached; the hard part shifts from ingesting location to serving proximity queries at massive read scale and computing shortest paths cheaply. The geospatial index and the routing engine, not a write firehose, are the design drivers.

Non-Functional Requirements (NFR)

• Scale: ~2B monthly users, ~1B daily active. On the order of ~500M places worldwide. A road graph of ~50-100M nodes (intersections) and a few hundred million directed edges (road segments). Live traffic fed by tens of millions of concurrent navigating phones.
• Latency: nearby search under ~200ms p99. A route computation under ~300ms p99 for typical intra-city routes, under ~1s for cross-country. Map tiles under ~50ms (they are CDN-cached static assets). ETA refresh within seconds of a traffic change.
• Availability: 99.99%+ on search and routing. These are the product; a user who cannot get directions leaves. Traffic ingestion can tolerate brief degradation - a few minutes of slightly stale traffic still gives a usable ETA.
• Consistency: eventual consistency is fine almost everywhere. A newly added restaurant appearing in search 10 minutes late is acceptable. Traffic speeds being 30-60s stale is acceptable and unavoidable. There is no transactional “assign exactly one” operation like Uber’s matching, so we never need strong consistency on the hot path. Route results need only be consistent within a single request (use one snapshot of traffic), not globally serialized.
• Durability: the Places dataset and the road graph are the crown jewels and must be durable and versioned (you roll out a new map build, and roll back if it is bad). Live traffic is ephemeral - it is a rolling window, and losing a minute of it self-heals.
• Freshness: places refresh on the order of minutes to hours; live traffic on the order of tens of seconds; the road graph itself changes slowly (a new build every few weeks).

Back-of-the-Envelope Estimation (BoE)

Real numbers with the arithmetic, because they dictate the architecture.

Read traffic (the dominant load):

1B daily active users.
Assume each does ~5 map sessions/day, each session ~4 search or
detail interactions and ~1 route request.

Searches/detail: 1B * 5 * 4 = 20B geo-reads/day
  = 20,000,000,000 / 86,400 ≈ 230,000 reads/sec average
  Peak (3x, commute + lunch) ≈ 700,000 reads/sec

Route requests: 1B * 5 * 1 = 5B routes/day
  = 5,000,000,000 / 86,400 ≈ 58,000 routes/sec average
  Peak (3x) ≈ 175,000 routes/sec

Map tiles: dwarf everything but are CDN-cached static assets.
  A pan/zoom pulls ~10-20 tiles; call it ~1M tile requests/sec at peak,
  almost entirely served from CDN edge, never touching origin.

The shape is the opposite of Uber: reads dominate, writes are tiny. ~700K proximity reads/sec and ~175K route computations/sec at peak. Routing is the expensive one per request (graph search), so it deserves the most aggressive precomputation.

Live traffic (the only real write stream):

~10M phones actively navigating at peak, each reporting a GPS trace
every ~5 seconds.
= 10,000,000 / 5 = 2,000,000 trace points/sec.
These are NOT stored per-point; they are aggregated into per-segment
speeds, so the durable write rate is tiny - a rolling speed per road
segment.

Storage:

Places:
  Per place ≈ 1 KB (id, name, coords, category, hours, rating,
  address, photo refs).
  500M places * 1 KB = 500 GB.  Modest; fully shardable, heavily cached.

Road graph:
  ~100M nodes + ~300M edges.
  Per edge ≈ 50 bytes (from, to, length, road class, base speed,
  geometry ref) -> ~15 GB for edges, plus geometry.
  The routable graph (nodes/edges/weights) is tens of GB - fits in
  memory across a routing fleet.

Precomputed routing structures (contraction-hierarchy shortcuts):
  add a bounded multiple of the edge count, still tens of GB per region.

Live traffic:
  ~300M segments * ~16 bytes (current speed, confidence, updated_at)
  ≈ 5 GB of live speed state. Fits in memory / Redis; overwritten in place.

Map tiles (pre-rendered, all zoom levels): petabytes, but they are
static blobs on object storage behind a CDN. Not a database problem.

Bandwidth:

Ingress: 2M trace points/sec * ~50 bytes ≈ 100 MB/sec inbound (traffic).
Egress: tiles dominate but are CDN-served. Origin egress for
  search/route JSON: 700K+175K reqs/sec * ~5 KB ≈ 4-5 GB/sec, spread
  across many regions and edge-cached where possible.

The takeaways: a read-dominated system (~700K geo-reads/sec, ~175K routes/sec), a mostly-static ~500GB Places dataset and a tens-of-GB road graph that both fit in memory across a fleet, a compute-heavy routing step that must be precomputed to be cheap, and a modest live-traffic stream aggregated into ~5GB of in-memory per-segment speeds. Precomputation and caching, not write throughput, are the levers.

High-Level Design (HLD)

The architecture splits into three planes: a search plane (proximity queries over the geo-indexed Places data), a routing plane (shortest-path computation over the road graph, weighted by live traffic), and a traffic plane (ingesting GPS traces and turning them into per-segment speeds that both other planes read). Tiles are a fourth, trivial plane: static assets on a CDN.

   ┌──────────────┐                               ┌──────────────┐
   │  User App /   │  search / directions / tiles  │  Navigating   │
   │  Browser      │                               │  phones (GPS) │
   └──────┬────────┘                               └──────┬────────┘
          │                                               │ traces / 5s
   ┌──────▼───────────────┐                        ┌──────▼──────────┐
   │     API Gateway       │                        │ Traffic Ingest   │
   │ (auth, routing, rate) │                        │  Gateway         │
   └───┬───────────┬───────┘                        └──────┬──────────┘
       │           │                                       │
       │ search    │ directions                    ┌───────▼─────────┐
       │           │                               │ Kafka: traces    │
 ┌─────▼──────┐  ┌─▼───────────────┐               │ (keyed by segment│
 │  Nearby /   │  │  Routing Service │               │  / geohash)      │
 │  Search Svc │  │  (CH graph search│               └───────┬─────────┘
 │             │  │  + ETA)          │                       │
 │ ┌─────────┐ │  └─┬────────┬───────┘               ┌───────▼─────────┐
 │ │Geo Index│ │    │        │                       │ Traffic Aggreg.  │
 │ │(S2/geoh)│ │    │ reads  │ reads live speeds     │ (Flink: map-match│
 │ └─────────┘ │    │ graph  │                       │  + windowed avg) │
 └──────┬──────┘    │        ▼                       └───────┬─────────┘
        │           │  ┌────────────────┐                    │
        │           │  │ Live Traffic    │◀───────────────────┘
        │           │  │ Store (Redis:   │  cell/segment -> speed
        │           │  │  segment->speed)│
        │           │  └────────────────┘
        ▼           ▼
 ┌────────────┐  ┌──────────────────┐        ┌────────────────────┐
 │ Places DB   │  │  Road Graph Store │        │   Map Tiles / CDN   │
 │ (sharded KV │  │  (in-memory graph │        │  (static blobs,     │
 │  + geo-idx) │  │  + CH shortcuts,  │        │   pre-rendered)     │
 │             │  │  region-sharded)  │        └────────────────────┘
 └────────────┘  └──────────────────┘

Nearby search flow:

1. User sends GET /search?q=coffee&lat=..&lng=.. to the API Gateway, which routes to the Search Service.
2. Search Service computes the S2/geohash cell for the user’s location, gathers the covering cells for the requested radius, and looks up candidate place IDs from the geo-index for those cells, filtered by the category (“coffee”).
3. It fetches place attributes (hours, rating, coords) for the candidates from the Places store (mostly served from cache), filters to open-now and within radius, and ranks by a blend of distance, rating, and popularity.
4. It returns the top N with coordinates, so the client can pin them on the map. The whole thing is a bounded cell lookup plus a small ranked fetch - no scan.

Directions / routing flow:

1. User sends GET /directions?origin=..&dest=..&mode=drive. API Gateway routes to the Routing Service in the region owning that geography.
2. Routing Service snaps origin and destination to the nearest road-graph nodes (a small local geo-query on the graph), reads the current live traffic speeds for the relevant region into its edge weights, and runs a shortest-path search over the road graph - accelerated by precomputed contraction-hierarchy shortcuts so it explores a tiny fraction of the graph.
3. It reconstructs the path into a road-following polyline plus turn-by-turn steps, sums the traffic-weighted edge times into an ETA, and returns the route.

Traffic ingestion flow:

1. Navigating phones stream anonymized GPS traces to the Traffic Ingest Gateway, which drops them on a Kafka topic.
2. A stream processor (Flink) map-matches each trace to road segments (which segment was this phone actually driving on), computes observed speed, and windows it (e.g. rolling 1-3 min) into a per-segment speed estimate.
3. The aggregated segment_id -> speed map is written to a fast in-memory Live Traffic Store (Redis), which the Routing Service reads on every route to weight edges. No raw trace is kept.

The key insight: places and the road graph are static and precomputed; only traffic is live, and it is a small aggregated stream. Search is a cache-friendly read over a precomputed index; routing is a cheap graph search only because the expensive part (the hierarchy) was computed offline. Nothing on the hot path is a heavy write.

Component Deep Dive

The hard parts, naive-first then evolved: (1) the geospatial index for nearby search, (2) ranking and filtering nearby results, (3) the routing engine, (4) ETA and live traffic.

1. The geospatial index for nearby search

This is the first core problem: given a point, return the places near it, fast, over ~500M static points.

Naive approach: scan all places and compute distance. For a search at (lat, lng), loop over all 500M places, compute the haversine distance to each, keep those within radius R matching the category, sort, return the closest.

Where it breaks:

• O(N) per query. 500M distance calculations per search, ~700K searches/sec = an impossible number of haversine computations per second. You are examining a cafe in Buenos Aires to answer a search in Bangalore.
• No pruning. The overwhelming majority of the dataset is irrelevant to any single query, but a scan touches all of it.

First evolution: a lat/lng bounding-box query in a relational DB. Index places on (lat, lng) and query WHERE lat BETWEEN ? AND ? AND lng BETWEEN ? AND ? AND category='coffee'. This prunes to a box, a huge improvement, but a B-tree on two independent columns cannot efficiently answer a 2D range (it picks one column, scans a stripe, filters the other), and a fixed-size box is a terrible fit for density that varies by five orders of magnitude between a city center and a desert. In Manhattan a 2km box returns thousands of cafes; in rural Rajasthan the same box returns zero and you must widen it repeatedly.

The answer: map 2D space to one-dimensional cell keys so proximity becomes a prefix/range lookup, with density handled by adaptive cell size. Three closely related tools; I will explain each and say which to use.

Geohash. A geohash encodes (lat, lng) into a short string by recursively bisecting the world and interleaving latitude and longitude bits. Each added character refines the cell, and the magic property is that points close in space share a geohash prefix:

precision 4  ≈ 39 km  x 19 km   cell
precision 5  ≈ 4.9 km x 4.9 km
precision 6  ≈ 1.2 km x 0.6 km
precision 7  ≈ 153 m  x 153 m

“Places near me” becomes “places whose geohash starts with my prefix” - a prefix lookup, not a distance scan. We bucket places by, say, a precision-6 geohash into geohash6 -> set<place_id> (further split by category).

S2 (the tool Google actually uses). S2 projects the sphere onto the six faces of a cube and lays a Hilbert curve over each face, producing a 64-bit cell ID at up to 31 levels. It is better than plain geohash in two ways that matter at planet scale:

• Less shape distortion. Geohash cells distort badly near the poles and have non-uniform aspect ratios; S2’s cube projection keeps cells much closer to equal-area worldwide.
• The Hilbert curve preserves locality better than geohash’s z-order. Two cells adjacent on the Hilbert curve are almost always spatially adjacent, so a region is covered by a small number of contiguous cell-ID ranges. That makes “everything in this area” a handful of range scans on a sorted key - ideal for a sharded key-value store.

S2 cell id (level 30) is a 64-bit int on a Hilbert curve.
A radius query -> S2RegionCoverer returns a small set of cell-id
ranges [lo, hi] that cover the query disc.
Lookup = a few range scans:  place_index WHERE cell_id BETWEEN lo AND hi

QuadTree. A QuadTree is the adaptive alternative: start with the whole map as one node; whenever a node holds more than a threshold (say 100) places, split it into four quadrants; recurse. Dense areas get deep, fine-grained leaves; sparse areas stay shallow. A query descends to the user’s leaf and walks outward to neighbor leaves until it has enough candidates. This directly solves the density problem a fixed geohash precision does not.

        world
       /  |  |  \
     NW  NE  SW  SE
              |
        (dense city -> split again)
       /   |    |    \
     ...  ...  ...   ...   (each leaf ≤ ~100 places)

How they combine in practice. For a static Places dataset, the winning design is S2 cell IDs as the index key in a sorted, sharded store, using a region coverer to turn any radius into a few cell-ID ranges. Adaptive precision (indexing at the level where a cell holds a manageable number of places) gives you the QuadTree’s density-adaptiveness through variable S2 levels. The reason to know all three: geohash for its dead-simple prefix-shareability and Redis-native support, S2 for equal-area cells and Hilbert-curve range queries at planet scale, and QuadTree for the mental model of adaptive subdivision.

The edge problem. The nearest place can sit just across a cell boundary. Whether geohash or S2, you must query the target cell plus its neighbors (the region coverer already returns a covering that overlaps the disc; for a single geohash cell you add the 8 adjacent cells), gather all candidates, then run exact haversine filtering on that small set.

Because places are static, this index is built offline in a batch job (or updated incrementally as places are added) and served read-only. That is the fundamental difference from Uber: no write firehose churns this index, so we can precompute aggressively and cache hard.

2. Ranking and filtering nearby results

Naive approach: return the geometrically closest matches. Take the candidates from the geo-index, sort by straight-line distance, return the top ten.

Where it breaks:

• Distance is not relevance. The closest “coffee” match might be a shut-down kiosk with a 2.1 rating, while a beloved 4.8-star cafe 300m further is what the user wants. Pure distance ignores quality.
• Open-now and attributes matter. A user searching at 11pm does not want the cafe that closed at 6pm. Filtering by hours, price, and other attributes has to happen, and it depends on the user’s local time and the place’s timezone.
• Category is fuzzy. “coffee” should match cafes, coffee shops, and maybe bakeries that serve coffee - a category/text match, not an exact string.

The fix: a two-stage candidate-then-rank pipeline, with attributes cached in memory.

• Stage 1 - cheap spatial + category retrieval. The geo-index returns a bounded candidate set (cells covering the radius) already filtered to the category via a secondary key (cell:category -> place_ids), or via an inverted index if the query is free text. This is fast and produces maybe a few hundred candidates.
• Stage 2 - attribute filter and scoring. For each candidate, fetch attributes (hours, rating, review_count, price, coordinates) - these are small and heavily cached, so this is memory-speed. Filter out closed/irrelevant places, then score:

score = w1 * proximity(distance)          # closer is better, decaying
      + w2 * quality(rating, review_count) # Bayesian-averaged rating
      + w3 * popularity(visit_frequency)   # from anonymized visit data
      + w4 * relevance(query, place)        # text/category match strength
open_now = is_open(place.hours, user_local_time)   # hard filter

• Open-now correctness. Store hours in the place’s local timezone with the timezone ID; compute open/closed against the user’s request time converted to that zone. This is a classic bug source - do not compare against UTC or the server’s clock.
• Widening. If the initial radius yields too few open results, progressively widen the S2 covering to coarser cells and re-query, rather than returning three stale options.

The point: the geo-index cheaply produces a small candidate set; ranking turns “what is nearby” into “what the user actually wants,” and because place attributes are static and small, the whole ranking runs against an in-memory cache.

3. The routing engine (shortest path at planet scale)

This is the second core problem and the part the Uber design gets to hand-wave: given origin and destination, compute the fastest road route over a ~300M-edge graph, fast.

Naive approach: run Dijkstra on every request. Model the road network as a weighted graph (nodes = intersections, edges = road segments, weight = travel time). For each directions request, run Dijkstra from origin, settling nodes until you reach the destination.

Where it breaks:

• Dijkstra explores a disc. Plain Dijkstra settles every node closer than the destination. For a cross-city route that is hundreds of thousands of nodes; for a cross-country route, tens of millions. At ~175K route requests/sec, running even a bounded Dijkstra per request is billions of node settlements per second. Impossible.
• Re-does the same work. The highway backbone between two cities is traversed by countless routes, but naive Dijkstra rediscovers it from scratch every time.

First evolution: A* with a distance heuristic. Guide the search toward the destination using straight-line distance as a lower bound (A*). This prunes the explored region from a full disc to an ellipse - a real improvement - but for long routes it still settles far too many nodes, and a good heuristic for time (not distance) is hard when speeds vary with traffic. A* alone does not get you to cross-country routing in 300ms.

The answer: precompute a hierarchy so queries explore almost none of the graph - Contraction Hierarchies (CH). The insight is that long routes overwhelmingly use “important” roads (highways) in the middle, and only touch minor roads near the endpoints.

Contraction Hierarchies, offline preprocessing:

• Rank every node by “importance” (roughly, how central it is to shortest paths). Then contract nodes one at a time from least to most important. When you remove a node, if the shortest path between two of its neighbors went through it, you add a shortcut edge directly between those neighbors carrying the combined weight. The result is the original graph plus a set of shortcut edges that let a search skip over unimportant nodes.

Preprocess (offline, per road-network build):
  order nodes by importance
  for each node v in increasing importance:
      for each pair (u, w) of v's neighbors:
          if shortest u->w path goes through v:
              add shortcut edge (u, w) with weight = w(u,v)+w(v,w)
Result: original edges + shortcuts, each node tagged with its level.

Contraction Hierarchies, query: run a bidirectional search - forward from the origin, backward from the destination - but at each node only relax edges that go upward in the hierarchy (to more important nodes/shortcuts). The two searches meet in the “high” part of the graph. Because both only ever climb, each explores a tiny number of nodes - hundreds, not millions - and shortcuts let them leap across the highway backbone in a few hops.

Query (online, per request):
  forward Dijkstra from origin, only relaxing edges to higher-level nodes
  backward Dijkstra from dest,  only relaxing edges to higher-level nodes
  stop when the two frontiers meet; best meeting node = shortest path
  unpack shortcuts back into the real road segments for the polyline
Explores ~hundreds of nodes even for a cross-country route -> sub-100ms.

This is the technique that makes planet-scale routing feasible: you pay a large one-time offline preprocessing cost so that every online query is a tiny bidirectional search. Variants (Customizable Route Planning, hub labeling) trade preprocessing flexibility for query speed; CH is the canonical one to name and explain.

Handling live traffic in a precomputed hierarchy. CH shortcut weights are computed offline, but traffic changes them every minute. You cannot re-preprocess the whole planet per minute. The practical answer is Customizable Route Planning (CRP) style: separate the topology (which shortcuts exist - rarely changes, computed on the slow map build) from the weights (edge travel times - refreshed cheaply from live traffic). A fast “customization” phase re-weights the existing shortcut structure with current traffic in seconds, without recomputing the hierarchy’s shape. So live traffic updates the numbers, not the structure.

Sharding the graph geographically. The planet graph is too big for one node to search interactively. Partition it into regions with a boundary/overlay graph connecting them: intra-region routes stay on one node; inter-region routes route region-to-region through the overlay (the same “important roads connect regions” idea, one level up). Each routing node holds its region’s graph plus shortcuts in memory (tens of GB).

4. ETA and live traffic

Naive approach: ETA = route distance / speed limit. Sum each segment’s length divided by its posted speed limit.

Where it breaks:

• Ignores congestion. A highway at its 100kph limit at 3am is a 20kph parking lot at 6pm. Free-flow ETA is wildly wrong exactly when people need it.
• Ignores time-of-day patterns. Even without a live jam, a road has a predictable rush-hour slowdown. A route requested for “leave at 8am tomorrow” needs historical/predicted speeds for that time, not the current speed.
• Ignores turn/stop costs. Traffic lights, turns, and stop signs add time that raw length/speed misses.

The fix: per-segment speed from a live traffic stream, blended with a historical model, plus turn penalties.

Live traffic pipeline. Millions of navigating phones stream anonymized GPS traces. A stream processor:

For each incoming trace point:
  map-match it to a road segment (which segment was this phone on?)
    - snap the noisy GPS to the most likely segment given recent points
  compute observed speed on that segment
Windowed aggregation (rolling 1-3 min) per segment:
  live_speed[segment] = robust_avg(observed speeds, weighted by recency)
  confidence[segment] = f(number of probes)
Write segment_id -> {speed, confidence, updated_at} to Redis.

Blending live with historical. For a segment with many current probes, trust the live speed. For a segment with few probes (a quiet side street, or a future departure time), fall back to a historical speed model - the typical speed for that segment at that day-of-week and time-of-day, computed offline from months of traces. The edge weight used in routing is:

speed(segment, t) =
    live_speed        if confidence high and t ≈ now
    historical(segment, day_of_week, time_of_day)   otherwise
    blend of the two  in between
edge_time = length / speed(segment, t) + turn_penalty(from, to)

• ETA for future departures uses the historical model along the route, optionally with a live prediction of how current jams will evolve.
• The routing/ETA feedback loop. These speeds feed both the ETA and the CH weight customization, so the router genuinely avoids jams (it picks a longer-but-faster detour) rather than just reporting a bad ETA on a congested route.

The elegant part, mirroring Uber’s surge: live traffic is a windowed aggregation over the same GPS traces the product already collects, written to a tiny in-memory speed map that both ETA and routing read O(1) per segment. The expensive map-matching and windowing happen asynchronously off the request path; the route request just reads current speeds.

API Design & Data Schema

Search and directions are read-heavy REST; traffic ingestion is a stream.

REST (user-facing)

GET /api/v1/search?q=coffee&lat=12.97&lng=77.59&radius_m=2000&open_now=true
  -> { results: [
        { place_id:"p_9", name:"Third Wave Coffee", lat:12.971, lng:77.593,
          category:"cafe", rating:4.6, review_count:1820, distance_m:180,
          open_now:true, price_level:2 }, ... ],
       next_page_token:"..." }

GET /api/v1/places/{place_id}
  -> { place_id, name, address, lat, lng, category, hours:[...],
       rating, review_count, phone, photo_refs:[...] }

GET /api/v1/directions?origin=12.97,77.59&dest=12.93,77.62&mode=drive&depart=now
  -> { routes: [
        { distance_m: 8200, duration_s: 1260, duration_in_traffic_s: 1740,
          polyline:"encoded...", steps:[
            { instruction:"Head south on 100ft Rd", distance_m:400,
              duration_s:70, polyline:"..." }, ... ],
          summary:"via ORR" } ],
       traffic_snapshot_ts: 1751... }

GET /api/v1/tiles/{z}/{x}/{y}.pbf     (vector tile, CDN-cached)

Traffic ingestion (phone -> backend)

// batched anonymized trace, sent every ~10s while navigating
{ "type":"TRACE", "session_token":"anon_ephemeral",
  "points":[ {"lat":..,"lng":..,"ts":..,"speed_mps":..,"bearing":..}, ... ] }
// no user identity; token rotates so traces are not linkable to a person

Data stores - the right tool per plane

1. Places store - a sharded key-value / document store (Bigtable / Cassandra) with an S2 secondary index. Places are read-heavy, schema-lightish documents queried by ID and by spatial cell. A KV/wide-column store scales reads horizontally and shards cleanly; a relational store buys us nothing here (no cross-place transactions) and shards worse. NoSQL is the right call: the access patterns are “get by id” and “get by cell range,” both trivial in a sorted-key store.

Table: places        (row key = place_id)
  place_id      STRING  PRIMARY
  name, address STRING
  lat, lng      DOUBLE
  s2_cell       INT64   -- cell id at index level, SECONDARY INDEX
  category      STRING  -- indexed
  hours         JSON    -- with timezone id
  rating        FLOAT
  review_count  INT
  popularity    FLOAT

Geo-index table:     (row key = s2_cell_range, sorted)
  s2_cell       INT64   -- Hilbert-ordered, so a radius = few range scans
  category      STRING
  place_id      STRING
  Query: WHERE s2_cell BETWEEN lo AND hi AND category = ?
  Shard by: high bits of s2_cell (geography) -> nearby places co-located

2. Road graph store - an in-memory graph with precomputed CH shortcuts, region-sharded. The routable graph plus shortcuts (tens of GB per region) lives in RAM on the routing fleet, loaded from a versioned build artifact. It is read-only between map builds; a new build is rolled out region by region with the ability to roll back.

Graph build artifact (per region, versioned):
  nodes[]:  node_id, lat, lng, level (CH importance)
  edges[]:  from, to, length_m, road_class, base_time_s, geometry_ref
  shortcuts[]: from, to, combined_time_s, unpacks_to:[edge_ids]
  boundary/overlay: nodes and edges connecting to adjacent regions
  Shard by: region (geographic partition); overlay graph stitches regions.

3. Live traffic store - Redis, in-memory, overwritten in place. segment_id -> {speed, confidence, updated_at}, ~5GB, region-partitioned to sit next to the routing nodes that read it. Non-durable by design - it is a rolling window and self-heals from the trace stream.

4. Historical traffic model - precomputed, read-mostly. segment_id x day_of_week x time_bucket -> typical_speed, computed offline from months of traces, stored in the same KV family, cached hot. Used for future-departure ETAs and low-probe segments.

5. Map tiles - static blobs on object storage behind a CDN. Pre-rendered per zoom level; the origin is touched only on cache miss. Not a database concern.

Why NoSQL/in-memory here but no relational store anywhere on the hot path: unlike Uber’s trips (transactional financial records that demand ACID and SQL), Google Maps has no per-request transactional entity. Everything is either a read of static precomputed data (places, graph) or a read of an aggregated stream (traffic). That is why the whole design leans on sharded KV stores, in-memory graphs, and CDN caching, and why eventual consistency is acceptable throughout.

Bottlenecks & Scaling

Where it breaks first, in order, and the fix for each:

1. Nearby-search read volume (a first-order load). ~700K proximity reads/sec. Fix: the S2/geohash geo-index turns each into a bounded lookup of a few cell ranges, not a scan. Shard the Places store by S2 cell (geography), so a query hits one or few shards. Cache aggressively: popular cells and popular places live in a Redis/edge cache, and identical searches (same cell + category) are cacheable for seconds since places are static.

2. Routing compute cost (the expensive per-request work). Dijkstra per request is impossible at 175K routes/sec. Fix: Contraction Hierarchies precomputed offline reduce each query to a small bidirectional search exploring hundreds of nodes. This is the single technique that makes the routing plane affordable - move the cost from online (per request) to offline (per map build).

3. Graph too big for one node. The planet graph does not fit interactively on one machine. Fix: partition the graph into geographic regions with an overlay/boundary graph; intra-region routes stay local, inter-region routes go through the overlay. Route requests are geo-routed to the region owning the origin. Each region’s graph + shortcuts sit in memory on that region’s routing fleet.

4. Live traffic in a precomputed hierarchy. CH weights are baked offline but traffic changes them every minute. Fix: CRP-style separation of topology from weights - the shortcut structure is computed on the slow map build; a fast customization re-weights it from the live traffic map in seconds. Traffic changes numbers, not shape, so you never re-preprocess the planet.

5. Hot regions and hot places. A city center, a viral restaurant, or a stadium concentrate both search and routing load onto a few shards. Fix: adaptive S2 level (finer cells in dense areas so a cell never returns 10,000 candidates) and replicated read caches for hot cells/places. Popular routes (common origin-destination corridors) can be cached briefly. Sub-shard hot regions onto dedicated routing nodes.

6. Traffic ingestion + map-matching load. 2M trace points/sec must be map-matched and windowed. Fix: it is a windowed streaming aggregation (Flink), fully off the request path, keyed by segment/geohash so a segment’s probes land together and aggregate locally. Output is a tiny segment -> speed map. Raw traces are never stored; only the rolling aggregate is kept.

7. Map-tile bandwidth. Tiles dwarf all other traffic in bytes. Fix: tiles are pre-rendered static assets on a CDN; the vast majority of requests never reach the origin. Vector tiles (small, client-rendered) further cut bytes and let one tile serve many styles/zooms.

8. Stale places vs freshness. A new or closed place must eventually appear/disappear. Fix: incremental updates to the geo-index (add/remove a place ID from its cell) propagate within minutes; caches carry short TTLs. Since consistency is eventual by design, this is a background job, not a hot-path write.

9. Map build rollout risk. A bad graph build could break routing continent-wide. Fix: versioned graph artifacts rolled out region by region with canary regions and instant rollback. The old build keeps serving until the new one is verified. Traffic customization runs on top of whichever build is live.

10. Single points of failure and multi-region. Fix: Search, Routing, and Traffic services are stateless behind load balancers and rebuild in-memory state from durable artifacts (graph builds, Places store) or the trace stream (traffic). The whole stack is deployed per geographic region and requests are geo-routed, so the latency-critical search and routing loops never cross a region boundary. Kafka, Redis, and the KV stores are replicated. No single box whose loss stops the product; at worst a region’s routing fleet reloads a graph while requests briefly retry or fail over to a neighbor.

Wrap-Up

The trade-offs that define this design:

• Precompute-and-cache over compute-on-demand. Places are static, so the geo-index is built offline and cached hard; the road graph is static between builds, so the expensive hierarchy is computed offline. We move cost from the hot path (per request, at planet scale) to cold builds, which is the only way search and routing stay cheap.
• S2 cell IDs over geohash prefixes or SQL boxes. We index space as Hilbert-ordered 64-bit cells so a radius query is a few contiguous range scans on a sorted key, with equal-area cells worldwide - better distribution and less polar distortion than geohash, and far better than a 2D SQL box that a B-tree cannot answer.
• Contraction Hierarchies over per-request Dijkstra. We pay a heavy one-time preprocessing cost so every route query is a tiny bidirectional search exploring hundreds of nodes, not millions - the technique that makes cross-country routing sub-second.
• Separate graph topology from edge weights. The shortcut structure is built on the slow map build; live traffic only re-weights it in a fast customization pass, so real-time congestion changes routes and ETAs without re-preprocessing the planet.
• Eventual consistency everywhere; no transactional hot path. Unlike a ride-hailing matcher, Maps has no “assign exactly one” operation, so we never pay for strong consistency - everything is a read of precomputed data or an aggregated stream, which is why NoSQL/in-memory stores and CDN caching carry the whole system.

One-line summary: a read-dominated geospatial system where ~500M static places are indexed by S2 cells for bounded nearby-search lookups, directions are answered by a bidirectional Contraction-Hierarchies search over a region-sharded in-memory road graph whose shortcut weights are refreshed from a windowed live-traffic aggregation of anonymized GPS traces, ETA blends live and historical per-segment speeds, and everything leans on offline precomputation, geographic sharding, and CDN caching rather than any strongly-consistent write path.