Ride hailing: build the design step by step

Part of the free System Design course on LogicWiz, in the chapter: Design ride hailing (Uber). The interactive whiteboard exercises and simulations run in the app.

Week 16, Day 3: Where does the driver's dot live?

"We asked the database for the nearest drivers. At rush hour it took four seconds, and the driver had already driven past."

A one-star review of the first prototype

Meera has the numbers. Now Kabir wants boxes. "Draw the simplest thing that could work. Break it with a number. Then fix only what broke."

The simplest design, and the number that breaks it

One app, one API server, one database. Each ping updates a row in a drivers table. A ride request runs a query for the nearest free drivers. It works for a demo with 50 drivers.

Now apply the numbers. Ten thousand writes per second is about 5 times what one primary does comfortably. The lookup must also finish in 50 ms while those writes pile up. The database fails first, and it fails on the least valuable data. A dot that is 5 seconds old is worth almost nothing. Nobody needs to save it forever.

Step 1: the latest position lives in memory

Move positions out of the database. A location service receives pings and keeps two small structures in an in-memory store. Together they are the geo index:

  • cell to drivers: each cell (a geohash or grid square, as in the geo lesson) holds the ids of drivers inside it.
  • driver to record: the latest latitude, longitude, status and time.

A ping writes the driver's record. If the driver moved into a new cell, it also removes the id from the old cell and adds it to the new one. One node of an in-memory store typically handles tens of thousands of simple updates per second, so 10,000 is comfortable, and sharding by city spreads it further. Each record expires after about 30 seconds. A dead phone leaves the map by itself.

Shard the index by city. Bengaluru never needs Delhi's drivers, and one city's failure stays in that city.

Two details separate good answers from great ones.

The boundary problem. A driver 80 metres from the pickup can sit in the next cell. So a lookup reads the pickup cell and the ring of cells around it. If it finds fewer than about 10 free drivers, it widens by one ring, up to a cap such as 3 km. In a hexagon grid, all six neighbours of a cell are the same distance away, so each ring widens the search more evenly than square cells do. Then it filters by exact distance and ranks by road ETA, not straight-line distance. A river changes everything.

The same problem exists between shards. A pickup in Noida, 1 km from the Delhi border, also asks the Delhi shard.

Cells are hints; the record is the truth. A driver crossing a border is removed from one set and added to another in two steps. A crash between them leaves the id in two cells. So the lookup reads each driver's record, then drops anyone older than 30 seconds or whose record names a different cell.

💡 Tip: Say the trade-off. The index is fast because it is soft state. You accept that a crash loses it, and you rely on the next 5 seconds of pings to refill it.

Step 2: history leaves the hot path, and sockets carry the traffic

The index holds only the latest position. Riders need to watch the cab move, and the company needs history. So the location service also appends each ping to a location stream, an ordered log that many readers can follow. Two readers matter: the gateway that sends positions to riders, and a job that copies pings to cold storage. Neither blocks the ping.

The realtime gateway holds the WebSocket connections. At peak that is 50,000 drivers plus up to 50,000 riders on trips: about 100,000 open connections. Six gateway instances share it at roughly 17,000 each, a load that servers built to hold connections handle. A load balancer spreads new connections.

Why not let drivers poll for offers? If 50,000 drivers ask "any offer?" every 2 seconds, that is 25,000 requests per second, nearly all empty. An offer would still wait up to 2 seconds. A pushed offer arrives at once. If the driver app is in the background, matching also sends a phone push notification.

Step 3: matching and the trip

Ride requests are only 120 per second, so this path can be careful. The ride service owns the trip's states and talks to the rides database, which is SQL. Accepting a ride changes a ride row and a driver row together, and SQL gives you one transaction for both. The matching service does the finding: ask the geo index for free drivers, rank them, offer the ride to the best one and wait.

How heavy is it? Count the worst case. A ride row, up to 3 offer rows, 3 drivers set to OFFERED, 2 of them set back to AVAILABLE, and the accept: about 10 small writes. At 120 rides per second that is about 1,200 writes per second. One primary handles about 2,000 comfortably, and most rides need fewer offers. Run three database instances so one failure does not stop trips.

Meera expected the geo index to decide who is free. It cannot. The index is soft state and can be a few seconds wrong. The assignment itself lives in the rides database, and the next lesson shows how.

One ride, end to end

sequenceDiagram
  participant D as Driver app
  participant G as Gateway
  participant L as Location svc
  participant X as Geo index
  participant R as Rider app
  participant S as Ride svc
  participant M as Matching
  participant B as Rides DB
  D->>G: ping every 5 s
  G->>L: location
  L->>X: update cell and record
  R->>S: POST /rides
  S->>B: ride = MATCHING
  S->>M: find a driver
  M->>X: free drivers near pickup
  M->>B: driver AVAILABLE to OFFERED
  M->>G: offer to driver
  D->>S: accept
  S->>B: ride ASSIGNED, driver ON_TRIP
  G-->>R: driver position and ETA

Read it as two lines. The ping line runs 10,000 times per second and never touches the database. The ride line runs 120 times per second and touches only the index and the database. Now build it.

📌 Summary: Start with one database, then break it with 10,000 writes per second. Live positions go to a sharded in-memory geo index with a TTL, history to a stream, and trips to SQL. Sockets push offers.

What Meera learns next

The boxes stand. Now the hard parts: how to offer a ride, how to stop two riders getting the same driver, and what happens when the location service dies.

Check your understanding

  1. A driver is 80 metres from the pickup point, but the pickup lookup reads only the pickup's own cell. The driver sits just across a cell border. What happens, and what is the fix?
  2. Why does every driver record in the geo index expire after about 30 seconds?
  3. A teammate wants driver apps to poll an HTTP endpoint for offers every 2 seconds instead of keeping a WebSocket. With 50,000 drivers online, what is the cost?
  4. The matching service reads the geo index and sees driver D marked AVAILABLE. Where should the system decide that D now belongs to this ride?