Design a Ride-Hailing Match

// Dispatch offers a trip to one driver at a time. The lease is the only thing
// stopping two riders from both receiving an accept from the same car.
const OFFER_TTL_S = 12; // the driver has 12 seconds to tap accept

async function tryOffer(tripId, driverId) {
  // SET key value NX EX n is the atomic claim: NX means only-if-absent, EX sets
  // the expiry in the same command. The longhand pair SETNX + EXPIRE is two
  // round trips and leaves an eternal lease if the process dies between them.
  const ok = await redis.set(`driver:lease:${driverId}`, tripId, {
    NX: true,
    EX: OFFER_TTL_S,
  });
  if (ok !== 'OK') return false; // already offered this trip or another one

  await pushToDriverApp(driverId, { type: 'offer', tripId, expiresInMs: OFFER_TTL_S * 1000 });
  return true;
}

// Only the lease holder may release it. A decline that arrives late, for a trip
// the driver was offered two trips ago, must not free the current lease.
const RELEASE = `
  if redis.call('GET', KEYS[1]) == ARGV[1] then
    return redis.call('DEL', KEYS[1])
  else
    return 0
  end`;

async function release(driverId, tripId) {
  await redis.eval(RELEASE, {
    keys: [`driver:lease:${driverId}`],
    arguments: [tripId],
  });
}

// Walk the shortlist in ETA order. Each miss costs one offer window, which is
// why the shortlist is ranked before any offer goes out, not after.
export async function dispatch(tripId, shortlist) {
  for (const driverId of shortlist) {
    if (!(await tryOffer(tripId, driverId))) continue;
    const answer = await waitForAnswer(tripId, driverId, OFFER_TTL_S * 1000);
    if (answer === 'accepted') return driverId;
    await release(driverId, tripId); // declined, or the window lapsed
  }
  return null; // no driver: widen the radius, or tell the rider honestly
}

// Every legal edge, written down once. Anything not listed here is rejected,
// which is cheaper than discovering at 02:00 that a trip went from completed
// back to in_progress.
const ALLOWED = {
  requested:   ['offered', 'cancelled'],
  offered:     ['accepted', 'requested', 'cancelled'], // back to requested on decline
  accepted:    ['arrived', 'cancelled'],
  arrived:     ['in_progress', 'cancelled'],
  in_progress: ['completed'],       // no cancel once the rider is in the car
  completed:   [],
  cancelled:   [],
};

// States a given transition is legal FROM, derived rather than written twice.
function statesLeadingTo(to) {
  return Object.entries(ALLOWED)
    .filter(([, nexts]) => nexts.includes(to))
    .map(([state]) => state);
}

// The guard lives in the WHERE clause, so concurrent events cannot interleave
// into an illegal state no matter how many dispatch workers are running.
export async function applyTransition({ tripId, to, eventSeq }) {
  const { rows } = await pool.query(
    `UPDATE trips
        SET state = $2, last_event_seq = $3, updated_at = now()
      WHERE id = $1
        AND state = ANY($4::text[])   -- legal from the CURRENT state only
        AND last_event_seq < $3       -- drops duplicates and reordered events
    RETURNING state`,
    [tripId, to, eventSeq, statesLeadingTo(to)]
  );

  if (rows.length === 0) {
    // Not an error and not retryable: the phone sent a stale or duplicate
    // event. Count it so a rising rate is visible, and return success.
    metrics.increment('trip.transition.ignored', { to });
    return null;
  }
  return rows[0].state;
}

import * as h3 from 'h3-js'; // v4; see h3-js/legacy for the v3 names

const lat = 37.7749, lng = -122.4194;

const cell = h3.latLngToCell(lat, lng, 8); // resolution 8, average ~0.74 km2
const ring1 = h3.gridDisk(cell, 1);        // 7 cells: the centre plus 6 neighbours
const ring2 = h3.gridDisk(cell, 2);        // 19 cells, for a sparse area

// Exact area of THIS cell, since cells are not perfectly uniform:
// h3.cellArea(cell, 'km2')

// Reading older code? The v3 spellings you will meet:
//   geoToH3     -> latLngToCell
//   h3ToGeo     -> cellToLatLng
//   kRing       -> gridDisk
//   h3ToParent  -> cellToParent
// Same functions, renamed in H3 4.0.0.

// The hierarchy is what makes the cell a useful shard key. A coarse ancestor
// groups a neighbourhood, so all dispatch decisions for one area are handled by
// one worker - and contention for a driver is resolved locally rather than
// across the fleet.
export function dispatchShard(lat, lng, shardCount) {
  // Each resolution step up multiplies cell area by about 7, so two steps is
  // roughly 49x: res 8 averages 0.74 km2, res 6 averages 36 km2.
  const coarse = h3.cellToParent(h3.latLngToCell(lat, lng, 8), 6); // ~49x larger
  // Hash the cell id, do not modulo it: H3 indexes are not evenly distributed.
  let hash = 0;
  for (const ch of coarse) hash = (hash * 31 + ch.charCodeAt(0)) | 0;
  return Math.abs(hash) % shardCount;
}

// The boundary case this creates: a rider at the edge of a coarse cell has
// candidate drivers in the neighbouring shard. Either let the shard read
// (not write) its neighbours' supply, or accept slightly worse matches at
// boundaries. Pick deliberately, because the symptom - long waits on one
// street - looks like a routing bug.