System design
Part 6 of 6 · Geospatial IndexingLocation Services — Nearby Search, Dispatch Shards & Hotspots
Indexes are useless without ingest, cell shards, bounded fan-out, ranking, and airport-scale hotspot splits. Nearby is encode plus k-ring plus haversine; assignment needs CAS on the driver. Cells, not one global tree, carry the fleet.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
What actually has to scale
Prefer
Bounded cell fan-out, TTL membership, hotspot splits
Success is a deadline on scatter-gather, a precise filter, and a plan for one melted cell. The fanciest tree is optional.
- Idempotent upsert by driver id; TTL beats delete storms.
- Match is a separate SLA from nearby lookup.
- Read replicas and ops caps for New Year's Eve.
Alternative
Redis GEO for the planet, or ES for 100 kHz GPS
GEO is a great start in one city. Elasticsearch geo is for POIs and documents. A single hot key at an airport is an outage with extra steps.
- Global lock around matching serializes the stadium.
- Cached cell sets go stale while drivers move.
- Hash rings are for placing shards — not this page's lecture.
Reference architecture
Indexes from earlier lessons plug into these hops.
- 1
Ingest
SDK streams location, throttled. Gateway encodes H3/S2/geohash at service resolution. - 2
Membership
cell → {driver → last_seen, attrs} in Redis/memory KV with TTL. - 3
Nearby
Cover/fan-out → mget → haversine/ETA → top-K. Bound k. - 4
Dispatch
Matcher reads candidates; CAS assign; notify. Compensate on conflict. - 5
Zones and tiles
Geofences: R-tree/GiST or S2 cover. Tiles: CDN quadkeys. Analytics: hex bins.
Overview
Indexes are useless without an architecture: ingest GPS, shard by cell, fan-out for nearby, rank for dispatch, survive airport-scale hotspots. This page stitches geohash, H3/S2, quadtree, and R-tree into a ride-hail or delivery shape.
You should be able to:
- Separate write QPS from nearby QPS from polygon QPS.
- Name hotspot mitigations without a 30-minute hash-ring recap.
- Say what must be strongly fenced (assignment) vs eventual (location).
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: GPS write path, nearby read path, assignment
Flow
- 1
Step 1 SDK sends throttled GPS
- nextStep 2 Encode the cell at service resolution
- 2
Step 2 Encode the cell at service resolution
- nextStep 3 Upsert into the shard that owns the cell, with TTL
- 3
Step 3 Upsert into the shard that owns the cell, with TTL
- nextStep 6 Scatter-gather shards with a deadline
- 4
Step 4 Pickup request
- nextStep 5 Cover cells - k-ring or S2 cover
- 5
Step 5 Cover cells - k-ring or S2 cover
- nextStep 6 Scatter-gather shards with a deadline
- 6
Step 6 Scatter-gather shards with a deadline
- nextStep 7 Filter seats, ETA, rating - keep top K
- 7
Step 7 Filter seats, ETA, rating - keep top K
- nextStep 8 Assign with compare-and-set on the driver record
- 8
Step 8 Assign with compare-and-set on the driver record
- CAS fails - driver already takenFailure path - try the next candidate, never double-assign
- 9
Failure path - try the next candidate, never double-assign
The SDK sends throttled GPS. The service encodes a cell and upserts the driver into the shard that owns it, with a TTL. A pickup covers a k-ring or an S2 cover, scatter-gathers those shards under a deadline, filters, and assigns with compare-and-set so two trips cannot take the same driver.
Lesson map
Location Services — Nearby Search, Dispatch Shards & Hotspots
Diagram 1 walks 8 steps from Step 1 SDK sends throttled GPS through Step 8 Assign with compare-and-set on the driver record.
Architecture. Step 1 SDK sends throttled GPS Ready. Step 2 Encode the cell at service resolution Ready. Step 3 Upsert into the shard that owns the cell, with TTL Ready. Step 4 Pickup request Ready. Step 5 Cover cells - k-ring or S2 cover Ready. Step 6 Scatter-gather shards with a deadline Ready. Step 7 Filter seats, ETA, rating - keep top K Ready. Step 8 Assign with compare-and-set on the driver record Ready. Failure path - try the next candidate, never double-assign 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 SDK sends throttled GPS Ready"] B["Step 2 Encode the cell at service resolution Ready"] C["Step 3 Upsert into the shard that owns the cell, with TTL Ready"] R["Step 4 Pickup request Ready"] D["Step 5 Cover cells - k-ring or S2 cover Ready"] E["Step 6 Scatter-gather shards with a deadline Ready"] F["Step 7 Filter seats, ETA, rating - keep top K Ready"] G["Step 8 Assign with compare-and-set on the driver record Ready"] X["Failure path - try the next candidate, never double-assign Ready"] A -->|continues| B B -->|continues| C R -->|continues| D C -->|continues| E D -->|continues| E E -->|continues| F F -->|continues| G G -->|CAS fails - driver already taken| X
Diagram 2 - Failure path: airport hotspot on one cell
Sequence
- 1
Drivers at airport → Shard for one cell
Step 1 3000 drivers upsert into one cell
- 2
Nearby API → Shard for one cell
Step 2 every pickup request reads the same megaset
- 3
Shard for one cell → Shard for one cell
Step 3 CPU and memory hot spot, p99 climbs
- 4
Nearby API → Nearby API
Step 4 deadlines expire and nearby returns partial results
- 5
Drivers at airport
Fix - finer resolution locally, split the cell into sub-shards, batch matching
Three thousand drivers upsert into one airport cell, and every pickup reads that same megaset. The shard's CPU and memory climb, deadlines fire, and nearby returns a partial list. Split the cell into finer local cells or sub-shards, and batch the match.
Diagram 3 - Decision: which store for which path
Decisions
- ?
Step 1 Which path?
- live fleet writesCells in Redis with TTL
- geofences and zonesPostGIS GiST or S2 cover
- map tilesCDN plus quadkeys
- 2
Cells in Redis with TTL
- nextStep 2 One cell too hot?
- Wrong pick - one megaset keySingle Redis key melts
- 3
PostGIS GiST or S2 cover
- Wrong pick for 1 Hz driver updatesIndex churn and slow writes
- 4
CDN plus quadkeys
- ?
Step 2 One cell too hot?
- yesSub-shard or finer resolution
- noConsistent hash from cell to shard
- 6
Sub-shard or finer resolution
- 7
Consistent hash from cell to shard
- 8
Index churn and slow writes
- 9
Single Redis key melts
Live fleet writes belong in cells with a TTL. Geofences belong in PostGIS GiST or an S2 cover. Map tiles belong on a CDN with quadkeys. A hot cell is sub-sharded or refined. A quiet cell hashes to a shard. GiST on 1 Hz driver updates churns the index, and one Redis key for a whole airport melts.
Read-heavy vs write-heavy
| Path | Shape | Store |
|---|---|---|
| Fleet writes | High QPS upserts | Cell KV, TTL, idempotent by driver |
| Nearby reads | Bursty rush hour | Scatter-gather cells; cache carefully (staleness) |
| Zones | Lower rate | GiST/R-tree or precomputed cell covers |
| Map tiles | Immutable | CDN + quadkeys — not the live fleet |
Downsample raw 1 Hz GPS to 0.2–0.5 Hz or on-significant-move. Finer cells ⇒ more membership churn.
Sharding by cell
Map cell_id → shard via consistent hash or static prefix ranges. Drivers pin to the shard of the current cell. On cell change: delete old + insert new (or dual briefly).
Query fan-out may touch many shards. Bound k / covering size. Scatter-gather with a deadline.
The ring, vnodes, and ~1/N movement live in consistent hashing. Here you only need: cell is the key you hash. Do not re-teach Maglev.
Hotspots (airports, stadiums, NYE)
Symptom: one cell owns huge cardinality / QPS.
Mitigations:
- Finer resolution locally
- Split cell into sub-shards
- Rate-limit updates
- Read replicas for nearby
- Pre-position supply via ops
- Do not use a single Redis megaset — partition by sub-cell
- Matching: batch with fairness; do not global-lock the hotspot
Nearby plus dispatch
Write path, then read path — two fences so the chart stays readable.
Flow
- 1
1 GPS update
- next2 Encode cell
- 2
2 Encode cell
- next3 Upsert shard TTL
- 3
3 Upsert shard TTL
Flow
- 1
1 Pickup request
- next2 k-ring or covering
- 2
2 k-ring or covering
- next3 Scatter-gather
- 3
3 Scatter-gather
- next4 Filter seats ETA
- 4
4 Filter seats ETA
- next5 CAS assign
- 5
5 CAS assign
Flow
- 1
1 Detect dense cell
- next2 Sub-shard or finer res
- 2
2 Sub-shard or finer res
- next3 Cap match batch
- 3
3 Cap match batch
Sequence
- 1
1 Driver → 2 Cell store
upsert cell TTL
- 2
3 Nearby → 2 Cell store
mget k-ring
- 3
2 Cell store → 3 Nearby
candidates
- 4
3 Nearby
haversine plus ETA
Assignment (not shown): compare-and-set on the driver record; compensate if two matchers raced.
Sandbox: multi-cell fan-out plus filter (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Same idea (TypeScript)
Didactic shard function. Production uses a consistent-hash ring — see the hashing cluster.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Pitfalls
Friday 5pm, one H3 cell holds 4,000 idle drivers. Nearby k=1 already returns 4k candidates. What do you change first: resolution, sub-shards, match batching, or update rate? Draw the CAS on assign when two matchers pick the same driver.
Interview Q&A
End-to-end nearby latency budget?
Answer
Encode is microseconds. mget cells is milliseconds. Filter is CPU. Matching is a separate SLA. Budget the gather, not the GIS library.
Why TTL membership?
Answer
Crashed apps stop updating. Auto-expire beats explicit delete storms and lease machinery you do not need for presence.
Cross-shard transaction for assign?
Answer
Compare-and-set on the driver record (or a trip lock). Compensate if two matchers conflict. Do not 2PC the whole k-ring.
Redis GEO vs DIY H3?
Answer
GEO is quick and hides neighbor math. H3 when hex analytics and a multi-service ID must align. Both still need sharding.
Elasticsearch geo?
Answer
Search/indexing of POIs and documents. Not the primary path for 100 kHz driver updates.
PostGIS when?
Answer
Geofences, complex predicates, reporting — GiST. Live dispatch is usually KV cells. GiST AM details: SQL indexes (geometry only).
Airport storm?
Answer
Finer cells, more shards, match batching, ops caps, read replicas. Never one Redis set named airport.
Consistency?
Answer
Eventual location is OK. Assignment needs strong fencing on driver id — CAS / version, not last GPS write.
Should nearby cache cell sets?
Answer
Rush-hour cache helps until it lies. Short TTL, or cache the ranked list with a staleness budget you can defend.
Where does consistent hashing apply?
Answer
Placing cell keys on shards and splitting a hot cell onto more owners. Rings and vnodes: CH hub. Stop there.