Design Ride Sharing (Uber/Lyft)

1Requirements

2Back-of-envelope estimation

3API design

4High-level design

Both apps hold persistent WebSocket (or gRPC streaming) connections to a gateway fleet; a connection registry maps user -> gateway node so backend services can push to any client. Driver location updates arrive over these connections and are dropped onto a Kafka topic, giving one durable stream that fans out to every consumer that needs positions.

The location service consumes the stream and maintains the live index: for each geographic cell (geohash prefix or H3 cell), a Redis structure holds the set of available drivers with their latest coordinates. Updates overwrite in place, so the index stores only current state; a parallel consumer appends the full history to Cassandra for offline use.

When a ride is requested, the matching service computes the pickup's cell plus its neighbor ring (to avoid boundary misses), fetches candidate drivers from the index, filters by status and vehicle type, ranks by road-network ETA from the routing service rather than straight-line distance, and offers the trip to the best candidate with a ~10s TTL, cascading to the next on decline or timeout.

Trip state lives in a strongly consistent transactional store. Acceptance is an atomic conditional update (trip: matching -> matched, driver: available -> on_trip); whichever accept lands first wins and the loser gets a clean 'already taken' failure. This is the guardrail against double dispatch regardless of how racy the surrounding pipeline is.

The surge service consumes the same location stream plus the request stream, computes supply/demand ratios per cell per minute, and publishes multipliers to a cache read by the pricing service at quote time. The multiplier shown at request time is locked into the trip record so the fare cannot drift mid-ride.

5Data model

6Deep dives

7Rapid implementation: build the MVP

Theory is table stakes. Here is how you would stand up a working version fast, on a budget, with the core algorithm in real code.

1. 01Scaffold Express + Socket.IO with separate driver and rider namespaces; the driver app emits {lat, lng} every 4 seconds.
2. 02Store live locations in geohash-6 cell hashes in Redis with a 15s freshness window, plus a driver-to-cell reverse key so cell moves are a cheap two-key update.
3. 03Create a Postgres trips table with a status state machine: requested, matching, matched, in_progress, completed, cancelled.
4. 04Build POST /rides: quote fare as distance x rate x surge, insert the trip in 'matching', then query the pickup's cell plus its 8 neighbors for candidate drivers.
5. 05Rank candidates by haversine distance for the MVP, push an offer with a 10s TTL to the top driver's socket, and cascade to the next on decline or timeout.
6. 06Implement accept as a conditional UPDATE ... WHERE status = 'matching'; zero rows updated means someone else won, so tell the driver it is taken.
7. 07During the trip, relay the driver's position to the rider's socket and mark completion, computing the final fare from the frozen quote.
8. 08Surge MVP: a per-cell counter of open requests vs. available drivers per minute; multiplier = clamp(requests / max(drivers, 1), 1, 3), frozen into the quote.

import geohash from "ngeohash";

const PRECISION = 6; // roughly 1.2km x 0.6km cells
const FRESH_MS = 15_000;

export async function updateDriver(id: string, lat: number, lng: number) {
  const cell = geohash.encode(lat, lng, PRECISION);
  const prev = await redis.getset("drv:" + id, cell);
  if (prev && prev !== cell) await redis.hdel("cell:" + prev, id);
  await redis.hset(
    "cell:" + cell, id,
    JSON.stringify({ lat, lng, t: Date.now() })
  );
  await redis.expire("drv:" + id, 15); // dead apps vanish from matching
}

export async function nearbyDrivers(lat: number, lng: number) {
  const center = geohash.encode(lat, lng, PRECISION);
  const cells = [center, ...geohash.neighbors(center)]; // avoid edge misses
  const out: Array<{ id: string; lat: number; lng: number }> = [];
  for (const c of cells) {
    const members = await redis.hgetall("cell:" + c);
    for (const [id, raw] of Object.entries(members)) {
      const p = JSON.parse(raw);
      if (Date.now() - p.t < FRESH_MS) out.push({ id, lat: p.lat, lng: p.lng });
    }
  }
  return out;
}

function haversineKm(a: Pt, b: Pt) {
  const R = 6371, d = Math.PI / 180;
  const dLat = (b.lat - a.lat) * d, dLng = (b.lng - a.lng) * d;
  const h = Math.sin(dLat / 2) ** 2 +
    Math.cos(a.lat * d) * Math.cos(b.lat * d) * Math.sin(dLng / 2) ** 2;
  return 2 * R * Math.asin(Math.sqrt(h));
}

export async function matchRide(tripId: number, pickup: Pt) {
  const candidates = (await nearbyDrivers(pickup.lat, pickup.lng))
    .map((c) => ({ ...c, dist: haversineKm(pickup, c) }))
    .sort((x, y) => x.dist - y.dist)
    .slice(0, 5);
  for (const c of candidates) {
    const accepted = await offerWithTtl(c.id, tripId, 10_000);
    if (!accepted) continue; // decline or timeout: next candidate
    // atomic compare-and-set is the double-dispatch guardrail
    const res = await pool.query(
      "UPDATE trips SET status = 'matched', driver_id = $1 " +
      "WHERE id = $2 AND status = 'matching'",
      [c.id, tripId]
    );
    if (res.rowCount === 1) return c.id; // this accept won
  }
  return null; // no driver found; widen the search ring
}