Storage Schema and Request Handling

In one line: three stores again, chosen by data shape — and the key-value store here does something specific: it is the routing directory that maps geography to servers.

The schema

KEY-VALUE STORE  (segment to server)      GRAPH DB (graph data)
  segID       : INT                         roadNetwork : GRAPH
  serverID    : INT
  coordinates : List[]     <- boundary     RELATIONAL DB (rush hour)
  neighbors   : List[]     <- segment IDs    edgeID    : INT
                                             hourRange : Tuple
                                             rush      : BOOL

Note: the segID, serverID, and edgeID are unique identifiers created by a uniqueID generator.

The key-value store is a routing directory — that is its real job

It is easy to read this as ordinary metadata. Look at what segID → serverID actually enables.

Lesson 12 states it: "the store provides the serverID hosting the required segment, ensuring requests are routed correctly." So the key-value store is what turns a coordinate into a machine address.

The lookup chain is:

user coordinates -> segID (via boundary comparison) -> serverID (via KV lookup) -> query that server

That makes it the same component as object storage's manager node and that building block's ZooKeeper mappings — a placement directory consulted on every request.

And it has the same properties: it must be fast (it is on the critical path), highly available (nothing routes without it), and it must change when servers change (a segment moving hosts must be reflected immediately, or requests go to the wrong machine).

Which is why a key-value store rather than a relational one — Lesson 12 says it "minimizes latency by providing quick access to segment metadata." Exact-key lookups, tiny values, read on every request. Textbook key-value profile.

The neighbors list makes segment traversal a graph problem too

neighbors: List[] holding adjacent segment IDs is a small field with a nice implication: the segments themselves form a graph.

That is what makes Lesson 8's bounding step efficient. To find every segment within 5 miles you do not scan all segments comparing coordinates — you start at the design's segment and walk the neighbour links outward until you exceed the radius. A breadth-first traversal over segments.

So there are two graphs at two scales: the road network inside a segment, and the segment adjacency graph above it. Lesson 7's exit-point graph sits between them.

Three levels of abstraction, each hiding the detail below — which is exactly the hierarchical structure that made the problem tractable.

Historical traffic in a relational DB, keyed by edge and hour range

The rush-hour table is small and precisely shaped: edgeID, hourRange, rush.

Relational is right here for the reason the databases material would give: this is structured, low-volume, and queried by attribute — "is edge X in rush hour during window Y?" is a straightforward indexed lookup, and the data changes rarely since patterns are learned over weeks.

Note the deliberate separation from live conditions. This table holds "historical traffic patterns" — recurring, predictable congestion. Current traffic lives in the graph's edge weights, updated continuously by Lesson 11's pipeline.

That is the transitory-versus-persistent split, made concrete in storage: persistent patterns in a queryable relational table, current conditions in the mutable graph weights.

And it is what makes Lesson 9's prediction possible. For a trip starting in two hours, current weights are irrelevant and the hourRange table is exactly what you need.

Adding a segment

1. A segment contains boundary coordinates and a road network graph.
2. The segment adder processes the request and assigns a unique ID via the ID generator.
3. The segment adder forwards the segment data to the server allocator.
4. The server allocator assigns a host server, deploys the graph, and returns the serverID.
5. The segment adder stores the segment-to-server mapping in the key-value store for request routing. It also saves the boundary coordinates.

Segments are deployed, not just stored — the graph lives in a server's memory

Step 4 says the allocator "assigns a host server, deploys the graph." That is stronger than writing to a database.

Lesson 5 established that segments must fit in memory for traversal to be fast. So a segment is not fetched from storage per query — it is loaded onto a specific machine and held resident there.

That is why the mapping is segID → serverID rather than segID → storage location, and why Lesson 12 lists replication of segment servers as the availability mechanism: losing a server means losing the in-memory graph, and something must already have it.

It also makes segment placement a capacity problem — the server allocator must balance segments across machines by memory footprint, and a dense urban segment is far larger than a rural one. Uniform segment sizes make that harder, which is another argument for Lesson 12's non-uniform sizing.

Note vertex_sequence on the precomputed path. That is what makes the high-level edge expandable back into turn-by-turn directions — without it the abstraction is fast and unusable.

Handling a user request

1. The user submits a source and a destination.
2. A distributed search determines the coordinates for these points.
3. The graph processing service identifies the segments containing the design and destination coordinates.
4. The service retrieves the hosting servers for these segments from the key-value store.
5. The service queries the relevant servers for the shortest path. If points lie in the same segment, the query runs locally. Otherwise, it connects segments across servers.

Step 5 has two very different execution paths

The distinction between same-segment and cross-segment routing is a fork in the architecture, not just a case:

Same segment — one server, one in-memory graph, a precomputed lookup. Fast and simple.

Cross-segment — Lesson 8's bounding to select segments, Lesson 7's exit-point graph, and queries to multiple servers whose results must be combined. That is a distributed fan-out with all the usual costs: the query is as slow as the slowest server involved, and any one of them failing affects the result.

So the design has an implicit fast path and slow path, and the fast path covers a large share of real queries — most navigation is local.

Worth naming in an interview, because it reframes the performance story: optimize the common case (local routing) and accept that long-distance routing is more expensive, rather than treating all routes as equivalent.

It also connects back to Lesson 5's segment-sizing tension: larger segments mean more queries stay local, which is a genuine argument against making them too small.

Distributed search runs before anything else, and it is on the critical path

Step 2 — geocoding text to coordinates — happens before any graph work.

That is a serial dependency inside the 2–3 second budget from Lesson 2. If geocoding takes 400 ms, routing has 1.6–2.6 seconds left.

Two implications: geocoding results should be cached aggressively, since popular destinations are searched constantly and their coordinates never change. And it strengthens the case for typeahead from Lesson 4 — if the client resolves the destination to a known place ID while the user types, geocoding at request time becomes a lookup rather than a search.

Same pattern as elsewhere in the chapter: move work off the critical path by doing it earlier, whether that is precomputing paths offline or resolving destinations during typing.

Interview signal by level

Next: the pipeline that keeps it current.