Katkat
Back

Design Ride Requests, Driver Matching, and Trip State

MetaSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSystem Design

Last updated

Design a high-scale real-time ride-hailing dispatch and trip lifecycle backend. The problem tests geospatial indexing, high-throughput location ingestion, concurrent driver assignment without double-booking, and idempotent distributed state management.

Scenario

Design the backend core for a global ride-hailing platform. The system must process real-time driver locations, find and rank nearby candidate drivers upon a rider's request, handle atomic dispatch without race conditions, and govern trip lifecycle state transitions with strict idempotency and fault recovery.

Requirements

Functional Requirements

  1. Location Ingestion: Ingest location pings from active drivers periodically and maintain an up-to-date spatial index.
  2. Candidate Search & Matching: When a rider requests a trip, search available drivers within a dynamic radius (e.g., 3–5 km) and offer the ride sequentially or via batching.
  3. Conflict-Free Assignment: Guarantee that a driver cannot be double-booked across competing ride requests, and a ride request cannot be claimed by multiple drivers.
  4. Trip State Machine: Manage trip states (REQUESTED, MATCHED, ARRIVED, IN_PROGRESS, COMPLETED, CANCELLED) ensuring transitions are idempotent, auditable, and resilient to out-of-order network packets.
  5. Driver Rejection & Timeout: If a targeted driver declines or fails to respond within a TTL (e.g., 15 seconds), reassign the ride to the next best candidate.

Non-Functional Requirements

  • Scale: 1,000,000 concurrent active drivers emitting updates every 4 seconds (250,000 location writes/sec). Peak load of 5,000 ride requests/sec.
  • Latency: Driver candidate discovery and initial dispatch offer within 1 second (p99).
  • Consistency: Strict consistency for driver assignment and trip state transitions; eventual consistency is acceptable for driver map discovery.
  • Fault Tolerance: Survive regional connection blips and node crashes without losing active trip states.

What Your Design Should Cover

  1. API Design: Endpoints for driver location updates, ride requests, driver accept/decline actions, and trip status updates.
  2. Data Storage & Indexing: Data models for trip entities and geospatial data structures (e.g., H3, S2, Redis GEO) suitable for high write-throughput.
  3. Matching Engine Architecture: Concurrency control (e.g., distributed locks, conditional leases, transactional reservation) to avoid split-brain or double-dispatch.
  4. Trip Lifecycle State Machine: Mechanism to guarantee strictly ordered, idempotent state updates and fare tracking.
  5. Failure Modes & Recovery: Handling driver app disconnects, driver crashes mid-trip, and stale location caches.

Hints

Hint 1

Decouple the high-throughput, loss-tolerant location ingestion pipeline from the transactional, strictly consistent trip state machine.

Hint 2

Prevent race conditions during driver dispatch by using short-lived reservation leases with atomic compare-and-swap operations rather than long-running distributed locks.

Hint 3

Model trip transitions using an explicit finite state machine with entity versioning or idempotency tokens to discard delayed or out-of-order network requests.

Follow-up questions

  • How would you transition the matching engine from a greedy first-response dispatch to a batched bipartite matching model run every few seconds?
  • If a driver loses network connectivity during a trip, how does the system reconcile offline GPS breadcrumbs and calculate accurate fares upon reconnection?
  • How do you mitigate hotspot and thundering-herd issues in specific spatial cells following major events like concerts or sporting events?