Design a Ride-Hailing Service (Uber)

Location Service: Handling 500K Location Updates/Sec

Half a million location updates per second require a purpose built geospatial index rather than relational database scans.

Ingestion Architecture: Driver mobile applications transmit GPS coordinates every 4 seconds over persistent WebSocket connections. Each WebSocket connection receives a server assigned session ID, which is registered in Redis before location updates begin. Each update includes that session ID, a monotonic sequence number, and a timestamp. The Location Service rejects updates from stale sessions or older sequence values, then updates the in memory geospatial index. Concurrently, it publishes telemetry records to the Kafka driver-location topic for downstream analytics, trip tracking, and speed profiling.

Geospatial Indexing Alternatives:

• GeoHash with Redis: Encodes latitude and longitude into hierarchical string prefixes where proximate points share common prefixes. While straightforward, Redis single-threaded write bottlenecks make sustaining 500K location updates per second difficult without extensive manual sharding.
• QuadTree: Recursively partitions two-dimensional space into four quadrants where each leaf node bounds at most ~100 drivers. The driver payload alone would require about 128 MB at 64 bytes per driver, before accounting for tree nodes and other index overhead. The structure can then be naturally sharded along metropolitan boundaries.
• Google S2 Geometry: Projects the spherical Earth onto the faces of an enclosing cube using hierarchical Hilbert curve space-filling cells across 30 levels, with each cell referenced by a 64-bit integer identifier.
• Uber H3 Hexagonal Grid: H3 provides 16 hierarchical resolutions. Resolution 9 has approximately 0.1 km² nominal cell areas with roughly 174-meter edges. Its hexagonal layout gives more uniform local neighborhoods than a square grid, which makes radial k-ring expansion predictable. For a fixed k, neighbor expansion is bounded, while filtering remains proportional to the returned driver set.

Matching Service: The Core Algorithm

Matching combines real time geospatial candidate retrieval with atomic assignment locks to prevent double booking drivers.

1. The rider initiates a booking request specifying pickup and dropoff coordinates.
2. The engine starts with a bounded search radius and expands it as needed, up to a configured maximum such as 5 km. At resolution 9, the service converts each radius into the required k-ring and then applies exact distance filtering rather than assuming that a single ring covers the full area.
3. The service filters candidates by status, vehicle category, and minimum rating, then ranks them using road network ETA, traffic conditions, and driver acceptance scores.
4. The system pushes a dispatch offer to the top-ranked candidate over WebSocket or push notification, initiating a 15-second response countdown.
5. If the driver accepts, the service performs an atomic state transition and assigns the driver. If the driver declines or times out, the engine advances to the next candidate or expands the search radius.

Batch matching fallback: When sequential k-ring expansion fails after three attempts in high contention areas, the system holds incoming requests for a 5 second collection window and executes min-cost bipartite matching across drivers and pending requests in the H3 cell, substantially improving fulfillment rates without blocking standard dispatches.

Assignment Concurrency: To reduce contention when two riders target the same driver, the service acquires a short lived Redis lock. The lock is not the source of truth. Final ownership is established by the PostgreSQL compare and set plus the unique active driver constraint:

SET driver:lock:drv_9821a trip_4b2190e NX EX 30

Pricing Service: Surge Pricing

Surge pricing dynamically balances localized supply and demand while operating asynchronously off the critical dispatch path.

The system partitions metropolitan areas into H3 hexagonal clusters (typically resolution 7). Within each cell, the Pricing Service tracks ride requests as demand and available drivers as supply over rolling time windows. When the demand-to-supply ratio rises above 1.5, a dynamic surge multiplier engages up to a configured ceiling of 8x. Multipliers are recalculated every 30 seconds and cached in Redis.

Fare Calculation Formula: The total fare is computed by taking base fare, adding elapsed duration multiplied by per-minute rates, distance multiplied by per-mile rates, applicable tolls, and booking fees, and then applying the localized surge multiplier, floored at the minimum ride fare.

Map and Route Service for ETA

Estimated time of arrival feeds candidate ranking and rider tracking, relying on precomputed routing graphs and cached segment traversals where possible.

The routing architecture operates independently from pricing calculations. Matching and Pricing services both query its APIs, but cached lookups ensure routing computations do not impede dispatch latency.

