Design Maps and Navigation

It is the Saturday of Mysuru Dasara. By four in the afternoon, tens of thousands of cars are leaving Bengaluru for the palace lights, about 150 km away, and nearly every driver has asked one maps app for the fastest way. Then a lorry breaks down on the highway near Mandya. Within a minute, the phones crawling past it have reported the slowdown. Within two, the arrival times of the cars behind it have jumped by twenty minutes, and new requests are routed around the jam. Behind that moment sit three systems: a map that draws at once, routes that come back in milliseconds, and arrival times that learn from every phone on the road.

The product: a maps and navigation app for a large country. People pan and zoom the map, search for a place, ask for the fastest route by car or two-wheeler, and follow turn-by-turn directions. The arrival time must stay honest as traffic changes, even at the evening peak. One trip runs through the whole chapter: from Indiranagar in Bengaluru to Mysuru Palace.

That Dasara evening hides three systems with very different shapes. Showing the map means serving small square pieces of the map, called tiles, to millions of screens. Finding a route is a graph search that must finish in well under a second. Live traffic is a stream of millions of location updates, turned into road speeds every minute. Treat them as three systems that share one map of roads.

Here is what is in scope today, and what is not:

The road data itself arrives as a regular map release; the work here is to serve it fast and keep it live. The non-functional requirements, as numbers:

• Smooth map: tiles appear within about 100 ms while panning, so they must come from a cache close to the user.
• Fast routes: a route between any two points in the country comes back in under a second, even at the evening peak.
• Honest ETAs: within about 10% on most trips, so within about 17 minutes on the three-hour Mysuru drive, using traffic no more than a couple of minutes old.
• Works on the move: guidance continues through tunnels and weak signal; the app does not need the server for every turn.
• Private: pings feed only road speeds. Each trip gets a random id, the first and last few hundred metres (near homes) are dropped, and only aggregates are kept long term.

Before choosing any machinery, size the flows. Start with the number that shapes the traffic pipeline: location pings from people who are navigating. Assume a large country at the evening peak with 5 million drivers navigating at once (the Dasara crowd is a local spike inside that), each phone recording a position of about 100 bytes every 4 seconds.

The other quantities follow the same way:

1.25 million writes a second is far beyond one database, but easy for a partitioned stream: 100 partitions take 12,500 pings, about 1.25 MB, a second each. Phones batch about four fixes per request, so the servers see roughly 310,000 requests a second while the stream still carries every position. None of it is kept for long: within a minute or two, the pings become one speed per road segment.

With the flows sized, the app talks to three services, each with its own call pattern. Here is the Mysuru trip as calls:

GET  /v1/tiles/{z}/{x}/{y}.mvt?v=2026-10-01                   -> 200 vector tile (cached for days)
GET  /v1/places/search?q=mysuru+palace&near=12.97,77.64       -> 200 { places[] }
POST /v1/routes  { from: [12.97, 77.64], to: [12.31, 76.66], mode: "car", departAt }
                                                              -> 200 { routes: [{ polyline, etaSec, steps[] }] }
POST /v1/trips/{tripId}/pings    { points: [{ lat, lng, speed, heading, t }] }  -> 202
GET  /v1/traffic/{z}/{x}/{y}                                  -> 200 { segments: [{ id, speedKmph }] }
POST /v1/trips/{tripId}/reroute  { position, heading }        -> 200 { route } or 204 (no better route)

Tile URLs carry the map version, so a new map release gets new URLs instead of stale cached tiles.

Tiles are addressed by zoom level and position (z/x/y), which makes them ideal for caching: the same URL means the same bytes for every user until the map version changes. Traffic is a separate, small overlay refreshed every minute, so the large base tiles can stay cached for days.

Pings are batched: the phone collects a few positions and sends them in one request, which saves battery and radio time. The server answers 202 at once; nothing the driver sees waits for the traffic pipeline. departAt lets the family plan tomorrow's drive with the typical traffic for that hour.

Behind those calls sits the core data: the road graph. Junctions are nodes and road segments are directed edges, so a two-way road is two edges. Each edge carries what routing needs to price it.

speed_profile holds the typical speed of each segment for every 15-minute slot of the week (7 × 96 = 672 slots), learned from months of history. It answers "how fast is this road on a Monday at 9 am" when live data is missing, and it predicts traffic for the part of a long trip that is hours away.

Each kind of data lives where its access pattern fits:

Only live speeds, and the shortcut values computed from them, change by the minute; everything else is rebuilt offline and copied.

Put together, the pieces form three lanes. The app pulls tiles from the CDN, sends pings into a stream that aggregators turn into live speeds, and asks the routing service, which loads those speeds into memory, for routes. The scene follows the Dasara evening: the map opens, the Mysuru route comes back, and then a jam changes it.

The three lanes share almost nothing at request time. Tiles never touch the routing service, and pings never wait for a route. The only link is the live speed table: aggregators write it every minute and routing servers load it, so a route query never waits on another service.

