Evaluation

In one line: the striking thing here is that one decision — segmentation — satisfies three of the four requirements. That is rare, and worth understanding why it happens.

What the single-server design failed at

Segmentation resolved all three:

• Distributed hosting: segments are hosted on separate servers, eliminating the global graph memory bottleneck.
• Load balancing: requests are distributed across segment servers based on the user's search area.
• Replication: replicating segments handles failover and distributes read load.

One decision, three requirements — because the constraint was shared

Segmentation delivers availability, scalability, and low latency simultaneously. That is unusual enough to be worth explaining.

The reason is that all three failures had the same root cause: everything lived in one place. Memory limits, connection limits, and single-point-of-failure are three symptoms of one architectural fact.

So partitioning fixes all three at once:

• Memory — each server holds only its segment.
• Connections — connections spread across segment servers by geography.
• Failure — losing a server loses one region's routing, not the service.

And it fixes latency as a bonus, because the graph being traversed is now small.

The generalizable observation: when several requirements fail for the same structural reason, one structural change can satisfy all of them. Look for the shared root cause before designing separate fixes for each symptom.

Note the honest parenthetical about replication — "though not detailed earlier" — the design admits it did not previously cover this. Replication of in-memory segment graphs is genuinely non-trivial, since Lesson 10 established segments are deployed into memory rather than fetched from storage.

Note: Google Maps uses lazy loading of data, putting less burden on the system, which improves availability.

Lazy loading is the client-side half of the same idea

Lesson 3 found that 99.75% of the response is map imagery. Lazy loading is how you avoid sending all of it.

Rather than delivering the whole route's tiles up front, the client fetches tiles for what is currently visible and loads more as the user pans or progresses. A cross-country route does not download the entire country.

That reduces bandwidth, improves time-to-first-render, and — as the note says — improves availability, because each request is smaller and a failure costs one tile rather than the whole map.

It is the same instinct as partitioning, applied to delivery: only materialize the piece you need right now. The server partitions the graph by geography; the client partitions the imagery by viewport.

Scalability

Scalability addresses handling increasing query volumes and managing growing data sets (more segments).

New segments can be added incrementally without rebuilding the entire graph. Scalability can be improved by using non-uniform segment sizes, with smaller partitions in dense urban regions and larger partitions in rural areas.

Non-uniform segments are the obvious refinement, and the reason is density

Uniform 5×5-mile squares are a simplification with a real cost, and the design names the fix.

A square in Manhattan contains thousands of intersections; the same square in rural Nevada may contain a dozen. Fixed geography produces wildly different graph sizes.

That breaks the design in both directions:

• Urban segments may exceed memory — violating the criterion Lesson 5 said everything rests on — and their O(V²) precomputation becomes prohibitive.
• Rural segments are nearly empty, so you pay per-segment overhead — metadata, a server allocation, exit-point bookkeeping — for almost no road network.

Non-uniform sizing fixes it by targeting roughly equal graph size rather than equal area. Smaller squares where roads are dense, larger where they are sparse.

This is exactly the weighted partitioning argument from earlier chapters: weighted round robin because servers are not identical, virtual nodes sized to machine capability because hardware is heterogeneous. Uniform partitioning is only correct when the underlying distribution is uniform, and geography emphatically is not.

Incremental segment addition is a genuine benefit of partitioning

"New segments can be added incrementally without rebuilding the entire graph."

That matters more than it sounds. With a single global graph, adding a newly-mapped region means rebuilding and re-precomputing everything — a batch job over billions of vertices.

With segments, a new region is a new segment: build its graph, precompute its internal paths and exit points, register it in the key-value store, and update its neighbours' adjacency lists. Nothing else is touched.

So the blast radius of a map update is one segment plus its neighbours, which is what makes continuous map improvement operationally feasible — including the new roads Lesson 11's analytics engine discovers.

Same property as sharding generally: partitioning bounds the cost of change, not only the cost of query.

Response times and accuracy

Processing a subgraph with hundreds of vertices is significantly faster than traversing a graph with millions. We cache processed subgraphs in memory to respond to requests almost instantly. A key-value store minimizes latency by providing quick access to segmentID values for graph processing and serverID for load balancing.

Accuracy: beyond static road data, we ingest live user location data and apply data science analytics to traffic patterns to dynamically update maps, refine routes, and improve ETA accuracy.

Accuracy is the only requirement with no architectural answer

Look at the table. Three requirements are met by structural decisions — partitioning, replication, caching. Accuracy is met by "collect live data, perform data analytics."

That is not an architecture; it is a process. And it reflects Lesson 2's observation that accuracy is a different class of requirement — it depends on modelling the world rather than on how you arrange servers.

Three consequences worth naming:

No amount of architecture fixes a bad ETA model. You can partition, replicate, and cache perfectly and still predict thirty minutes for a fifteen-minute trip.

It requires continuous investment. Availability, once achieved structurally, stays achieved. Accuracy degrades as the world changes and needs ongoing measurement against actual arrival times.

It is the only requirement whose quality the user directly judges. Nobody notices your replication factor; everybody notices when the ETA was wrong.

So the honest reading of this design is that it solves the engineering problem well and hands the hard problem to data science — which is a legitimate division, and worth saying rather than glossing.

What the design leaves out — worth volunteering

• Replication of segment servers is asserted, not designed. Lesson 12 admits it was "not detailed earlier." Replicating an in-memory graph that is deployed rather than fetched is genuinely non-trivial.
• Map matching is assumed — Lesson 6 handles a user on a known edge, but inferring which edge from noisy GPS is a separate problem.
• The bounding heuristic can miss routes forced outside the corridor by geography.
• Uniform segments are acknowledged as a simplification needing non-uniform sizing.
• Precomputation is per transport mode, multiplying storage and compute by the number of modes.
• Tile serving — 99.75% of the bandwidth — is essentially out of scope.

Worth volunteering: accuracy is the one requirement partitioning cannot help with. You can engineer latency and availability; whether the ETA is right is a data and modelling problem.

Interview signal by level

Next: the whole design under interview conditions.