01. Ride-Hailing Service — High-Level Design¶

~15 min read · Part 2 of 4 (Overview → HLD → LLD → Q&A)

This file turns the three-plane narrative from the overview into boxes and the flows between them. Read the architecture top to bottom, follow a location write and a match request through it, then look at what happens when the downtown shard gets hot at 6pm.

Architecture¶

   ┌───────────┐                                   ┌───────────┐
   │ Driver app│ location every 4s                 │ Rider app │ request ride
   └─────┬─────┘                                   └─────┬─────┘
         │                                               │
         ▼                                               ▼
   ┌──────────────────────────────────────────────────────────┐
   │                    API Gateway / LB                        │
   └───────┬───────────────────────────────────────┬───────────┘
           │ location firehose (1.25M/s)            │ match req (~1k/s)
           ▼                                        ▼
   ┌────────────────┐                     ┌────────────────────┐
   │ Location Ingest│                     │  Matching /         │
   │  service       │                     │  Dispatch service   │
   └───────┬────────┘                     └───┬──────────┬──────┘
           │ write cell                       │ query     │ claim
           ▼                                  ▼           ▼
   ┌──────────────────────────┐   ┌────────────┐  ┌──────────────┐
   │  Geo Index (in-memory,   │◀──┤ ETA / Route │  │ Trip Store   │
   │  sharded by H3 cell)     │   │  service    │  │ (durable,    │
   │  cell → [driver states]  │   │ (road graph)│  │  sharded)    │
   └──────────────────────────┘   └────────────┘  └──────┬───────┘
           ▲                                              │
           │ demand/supply                                ▼
   ┌───────┴────────┐                             ┌──────────────┐
   │ Surge / Pricing│                             │  Event Bus    │
   │  service       │                             │  (Kafka)      │
   └────────────────┘                             └──────┬───────┘
                                                          ▼
                         ┌──────────────┐        ┌──────────────┐
   push to apps ◀────────┤ Notification │        │ Analytics /   │
   (WebSocket)           │  / streaming │        │ history store │
                         └──────────────┘        └──────────────┘

Read it as two flows meeting at the geo index. Down the left, driver apps push location every 4 seconds through the gateway into the Location Ingest service, which writes each update into the in-memory Geo Index, sharded so that a given geographic cell always lands on the same node. Down the right, a rider request enters the Matching service, which reads the Geo Index for candidates near the pin, asks the ETA service to rank them over the road network, checks Surge for the current multiplier, and then atomically claims a driver and writes the trip to the durable Trip Store. Trip state changes flow onto the Event Bus, which fans out to the Notification service (pushing live updates to both apps) and to the analytics/history store. The two data planes — sloppy ephemeral location on the left, strongly-consistent trip state on the right — meet only at the moment of the claim.

Components¶

API Gateway / Load balancer. Terminates connections from millions of apps, authenticates, and routes the location firehose and the match requests to different service tiers so a surge of one cannot starve the other. Location updates are cheap, unauthenticated-fast-path, best-effort; match requests are the expensive, guarded path.

Location Ingest service. A stateless, horizontally-scaled tier whose only job is to validate a location update and write it to the correct Geo Index shard. It does almost no work per message, which is deliberate — at 1.25M messages/second, any per-message cost is multiplied by a million. It drops or downsamples updates under overload rather than backpressuring drivers.

Geo Index (in-memory, sharded by cell). The heart of the system: a partitioned in-memory map from geographic cell (an H3 hexagon or geohash prefix) to the list of driver states currently in that cell. Writes are "upsert this driver into this cell"; reads are "list drivers in these cells." It is not durable and not the source of truth for anything except "who is roughly where, right now." Losing a shard loses a few seconds of freshness for one region, self-healed by the next update round.

Matching / Dispatch service. The latency-critical brain. On a request it does the bounded local search (query cells, prune, rank by ETA), runs the dispatch loop (offer → wait → fall through), and performs the atomic driver claim that guarantees one-trip-per-driver. It holds no durable state itself; the claim and the trip live in the Trip Store.

ETA / Routing service. Answers "how long from A to B by road, given current traffic." Backed by a road-network graph with precomputed shortest-path structures and live traffic speeds. Matching calls it to rank the pruned candidate set; it is a read-heavy service with an in-memory graph and many replicas.

Surge / Pricing service. Continuously computes, per cell, the ratio of recent demand (requests) to available supply (idle drivers) and turns it into a fare multiplier. It reads request signals and the Geo Index supply counts, publishes a multiplier per cell, and Matching reads it to price the trip.

Trip Store. The durable system of record for trips: sharded (by city/region, then trip id) relational or NoSQL storage holding the trip's lifecycle, the assigned driver, timestamps, and fare. This is where strong consistency lives — the driver-claim writes here.