The big picture showed the Mysuru route coming back in about 10 ms. This page asks why that is hard. Routing is a shortest-path search on the road graph, where each edge's weight is its travel time (length divided by speed), not its length.

The textbook tool is Dijkstra's algorithm, and it behaves like a ripple from a stone dropped in a pond. It settles junctions in order of travel time from the start, always taking the nearest one not yet settled, until the destination is settled. A ripple spreads in every direction at once.

That is the problem. Mysuru Palace is about 150 km and close to three hours from Indiranagar, so the search first settles every junction it can reach sooner: all of Bengaluru, and out past Tumakuru, Kolar and Hosur, which lie in the wrong direction. That is in the order of a million junctions, or about a second of CPU. Treat that second, and the 10 ms later in this chapter, as illustrative: real figures depend on the code and the graph, but a gap of about a hundred times is the point.

Most requests are shorter trips inside one city, but suppose every query cost a second: 20,000 queries a second would need about 20,000 CPU cores, and every driver would wait a second for each reroute. The usual trims help only a little:

The trims make the ripple smaller, not different. The big win comes from doing work in advance, once, so that a query can skip most of the map. Which work would let a query skip the lanes of Mandya?

Think about how you would plan the Mysuru drive yourself. You care about the lanes near home and the lanes near the palace; in between, you simply take the highway. Nobody plans a way through the lanes of Mandya.

Routing can work the same way. Split the graph into regions of a few thousand junctions each: a neighbourhood like Indiranagar inside the city, hundreds of square kilometres of farmland outside it. A region's border junctions are where its roads cross into neighbouring regions. For every region, precompute the best travel time between each pair of its border junctions. Each value is a shortcut: one edge that stands for a whole path through the region.

A query then searches the start's region in full detail out to its border junctions, crosses the middle on shortcuts, and searches the destination's region in from its borders.

Nothing is lost. Any route through a region enters and leaves it at border junctions, and the shortcut already holds the best time between them, so the search finds the exact fastest route, over a much smaller graph. Each shortcut also remembers the path it stands for, so the final route can be unpacked into real roads.

In numbers, for illustration: 30 million junctions in regions of about 3,000 make 10,000 regions. With about 30 border junctions each, a region has about 870 shortcuts (30 × 29, one per ordered pair), so the country needs about 9 million shortcut values, some 35 MB at 4 bytes each. The middle of a trip becomes a graph of about 150,000 border junctions, since neighbours share them, instead of 30 million junctions.

Is one level enough for a 150 km trip? The next page shows why not, and what to do about it.

One level is not enough. Indiranagar to Mysuru crosses several hundred small regions, so the search still settles thousands of border junctions, each with about 30 shortcuts to scan: roughly ten times less work than plain search, not the hundred times the design needs.

So stack the levels. Group about 30 neighbouring regions into a level-2 region, roughly a district, with shortcuts between its borders, computed cheaply from the level-1 shortcuts inside it. Group those again into level 3, roughly a state: 10,000 small regions become about 330, then about 11.

The search follows one rule: at every junction, use the shortcuts of the biggest region that contains neither the start nor the destination. That means every lane near Indiranagar, small-region hops a few kilometres out, district-sized hops across the middle, and down again near Mysuru: lanes to a state highway, then a national highway.

The search did not get cleverer; the graph it searches got smaller. In this illustration a few thousand junctions replace a million, about 1 s becomes about 10 ms, and 20,000 queries a second need around 200 cores instead of 20,000: a handful of large servers per region, each holding the graph and every level in memory. For Bengaluru to Delhi, about 2,100 km, plain search would settle much of the country, while the shortcut query adds only a level or two.

Shortcut values are travel times, and travel times change. When the lorry blocks the highway near Mandya, every shortcut whose best path runs along that stretch is suddenly wrong. How do shortcuts keep up with live traffic?

The design keeps a slow step and a fast step apart. Splitting the graph depends only on the road layout; shortcut values depend on speeds. The split is hours of offline work, redone with each map release. The values are recomputed every minute from the latest live speeds.

The refresh is cheap because it is local. A small region's values come from about 30 short searches inside its 3,000 junctions, tens of milliseconds of work, and a bigger region reuses the shortcuts of the smaller ones inside it. The Mandya jam touches one small region and the two bigger regions around it, so updating them takes well under a second. At the evening peak, when speeds change everywhere, recomputing all 10,000 small regions costs a few hundred core-seconds: about ten seconds on one 64-core server.

A refresh service publishes the new values, about 35 MB for the small regions, and each routing server swaps them in all at once, so no query mixes old values with new ones. A closed road is the same move with an infinite weight: the next refresh routes everyone around it.

Every query starts with a smaller search of its own. The family's phone reports a GPS fix outside their gate in Indiranagar, and they tapped Mysuru Palace as the destination. Both are points, but the graph needs a road segment and a position along it. Checking all of the country's roughly 45 million road segments (a two-way road counts once here) would take longer than the route itself, so the segments get a spatial index.

