Design Uber (Ride-Hailing)

A ride-hailing platform (Uber, Lyft, Grab) matches a rider who wants a car here, now with a nearby driver, tracks both in real time, and prices the trip. Where the chat system held millions of stateful connections, ride-hailing holds millions of moving points and must answer one question fast and constantly: which drivers are near this rider? That “nearest neighbor on a sphere, with everything moving” query is the heart of the design, and ordinary B-tree indexes can’t answer it. We’ll follow the framework.

1. Requirements

Functional

• Drivers continuously report location; riders request a ride from their location.
• Find nearby available drivers and match/dispatch one (handling declines/timeouts).
• Live tracking — rider sees the car approach; both see ETAs.
• Pricing, including surge when demand outstrips supply.

Non-functional

• High write throughput — every driver pings location every few seconds.
• Low-latency matching — a rider shouldn’t wait seconds for a car to be found.
• Geo-locality — a query in Lagos shouldn’t scan drivers in Lima.
• High availability; a brief stale location is acceptable, a lost trip is not.

This is a write-heavy geospatial problem

Most case studies are read-heavy. Ride-hailing is dominated by a firehose of location writes plus a constant stream of proximity reads. Both need a spatial index that supports “points near a point” — which is exactly what a one-dimensional database index cannot do efficiently.

2. Back-of-envelope estimation

LOCATION FIREHOSE (the write problem)
  active drivers:   ~5M online at peak (illustrative)
  ping interval:    every ~4 seconds
  location writes:  5e6 ÷ 4 ≈ 1.25M location updates/sec

MATCHING (the read problem)
  ride requests:    far lower — say ~5,000 requests/sec at peak
  per request:      a proximity query returning ~tens of candidate drivers
  per request:      a few ETA computations over the road network

1.25M location writes/sec would crush a relational table — and worse, each write would need to update a spatial index. The trick is that driver locations are ephemeral: you don’t need the durable, transactional guarantees of a database for “where is car 42 right now.” Keep the live location index in memory (Redis/in-process grid), durably persist only trips. The proximity read is modest in QPS but expensive per query, so the index must make “drivers near (lat,lng)” cheap.

3. API sketch

POST /v1/drivers/{id}/location   { lat, lng, ts }        → 204    // high-frequency, fire-and-forget
POST /v1/rides                   { rider_id, pickup }     → { ride_id, status: "matching" }
GET  /v1/rides/{id}              → { status, driver?, eta, route }
POST /v1/rides/{id}/accept       { driver_id }            → 200    // driver accepts dispatch

Location updates and live tracking ride over a persistent connection (WebSocket) rather than fresh HTTP requests each time — see real-time: polling, WebSockets, SSE. At 1.25M pings/sec, the per-request overhead of new connections would dominate.

4. Data model

driver_location (in-memory spatial index — ephemeral)   trips (durable SQL — source of truth)
  driver_id                                               trip_id (PK)
  geo_cell (H3 / geohash)   ← the index key              rider_id, driver_id
  lat, lng, heading                                       state (requested|matched|enroute|done)
  available (bool)                                        pickup, dropoff, route
  updated_at (TTL)                                        fare, surge_multiplier, timestamps

surge_state (per geo cell, recomputed continuously)
  geo_cell, supply, demand, multiplier

The keystone is geo_cell: every driver is bucketed into a spatial cell so “nearby” becomes “same or adjacent cell” — a cheap lookup instead of a full scan. Choosing that cell scheme is the whole geospatial-indexing question.

5. The core problem: indexing a moving map

Storing (lat, lng) and querying WHERE lat BETWEEN ... AND lng BETWEEN ... forces a 2-D range scan that a normal B-tree (one-dimensional) can’t serve efficiently — you’d scan a stripe of latitude and a stripe of longitude and intersect them. Spatial indexes solve this by mapping 2-D space onto a 1-D key whose ordering preserves proximity, or by recursively subdividing space.

