Walkthrough: Designing a Geospatial Matching System

The problem

You’re asked to design a location-matching system — Uber’s rider-driver matching, DoorDash’s dispatch, Yelp’s “restaurants near me.” The interviewer says something like: “Design the service that, given a user’s location, finds the nearby drivers (or restaurants, or couriers) and matches them — in real time, as everyone moves.”

Sounds like a database query with a WHERE distance < 5km. It isn’t. The trap is that proximity is not a value you can index on directly — latitude and longitude are two independent dimensions, and a standard B-Tree indexes one column at a time. A range scan on latitude returns a horizontal band spanning the whole planet; intersecting it with a longitude band is a scatter-gather across millions of rows. The entire question is about how you turn 2D proximity into a 1D key you can index, and how you keep that index fresh when a million drivers move every few seconds.

Below is how I’d walk through this, start to finish.

1. Requirements

First 3–5 minutes. Questions I’d ask to pin down what we’re building:

Functional requirements

• R1. Drivers (suppliers) continuously report their current location.
• R2. A rider (consumer) requests a match from their location.
• R3. The system returns nearby available drivers within a radius, ordered by proximity (or ETA).
• R4. The system matches a rider to one driver and holds that driver until accept/decline.
• R5. “Nearby” queries also power a browse view (show all drivers on the map near me).

Scope

This design covers location ingestion and proximity matching. Explicitly out of scope:

• Routing / ETA computation (a separate system — a road-network graph problem, not a proximity one)
• Pricing / surge (peer system that consumes supply-demand density, doesn’t shape the index)
• Trip lifecycle after match (payments, navigation — a stateful workflow, its own question)
• Map rendering / tiles (client-side concern)

Non-functional requirements

• Scale. How many active drivers per city? How often do they report location? What’s the peak concurrent rider QPS? For a geospatial system, the update rate matters more than the query rate — that’s the reverse of most systems.
• Freshness. How stale can a driver’s location be before a match is wrong? For ride-hailing, a driver 4 seconds stale is fine; 60 seconds stale means the match is a street away.
• Match latency. A rider waiting on “finding your driver” tolerates ~1–2 seconds, not 10.
• Accuracy vs recall. Is a “nearby” result allowed to miss a driver just across a boundary? A browse view tolerates approximation; a match should not systematically miss the closest driver.
• Availability over consistency. A slightly stale or slightly incomplete driver list is acceptable; a matching service that’s down strands riders. AP over CP for the location index.

Say the interviewer confirms: 3M active drivers globally, ~600K in the busiest city at peak, each reporting location every 4 seconds, ~100K rider match requests/sec at peak, freshness tolerance ~5 seconds, match latency budget ~1 second, ride-hailing (single-match) semantics.

2. Capacity estimate

• Location updates (the firehose): 3M drivers ÷ 4 sec ≈ 750K updates/sec globally, ~150K/sec concentrated in the busiest city. This is the number that decides the architecture.
• Match queries: 100K/sec peak. Each query reads a small spatial neighborhood (tens to low-hundreds of drivers), not the whole city.
• Storage (hot state): 3M drivers × ~100 bytes (id, lat, lng, status, timestamp) ≈ 300 MB of current location. This fits in memory — the live index is small; it’s the update churn that’s expensive, not the size.
• Historical location (for analytics/replay) is a separate append-only firehose to cold storage; not on the matching path.

I’d say out loud: “The live index is tiny — 300 MB fits in RAM. The whole problem is that it’s being rewritten 750K times a second. So I’m optimizing for cheap updates and in-memory range queries, not for storage.”

3. High-level architecture

Before committing to an index, I’d sketch the topology. The system has three logical subsystems:

1. Location ingestion — accepts the driver-location firehose, updates the live spatial index.
2. Spatial index — the in-memory structure that answers “who’s near this point?” This is where the design’s character lives.
3. Matching service — takes a rider request, queries the index for candidates, runs the match/hold protocol.

flowchart TD
  Driver[Driver App] --> LB[Location Ingest Gateway]
  Rider[Rider App] --> API[Match API]

  LB --> LocSvc[Location Service]
  LocSvc --> GeoIndex[(Geo Index · in-memory)]

  API --> MatchSvc[Matching Service]
  MatchSvc --> GeoIndex
  MatchSvc --> MatchState[(Match State)]

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class GeoIndex,MatchState store

