Stackbook Logo
← Back to System Architectures

Designing a Ride-Hailing Dispatch System

Design a ride-hailing dispatch system with geospatial driver indexing, low-latency matching and safe handling of offers, timeouts and driver churn.

5 min read

Dispatch matches a rider request to a nearby available driver within seconds. It combines a high-write location stream, a geospatial index, a matching algorithm and a strict rule that one driver is never assigned two trips.

Requirements

Functional

  • Drivers report location and availability.
  • Riders request a trip; the system finds, offers and assigns a driver.
  • Track trip state from request to completion; handle cancellations and re-dispatch.

Non-functional

  • Match latency p95 under 3 seconds.
  • One active trip per driver, enforced strictly.
  • 99.95% availability for dispatch in each city.
  • Location freshness within 5 seconds.

Capacity Estimation

Assume 1M drivers online globally, each sending a location update every 4 seconds: 250,000 writes per second. Each update is about 100 bytes, so 25 MB per second of ingress. Trip requests at peak are about 5,000 per second. Location data is ephemeral: only the latest position matters for dispatch, so 1M entries at 100 bytes is 100 MB in memory, trivial. History goes to a stream for analytics and is retained for 30 days.

High-Level Design

Driver App -> Location Gateway -> Kafka (locations) -> Geo Index (Redis/in-memory, sharded by cell)
                                                    -> Analytics sink
Rider App -> API -> Trip Service -> Dispatch Service
                                      |-> Geo Index (nearby drivers)
                                      |-> ETA Service (road graph)
                                      |-> Offer Manager (push to driver)
                                      '-> Trip DB (state machine)

Dispatch is sharded by city or by geographic region, so each shard owns its drivers and trips and can fail independently.

Data Model

  • Geo index entry: driver_id -> (lat, lng, heading, status, updated_at), bucketed by cell id
  • trips(trip_id, rider_id, driver_id, state, pickup, dropoff, fare_estimate, version)
  • offers(offer_id, trip_id, driver_id, state, expires_at)
  • driver_state(driver_id, status, current_trip_id, version)

The geo index uses a hierarchical cell system such as geohash, H3 or S2. A query takes the rider's cell plus its ring of neighbors, expanding the ring until enough candidates are found.

Deep Dives

Matching

Candidates are ranked by ETA by road, not straight-line distance, plus driver rating, acceptance history and vehicle type. Instead of greedily matching each request on arrival, batch requests in a window of 1 to 2 seconds and solve a bipartite assignment problem. This lowers total wait time at the cost of a small added delay, and avoids a rider stealing the only driver who was better suited to a neighbor.

Preventing double assignment

A driver may be a candidate for several simultaneous requests. Assignment must be an atomic compare-and-set on driver_state: change status from available to offered or assigned only if the current status is available and the version matches. Only the request that wins the update proceeds. Losers move to the next candidate. Because driver_state lives in one shard, this is a single-row operation, with no distributed transaction.

Offers and timeouts

An offer is sent to one driver, or to a few in parallel for dense areas, with a 10 second expiry. The offer is a record with a deadline. If the driver declines or the timer fires, the Offer Manager releases the driver back to available and offers to the next candidate. Timers are driven by a durable scheduler rather than in-memory sleeps so a crash does not leak drivers in the offered state. A reaper also resets any driver stuck in offered beyond the deadline.

Idempotency and trip state

Trip creation takes a client request id so a retried tap does not create two trips. Trip transitions requested, matched, arrived, in progress, completed are validated by a state machine with versioned updates. Driver app calls such as accept are idempotent: accepting an already accepted offer returns success.

Location ingest

Updates are written to Kafka partitioned by driver_id for ordering, and the index consumer applies last-writer-wins by timestamp. Dropped updates are harmless because new ones arrive in seconds. Adaptive frequency lowers the rate for idle or stationary drivers, cutting ingest by a third or more.

Failure Modes and Trade-offs

  • Dispatch shard failure: a standby rebuilds the geo index from Kafka in under a minute; in-flight trips are recovered from the trip database.
  • Stale locations: drivers without an update for 15 seconds are excluded from matching.
  • GPS jitter and spoofing: smooth with map matching and flag impossible speeds.
  • Surge in one area: cell hotspots are split by finer cells or by replicating read-only index copies.
  • Greedy versus batched matching: greedy has the lowest latency, batching gives better global efficiency.
  • Strong state versus availability: driver state is strongly consistent within a shard, while the map shown to riders is eventually consistent.

Key takeaways

  • Keep only the latest driver position in a sharded in-memory geo index; stream history elsewhere.
  • Rank by road ETA and consider batched assignment for global efficiency.
  • Use a versioned compare-and-set on driver state so one driver is never double-assigned.
  • Make offers durable records with deadlines, backed by a reaper for stuck states.
  • Shard by region so failures and load stay local.
  • Use idempotent trip creation and a validated trip state machine.