Problem RestatementProblem
Google asked: design an interactive map that shows more than 100 million data points (e.g., every store, sensor or event location). At zoomed-out levels, show aggregated information (a heat map or cluster bubbles with counts). At close zoom, show individual pins that can be clicked. Panning and zooming must be smooth.
Why It's Hard
- 100M points × ~20 bytes ≈ 2 GB of raw coordinates. A browser can't download or draw that.
- On screen, only a few thousand things can be shown usefully anyway.
Deep Dive — Putting 100 million points on a screenDeep dive
The screen has about two million pixels and the dataset has a hundred million points. Most of the design follows from that ratio.
Send the points in the viewport
Query the points inside the current bounding box and let the client draw them.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
VIEW["Zoomed out - whole country in view"] --> Q["Query the bounding box"]
Q --> N["40,000,000 points match"]
N --> WIRE["Hundreds of MB over the network"]
WIRE --> BROWSER["Browser cannot hold or draw them"]
N --> PIX["They would land on 2M pixels anyway - 20 points per pixel"]At low zoom the viewport is the dataset. And even if it arrived, the information is not there to be seen: twenty points per pixel renders as a solid block, so the transfer buys nothing.
Cluster on the server per request
Aggregate the points in the viewport into clusters and return those.
The payload is now small and the picture is readable. The cost is that clustering happens per request, over tens of millions of points, for every pan and zoom — and adjacent users looking at the same city each pay for it separately. Interaction feels slow exactly when the map is being explored.
Precompute a tile pyramid
Split the world into tiles addressed z/x/y — zoom 0 is one tile, zoom z is 4^z — and precompute the contents of each tile once:
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
SRC[("100M points")] --> BUILD["Batch build, per zoom level"]
BUILD --> LOW["z 0-8: heat map values or grid cell counts"]
BUILD --> MID["z 9-13: clusters - '1,240 here'"]
BUILD --> HIGH["z 14+: individual points, a few hundred per tile"]
LOW --> STORE[("Tile store")]
MID --> STORE
HIGH --> STORE
STORE --> CDN["CDN - tiles are immutable, cached at the edge"]
CDN --> CLIENT["Client fetches the 10-30 tiles covering the screen"]- The client always fetches a similar amount of data, whatever the zoom: a couple of dozen tiles, each with a bounded payload. Panning fetches a few new tiles and reuses the rest.
- The content changes with the zoom, because the useful answer does: a heat map when a country is in view, clusters at city scale, individual points once the area is small enough for them to be distinguishable.
- Tiles are immutable and cacheable.
z/x/yis a natural cache key, so the CDN absorbs the traffic and the expensive aggregation happens once per data refresh rather than once per pan.
Filters are the awkward part worth raising unprompted: a tile is precomputed for all points, so a user filtering by category cannot use it directly. Either precompute tiles per common filter, or serve filtered views from a live aggregation at high zoom only, where the point count is small enough to afford.
Building the Tile Pyramid
- A batch job (e.g., Spark, or tools like tippecanoe) assigns each point to its tile at the highest zoom, then rolls up counts to parent tiles zoom by zoom (each parent = the sum of its 4 children). This is cheap once the highest level is done.
- Store tiles as vector tiles (compact binary with points or cells and attributes), so the client can style them and show tooltips.
- Total tiles: only tiles with data are stored. Empty ocean tiles are skipped.
- Serve from object storage through a CDN. Tiles are static files, so they're very cacheable and cheap.
Client Rendering
- Use a WebGL map library (e.g., Mapbox GL / deck.gl) that can draw tens of thousands of shapes smoothly.
- As the user zooms, fetch the new zoom's tiles and fade between levels. Prefetch the neighboring tiles.
- Clicking a pin calls a details API by point ID (the tile only carries IDs and minimal attributes).
Updates and Filters
- Data changes: mark the tiles containing changed points as dirty (at all zoom levels up the chain) and rebuild them incrementally, with cache-busting via tile versions.
- Filters (e.g., "only category = restaurant"): options are:
- Precompute separate pyramids for a few common filters.
- Store per-category counts in each aggregated cell, and let the client combine selected categories.
- For arbitrary filters, generate tiles dynamically from a spatially indexed database (PostGIS with
ST_AsMVT, or ClickHouse with geohash cells), cached per filter.
Wrap-UpWrap-up
Split the world into z/x/y tiles and precompute a tile pyramid: individual points at high zoom, and cluster or heat-map aggregates rolled up zoom by zoom at lower levels, stored as vector tiles and served through a CDN. The WebGL client fetches only visible tiles for the current zoom and loads point details on click. Rebuild dirty tiles incrementally on data changes, and handle filters with per-category counts, extra pyramids or cached dynamic tiles from a spatial database.