Skip to content
Tutorials Center
My learning

Topics

Lesson 56 of 65 ยท Case Studies: Classic Designs

Design a Ride-Sharing Service (Uber-style)

Design a ride-hailing service: driver location updates, geohash and quadtree indexes, nearest-driver search, matching, trip state machine and surge pricing, with Python.

A ride-sharing app connects riders with nearby drivers in seconds. The system is dominated by location: millions of drivers send their position every few seconds, and each ride request asks "who is near this point right now?". That makes this case study the standard lesson in geospatial indexing, plus a good example of a real-time matching workflow and a trip state machine.

Requirements

  • Riders request a trip from A to B and see nearby drivers, a price estimate and an ETA.
  • The system matches the rider with a suitable nearby driver, who accepts or declines.
  • Both parties see each other's live location during the trip.
  • Payment at the end, ratings, and trip history.
  • Scale: 100 million riders, 5 million drivers, 1 million concurrent drivers online, 20 million trips per day.

Estimates: if each online driver sends a location update every 4 seconds, 1 million drivers produce 250,000 updates per second. Twenty million trips per day is only about 230 requests per second on average (peaks maybe 2,000), so searches are modest and location writes are the heavy path.

Location updates

Driver apps send {driver_id, lat, lng, status, timestamp} over a persistent connection or lightweight UDP/HTTP. Each update overwrites the driver's current position, so it belongs in a fast in-memory store, not a disk database. A separate stream copies updates to a history store (for analytics and trip replay).

flowchart LR
    D["Driver app"] --> LG["Location gateway"]
    LG --> LS[("In-memory location index")]
    LG --> K["Event stream"] --> H[("History / analytics")]
    R["Rider request"] --> TS["Trip service"]
    TS --> MS["Matching service"]
    MS --> LS
    MS --> D
    TS --> PS["Pricing"] 
    TS --> TDB[("Trip database")]

The location index is rewritten constantly and read for matching.

Finding nearby drivers: geospatial indexes

Scanning every driver per request is too slow. Common indexes:

  • Geohash: encode a location as a string where nearby places share a prefix (9q8yy covers a small rectangle). A grid of fixed cells: to find nearby drivers, look in the rider's cell and its 8 neighbours.
  • Quadtree: recursively split the map into four quadrants, subdividing busy areas more finely (a dense city center gets small cells, a desert large ones).
  • H3 hexagons (used by large providers): a hierarchical grid of hexagons, which have uniform neighbour distances.
Python A grid index for nearest drivers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Distances are in kilometres. Moving a driver is just removing it from one cell set and adding it to another, which is why this structure handles 250,000 updates per second when sharded by region.

Matching

Matching is not simply "nearest wins". The service takes candidate drivers from nearby cells and ranks them by ETA (road distance, not straight line, using a routing service), driver rating, vehicle type, and whether they are heading toward the pickup. It then offers the trip to the best driver with a short timeout (say 10 seconds). If the driver declines or times out, it offers to the next. Each driver must receive only one offer at a time, and each rider must be matched to only one driver, which needs a lock or atomic state change per driver.

Python Offer, timeout and next driver

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The trip state machine

A trip moves through well-defined states: REQUESTED -> MATCHING -> DRIVER_ASSIGNED -> DRIVER_ARRIVED -> IN_PROGRESS -> COMPLETED, with CANCELLED possible before pickup. Each transition is validated and saved with a version number (so two concurrent actions cannot both succeed) and published as an event that triggers notifications, pricing and payment. A trip table sharded by trip ID, with the active trip also cached in memory, keeps this fast and consistent.

Pricing, ETA and surge

  • Fare estimate: base fee + distance + time, multiplied by a surge factor.
  • Surge: compute demand versus supply per area every minute. If requests in a cell outnumber free drivers, raise the multiplier, which both attracts drivers and cools demand. Smooth the values to avoid flicker.
  • ETA and routing: a routing engine over road graphs with live traffic; cache popular routes and precompute.
  • Live tracking during a trip: stream the driver's location to the rider's phone over WebSockets.
  • Reliability: if the matching service crashes mid-offer, the trip state machine and a timeout sweep recover orphaned offers.
  • Fraud and safety: share-trip features, route-deviation alerts and anomaly detection.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which path dominates load in a ride-sharing backend?

    A million drivers sending positions every few seconds create hundreds of thousands of writes per second.
  2. 2. Why search the rider's cell and its 8 neighbours in a grid index?

    The nearest driver may be in an adjacent cell, so the search must include them.
  3. 3. What is the benefit of a quadtree over a fixed grid?

    A dense area split into smaller cells keeps each lookup small.
  4. 4. Why must a driver be reserved while an offer is pending?

    An atomic reservation prevents double matching.

Summary

  • Location updates are the write-heavy path; keep current positions in an in-memory index and stream history separately.
  • Geohash grids, quadtrees and hexagon grids find nearby drivers without scanning everyone.
  • Matching ranks by ETA and quality, offers to one driver at a time and uses atomic reservations.
  • A trip is a versioned state machine whose transitions emit events.
  • Surge pricing balances supply and demand per area.

Next: Design a Payment System