The spatial index is the part that decides the system’s character.

4. Architecture evolution

A geospatial system evolves through recognizable levels. Naming them early frames why the design looks the way it does:

Each level preserves the previous as a fallback — the in-memory grid can rebuild from the durable location log; a quad-tree degrades to a fixed grid if rebalancing lags.

The design in this walkthrough is Level 3, with Level 4 named: an in-memory Geohash grid, sharded by geographic region, with a discussion of when to switch to an adaptive structure.

I’d say out loud: “I’m designing for Level 3 — an in-memory Geohash grid — and I’ll name exactly the density problem that pushes you to a quad-tree at Level 4. Landing at Level 3 with awareness of the density trade-off is the signal here.”

Target architecture (Level 3)

This is the complete system we’re designing. Every section that follows explains one part of this diagram:

flowchart TD
  Driver[Driver App] -->|location every 4s| Ingest[Location Ingest Gateway]
  Ingest --> Kafka[(Location Log · Kafka)]
  Kafka --> LocSvc[Location Service]
  LocSvc --> GeoIndex[(Geo Index · Redis GEO / grid)]
  Kafka --> ColdStore[(Historical Locations)]

  Rider[Rider App] --> API[Match API]
  API --> MatchSvc[Matching Service]
  MatchSvc --> GeoIndex
  MatchSvc --> Availability[(Driver Availability)]
  MatchSvc --> MatchState[(Match State · holds)]

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class Kafka,GeoIndex,ColdStore,Availability,MatchState store

5. Core design choice: the spatial index

This is the question. Three options:

(a) Geohash. Interleave the bits of latitude and longitude and Base32-encode them into a string. Nearby points share a common prefix, so a proximity query becomes a prefix match — a 1D range scan on a plain string index. Cell size is fixed by prefix length (e.g., 6 chars ≈ 1.2km × 0.6km).

(b) Quad-tree. Recursively subdivide space into four quadrants, splitting a cell only when it holds more than K points. Dense areas (downtown) get deep, fine subdivisions; sparse areas (rural) stay coarse. A query descends the tree to the relevant leaves.

(c) S2 / H3. Google’s S2 projects the sphere onto a cube and uses a Hilbert curve for 1D ordering; Uber’s H3 uses hexagonal cells. Both fix the equal-area and boundary problems that plague naive Geohash.

Why Geohash wins for the interview (with H3 named)

The justification is topic-specific: Geohash turns the hard part — 2D proximity — into the easy part — a 1D prefix scan that any string index or Redis sorted set supports natively. For an interview, it’s the scheme you can explain and defend in ninety seconds, and it’s what Redis GEO commands implement under the hood. I’d commit to Geohash for the core design and name H3 as the production upgrade specifically because hexagons have uniform neighbor distance (every neighbor is equidistant, unlike a square grid’s diagonal-vs-orthogonal problem) — which matters when “nearest” must be precise.

Tradeoff matrix

The Geohash cost: fixed cell size and the boundary problem (below). The payoff: it’s simple, updates are O(1), and it maps directly onto infrastructure you already have (Redis, any sorted index). For a system whose real bottleneck is update throughput, the O(1) update wins — and the boundary problem has a bounded, well-known fix.

The boundary problem (and its fix)

The fix: query the rider’s cell plus its 8 neighbors (a 3×3 grid of cells). Geohash libraries expose a neighbors() function that computes the 8 adjacent hashes. You scan all 9 cells, gather candidates, then compute exact haversine distance to filter and sort. The cell is a coarse recall filter; the precise distance is the ranking pass. Choose the prefix length so one cell is comfortably larger than the typical search radius, so 3×3 always covers it.

Architecture decisions

Core data structures

Before the paths, the structures that make this work:

Full schemas are in §9. What matters now: the index and locations are in-memory (Redis), sharded by region so every proximity query is single-shard.

6. Location ingestion path [R1]

Extending the target architecture with the write-path components:

