System design
Part 5 of 6 · Geospatial IndexingS2 & H3 — Hierarchical Hex/Cell IDs (Uber/Lyft-Style Designs)
S2 maps the sphere to Hilbert-ish cell IDs; H3 is a hex hierarchy with k-rings. Ride-hail and delivery key membership, shards, and heatmaps by those IDs. Pick hex for uniform rings, S2 for spherical coverings — this is public architecture, not one private paper.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Hex rings vs sphere coverings
Prefer
H3 for k-rings and bins; S2 for shape coverings
Demand/supply heatmaps and dispatch catchments like equal-ish neighbor hops. Polygons, caps, and global map tiles like mixed-level S2 coverings. Many products run both.
- Hex: one distance to six neighbors; squares have diagonal stretch.
- S2 compact() mixes levels to cover a region with fewer cells.
- Geohash still wins on simplicity and Redis GEO.
Alternative
Geohash only, or claiming a secret company algorithm
Geohash works. Interviews want you to know why hex/sphere exist. Public Uber H3 docs and S2 library docs are enough — do not pretend you reverse-engineered matching.
- Pentagons break 'always 6 neighbors.'
- Resolution cutovers need dual-read.
- R-trees still own arbitrary SQL polygons under write-light load.
Uber/Lyft-style pattern (generic)
Public H3/S2 docs plus eng blogs — not a private paper.
- 1
Pick resolution
From median trip length or search radius. Dispatch cell may be finer than surge bins. - 2
GPS → cell upsert
cell → driver set in Redis with TTL. Overwrite on move. - 3
Request cover
H3 gridDisk(k) or S2 RegionCoverer. Bound k / max cells. - 4
Union, filter, rank
Haversine plus ETA. Metrics count per cell for positioning. - 5
Hot cells
Raise resolution or split the shard. Depth: location services.
Overview
Modern ride-hail and delivery systems often key state by hierarchical spherical cells: Google S2 (Hilbert on a cube-projected sphere) and Uber H3 (hexagon hierarchy). Interviews ask why hex vs square, how k-rings replace geohash 8-neighbors, and how cell IDs become shard keys and metric bins.
This is general architecture from public H3 docs, S2 library docs, and public eng blogs.
You should be able to:
- Give one-sentence S2 and H3.
- Map radius → k or covering.
- Refuse to invent a proprietary matcher — cells + fan-out + ETA is the public design.
Diagrams - step by step
Three small diagrams. Step numbers in the labels give the animation order. The lesson map under Diagram 1 plays those steps.
Diagram 1 - Happy path: hierarchical cells for nearby drivers
Decisions
- 1
Step 1 Pick resolution from the search radius
- nextStep 2 GPS update - latLngToCell
- 2
Step 2 GPS update - latLngToCell
- nextStep 3 Upsert driver into the cell set with a TTL
- 3
Step 3 Upsert driver into the cell set with a TTL
- nextStep 4 Rider request - compute the center cell
- 4
Step 4 Rider request - compute the center cell
- nextStep 5 H3 or S2?
- ?
Step 5 H3 or S2?
- H3Step 6a gridDisk with k rings
- S2Step 6b RegionCoverer with mixed-level cells
- 6
Step 6a gridDisk with k rings
- nextStep 7 mget cells and union candidates
- assume 6 neighbors everywhereFailure path - pentagon cells break ring math
- 7
Step 6b RegionCoverer with mixed-level cells
- nextStep 7 mget cells and union candidates
- 8
Step 7 mget cells and union candidates
- nextStep 8 Rank by ETA
- 9
Step 8 Rank by ETA
- 10
Failure path - pentagon cells break ring math
Pick a resolution from the search radius. GPS writes call latLngToCell and upsert the driver into that cell with a TTL. A rider request covers either an H3 gridDisk or an S2 RegionCoverer, unions the members, and ranks by ETA.
Lesson map
S2 & H3 — Hierarchical Hex/Cell IDs (Uber/Lyft-Style Designs)
Diagram 1 walks 9 steps from Step 1 Pick resolution from the search radius through Step 8 Rank by ETA.
Architecture. Step 1 Pick resolution from the search radius Ready. Step 2 GPS update - latLngToCell Ready. Step 3 Upsert driver into the cell set with a TTL Ready. Step 4 Rider request - compute the center cell Ready. Step 5 H3 or S2? Ready. Step 6a gridDisk with k rings Ready. Step 6b RegionCoverer with mixed-level cells Ready. Step 7 mget cells and union candidates Ready. Step 8 Rank by ETA Ready. Failure path - pentagon cells break ring math Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB A["Step 1 Pick resolution from the search radius Ready"] B["Step 2 GPS update - latLngToCell Ready"] C["Step 3 Upsert driver into the cell set with a TTL Ready"] D["Step 4 Rider request - compute the center cell Ready"] E["Step 5 H3 or S2? Ready"] F["Step 6a gridDisk with k rings Ready"] G["Step 6b RegionCoverer with mixed-level cells Ready"] H["Step 7 mget cells and union candidates Ready"] I["Step 8 Rank by ETA Ready"] X["Failure path - pentagon cells break ring math Ready"] A -->|continues| B B -->|continues| C C -->|continues| D D -->|continues| E E -->|H3| F E -->|S2| G F -->|continues| H G -->|continues| H H -->|continues| I F -->|assume 6 neighbors everywhere| X
Diagram 2 - Failure path: resolution change without dual-write
Sequence
- 1
Writers → Cell store
Step 1 writes switch to resolution 9 cells
- 2
Readers → Cell store
Step 2 readers still compute resolution 8 cells
- 3
Cell store → Readers
Step 3 lookups hit empty resolution 8 sets
- 4
Writers
Step 4 nearby search returns no drivers during the cutover
- 5
Writers
Fix - dual-write both resolutions or read-repair with parent and child APIs, then flip readers
Writers move to resolution 9 while readers still query resolution 8, so every lookup hits an empty set. Dual-write both resolutions, or read-repair through the parent and child APIs, then flip the readers.
Diagram 3 - Decision: H3 vs S2 vs geohash vs R-tree
Decisions
- ?
Step 1 Main need?
- demand bins and ring expansionH3 hex cells
- cover polygons on the sphereS2 cells
- simple string keysGeohash
- complex polygon predicates in SQLR-tree via GiST
- 2
H3 hex cells
- nextStep 2 Hot cell like an airport?
- 3
S2 cells
- nextStep 2 Hot cell like an airport?
- 4
Geohash
- Wrong pick for ring distanceDiagonal neighbors farther than edge neighbors
- 5
R-tree via GiST
- Wrong pick as a fleet shard keyNode splits under write churn
- ?
Step 2 Hot cell like an airport?
- yesFiner resolution or split the shard
- 7
Finer resolution or split the shard
- 8
Diagonal neighbors farther than edge neighbors
- 9
Node splits under write churn
Demand bins and ring expansion want H3. Covering polygons on the sphere wants S2. A simple string key can stay a geohash. Complex SQL predicates want an R-tree via GiST. A hot airport cell gets a finer resolution or its own shard. Geohash rings are uneven, and an R-tree splits under fleet write churn.
S2 in one page
- Project sphere → 6 cube faces → quadtree per face → cell id along a Hilbert-ish curve.
- Cell IDs are 64-bit; parent/child by bit prefix; good 1D locality along the curve.
- Coverings: approximate a polygon or radius as a compact set of mixed-level cells.
- Strength: spherical correctness, region cover, indexing shapes at global scale.
- Weakness: heavier API than geohash; cells are square-ish on a face, not hex.
Lyft has described S2 cells for chunking map data on device — same ID family, different product surface.
H3 in one page
- Icosahedron → hex grid hierarchy. Twelve pentagon artifacts at vertices — know they exist.
- Resolution 0..15;
latLngToCell/cellToLatLng/gridDisk(k-ring). - Hex neighbors ≈ equidistant — cleaner ring distance for demand/supply heatmaps.
- Strength: analytics bins, dispatch catchment, uniform-ish neighbor hops.
- Weakness: pentagons; area not perfectly equal across the globe; library dependency.
Uber's public H3 writeup is explicit: hexagons for one neighbor distance, hierarchy for rollup.
Why hex vs quad vs Hilbert
| Shape / curve | Neighbor story | Typical job |
|---|---|---|
| Square / geohash | Diagonal farther than edge — anisotropic rings | Simple KV keys, Redis GEO |
| Quadtree | Adaptive, not a stable global id without a path | Tiles, in-process skew |
| Hilbert / S2 | Excellent 1D locality for packing and coverings | Sphere shapes, map chunks |
| Hex / H3 | 6-neighborhood symmetry for expand-by-k | Heatmaps, dispatch rings |
vs geohash and R-tree
- Geohash: simpler strings; worse sphere/hex properties. Still the right default for many KV designs. Depth: geohash.
- R-tree: better arbitrary polygons in SQL; worse as a fleet shard key under write churn. Depth: R-trees.
- S2/H3: first-class hierarchical IDs for storage and analytics.
Cell → shard mapping: consistent hashing for cell keys / hotspots only.
Cell fan-out for radius
H3 and S2 are two covers, not two side-by-side subgraphs. One decision, then fetch.
Decisions
- 1
1 latlng plus radius
- next2 Pick resolution
- 2
2 Pick resolution
- next3 Hex or sphere?
- ?
3 Hex or sphere?
- hex rings4 H3 gridDisk
- sphere cover4 S2 covering
- 4
4 H3 gridDisk
- next5 mget cell sets
- 5
4 S2 covering
- next5 mget cell sets
- 6
5 mget cell sets
- next6 Filter plus rank
- 7
6 Filter plus rank
Bound k and S2 maxCells. Scatter-gather without a deadline is how nearby p99 dies. Pipeline: location services.
Sandbox: k estimate and haversine (Python)
No native H3 in the sandbox. gridDisk is a placeholder list; production calls the library.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Same idea (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Pitfalls
Median hex edge is 120 m. What k do you pass to gridDisk? If the rider is next to a pentagon, how many neighbors might you get? How do you still bound the mget?
Interview Q&A
Why not geohash only?
Answer
It works. H3/S2 fix neighbor uniformity and sphere cover. Geohash remains fine for many KV designs and Redis GEO.
Pentagons in H3?
Answer
Twelve, at icosahedron vertices. Do not assume every cell has six neighbors. Handle in edge cases and tests.
How do you change resolution?
Answer
Parent/child APIs. Dual-write or read-repair during cutover. Old membership keys linger until TTL.
S2 covering vs H3 disk?
Answer
Covering mixes levels to approximate a shape with fewer cells. Disk is equal-resolution hex rings. Different APIs, same fetch-union-filter.
Surge pricing bins?
Answer
H3 cells as aggregation keys are a common public pattern. Dispatch resolution can differ from pricing resolution.
Lyft vs Uber?
Answer
Both use hierarchical geospatial ideas publicly (H3 blogs, S2 map chunks). Do not claim one proprietary algorithm. Discuss cells, fan-out, and ETA.
Hilbert benefit?
Answer
Nearby cells sit close in 1D id space — better packing, scans, and bulk R-tree cousins.
Write rate?
Answer
Cell upsert with TTL beats R-tree node splits for millions of movers.
How is this a shard key?
Answer
Hash or range the cell id onto a shard. Hot airports split — consistent hashing for that mapping only.
Can S2 replace PostGIS?
Answer
Coverings help point-in-polygon at scale. Complex predicates, joins, and GIS editing still like R-tree / GiST.