Google Maps and Planetary-Scale Spatial Serving
Map serving is fast because almost nothing is computed on request — the world is precomputed into a pyramid of tiles, and space is indexed onto a one-dimensional curve.
The problem
Render any part of the world, at any zoom level, on any device, in the time it takes a finger to drag — for a dataset covering the entire planet with roads, buildings, terrain, labels, businesses and live traffic.
Rendering that on request is not possible. Almost the entire architecture is an answer to "how do we avoid computing this now?"
The techniques
Tile pyramids. The world is pre-rendered into square tiles at each zoom level: one tile at zoom 0, four at zoom 1, sixteen at zoom 2, quadrupling each level. A viewport becomes "fetch these particular tiles" — a set of independent, immutable, cacheable objects with predictable keys. That converts a rendering problem into a static asset delivery problem, which CDNs already solve perfectly.
Vector tiles rather than images. Modern implementations ship geometry and let the client render. Smaller payloads, client-side styling and rotation without a round trip, and resolution independence.
Space-filling curve indexing (S2). Google's S2 library projects the sphere onto six cube faces and orders cells along a Hilbert curve, turning a 2D location into a 1D cell ID with strong locality — points near each other in space are usually near each other in ID space. So a spatial range query becomes a range scan on a sorted index, which every database already does well. Cell IDs are also natural shard keys, cache keys and join keys.
Precomputed routing. Continental shortest-path queries are not run as plain Dijkstra over hundreds of millions of edges. Techniques in the contraction-hierarchies family precompute shortcuts through the graph offline so that queries explore a tiny fraction of it, reducing route computation by orders of magnitude at the cost of a heavy preprocessing step.
The architectural lessons
1. Precompute along the dimension the user moves through. Users pan and zoom, so the precomputation is organised by location and zoom. Identify the axis of variation and materialise along it.
2. Reduce dimensionality to reuse existing machinery. A Hilbert curve turns a hard 2D indexing problem into an easy 1D one. This is the same move as hashing to a shard key.
3. Immutability makes caching trivial. A tile for a given location, zoom and version never changes, so it can be cached forever at every layer. Versioning in the key means updates are a new key rather than an invalidation — the invalidation problem is designed away rather than solved.
4. Separate what changes at different rates. Base map geometry changes monthly; traffic changes every minute. They are different layers with different pipelines, composed at the client, so the expensive stable thing is not recomputed because a cheap volatile thing changed.