Part 2 of 7 · 2 min read
Scope and numbers
Petabytes of tiles, millions of updates.
Think of a paper atlas that is also a taxi guide. The atlas has a page for every zoom level. The guide reads the roads as a network, picks a route, and tells the driver about a jam as it forms.
Questions and the answers assumed here (from the book's sample talk).
- Which features? Location updates, navigation, estimated time of arrival (ETA) and map rendering.
- Road data? Terabytes of data from outside sources are available.
- Traffic? Yes, since it is key for accurate times.
- Travel modes? Several, such as driving and walking.
- Multi-stop trips, business places, photos? Not in this design.
Requirements. Accuracy of the route and ETA. Smooth map display on a phone. Low data and battery use.
Numbers (from the book).
- Users: 1 billion daily users, each using navigation 35 minutes a week. That is 35 billion minutes a week, or 5 billion minutes a day.
- Location updates: a point every second would be 5 billion × 60 = 300 billion a day, or about 3 million a second. Batched every 15 seconds, the rate is about 200,000 a second, and 1 million at peak (5 times).
- Map tiles: the finest zoom level (21) needs about 4.3 trillion tiles to cover the world. At 100 KB each, that is about 440 PB. About 90 per cent of the world is empty land and sea, and those tiles compress very well, so the book takes about 50 PB for this level. Each lower level has a quarter as many tiles: 50 + 50/4 + 50/16 + ... is about 67 PB, so about 100 PB in all.
- Tile data per trip: a 1 km × 1 km area needs 25 tiles of 200 m, which is 2.5 MB. At 30 km/h, that is 75 MB an hour, or 1.25 MB a minute.
- CDN: 5 billion minutes × 1.25 MB is 6.25 billion MB a day. That is about 72,000 MB a second (the book rounds to 62,500). Spread over 200 points of presence, each serves a few hundred MB a second.
The finding: storage is huge but static, and the write rate is high but simple. The map is a caching and CDN problem, and the route is a graph problem.
ETA
Estimated time of arrival is the predicted time at which a traveller will reach the destination, given the route and current traffic.
Example: "27 minutes" for a drive with a slow motorway at this hour.
Check yourself: 1. Why are location updates batched? 2. Why does the book cut the tile storage by 80 to 90 per cent? 3. What sets the CDN cost?