Geohash

Interleave the bits of latitude and longitude and Base32-encode them. The result: points that are near each other share a long common prefix. “Find nearby” becomes “find keys sharing my prefix” — a partition-friendly, range-scannable string.

9q8yyk  ┐
9q8yym  ├─ share prefix 9q8yy → spatially clustered
9q8yyq  ┘

Costs: the boundary problem — two points can be physically adjacent but sit just across a cell edge, giving totally different prefixes. You must also query the 8 neighboring cells, not just your own, to avoid missing a car parked right across the street.

QuadTree

Recursively split each region into four quadrants until each leaf holds few enough points. Buys: density adaptivity — dense Manhattan subdivides deep, empty ocean stays coarse. Costs: it’s a tree to rebalance as points move, more complex than a flat grid.

H3 — Uber’s hexagonal grid

Uber built and open-sourced H3, a hierarchical hexagonal geospatial index. Hexagons have a property squares and rectangles lack: every neighbor is equidistant. A square cell has 4 edge neighbors at one distance and 4 corner neighbors at another — ambiguous “adjacency.” A hexagon has 6 neighbors, all the same distance away, which makes “expand my search by one ring” clean and makes gradients (like surge) smooth across cells.

square grid:  edge-neighbors ≠ corner-neighbors   hex grid (H3): all 6 neighbors equidistant
   . . .                                                 . .
   . X .   ← 8 neighbors, two distances              . X .   ← 6 neighbors, one distance
   . . .                                                 . .

A neat consequence of hexagons on a sphere

You can tile a plane with hexagons perfectly, but you can’t tile a sphere with only hexagons — H3 builds on an icosahedron and is forced to include exactly 12 pentagon cells per resolution (placed over oceans to avoid populated areas). It’s the geometric tax for wrapping a hex grid around a globe — and a reminder that elegant abstractions still meet the awkward shape of the real world.

Google’s S2 is the other well-known scheme (it maps the sphere onto cube faces and orders cells along a Hilbert space-filling curve). Geohash, QuadTree, H3, S2 — all are answering the same question: turn “near me on a sphere” into a cheap index lookup.

6. Matching, tracking, and surge

  driver pings ══WebSocket══►  Location service ──► update in-memory H3 index (cell, TTL)
                                                         ▲
  rider requests ride ─► Matching service ─► query nearby cells ─► candidate drivers
                              │  rank by ETA over the ROAD NETWORK (not straight-line)
                              ▼
                       dispatch offer ─► driver accepts/declines/timeout ─► next candidate
                              │
                              ▼  on accept
                       create trip (durable) ─► live-track both parties ─► price

Matching/dispatch. From the rider’s cell and its neighbor ring, gather available drivers, then rank by estimated time of arrival over the actual road network — straight-line distance is wrong (a driver across a river is “close” but 20 minutes away). Offer the best candidate; if they decline or time out, move to the next. Dispatch is a stateful, time-bounded negotiation, not a single query.

Surge pricing is supply-demand control made of geo cells. When open requests outstrip available drivers in a cell, the multiplier rises: it rations scarce supply toward those who value the ride most and signals drivers to move toward demand. Buys: the marketplace clears instead of everyone staring at “no cars available.” Costs: real user friction and, predictably, public-relations blowups when prices spike at the worst moment. The H3 grid is also why surge can be drawn as a smooth neighborhood-by-neighborhood heat map — adjacent hexagons are uniformly adjacent.

By the numbers — why locations live in memory, not a database

The firehose was ~1.25M writes/sec. Put each write through a durable, transactional table:

1.25M writes/sec, each updating a spatial index, each fsync-durable
  → a relational table with a spatial index simply cannot sustain this
in-memory grid (Redis GEO / in-process H3 buckets):
  → an update is "remove driver from old cell, add to new cell, refresh TTL" — microseconds, no disk