flowchart TD
  Driver[Driver App] -->|lat,lng every 4s| Ingest[Location Ingest Gateway]
  Ingest --> Kafka[(Location Log · Kafka)]
  Kafka --> LocSvc[Location Service]
  LocSvc --> GeoIndex[(Geo Index · Redis)]
  Kafka --> ColdStore[(Historical Locations)]

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class Kafka,GeoIndex,ColdStore store

Step by step:

1. Driver app sends (driver_id, lat, lng, timestamp) every ~4 seconds to the ingest gateway. Connections are pooled/persistent to avoid per-update handshake cost.
2. Gateway appends the raw update to a Kafka log, partitioned by region_id (so all of a city’s updates land on ordered partitions), and returns immediately. The driver never waits on the index write.
3. Location service consumes the log and updates the live index:
   • Compute the new geohash from (lat, lng).
   • Look up the driver’s previous geohash from driver_location.
   • If the cell changed, remove driver_id from the old cell’s set and add it to the new one. If unchanged, only refresh the timestamp — no index mutation.
4. Kafka also fans the same log to cold storage for analytics/replay — a separate consumer, no impact on the hot path.

7. Matching path [R2, R3, R4]

flowchart TD
  Rider[Rider App] --> API[Match API]
  API --> MatchSvc[Matching Service]
  MatchSvc -->|9-cell scan| GeoIndex[(Geo Index · Redis)]
  MatchSvc -->|filter available| Availability[(Driver Availability)]
  MatchSvc -->|hold winner| MatchState[(Match State)]

  classDef store fill:#eef2f1,stroke:#2c5f5d,stroke-width:2px,color:#1f2937;
  class GeoIndex,Availability,MatchState store

Rider match, step by step:

1. Rider requests a match with their (lat, lng). Matching service computes the rider’s geohash.
2. Recall: compute the 9 cells (own + 8 neighbors) and scan their driver sets from the geo index. This yields the candidate set — tens to low-hundreds of drivers.
3. Filter: drop drivers whose status isn’t available (join against availability) and whose location timestamp is older than the freshness SLO (5s) — a stale driver may have moved.
4. Rank: compute exact haversine distance (or call the ETA service if the budget allows) for each candidate; sort ascending.
5. Expanding-radius fallback: if the 9-cell scan yields too few available drivers (sparse area), widen to a coarser prefix (a larger cell) and re-scan. Cap the expansion so a rider in the countryside doesn’t scan the whole state.
6. Hold: attempt an atomic hold on the closest driver (see the protocol below). If the driver declines or the hold expires, offer the next-closest. This is the dispatch window.
7. Return the matched driver to the rider.

The match/hold protocol [R4]

The correctness core: one driver must not be offered to two riders simultaneously. The hold is a short-lived exclusive lock.

The mechanism, concretely: when the matching service picks the closest driver, it does an atomic conditional write to match_state — SET driver_id → (rider_id, expires_at) IF NOT EXISTS, with a TTL of, say, 15 seconds (the accept window). If the write succeeds, this rider owns the offer; the service pushes the request to that driver. If the write fails (another rider grabbed the driver microseconds earlier), the service moves to the next-closest candidate. On driver accept, the hold converts to a confirmed match; on decline or TTL expiry, the hold auto-releases and the driver returns to the available pool. The state we store per hold is just { rider_id, expires_at } keyed by driver_id — cheap, self-expiring, and the TTL guarantees no driver is stranded if a matching service instance crashes mid-hold.

8. API design [R1, R2, R3]

POST /api/drivers/location                    [R1 — report location]
  body:    { driver_id, lat, lng, timestamp }
  returns: { ok }          // fire-and-forget; 202 Accepted

GET /api/drivers/nearby?lat=&lng=&radius=      [R5 — browse view]
  returns: { drivers: [{ driver_id, lat, lng, distance_m }], ... }

POST /api/match                                [R2, R3, R4 — request a match]
  body:    { rider_id, lat, lng }
  returns: { match_id, driver: { driver_id, eta_s, distance_m } }

Non-obvious decision: the location endpoint returns 202 Accepted, not 200 OK. The write is asynchronous — it lands in Kafka, not the index — so the API must not imply the index reflects it yet. Pretending the write is synchronous invites a client to immediately query and expect its own move reflected. Worth saying out loud.

