Building Blocks of a Ride-Hailing Platform

Designing a ride-hailing system requires coordinating a handful of specialized services that together support the entire trip lifecycle, from ride request through completion and billing. The core components are:

  • Driver Location Manager: Ingests location updates from driver apps and maintains an up-to-date index of car positions.
  • Trip Dispatcher: Handles ride requests from users and assigns an available driver.
  • Arrival ETA Calculator: Computes the time for a driver to reach the rider after trip acceptance.
  • Trip Recorder: Captures GPS signals emitted during an active trip and persists them for downstream consumers.
  • Map Matcher: Converts raw GPS traces into routes on the actual road network.
  • Price Calculator: Derives trip cost from the recorded route and trip information.

These services fall into three functional groups: pre-trip components (discovery and dispatch), on-trip components (tracking and settlement), and data storage.

Pre-Trip: Discovery and Dispatch

Before a trip starts, the system must support three operation sequences: location updates from drivers, queries for nearby cars from riders, and ride requests that end in dispatch. The driver location index sits at the center of all three.

Driver locations are stored as objects containing position, occupancy, and trip status. These objects are sharded across a distributed in-memory index using attributes like city or product type, with replication for availability. Each node holds a slice of the driver objects and serves real-time queries against them. The index needs to handle high read and write volume, but the data it holds is ephemeral — no long-term durable storage is required.

The ETA Problem

Once a ride is dispatched, customers need a pickup ETA that accounts for route characteristics, traffic, and weather. Calculating ETA boils down to two steps: finding the least-cost route on the road network, and estimating traversal time for that route.

The physical map is modeled as a graph where intersections are nodes and road segments are directed edges. A naive shortest-path computation with Dijkstra's algorithm runs in O(N log N) for N nodes, which does not scale for a platform of this size. Partitioning the graph and pre-computing paths within partitions lets the search interact only with partition boundaries, reducing complexity to O(N' log N') where N' is roughly the square root of N.

Traffic information — itself a function of time, weather, and real-world events — populates the edge weights on that graph, and those weights feed the ETA estimate.

On-Trip: Tracking and Settlement

During the trip, the driver app publishes GPS locations. The Trip Recorder consumes those messages through Kafka streams and writes them to a durable location store. At trip completion, the Map Matcher takes the raw GPS trace and generates the actual map route.

Location Store Design

The store that persists GPS locations must handle a high volume of writes, provide durability, and support time-series queries like "where was this driver between t1 and t2." Cassandra is a fit here. Using a composite partition key of driver identifier plus timestamp keeps each driver's points ordered by time, enabling efficient range queries. Each location point is stored as a serialized message containing latitude, longitude, speed, and course.

Map Matching with HMM

Raw GPS signals often fall far from the actual road network — urban canyons from tall buildings and sparse signal sampling are common culprits. Map matching determines the actual road route the car took given noisy observations.

One approach models the problem as a Hidden Markov Model. Road segments are hidden states and GPS signals are observations. Emission probabilities capture the likelihood of observing a signal from a given road segment; transition probabilities capture the likelihood of moving from one segment to another. The Viterbi algorithm, a dynamic programming technique, then finds the most probable sequence of road segments given the observed GPS trace.

The matched route serves two purposes: pinpointing the driver's actual position on the network and providing the basis for fare calculation in the trip receipt.

Tuning the Hot Path

In the base design, both heavy reads and writes hit the same data store. A straightforward optimization is to split that traffic by caching raw driver locations in a distributed cache such as Redis. The MapMatcher then consumes driver positions from Redis to produce matched map data, which is persisted to Cassandra.

ETA accuracy can also be improved with machine learning layered on top of the deterministic ETA calculation. The first step is feature engineering—region, time, trip type, and driver behavior are all plausible inputs. Because ETA does not scale linearly with features like hour of day, and because there is no prior information about feature interactions, a non-linear, non-parametric model such as Random Forest, neural networks, or KNN is appropriate. Monitoring customer complaints when the predicted ETA is off can further refine the model.

One instructive finding from Uber's data science team is the correlation between ETA error (actual minus predicted) and region. Plotting the probability density function of the error reveals thicker tails in India compared to North America, indicating worse predictions there. This makes region a critical feature for any ETA-prediction model.

Resiliency Through Failure Injection

Every component in this architecture—driver location management, map matching, ETA calculation—is its own micro-service. To make the system resilient, fallback mechanisms should be in place for service failures, such as serving the most recently cached data or routing to fallback services. Chaos engineering is a standard practice for validating this: disruptions are injected into the system while performance is monitored on dashboards.

The Chaos Platform at Uber operates by taking disruption configurations from developers via command-line arguments. Worker environments trigger agents on hosts to induce the configured failures. These workers maintain disruption logs and events through streaming RPC, persisting the information to a database.

Two categories of disruptions are typically injected:

  • Process-level failures: SIGKILL, SIGINT, SIGTERM, CPU throttling, memory limiting.
  • Network-level failures: inbound call delays, outbound packet loss to external dependencies, and blocked database reads/writes.

Moving to Automatic Matching

The initial design relies on drivers being notified of nearby riders and choosing which trips to accept. A natural extension is automated driver-rider matching based on factors including distance, driver direction, and traffic conditions. A naive approach is to assign each rider the nearest driver, but that fails to handle the trip upgrade scenario: a rider is matched to a driver while, at the same instant, an additional driver and rider join the system, invalidating the original assignment.

Matching and dynamic pricing in ride-hailing are active research areas at Uber; the key machine learning and statistical problems are predicting demand, supply, and travel time across the road network, which feed directly into the matching algorithms.