Design a Ride-Share Dispatch (Uber / Lyft)

The central data structure is a spatial index that supports "find all drivers within R meters of (lat, lon)" in milliseconds.

Geohash
Encode (lat, lon) as a base32 string where each character refines the cell. Prefix-shared strings = nearby cells.

• Pro: simple, sortable, works in any KV store.
• Con: cell shapes are rectangular and distorted near the poles. "Nearby cell" can be far away across hash-prefix boundaries.
• Used by early Uber, many tutorials.

S2 (Google)
Project Earth onto an inscribed cube; subdivide each face into a quad-tree. Each cell = 64-bit S2 cell ID.

• Pro: spherical correctness. Cells nest hierarchically (multi-resolution queries).
• Con: complex math. Cell shapes still aren't quite uniform.
• Used by Google Maps, Pokemon Go, MongoDB geo features.

H3 (Uber)
Hexagonal grid. Each cell is a regular hexagon at the chosen resolution.

• Pro: hexagons have 6 equidistant neighbors (squares have 4 close + 4 diagonal). Better-shaped neighborhoods.
• Pro: open source, well-documented, used in production at Uber.
• Con: more complex than geohash.
• Used by Uber, modern ride-share systems, FB.

Recommendation: H3 for new systems. Geohash for the simplest possible answer. S2 if you're integrating with Google's stack.

Index implementation

• Hot: cell_id → set of driver_ids. Redis Cluster, sharded by cell. Updates on every driver location refresh.
• Match query: compute the set of cells overlapping the search circle (k-ring), union the drivers in those cells, distance-filter, rank.

Sharding strategy
Shard the index by spatial region (city, country). All drivers in a city sit on the same cluster. Cross-shard queries are rare (airport pickups crossing boundaries).

Resolution choice
Match resolution to typical search radius. H3 res-9 hexagon is ~150m across - good for dense urban areas. Lower resolutions (larger cells) for rural areas.

2.5M location updates per second is heavy. Naive "update one row in DB per update" doesn't scale.

Update path

1. Driver app sends update over persistent connection (WebSocket or HTTP/2 stream) every 4-8 seconds.
2. Gateway receives, validates (driver authenticated, location plausible).
3. Forward to spatial-index updater for the driver's region.
4. Updater removes driver from old cell, adds to new cell. Atomic in Redis (Lua script).

Write batching
At 2.5M updates/sec, updating 2.5M Redis keys/sec needs ~50-100 Redis nodes. Batch by cell - if many drivers update at once, batch their cell-membership changes into a single MULTI/EXEC. Cuts ops by 5-10x.

Conflation
If a driver sends multiple updates in flight (network jitter), only the latest matters. Conflate at the gateway: keep the latest in-memory, write at fixed rate (2 Hz). Reduces tail-load on Redis.

Persistence vs ephemeral
The spatial index is rebuildable from current driver state. Don't persist every update. Persist a snapshot every minute for fast recovery. Crash recovery: replay live updates from connected drivers.

Driver going offline
Active flag with TTL. Each location update refreshes the TTL (60 seconds). No update for 60 seconds → driver is removed from the index automatically. No explicit "offline" message required.

Privacy
Driver locations are PII. Encrypted in flight. Aggregated location (heatmaps) for analytics; raw location only retained as long as needed for support / forensics. Don't log raw locations to wide-access systems.

Naive: pick the driver with the shortest ETA. Real systems optimize multiple objectives.

ETA-only matching
Pick driver minimizing ETA-to-pickup. Simple. Works as v1.

• Problem: ignores driver utilization. A nearby driver might be about to drop off; a slightly farther driver might be free now.
• Problem: can starve drivers in low-density areas (always picking the closest creates clustering).

Multi-factor ranking
Score = w1·(-ETA) + w2·driver_acceptance_rate + w3·driver_idle_time + w4·rider_score + w5·surge_optimality.

• Acceptance rate: drivers who routinely decline waste rider time.
• Idle time: prefer drivers waiting longer (fairness).
• Surge optimality: in surge zones, prefer drivers who can complete this trip and reposition for more surge work.

Pool / shared rides
Match multiple riders to the same driver if their routes overlap.

• Constraint: detour for each rider < threshold (15% of trip distance, 5 minutes ETA).
• Constraint: vehicle capacity.
• Optimization: maximize platform revenue / minimize total distance / minimize per-rider ETA increase.
• Algorithm: variant of dynamic ridesharing or insertion heuristics. Computationally hard at scale.

Batching matches
Naive matching is per-request. Better: collect requests in 1-2 second windows, solve a batch optimization over (riders × candidate drivers).

• Allows globally better matches.
• Adds 1-2 seconds latency. Only used for non-time-critical products.

Match acceptance
Driver might decline. Two strategies:

• Sequential: offer to driver 1; if declined, offer to driver 2; etc.
• Parallel: offer to top-K drivers; first accept wins.
• Parallel is faster for the rider but creates "phantom dispatches" for drivers who decline.

Real systems: sequential by default, with parallel for low-acceptance markets.

ETA appears multiple times: pre-request preview, during match selection, during pickup, during trip. Each is a query against a real-time ML system.

Components of ETA

• Path: shortest route under current traffic.
• Travel time: per-edge time estimates from current speed observations.
• Pickup time: driver-to-pickup-location, accounting for parking / approach.
• Wait time: driver acceptance + boarding overhead.

Routing graph
Per-city road network. Nodes = intersections, edges = road segments. Edge weight = expected travel time at time t.

• Precompute: contraction hierarchies for fast shortest-path queries (~ms).
• Live: update edge weights from current traffic observations every minute or so.

Live traffic input
Speed observations from in-trip drivers ("probe vehicles"). At 10M concurrent drivers globally, the platform has the densest real-time traffic data anywhere.

ML refinement
Pure shortest-path × current speeds is a baseline. ML adds:

• Time-of-day effects (rush hour patterns).
• Day-of-week patterns.
• Weather signals.
• Event signals (game ending, concert).
• Pickup-location-specific ETAs (this address always takes 60s extra because of parking).

Continuous re-estimation
During pickup, ETA is recomputed every 30 seconds and pushed to the rider's app. Sets expectations and reduces cancellations.

ETA accuracy is a product KPI
"Driver arriving in 2 minutes" that turns into 8 minutes destroys trust. Internal accuracy targets: median error < 30 seconds, p95 error < 2 minutes. Monitored continuously.

Demand spikes (rain, sports event, surge in requests) outstrip supply. Surge pricing rebalances by raising fares to attract more drivers and discourage marginal demand.

Per-cell supply-demand ratio
Compute over ~5-minute rolling window: (active requests in cell) / (available drivers in cell). Above threshold → apply surge multiplier (1.2x, 1.5x, 2x, etc.).

Geographic granularity
Surge applies per cell (H3 resolution-7 or similar - few-km hexes). Adjacent cells can have different multipliers; smoothing prevents sharp boundaries that game the system.

Driver and rider visibility

• Driver app shows surge zones as a heatmap. Drivers reposition into surge zones. This is the supply-side response.
• Rider sees the surge multiplier before committing. Some riders cancel; some pay.

Optimization horizon
Naive surge is short-term reactive. Modern systems forecast surge 15-30 minutes ahead and incentivize drivers to position preemptively.

Anti-gaming

• Drivers who hover at surge boundaries to game the system are detected and demoted in matching.
• Coordinated driver "log-off" actions (drivers pretend to log off to spike surge) are detected by analyzing log-off timing patterns.

Fairness considerations
Surge in low-income areas is regulated in some jurisdictions. Some platforms cap surge at certain levels for accessibility services. Surge during emergencies (hurricanes) is typically suspended and pre-positioned drivers compensate via base-fare boosts instead.

The economics
Surge is the price discovery mechanism. It's not just revenue extraction - it actively shifts driver supply to where demand is. Platforms that don't surge end up with hour-long waits.

Once a match is made, the trip enters a strongly consistent state machine. This is where the dispatch system intersects payment, fraud, and support.

State machine

• requested → assigned → driver_arrived → in_trip → completed → paid
• (Side states: cancelled_by_rider, cancelled_by_driver, no_show)

Each transition is an atomic write to the trip orchestrator's DB (DynamoDB conditional update or relational DB with row lock). Listeners (notifications, payment, analytics) react to state-change events.

Why strong consistency here
The match assignment must be exclusive (one driver, one trip). Two riders being matched to the same driver simultaneously is a P0 bug.

Idempotency
Drivers and riders retry actions (network flakes). Every action carries a client-generated UUID; the orchestrator dedupes. Critical for payment to avoid double-charging.

Out-of-order events
"Driver arrived" and "driver started trip" can arrive out of order (network reordering). State machine validates allowed transitions and rejects invalid ones.

Failure recovery
Trip orchestrator outage during an active trip is bad. Solutions:

• Active replication across multiple regions for trip state.
• Each driver's app maintains optimistic local state and syncs on reconnect.
• Operations dashboard for support to manually resolve stuck trips.

Lost-driver / lost-rider
GPS loss, dead phone. Detect prolonged silence; ping the other party. Allow rider to manually mark "ride completed" if driver is unreachable. Insurance / safety policies kick in.

Fraud detection
Trip patterns that suggest collusion (driver repeatedly accepts trips from a single rider with no actual movement) are flagged for review. Fraud detection runs offline; doesn't slow the dispatch hot path.