Event Bus + Notification + Analytics. Trip lifecycle events (matched, arrived, started, completed) publish to a durable log. The Notification service consumes them to push live state to the rider and driver apps over persistent connections, and the analytics pipeline consumes them for dashboards, plus the downsampled location aggregates for supply heatmaps. Decoupling here keeps push-fanout and analytics load off the matching path.

Primary write path (driver location update)¶

POST /v1/locations arrives at the gateway, which routes it to the Location Ingest tier over the cheap fast path.
Ingest validates the payload (plausible coordinates, recent timestamp, known driver) and computes the driver's cell id from (lat, lng) — e.g. the H3 index at resolution 8.
It upserts the driver's state {driver_id, lat, lng, heading, status, ts} into that cell's bucket in the Geo Index shard that owns the cell, and, if the driver crossed a cell boundary since the last update, removes them from the old cell.
Each entry carries a short TTL (a few times the update interval). A driver who stops reporting ages out automatically, so a crashed app or dead phone does not leave a ghost car on the map.
The service returns 204 and moves on. The write is best-effort and fire-and-forget: a single dropped update is invisible because another arrives in 4 seconds. There is no durable write here at all.

Primary read path (match a rider request)¶

POST /v1/rides reaches the Matching service through the gateway.
Matching computes the pin's cell and gathers a k-ring of neighboring cells covering roughly the search radius, then reads all driver states in those cells from the Geo Index — the ~500 candidates in the downtown scenario.
It filters to available drivers and prunes to the closest ~20 by cheap straight-line (haversine) distance, because computing a real ETA for all 500 would blow the budget.
It calls the ETA service to compute road-network time-to-pickup for those ~20 and ranks them, reads the current surge multiplier for the cell, and returns 202 to the rider immediately with a fare estimate and "matching" status.
It enters the dispatch loop: offer the trip to the best-ranked driver, push the offer to that driver's app, and wait a short window (≈15 s) for accept. On accept it performs the atomic claim — a conditional write flipping the driver to on_trip and inserting the trip row — which is the one strongly-consistent step. On decline or timeout it falls through to the next candidate.
On a successful claim it writes the trip to the Trip Store and publishes a matched event; the Notification service streams the driver's identity and live position to the rider, and the ETA counts down. The car icon the rider sees moving is that driver's ongoing location updates flowing through the same firehose.

Storage choices¶

