CSE Roadmap

Specialist tier · about 5 hours · 7 parts

Part 5 of 7 · 3 min read

Navigation

From A to B, kept fresh.

Parts of navigation.

  1. Geocoding service: turns the origin and destination into coordinates.
  2. Route planner: the coordinator. It asks the other services below.
  3. Shortest-path service: finds the top few paths by road structure alone, without traffic, using A* over routing tiles. The geohash of the origin and destination picks the first tiles. The search loads neighbouring tiles from object storage (or its local cache) as it grows, and can climb to larger tiles. Because the road graph rarely changes, results can be cached.
  4. ETA service: predicts the time for each candidate path, using machine learning on current and expected traffic, since the jam at minute 20 matters more than the jam now.
  5. Ranker: applies the user's filters (such as avoiding tolls or motorways) and sorts the routes from fastest to slowest.

Background updates from the location stream.

  • Traffic update service: reads the stream, works out speeds on each road, and updates the live traffic database that the ETA service reads.
  • Routing tile processing service: a periodic job that turns the raw road data into routing tiles, and also reads the stream to spot new or closed roads. It writes the tiles to object storage, organised by geohash.

Data stores in all.

Data Store Why
Routing tiles Object storage, cached on the routing servers Big, read as whole files, no database features needed
User locations Wide-column store (Cassandra) Heavy writes
Places for geocoding Key-value store Many reads, few writes
Pre-built map tiles Object storage behind a CDN Static, shared, huge
Live traffic A fast store updated from the stream Read by the ETA service

Rerouting. Without it, a route made at the start can become poor. The server must know which navigating users a traffic change affects.

  • Naive: store each user's route as a list of routing tiles. When a tile has an incident, scan all rows. With n users and routes of m tiles, that costs n × m.
  • Better: for each user, store the chain of tiles from the current tile up through each larger tile that contains it, until a tile also holds the destination. To check a traffic change, compare it only with the last (largest) tile of each row. If the changed tile is not inside it, the user is safe. This avoids scanning every tile of every route.
  • Better routes after a jam clears: keep a few alternative routes for each user, recompute their ETAs regularly, and notify the user when another one becomes faster.

A worked example (made up). A crash blocks one street-level tile. The server checks 2 million active routes by their largest tile. 12,000 contain the area. Only those get new ETAs. Of them, 3,000 get a faster alternative and a notice on their phones.

Pushing to the phone. Mobile push notifications carry small payloads (4,096 bytes for iOS) and are not reliable for this. Long polling has more overhead. WebSocket and server-sent events both work. The book prefers WebSocket for its two-way channel, which also helps with features such as last-mile delivery.

A*

A* is a path-finding algorithm that searches a graph by always extending the most promising path first, using an estimate of the distance left.

Example: on a road graph, A* tries streets that head towards the destination before streets that head away.

Check yourself: 1. Why does the shortest-path service ignore traffic? 2. How does the traffic service learn about jams? 3. Why store the chain of larger tiles per user?