The POST /api/match endpoint abstracts the entire recall → rank → hold pipeline. The client doesn’t know whether the index is Geohash or H3, or how many cells were scanned — so the backend can evolve from Level 3 to Level 4 without an API change.

9. Data model and storage

Requirements → components

Access frequency

Storage technology choices

Access pattern matrix

Schemas

Geo index [R3, R5]

geo_index (Redis, per region shard):
  key:      geohash_prefix          # e.g. 6-char cell "9q8yyk"
  value:    SET of driver_id        # members currently in this cell
  # Redis GEO alternative: GEOADD region_key lng lat driver_id
  #   (Redis stores the geohash internally as a sorted-set score)

The prefix length is the tuning knob: shorter prefix = larger cell = more candidates per scan but fewer cells to touch. Pick it so one cell exceeds the typical search radius, keeping the 3×3 scan sufficient.

Driver location [R1]

driver_location (Redis hash):
  key:      driver_id
  fields:   lat, lng, geohash, updated_at

Read on every update to decide move vs refresh. Keeping the current geohash here avoids re-deriving the old cell.

Match state [R4]

match_state (Redis):
  key:      driver_id
  value:    { rider_id, expires_at }
  op:       SET driver_id ... NX EX 15     # atomic, 15s TTL

The TTL is load-bearing: it guarantees a driver is never held forever if the matching service instance that placed the hold crashes before resolving it.

Driver availability [R2]

driver_availability (Redis):
  key:      driver_id
  value:    status  (available | on_trip | offline)

Filters the recall set to matchable drivers. Kept separate from location so a status flip doesn’t churn the geo index.

10. Failure modes

Six scenarios, grouped by what they threaten:

Freshness failures

Location consumers fall behind (Kafka lag)

Threatens: freshness.

The index reflects positions from N seconds ago. Matches point riders at where drivers were. Kafka absorbs the backlog with no data loss. Mitigation: scale consumers per region; monitor consumer lag as the primary freshness metric and drop candidates whose updated_at exceeds the freshness SLO so a stale driver is never matched. The feed is stale, not wrong.

A driver goes dark (app crash, tunnel, dead battery)

Threatens: freshness / correctness.

The driver stops reporting but stays in the index at their last cell. Mitigation: every index entry carries updated_at; the recall filter drops entries older than the SLO, and a sweeper evicts long-silent drivers. A driver in a tunnel reappears and re-adds themselves on the next heartbeat.

Latency failures

Hot region (rush hour downtown)

Threatens: latency.

One region’s shard takes disproportionate update and query load; dense cells return huge candidate sets. Mitigations, in order: shard hot regions more finely (a city subdivides into district shards); cap the candidate set and rank only the closest K; and this is the concrete moment to adopt an adaptive index (H3/quad-tree) whose cells split under density.

Redis geo shard loss

Threatens: latency (briefly), then recovered.

A shard dies; its region’s live index is gone. Mitigation: the index is a materialized view of the Kafka log — replay the last few seconds of that region’s partition to rebuild current positions. During rebuild, matches in that region degrade to a wider-radius scan against a neighboring shard or queue briefly. Nothing is permanently lost because the log is the source of truth.

Correctness failures

Double-match under concurrency

Threatens: correctness.

Two riders target the same idle driver simultaneously. The SET NX hold makes this safe: exactly one write wins, the loser falls through to the next candidate. Without the atomic hold, both would dispatch. This is the failure the hold protocol exists to prevent.

Boundary miss

Threatens: correctness (recall).

A closer driver sits just across a cell edge and is silently excluded. The 9-cell (own + neighbors) scan is the fix; a single-cell scan is the bug. Under the expanding-radius fallback, always expand symmetrically so the neighbor cells stay covered.

11. What I’d skip, and say I’m skipping

Time check — five minutes left. Things I’d explicitly defer:

