Part 6 of 7 · 2 min read
Trade-offs
What to say out loud.
Trade-offs and what to say
| Choice | Gain | Cost |
|---|---|---|
| Batch location updates | 15 times fewer requests | Up to 15 seconds of delay |
| Pre-built tiles on a CDN | Cheap and fast | 100 PB of storage, rebuild when the map changes |
| Client computes tile URLs | One less call | A change needs an app update |
| Tile service returns URLs | Flexible | An extra service and call |
| Vector tiles | Smaller, smooth zoom | More work on the phone |
| Routing tiles in object storage | Cheap, simple | Tile loading on demand, cache needed |
| Three levels of detail | Fast long routes | Links between levels to maintain |
| ML ETA | Better estimates | Models and data to run |
| WebSocket for reroutes | Two-way, light | Stateful servers |
Extension. Multi-stop trips for delivery drivers: choose the best order of stops using live traffic (a hard problem, close to the travelling salesman problem), then navigate between them.
Interview angle
Answer in your head first, then open it.
How do you store the map?
Pre-built image or vector tiles by geohash and zoom, in object storage behind a CDN.
How is a route found on a huge graph?
Routing tiles with three levels of detail, and A*.
How is traffic known?
From the stream of users' location updates.
How do you cut the location traffic?
Batch on the phone and slow down in traffic.
How does rerouting scale?
Store a tile chain per user, check only the largest tile, and push through WebSocket.
One follow-up to try. "Offline maps." A good reply: let the user download the tiles and routing tiles of one region. Tiles are static files, so this is a package of a region. The phone runs A* on local routing tiles. The trade-off is device storage (tens to hundreds of MB), staleness of road data, and no live traffic.
Check yourself: 1. What are the costs of batching? 2. Why is the offline follow-up easy for tiles? 3. What is the main trade-off of vector tiles?
Words you will meet
| Word | Meaning |
|---|---|
| Geocoding | Turning an address into coordinates |
| Geohash | A short string that names a grid cell |
| Map tile | A small square picture of part of the map |
| Routing tile | A small piece of the road graph |
| ETA | The predicted time of arrival |
| Point of presence (POP) | A CDN location near users |
| Vector tile | A tile of shapes drawn by the phone |