Design a Real-Time Ride Matching System

Framing statement:

“Before I dive in, let me frame how I’d approach this. Uber’s ride matching system is the core of a two-sided marketplace that spans multiple teams — a geospatial platform team, a dispatch optimization team, a marketplace/pricing team, a supply management team, and a real-time data infrastructure team. I’d like to focus on the most architecturally interesting challenge: the real-time dispatch engine — specifically, how we match riders with optimal drivers in under 2 seconds considering proximity, ETA, fairness, and supply-demand balance across 10K+ cities. I’ll propose a phased approach.”

Phased delivery:

Team ownership:

Key ambiguity I’d challenge:

“When we say ’match in under 2 seconds,’ I want to clarify: is that from the moment the rider taps ’Request’ to when a driver receives the offer, or until the driver accepts? The architecture changes significantly — if we include driver acceptance (15-second window), we have cascading fallback logic. I’ll design for sub-2s to first driver offer, with a total match budget of ~30s including retries.”

Functional Requirements (Phase 1)

• ·FR1: Rider requests a ride and is matched with an optimal nearby driver in real-time
• ·FR2: System tracks driver locations (GPS updates every 4 seconds) and maintains a live geospatial index
• ·FR3: Matching considers ETA, driver rating, fairness (wait-time equity), and supply health
• ·FR4: Driver receives ride offer with 15-second accept window; on decline, system cascades to next-best driver
• ·FR5: System supports multiple ride types (UberX, XL, Black, Comfort) with vehicle-type filtering
• ·FR6: Rider sees real-time ETA updates and driver position after match confirmation

Non-Functional Requirements

Organizational Context

• ·Existing system: This is a re-architecture of the DISCO (Dispatch Optimization) platform, not greenfield — must coexist with legacy dispatch during migration
• ·Multi-product: Matching engine must eventually serve Rides, Eats, and Freight (unified Fulfillment Platform), so abstractions should not be rides-specific
• ·Regulatory: Data residency requirements per country (EU GDPR, China data localization), driver labor laws vary by jurisdiction
• ·Timeline: Phase 1 in 3 months with the DISCO team (12-15 engineers) plus support from Geospatial and Infra teams

Out of Scope (Explicitly)

• ·Fare calculation and payment processing (Marketplace/Pricing team)
• ·Driver onboarding and identity verification
• ·Navigation/routing engine (separate Maps team)
• ·Rider/driver chat and in-trip experience
• ·Uber Eats-specific matching (restaurant prep time adds different constraints)

Scale Numbers

Storage Estimation

Cost Estimation

Architectural implication: GPS ingestion bandwidth and Kafka infrastructure dominate costs. We need efficient binary protocols for location updates (not JSON), aggressive batching on driver-side, and tiered storage (hot location data in Redis, warm in Cassandra, cold in HDFS). The matching compute itself is surprisingly cheap relative to data ingestion — the bottleneck is I/O, not CPU.

External API (Client-Facing)

Inter-Service Contracts

API Governance

• ·Versioning: URI versioning for external (/v1/), semantic versioning for internal Protobuf schemas
• ·Schema registry: Protobuf for all inter-service and Kafka event schemas, enforced via CI/CD schema compatibility checks
• ·Rate limiting: Per-rider: 5 ride requests/min, Per-driver: 60 location updates/min (batched), Per-city: adaptive based on supply capacity
• ·Idempotency: All ride requests carry client-generated idempotency key to prevent duplicate dispatches on network retry

Core Entities

Data Ownership Boundaries

Storage Technology Choices

Data Lifecycle

Architecture Diagram

Service Boundaries with Ownership

Sync vs Async Communication

Failure Domain Boundaries

Deep Dive 1: Geospatial Indexing with H3

Core Decision: Spatial Index Selection

Decision: H3 (Uber’s own library)

H3 is the clear choice because Uber developed it specifically for ride matching. The hexagonal grid means all six neighbors are equidistant from the center — unlike square grids where diagonal neighbors are ~1.41x farther. This property is critical for expanding-ring searches: when we search “1 ring out,” every neighboring cell represents the same additional distance.

Resolution strategy:

Driver index structure (in Redis):