• Road-network ETA. I’ve been ranking by straight-line haversine distance. Real dispatch ranks by ETA over the road graph — that’s a routing system (Dijkstra/contraction hierarchies over a map graph), a whole separate question. I’d say “assume an ETA service” and move on.
• Surge pricing. It consumes the supply-demand density the index already exposes, but it doesn’t shape the index. One sentence, not a section.
• Trip lifecycle after match. Navigation, payment, ratings — a stateful workflow (a saga), its own design.
• Batched dispatch windows. Advanced dispatch batches requests over a short window and solves a global assignment (minimize total wait) rather than greedy nearest-first. I’d name it as the optimization beyond greedy matching, not build it.
• Multi-region driver roaming across shard boundaries (a driver near a city edge). Handle with overlapping shard boundaries; name it, don’t detail it.

Saying “I’d skip this, and here’s why” shows I know the full surface and am scoping deliberately.

Interview flow summary

Architecture at a glance

INGESTION PATH                      MATCHING PATH

Driver location (4s)                Rider match request
 ↓                                   ↓
Ingest Gateway (202)                Matching Service
 ↓                                   ↓
Kafka (region-partitioned)          Recall: scan 9 geohash cells
 ↓                                   ↓
Location Service                    Filter: available + fresh
 ↓                                   ↓
Move-or-refresh in Geo Index        Rank: exact haversine distance
                                     ↓
                                    Hold: SET NX + TTL → dispatch

The walkthrough order for your whiteboard

1. Requirements & scope    — find the update firehose, not just rider QPS
2. Capacity estimate       — 750K updates/sec; index fits in RAM
3. Architecture evolution  — naive SQL → geohash → in-memory grid → adaptive
4. Spatial index choice    — geohash; reduce 2D to 1D prefix; H3 later
5. Boundary problem        — 9-cell scan + exact-distance rank
6. Ingestion path          — Kafka log → move-or-refresh index
7. Matching path           — recall → filter → rank → hold protocol
8. API                     — 202 on location; hide cell scheme
9. Data model              — in-memory index, region-sharded schemas
10. Failure modes          — freshness / latency / correctness

If the interviewer pushes deeper:

12. Wrap-up

One crisp sentence before the interviewer’s next question:

This design reduces 2D proximity to a 1D geohash prefix so the index is a simple in-memory range scan, absorbs the location firehose through a replayable log that keeps updates O(1), covers the geohash boundary problem with a 9-cell recall plus exact-distance ranking, and guarantees single-match correctness with an atomic TTL hold — while naming density skew as the trigger to graduate from a fixed grid to an adaptive H3 index.

What separates levels on this question

• SDE II reaches for a managed geospatial store — Redis GEO (GEOADD + GEOSEARCH BYRADIUS) — which is a correct, sufficient answer at small scale and the right place to start. The gap: treating it as the final answer, querying a single cell if hand-rolling (the boundary bug), and matching without an exclusive hold.
• SDE III names the boundary problem and fixes it with the 9-cell scan + exact haversine rank, treats location ingestion as a firehose fronted by a log (O(1) updates, move-or-refresh), and makes single-match correct with a TTL hold.
• Staff/Principal identifies the update rate (not query rate) as the real load, names density skew as the concrete trigger to move from a fixed grid to H3/quad-tree, treats the in-memory index as a materialized view rebuildable from the log, and separates recall (cheap/approximate) from precision (exact/ranked) as an explicit design seam.

The difference isn’t knowing what a geohash is. It’s naming the asymmetry — that the write firehose dwarfs the read load, that proximity must become a 1D key, and that cell boundaries and density skew are the two failure modes the whole design has to answer for.

Further reading

• Designing Data-Intensive Applications — Kleppmann. Chapter 3’s discussion of multi-dimensional indexes (R-trees, and why one-dimensional indexes fail for geospatial) is the primary source behind this question’s core tension.
• System Design Interview Vol. 2 — Alex Xu. The “Proximity Service” chapter is the textbook walkthrough for geohash vs quad-tree.
• Redis Geospatial — official docs for GEOADD / GEOSEARCH; shows how the sorted-set-of-geohashes index works in practice.
• H3: Uber’s Hexagonal Hierarchical Spatial Index — the operator’s own explanation of why hexagons beat squares for dispatch, and the density-adaptation this walkthrough defers to Level 4.
• S2 Geometry — Google’s sphere-to-cube + Hilbert-curve library; the primary source on equal-area cells and 1D ordering of 2D space.
• Geohash — the encoding itself: bit-interleaving, Base32, and the prefix-similarity property the whole design rests on.