• Routing Engine: Employs Open Source Routing Machine (OSRM), Valhalla, or custom contraction hierarchies over OpenStreetMap road networks.
• Pickup ETA: Determines driving time from candidate driver coordinates to the rider pickup point using road network topology rather than Euclidean distances.
• Real-Time Traffic Adjustments: Aggregates driver speed telemetry from Kafka across road segments in Apache Flink to dynamically update segment speed multipliers.
• Trip ETA: Calculates travel duration from pickup to dropoff accounting for live congestion, caching origin-destination cell pairs with a 60-second time to live.

Ride Service: Trip State Machine

The trip state machine persists authoritative transitions so matched rides survive service restarts and client network disconnects.

The service orchestrates transitions across REQUESTED, MATCHED, DRIVER_EN_ROUTE, ARRIVED, IN_TRIP, COMPLETED, and PAYMENT_DONE states, with cancellation paths supported from early phases under applicable cancellation fee policies. Driver assignment is stored with the trip transition so the durable record remains the authority. Every state transition executes as an atomic PostgreSQL transaction with optimistic locking and records its Kafka event in the same transaction through the outbox. The outbox publisher delivers those events to the trip-events topic, and consumers process them idempotently. The PAYMENT_DONE transition is driven by a confirmed payment event, and client applications always resynchronize against the server authoritative state after reconnecting.

Payment Service

Payment integration handles post trip charging and driver payout workflows while the payment provider internals, settlement ledger, and provider-specific reconciliation remain separate. Idempotency keys and transactional outbox patterns prevent duplicate charges during network retries and payment gateway handshakes.

• Trip Completion Trigger: Activates asynchronously when the Ride Service emits a COMPLETED event.
• Final Fare Auditing: Reconciles recorded GPS mileage, actual elapsed trip duration, dynamic surge multiplier, bridge tolls, and booking fees.
• Cardholder Processing: Submits charges to payment service providers (PSPs) using an operation scoped idempotency key such as trip_id plus charge attempt to prevent double billing while allowing separate refund or payout operations.
• Driver Disbursement: Aggregates driver net earnings after platform commission and schedules weekly automated clearing house (ACH) payouts.
• Fare Splitting: Divides trip totals across multiple participating riders when split fare requests are authorized.

Notification Service

Channel adapters isolate provider-specific dispatch logic across Apple Push Notification service (APNs), Firebase Cloud Messaging (FCM), and SMS fallbacks.

• Lifecycle Notifications: Consumes Kafka trip-events and delivers push alerts for driver arrival, trip initiation, and payment receipts.
• Continuous Tracking Stream: Active vehicle movement updates during DRIVER_EN_ROUTE and IN_TRIP flow over persistent WebSocket channels rather than push notifications.

Event Bus Design (Kafka)

The distributed event bus decouples core producers from downstream consumers and buffers high volume telemetry spikes during peak hours.

topics:
  driver_location:
    partitions: 256 # Partition by driver_id to preserve per-driver ordering
    retention: 24h # Hot telemetry retention, archived to the data lake for long-term analytics
    replication_factor: 3
    min_insync_replicas: 2
    producers:
      - "Location Service (GPS ingest)"
    consumers:
      - "Trip Tracking Service"
      - "ETA Traffic Model (Flink speed aggregation)"
      - "Fraud and GPS Spoofing Detection"

  trip_events:
    partitions: 64 # Partition by trip_id
    retention: 7d # Compliance and dispute replay
    replication_factor: 3
    min_insync_replicas: 2
    producers:
      - "Ride Service through transactional outbox"
    consumers:
      - "Notification Service"
      - "Payment Service (triggered on COMPLETED)"
      - "Analytics Warehouse"
    idempotency_key: "(trip_id, transition, version)"

  payment_events:
    partitions: 32 # Partition by trip_id
    retention: 7d # Payment audit and replay
    replication_factor: 3
    min_insync_replicas: 2
    producers:
      - "Payment Service through transactional outbox (charge, refund, driver payout)"
    consumers:
      - "Ride Service (transitions COMPLETED to PAYMENT_DONE after confirmed settlement)"
      - "Finance General Ledger"

  push_notifications:
    partitions: 32
    producers:
      - "Notification Service"
    consumers:
      - "APNs and FCM dispatch workers"

execution_paths:
  sync_path: "Validate request, persist the trip row and outbox record in one PostgreSQL transaction, then return 201 Created"
  async_path: "Outbox publishing, location ingest streaming, surge recalculation, push notifications, and analytics pipelines"

reliability:
  event_delivery: "At-least-once delivery with idempotent consumers"
  outbox: "Prevents the PostgreSQL to Kafka dual-write gap for trip state events"