Deep Dive 2: Matching Algorithm (DISCO Core)

Three-phase matching pipeline:

Phase 2 ML Enhancement (via Michelangelo):

In Phase 2 of the project, the static weight-based scoring is replaced with an ML model that predicts P(successful_trip | driver, rider, context):

Deep Dive 3: UberPool (Shared Rides)

Deep Dive 4: Fairness in Dispatching

Deep Dive 5: Ringpop-Based Sharding and Consistency

Deep Dive 6: Disaster Recovery (Driver-Side State Digest)

Migration Strategy: Legacy DISCO → H3-Based DISCO v2

Since Uber’s existing dispatch system uses S2 cells and simpler nearest-driver matching, the migration to H3-based multi-factor matching must be carefully staged.

Phase 1: Shadow Mode (Weeks 1-6)

• ·Deploy DISCO v2 alongside legacy DISCO in 3 pilot cities (e.g., San Francisco, Sao Paulo, Bangalore — diverse traffic patterns)
• ·Both systems receive every ride request; legacy DISCO makes the actual dispatch decision
• ·DISCO v2 runs full matching pipeline but only logs its decision (no driver impact)
• ·Compare: match quality (ETA accuracy, driver idle time), latency (p50/p99), candidate overlap
• ·Validate H3 indexing correctness against S2-based results
• ·Metrics dashboard: side-by-side comparison per city

Phase 2: A/B Test (Weeks 7-14)

• ·5% of ride requests in pilot cities routed to DISCO v2 for actual dispatch
• ·A/B test metrics: rider wait time, driver earnings/hour, cancellation rate, match latency
• ·Ramp: 5% → 10% → 25% → 50% over 4 weeks per city
• ·DISCO v2 must show statistical improvement (or no regression) on all primary metrics before ramp
• ·On-call rotation: DISCO team staffs dedicated on-call for v2 during rollout

Phase 3: City-by-City Rollout (Weeks 15-26)

• ·After pilot cities validated, roll out to remaining cities in tiers:
• ·Tier 1: Top 20 cities by trip volume (weeks 15-18)
• ·Tier 2: Cities 21-200 (weeks 19-22)
• ·Tier 3: All remaining cities (weeks 23-26)
• ·Each tier: 1 day at 10%, 2 days at 50%, then 100%
• ·Legacy DISCO remains deployed (cold standby) for 4 weeks after each tier completes

Phase 4: Legacy Decommission (Months 7-9)

