36. Ride-Hailing & Proximity Search (Uber)

Business context. A marketplace. The north-star metrics are completed trips and ETA / match rate. Latency of matching and accuracy of driver locations directly affect conversion: riders cancel if the ETA is bad.

Requirements. Drivers send their location every ~4 s; riders request a ride → match a nearby available driver; track the trip live; pricing (surge); payments at the end. Scale: 5M active drivers at peak sending updates every 4 s → ~1.25M location writes/s; ~50k ride requests/min at peak.

Design.

Driver app ─▶ Location ingest (WebSocket/UDP-ish) ─▶ in-memory geo index (sharded by city/region → H3 cell)
                                              └──▶ Kafka (location stream) → trip tracking, ETA models, analytics
Rider request ─▶ Dispatch service (per city/region shard):
     1. find candidate drivers: H3 k-ring around pickup, filter available, vehicle type
     2. ETA for each candidate via routing engine (road graph, traffic) — not straight-line distance
     3. offer to best driver (with timeout), else next; lock the driver (one active offer per driver)
Trip service (state machine: requested → matched → arriving → in_trip → completed) ─▶ durable store
Pricing (supply/demand per H3 cell, near real time) · Payments (§39)

Deep dives.

Location index: don't write 1.25M updates/s to a database. Keep the current location in memory (sharded by geography, each shard replicated), and persist only the stream (Kafka) for history. H3 hexagons give uniform neighbor distances for k-ring searches and surge pricing.
Geographic sharding: Manhattan at rush hour is a hot shard. Shard by cell, with dynamic splitting for dense areas. Cities are natural isolation units (city-level cells).
Matching consistency: two riders must not get the same driver. Make the driver's state transition available → offered atomic in its owning shard (single writer), with the offer TTL as a lease.
Batch matching: instead of greedily assigning each request, match in short windows (~2 s) to optimize globally (minimize total ETA). Better marketplace efficiency, slightly higher latency. This is a business trade-off; say so.
Phone networks are unreliable: design for out-of-order and duplicated location updates (keep the latest timestamp per driver), and for reconnecting apps resuming trip state from the server.

Strategic lens. The trip state machine and payments need strong consistency and durability. Location is high-volume ephemeral data where staleness of seconds is fine. Splitting these two consistency classes is the key architectural insight. Regional isolation (city cells) contains outages and fits local regulation.

Follow-ups: ETA computation (contraction hierarchies, ML corrections); surge pricing pipeline (streaming aggregation per cell); pool/shared rides (a much harder matching problem); fraud (GPS spoofing).

🏗️ Flow: from ride request to matched driver.

 Rider ─request(pickup, product)─▶ API ─▶ Dispatch (city shard: e.g. SF)
   1. supply = geo_index.k_ring(h3(pickup, res=8), k=2) filter status=AVAILABLE, product
   2. ETAs = routing_engine.batch_eta(candidates → pickup)   (road graph + live traffic + ML correction)
   3. batch window (e.g. 2 s): solve assignment across all open requests in the area
   4. offer to driver D (state AVAILABLE → OFFERED, lease 15 s) ─push (RAMEN)─▶ Driver app
   5a. accept ─▶ trip state MATCHED (durable, strongly consistent) ─▶ notify rider
   5b. timeout/decline ─▶ D back to AVAILABLE; next candidate
 Location stream: driver app ─every 4 s─▶ ingest ─▶ geo_index (memory) + Kafka (history, ETA training)

🌍 How it's built in production.

Uber H3 (2018) for spatial indexing and marketplace analytics: surge pricing is computed per hexagon.
Uber Ringpop: an earlier open-source library for application-layer sharding (consistent hashing plus SWIM gossip membership) that let dispatch services own geographic keys in memory.
Uber DISCO (dispatch optimization): supply and demand matching moved from greedy nearest-driver to batched global matching to improve total ETAs and marketplace efficiency.
Uber Cadence/Temporal for long-running trip and payment workflows; Schemaless/Docstore (on MySQL) for durable trip data.

⚠️ Corner cases.

GPS noise: urban canyons and tunnels cause location jumps. Use map matching (snap to the road graph), Kalman filtering, and reject impossible speeds.
Accept after expiry: the driver taps accept at 15.2 s and the offer already moved to another driver. The trip assignment must be a conditional write (offer still valid for this driver), and the late driver gets "offer expired".
Rider cancels during an offer: release the driver atomically. Race between cancel and accept: the first committed state transition wins, and the other gets a clear error.
Shard boundaries: a pickup near the edge of a city or shard needs drivers from the neighboring shard. Query overlapping regions, or use cell-based routing that understands neighbors.
Airports and geofences: queued pickup zones with FIFO driver lots. Pure proximity doesn't apply.
App killed mid-trip: the server is the source of truth for trip state. The app resumes from the server, and fares are computed server-side from the persisted location trace.