Driver location is ephemeral — a ping from 8 seconds ago is worthless, so there’s nothing to durably protect. Keeping the live index in memory buys you the throughput to absorb the firehose and millisecond proximity reads; it costs you durability you don’t need (a restarted node just waits one ping interval to refill) and the RAM to hold every active driver. Trips — the thing you bill and audit — do go in a durable database. Match the storage to what each piece of data is actually worth.

It actually happened — Uber’s surge during the 2014 Sydney siege

On 15 December 2014, during a hostage siege in Sydney’s Martin Place, people fleeing the CBD opened the Uber app and found surge pricing automatically engaged — the algorithm saw a spike in demand and raised the multiplier, exactly as designed, with no idea why demand had spiked. The backlash was immediate; Uber turned surge off for the area, offered free rides out of the zone, and refunded affected fares. The lesson is the thread of this page: surge buys a marketplace that clears under scarcity, but it costs you a system that prices a tragedy like a concert let-out unless humans (or guardrails) intervene. An automatic supply-demand control is only as humane as its caps and overrides.

Key trade-offs

• In-memory location index vs durable store: in-memory buys firehose throughput and fast proximity reads; it costs durability you don’t need for ephemeral pings (trips stay durable).
• Geohash vs QuadTree vs H3: geohash is simple and range-scannable but has the boundary problem; QuadTree adapts to density but is a tree to maintain; H3’s hexagons buy uniform adjacency and smooth gradients at the cost of 12 unavoidable pentagons and a library dependency.
• Road-network ETA vs straight-line distance: real ETA buys correct matches; it costs a routing computation per candidate.
• Surge on vs off: surge buys a clearing marketplace; it costs user trust and demands caps/overrides for emergencies.

Check your understanding

1. Why can’t an ordinary B-tree index answer “find drivers near this point” efficiently, and what do spatial indexes do instead?
2. Explain the geohash boundary problem and how a query works around it.
3. What property do hexagons (H3) have that squares lack, and why does it matter for proximity search and surge maps?
4. Why are driver locations kept in an in-memory index while trips go in a durable database?
5. What does surge pricing buy the marketplace and what does it cost — and what does the 2014 Sydney incident teach about automatic supply-demand control?

Show answers

1. A B-tree is one-dimensional, so a 2-D lat/lng query becomes two separate range scans you must intersect — a “near me” query degrades to scanning stripes of space. Spatial indexes instead map 2-D space onto a proximity-preserving 1-D key (geohash, H3, S2’s Hilbert curve) or recursively subdivide space (QuadTree), so “nearby” becomes “same/adjacent cell” — a cheap lookup.
2. A geohash shares a long prefix for nearby points, but two physically adjacent points can fall just across a cell edge and get completely different prefixes. So a proximity query must search the driver’s own cell plus its 8 neighboring cells, not just the matching prefix, or it would miss a car parked right across the boundary.
3. A hexagon has 6 neighbors all at the same distance, whereas a square has 4 edge-neighbors and 4 corner-neighbors at two different distances (ambiguous adjacency). Uniform adjacency makes “expand the search by one ring” clean for proximity queries and makes surge gradients smooth across neighboring cells. (The catch: you can’t tile a sphere with hexagons alone, so H3 has exactly 12 pentagons.)
4. Driver location is ephemeral — an 8-second-old ping is worthless — so there’s nothing to durably protect, and at ~1.25M writes/sec a durable spatial table can’t keep up. An in-memory grid updates in microseconds and serves millisecond proximity reads; a restarted node just refills on the next ping. Trips, which you bill and audit, are durable data and belong in a real database.
5. Surge buys a marketplace that clears under scarcity — rationing scarce cars toward those who value the ride most and signaling drivers toward demand, instead of everyone seeing “no cars available.” It costs real user friction. The 2014 Sydney siege showed the danger: the algorithm raised prices during a tragedy because it saw demand without context — so automatic supply-demand control needs caps and human overrides to stay humane.