Cut the map into a grid of cells about 150 m across, and list in each cell every segment whose shape passes through it; a long highway segment appears in many cells. To snap a point, read its cell and the eight around it, measure the distance to each candidate segment, and project the point onto the closest. If the nine cells hold no road at all, as in a field outside a village, widen the search ring by ring.

The next chapter, on nearby places, builds the same kind of grid for places and shows why the eight neighbours matter. The other common choice is an R-tree, offered by databases with spatial support, which groups segments into nested bounding boxes. Nearest by distance is only the start; four rules keep a snap off the wrong road:

Size: about 45 million segments, each listed in two or three cells at 16 bytes an entry, is about 2 GB, so every routing server keeps the index in memory beside the graph. The traffic pipeline, on the next page, uses the same index to snap whole traces of fixes instead of one point.

Snapping placed one point on a road. The traffic pipeline does the same for millions of points and answers a harder question: how fast is each road moving right now? Every navigating phone is a traffic sensor.

Use the median, not the average. A bus waiting at its stop, or a GPS jump that implies 300 km/h, is an outlier; on a segment with few samples one outlier can drag an average far off, while the median barely moves. Where data is thin, such as a quiet road at 3 am, fall back to the typical speed for that time of week.

An ETA is the sum of travel times along the route. Here is the Mysuru trip on the evening of the breakdown:

Look at the lorry's row. A car 5 km behind it reaches the jam in minutes and should be charged the full 20. A family leaving Indiranagar reaches it in about 105 minutes, and by then the lorry may well be gone. So blend: live speeds for the next stretch, shifting to the typical speed for the time you will arrive further out. For the family, that prices the stretch at its typical 1.5 minutes and the trip at about 2 hours 37 minutes. How fast to shift is learned by comparing past ETAs with actual arrivals.

The last lane is the one people see first: when the family opens the app, the map must appear within about 100 ms. The world map is cut into square tiles arranged as a pyramid. At zoom 0 one tile shows the whole world. Each zoom level splits every tile into four, so zoom z has 4^z tiles and each tile is half as wide as one level up. Five levels show how fast it grows:

Widths are at the equator and shrink towards the poles. A phone screen shows a dozen or so tiles at a time, so opening the map costs a dozen or so small requests, almost all answered by the CDN.

You cannot pre-render 69 billion tiles, and you do not need to: most are ocean or empty land that nobody zooms into. Pre-build the low zooms everywhere and the high zooms over populated areas, render the rest on first request, and cache them like any other tile.

Tiles come in two kinds. Raster tiles are pre-drawn images: little work for the phone, but larger, a new set for every style and language, and labels that turn when the map rotates. Vector tiles carry road and building shapes plus labels, and the phone draws them: smaller, one set for day, night and every language, labels that stay upright, but drawing needs the phone's GPU. Vector tiles are the usual choice for apps; raster tiles still suit simple web maps and very old phones.

With the three lanes built, here is how each one fails. Every failure below has a planned response, and each row names what the user notices as well as what the system does.

Most of these responses work because the expensive data is read-only at request time. The graph and tiles are built offline and copied everywhere, so losing a server loses nothing. Only live speeds, and the shortcut values computed from them, change all the time, and even they have a fallback in typical speeds.

Each choice in this design buys one thing with another. Four are worth naming:

Most of them trade freshness or speed against work done somewhere else: on the build servers, in the ping stream, or on the phone.

Tile bandwidth dominates the bill: if 50 million people a day each load about 100 tiles of roughly 20 KB, the CDN moves about 100 TB a day, while routing runs on a few dozen large servers across all regions and zones.

Optional: what the phone does once the trip starts, and how rerouting avoids flapping and herding.

Once a route is chosen, the phone does most of the work. It holds the route's shape and every turn, and compares each GPS fix with the route locally. No server is needed to say "turn left in 200 m", so guidance keeps working when the network drops. In a tunnel, where GPS drops out too, the phone estimates its position from its last known speed along the route.

There are two reasons to reroute, and they are handled differently:

The threshold for traffic reroutes prevents flapping: without it, two routes with nearly equal ETAs would swap every minute and confuse the driver. A subtler problem is herding: if every car behind the Mandya lorry is sent down the same village road, the village road jams. One remedy is to spread drivers across several good alternatives; another is to add the expected extra traffic to a side road's weight before sending more drivers there.

A 45-minute slot leaves about 40 minutes of design once introductions and your own questions are done. Here is maps on that clock.

Pick the deep dive from the interviewer's question. If they ask how a route comes back so fast, go deep on region shortcuts and stacked levels. If they ask where the ETA comes from, cover the ping pipeline, map matching and the live and typical blend. If they care most about the screen, cover the tile pyramid and versioned URLs.

Interviewers change the problem to see whether your design bends or breaks. Try each one before opening the answer.