Geo Index: in-memory, sharded key-value keyed by cell. Chosen for microsecond upserts and reads at firehose scale, and because the data is ephemeral by nature. Redis with its geospatial commands, or a purpose-built in-memory service, fits. Not durable on purpose — durability here would cost enormously for data that is stale in 4 seconds. Sharding is by cell (so a region's writes and reads co-locate), not by driver id.
Trip Store: durable, sharded relational or NoSQL. Trip state transitions need atomicity and strong consistency (the driver claim), plus point lookups by ride_id and range queries by rider/driver for history. A relational store partitioned by region, or a NoSQL store with conditional writes, both work. This is the only plane where losing data is unacceptable.
Road graph (ETA): in-memory, read-only replicas. The graph and its precomputed shortest-path structures are large but static-ish; load them into memory on many replicas and rebuild periodically as traffic and map data change. Reads dominate completely.
Surge state: in-memory, short-window counters per cell. Demand and supply counts over a rolling few-minute window; cheap to compute, cheap to lose (recomputed continuously).
Analytics / history: append-optimized columnar/time-series. Downsampled location aggregates and completed-trip records for heatmaps and business reporting, kept off the hot paths behind the event bus.

Scaling¶

Location write path. The firehose scales by sharding the Geo Index geographically: each shard owns a set of cells, and the Ingest tier routes each update to the shard for its cell. At 1.25M writes/second spread across, say, hundreds of shards, each shard handles single-digit-thousands of writes/second — comfortable in memory. Adding capacity means splitting cell ranges onto more shards. The adaptive-frequency dial is also a scaling lever: because a large fraction of online drivers are parked and idle, backing idle drivers off from every-4-seconds to every-10-seconds can cut the aggregate firehose by a third or more without hurting active-trip freshness.

Match read path. Matching is stateless and scales by adding servers behind the gateway; ~1,000 requests/second is modest. The real cost per request is the ETA computation, which is why we prune to ~20 candidates before calling ETA — computing road-network time for 500 drivers per request at 1,000 requests/second would be 500k ETA calls/second, versus 20k with pruning, a 25× reduction that keeps the ETA fleet small.

Hot cell. The downtown-at-6pm scenario is the geographic hot key. That one cell (and its neighbors) absorbs ~125 location writes/second from 500 drivers and a burst of match requests from every rider in the area at once — concentrated on a single Geo Index shard. Defenses: cells are sized so no single cell holds too many drivers (finer resolution downtown, coarser in rural areas), the hottest cell's shard can be given dedicated capacity, and match queries against a dense cell cap the candidate scan (read the closest N, not all 500). The counterpoint to the URL-shortener's cache story: here you cannot cache the answer because the data changes every 4 seconds, so the hot-key defense is finer partitioning and bounded reads, not caching.

Operational signals¶

The healthy signal is time-to-match p50, which should sit at a couple of seconds and barely move as request volume rises — a busy evening that keeps match latency flat is the system working as designed. The first metric to degrade under trouble is the offer-accept round-trip / dispatch depth: when matches start requiring three or four offers instead of one (drivers declining, offers timing out), time-to-match climbs before anything else does, and it is the earliest sign that supply is thin or the ETA ranking is sending offers to the wrong drivers. The misleading metric is average location-ingest latency — it stays flat and green even when matching is completely broken, because ingest is a separate, healthy plane; a candidate who watches ingest health to reason about match health is watching the wrong graph. The graph an experienced operator opens first during an incident is the per-cell supply/demand heatmap: it shows instantly whether a region has gone unmatchable because demand spiked, supply evaporated, or one shard stopped accepting writes.

Failure modes and resilience¶

Geo Index shard loss. The cells on that shard go dark: drivers there vanish from candidate sets and riders there cannot be matched for a few seconds. Because the data is ephemeral, recovery is automatic — bring up a replacement shard and the next round of location updates repopulates it within one update interval. Mitigation: replicate hot shards and route reads to a replica during failover so the gap is sub-second rather than seconds.
Downtown hot cell at 6pm (the threaded scenario). 500 drivers and a request storm hit one shard simultaneously. If that shard saturates, match latency in the busiest part of the city spikes at the worst possible moment. Mitigations stack: size downtown cells at a finer resolution so drivers spread across more shards; cap the candidate scan so a match reads the nearest 50, not all 500; and give the identified hot shard dedicated headroom during known peaks. The design goal is that the busiest cell degrades to slightly slower matches, never to no matches.
Location Ingest overload. If the firehose exceeds ingest capacity, the tier sheds load by dropping or downsampling updates rather than backpressuring drivers — a dropped update is invisible in 4 seconds, but a stalled ingest tier would stale the entire map. Adaptive frequency is the pressure-relief valve.
Double-dispatch (assignment race). Two matching workers try to claim the same driver for two riders. This is the one failure the system must never allow; it is prevented by the atomic conditional claim (LLD), where only one write wins and the loser falls through to its next candidate. A soft failure here means a slower match; a broken claim means a driver promised to two riders, which is a correctness bug, not a performance one.
ETA service degradation. If routing is slow or down, matching falls back to ranking by straight-line distance — worse matches (a car across the river looks close but is 15 minutes away) but the system keeps dispatching. Degrade the quality of the match, never the availability of it.
Trip Store unavailability. The claim cannot be persisted, so new matches stall in the affected region while in-progress trips (already persisted) continue via cached state and the event stream. Mitigation: replicate the store per region and fail over; matching in unaffected regions is unharmed because the store is regionally sharded.

Where this shows up in production¶

Uber H3 — the hexagonal hierarchical geospatial index Uber built and open-sourced precisely because square geohash cells have uneven neighbor distances; hexagons give uniform adjacency for the k-ring candidate search described here.
Lyft — runs the same split of an ephemeral location plane against a durable trip plane, and publicized adaptive location-reporting frequency to cut the mobile-data and ingest cost of idle drivers.
Google S2 — the spherical cell library (used across Google geo products) that is the main alternative to H3 for turning a lat/lng into a shardable cell id.
Redis GEO commands (GEOADD, GEOSEARCH) — the in-memory "add a point to a cell, query points in a radius" primitive that many teams use as the geo index before outgrowing it.
DoorDash / Instacart dispatch — the same bounded-local-search-then-rank matching applied to couriers instead of cars, with batching added because food orders tolerate a little more wait than a rider standing on a curb.
OSRM / Valhalla routing engines — the road-graph routing services that answer the ETA-by-road query the matcher depends on, standing in for the "ETA service" box.
Kafka in trip pipelines — the durable event log that decouples trip-lifecycle fan-out (push to apps, analytics, payments) from the synchronous match path, so a slow consumer never slows a dispatch.
Uber's Michelangelo / ML ETA — the layer that corrects raw road-graph time with a learned model of real-world pickup delays (finding the rider, parking), the difference between a naive ETA and one riders trust.