• ·Remove legacy DISCO traffic routing
• ·Migrate S2-based data pipelines to H3
• ·Decommission legacy DISCO instances and S2 index infrastructure
• ·Archive legacy code (don't delete — may need for forensic debugging)

Rollback Plan

Cross-Team Coordination

Bottleneck Analysis

Observability

Key metrics (RED method):

Critical alerts:

1. Match latency p99 > 2s — Matching SLA violated. Investigate: ETA service latency, Redis query time, candidate pool size. Auto-remediation: fall back to nearest-driver matching (skip ML scoring).

2. Match failure rate > 5% — Too many ride requests ending in “No drivers available.” Investigate: supply levels per city, surge pricing response, driver app GPS issues.

3. Kafka consumer lag > 30s on supply.location-updates — Driver positions becoming dangerously stale. Investigate: consumer throughput, partition imbalance. Auto-remediation: scale consumers, alert on-call.

4. Ringpop membership churn > 10 nodes/min — Cluster instability causing constant rebalancing. Investigate: network partitions, host health. Auto-remediation: freeze rebalancing (pin assignments) until stabilized.

5. Offer cascade rate > 40% — More than 40% of first-choice drivers declining. Investigate: offer quality (are we picking distant drivers?), driver incentive issues, app push delivery issues.

Distributed tracing:

• ·Trace from rider tap "Request" → API Gateway → Trip Service → DISCO (candidate generation → scoring → dispatch) → Offer Manager → Driver App → Accept → back to Rider
• ·Include span tags: city_id, h3_cell, candidate_count, search_radius, algorithm_version, cascade_attempt
• ·Trace sampling: 100% for match failures, 10% for successful matches, 0.1% for location updates
• ·Tool: Jaeger (Uber open-sourced this for exactly this use case)

2-3 Year Evolution

Year 1: Foundation — H3-Based Matching with ETA Optimization

Core DISCO v2 operational across all 10,000+ cities with H3-based geospatial indexing replacing legacy S2 cells. Multi-factor scoring (ETA, fairness, supply health) active for all ride types. DeepETA model integrated via Michelangelo reduces rider wait time by 10-15% vs distance-only matching. Fairness mechanisms (wait-time boost, supply health scoring) reduce driver earnings variance by 20%. Disaster recovery via driver-side state digest operational with <30s recovery time. Operational maturity: comprehensive Jaeger tracing, RED metrics dashboards per city, automated runbooks for top 10 incident types, on-call rotation with 15-min response SLA.

Year 2: ML-Powered Matching, Dynamic Pricing, Multi-Modal

Replace static scoring weights (alpha/beta/gamma) with ML model that predicts P(successful_trip) per driver-rider pair. Model trained on billions of historical trips via Michelangelo, features include real-time traffic, weather, driver fatigue signals, rider behavioral patterns. Integrate dynamic pricing directly into matching: surge multiplier influences which drivers are shown to which riders (higher-surge rides preferentially offered to drivers in low-supply areas, creating natural rebalancing). UberPool batch matching optimization: 5-second batching windows with global optimization yield 15% improvement in shared ride efficiency. Multi-modal trip planning: for trips where transit + Uber is faster/cheaper, suggest combined itinerary (e.g., “Take subway to downtown, Uber last mile”). Begin work on unified Fulfillment Platform abstractions so same matching engine can serve Rides, Eats, and Freight with product-specific scoring plugins.

Year 3: Autonomous Vehicles, Predictive Positioning, Unified Matching

Autonomous vehicle (AV) fleet integration: AVs have no “driver acceptance” step — matching is deterministic and instant. AV scoring includes battery/fuel level, passenger pickup capability, maintenance schedule. Mixed fleet matching: optimize human driver + AV allocation per area based on ride type, time of day, and AV coverage zones. Predictive supply positioning: demand forecasting model (trained on 3 years of trip data, weather, events, holidays) pre-positions drivers 15-30 min before demand spikes. Instead of reactive surge pricing, proactively nudge supply to match predicted demand. Unified matching engine live across Rides, Eats, and Freight: a single driver can be offered a ride OR a food delivery based on which maximizes platform-wide efficiency. Cross-product matching reduces driver idle time by an estimated 20%.

Cost Optimization Roadmap

The key staff-level insights in this design:

1. H3 hexagonal grid is the foundational data structure — Uber built it specifically because hexagons provide equidistant neighbors, eliminating edge artifacts that plague square/rectangular grids in expanding-ring driver searches. The resolution hierarchy (res4 for sharding, res7 for pricing zones, res9 for driver indexing) maps cleanly to different system concerns.

1. Ringpop consistent hashing co-locates data and compute — By sharding DISCO instances by H3 res4 cell, every matching operation hits a local in-memory driver index with zero network hops. This is why matching can complete in <500ms despite evaluating 10-50 candidates with ML-based scoring.

1. Fairness is a first-class architectural concern, not an afterthought — The 25% weight on fairness_boost in scoring, combined with anti-cherry-picking rules and supply health scoring, directly addresses driver retention — the biggest operational risk in a two-sided marketplace. Without fairness, top drivers cluster at hotspots, edge-area drivers churn, and supply collapses.

1. Driver-side state digest is an elegant disaster recovery pattern — Pushing encrypted state to the entity that is already distributed (millions of driver phones) avoids the cold-start problem of rebuilding from Kafka logs. Recovery in ~30 seconds vs minutes from log replay.

1. The matching pipeline degrades gracefully — Each failure domain has an independent degradation mode: stale GPS positions are still useful, ETA service failure falls back to distance heuristics, ML scoring failure falls back to static weights, push delivery failure triggers automatic cascade to next driver. The system never hard-fails on a single component.

1. Migration via shadow mode + A/B testing + city-by-city rollout reflects the reality that you cannot do a big-bang cutover for a system processing 36M trips/day — the strangler fig pattern with per-city feature flags gives confidence at each stage while keeping legacy as a safety net.