At a glance#
| Number | Value | What it drives |
|---|---|---|
| Users | 2B+ monthly · 500M daily (assumed a quarter) | Google doesn't publish daily or request figures |
| Driving | 1B km a day (2020) · 1T km of directions in 2024 | ~25M driving hours a day at an assumed 40 km/h |
| Navigating phones | ~3M at the peak hour | a 3× peak over ~1M on average |
| Probes | ~600,000 points / s · ~18B a day | a fix every 5 s, sent in 30 s batches |
| Route queries | ~61,000 / s · design for 100,000 | route checks once a minute outnumber new requests 8 to 1 |
| Dijkstra vs overlay | 2.2 s vs 1.65 ms a query | ~134,000 cores vs ~610: preprocessing is mandatory |
| Map updates | 100M a day | most are places; geometry changes dirty a tile and 16 ancestors |
| Tiles | ~1M fetches / s · ~160 Gbps at peak | immutable by version, 95%+ CDN hits |
| ETAs | 97%+ of trips accurate (2020) · up to 50% better with GNNs | time each road for arrival, then a learned correction |
Architecture#
DiagramRouting, traffic and tiles on one page: a slow loop, a fast loop, a read path
%% title: Routing, traffic and tiles on one page: a slow loop, a fast loop, a read path
flowchart TD
APP@{ icon: "sd:phone", label: "Android · iOS · web apps<br/>a fix every 5 s · cached tiles" } ==>|"tiles"| CDN@{ icon: "sd:cdn", label: "CDN<br/>vector tiles · traffic overlay ~60 s" }
APP ==> API@{ icon: "sd:api", label: "API gateway<br/>directions · probes" }
MAPDB@{ icon: "sd:database", label: "Map data<br/>versioned road graph" } -.->|"new version"| TB["Tile builder<br/>dirty quadkeys only"]:::service
TB --> TS@{ icon: "sd:object-storage", label: "Tile store<br/>immutable, by version" }
CDN -.-> TS
API ==>|"probe batches"| KP@{ icon: "tech:kafka", label: "Kafka · probes<br/>partitioned by region" }
KP ==> MM@{ icon: "tech:flink", label: "Flink · map matching<br/>HMM · 1-min windows" }
MM ==> SPD@{ icon: "tech:redis", label: "Redis · live speeds<br/>speed · devices · age" }
SPD --> CUST["Customizer<br/>overlay costs every few s"]:::core
MAPDB -.->|"partition + overlay shape"| ROUTE["Routing service<br/>one region per server"]:::hot
CUST --> ROUTE
API ==>|"directions"| ROUTE
ROUTE --> ETA@{ icon: "sd:ml", label: "ETA service<br/>time-dependent walk + model" }
HIST@{ icon: "sd:database", label: "Historical profiles<br/>weekday · quarter-hour" } -.-> ETA
class APP client
class CDN,API edge
class MAPDB,TS,SPD,HIST store
class KP queue
class MM,ETA service- Split preprocessing by what it depends on: partition and overlay shape change with the map; overlay costs change with traffic, every few seconds.
- Probes are a stream, speeds are a table: 600,000 points a second become a ~2 GB table of segment speeds that routing, ETAs and the overlay all read.
- Tiles are immutable by version; traffic colours live in a separate overlay with a short expiry.
DiagramCustomizable route planning: what changes when
%% title: Customizable route planning: what changes when flowchart TD MAP(["Road graph<br/>junctions · segments · turns"]):::client -.->|"map changes"| PART["Partition<br/>cells with few boundary roads"]:::service PART --> TOPO["Overlay shape<br/>boundary-to-boundary shortcuts"]:::service TOPO --> CUST["Customize · 0.37 s on 12 cores<br/>shortcut costs, bottom up, in parallel"]:::core SPD(["Live speeds · closures = infinite cost"]):::queue ==> CUST CUST ==> Q["Query · 1.65 ms<br/>real roads in the end cells, shortcuts between"]:::hot Q --> OUT(["Route · a few thousand junctions scanned"]):::ok CH(["CH: 0.11 ms queries, but contract again on every speed change"]):::bad -.->|"rejected for live traffic"| Q
Key flows#
DiagramAnanya asks for the airport
%% title: Ananya asks for the airport sequenceDiagram autonumber participant A as Ananya's app participant G as API gateway participant R as Routing, Bengaluru participant E as ETA service A->>G: Koramangala to the airport, now G->>R: Query on the current overlay costs R->>R: Source cell, overlay, target cell R->>E: Three alternatives, 38 to 44 km E->>E: Each road at the speed expected on arrival E-->>A: Hebbal 1 hr 12 · ORR 1 hr 15 · toll 1 hr 19 Note over E: Hebbal at 6:15 uses history, 10 km/h, not the 35 km/h of now
DiagramA truck breaks down, routes avoid it in about 2 minutes
%% title: A truck breaks down, routes avoid it in about 2 minutes sequenceDiagram autonumber participant P as Phones behind the truck participant K as Probe stream participant M as Map matching participant S as Live speeds participant C as Customizer participant D as Drivers on that route P-)K: Fixes every 5 s, batches every 30 s K-)M: Partition for Bengaluru M->>M: Viterbi over nearby segments, trip ends deleted M-)S: 1-min window, 20 devices at 5 km/h S->>C: Segment speed drops C->>C: Re-customize its cell, under a second D->>C: Once-a-minute route check C-->>D: Faster route via another road Note over P,D: under 30 s + ~10 s + 60 s + under 1 s
DiagramA road edit becomes new tiles
%% title: A road edit becomes new tiles sequenceDiagram autonumber participant E as Map edit participant DB as Map data participant B as Tile builder participant T as Tile store participant P as Phone E->>DB: New flyover geometry DB->>B: Dirty quadkeys, z16 tile + 16 ancestors B->>T: Rebuilt tiles under version v+1 P->>T: Manifest for v+1 via the CDN T-->>P: Only tiles whose content changed Note over T: old URLs never change, nothing to invalidate
Data model#
DiagramCore entities
%% title: Core entities
classDiagram
class Segment {
+segmentId : int64
+from : junction
+to : junction
+lengthM : float
+roadClass : highway / arterial / local
}
class Cell {
+cellId : level + index
+boundary : junctions
+shortcuts : boundary × boundary
}
class LiveSpeed {
+segmentId : int64
+kmh : median of traversals
+devices : count · at least 3
+age : seconds
}
class Profile {
+segmentId : int64
+kmh : 7 days × 96 quarter-hours
}
class Traversal {
+segmentId : int64
+device : rotating anonymous id
+seconds : time across the segment
}
class Tile {
+quadkey : one digit per level
+version : map version
+body : vector geometry
}
Cell "1" --> "many" Segment : contains
Traversal "many" --> "1" LiveSpeed : aggregated into
LiveSpeed "1" --> "1" Segment : costs
Profile "1" --> "1" Segment : fills in
Tile "many" --> "many" Segment : draws- Routing data for a Western-Europe-sized region is ~3 GiB plus 0.07 GiB per cost function: one region fits in one server's memory.
- A tile's quadkey starts with its parent's: dropping the last digit goes up a level.
Lifecycle#
DiagramA road segment's speed, from history to live and back
%% title: A road segment's speed, from history to live and back stateDiagram-v2 [*] --> HISTORICAL HISTORICAL --> LIVE: 3+ devices in 5 minutes LIVE --> LIVE: new traversals, 1-min windows LIVE --> STALE: no new traversals, trust fades STALE --> HISTORICAL: faded fully to the profile STALE --> LIVE: traversals return LIVE --> CLOSED: none where history expects many, U-turns, reports CLOSED --> LIVE: traversals reappear class LIVE ok class CLOSED bad class STALE queue
Decisions#
| Decision | Chose | Over | Because |
|---|---|---|---|
| Shortest paths | CRP: partition + overlay, customized from speeds | Dijkstra per request | 2.2 s a query would need ~134,000 cores at peak |
| Preprocessing | Metric-independent once, costs re-customized | Contraction hierarchies | CH must contract again on speed changes; CRP re-customizes in 0.37 s |
| Graph placement | Whole region per server, replicated | One graph sharded across machines | no network hops inside a search; ~3 GiB a region |
| Traffic | HMM map matching, median per segment, 3+ devices | Averaging raw fixes in an area | flyovers, buses and walkers; privacy by count |
| ETA | Time-dependent walk, live near and history far, plus a model | Sum of current speeds | the Hebbal jam forms at 6:15, not 5:40 |
| Closures | Infinite cost, re-customize the cell | Wait for a new map version | minutes matter; tiles can follow |
| Tiles | Vector tiles, quadkeys, immutable URLs by version | Raster tiles overwritten in place | 100× less data; nothing to invalidate |
When it breaks#
| Failure | What users see | Contain it with |
|---|---|---|
| Overlay costs go stale in a region | routes ignore new jams | cost-age SLO; routing keeps answering from stale costs |
| 20,000 drivers sent to one side street | a new jam the router made | add assigned routes' load to costs; spread over alternatives |
| A road with one old probe | a wrong colour, a wrong route | below 3 devices, use the historical profile |
| 99 phones fake a jam | red street, needless reroutes | weight devices by trust; cross-check neighbours and reports |
| Flooded underpasses | routes into water | no traversals + U-turns + reports: close it in seconds |
| Correction model down | slightly worse ETAs | the time-dependent walk still gives the ETA |
| Monsoon evening, 2× requests | longer routes, wider ETA ranges | ~73 cores is cheap; degrade alternatives, then overlay refresh |
Say it in the interview#
- "Precompute what depends on the map, recompute what depends on traffic." Partition and overlay shape rarely change; costs change every few seconds.
- Dijkstra is correct and too slow: 2.2 s per continental query; an overlay answers in about 2 ms.
- CRP over CH for live traffic: CH's queries are faster, but CRP re-customizes in 0.37 s instead of contracting again.
- Probes to speeds: HMM map matching, 1-minute windows, at least 3 devices, trip ends deleted, about 2 minutes from slowdown to reroute.
- Time each road for arrival: live speeds near, history far, a learned correction on top; 97%+ of trips accurate.
- Tiles never change in place: quadkeys, vector tiles, a map version in every URL, traffic in its own overlay.
- Closures are costs: infinite cost and a re-customized cell, in seconds, never waiting for the map build.