Ride-Sharing Proximity Dispatch (Uber & Lyft)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

-- PostgreSQL Authoritative Trip Storage
CREATE TABLE trips (
    trip_id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    rider_id UUID NOT NULL,
    driver_id UUID NULL,                        -- Assigned after dispatch acceptance
    status VARCHAR(20) NOT NULL,                -- 'REQUESTED', 'OFFERED', 'ACCEPTED', 'COMPLETED'
    pickup_h3_index VARCHAR(15) NOT NULL,       -- H3 Resolution 8 index (e.g., '8828308281fffff')
    dropoff_h3_index VARCHAR(15) NOT NULL,
    pickup_latitude DOUBLE PRECISION NOT NULL,
    pickup_longitude DOUBLE PRECISION NOT NULL,
    dropoff_latitude DOUBLE PRECISION NOT NULL,
    dropoff_longitude DOUBLE PRECISION NOT NULL,
    surge_multiplier NUMERIC(3, 2) NOT NULL DEFAULT 1.00,
    fare_amount NUMERIC(10, 2) NULL,
    requested_at TIMESTAMP WITH TIME ZONE DEFAULT CURRENT_TIMESTAMP,
    completed_at TIMESTAMP WITH TIME ZONE NULL
);

CREATE INDEX idx_trips_rider ON trips (rider_id, requested_at DESC);
CREATE INDEX idx_trips_driver ON trips (driver_id, requested_at DESC) WHERE driver_id IS NOT NULL;

-- Redis Data Structures for Geospatial Tracking:
-- 1. Cell Member Set:
--    Key: h3:cell:8828308281fffff -> Set of driver_id { "drv_101", "drv_402" }
-- 2. Driver Location Hash:
--    Key: driver:drv_101 -> Hash { "lat": 37.7749, "lon": -122.4194, "cell": "8828308281fffff", "status": "AVAILABLE", "updated_at": 1718000000 }
-- 3. Surge Pricing State:
--    Key: surge:cell:8828308281fffff -> Hash { "multiplier": 1.8, "demand": 45, "supply": 12 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

// Production Geospatial Dispatch & Atomic Lock Reservation
import { latLngToCell, gridDisk } from 'h3-js';

export interface DriverCandidate {
  driverId: string;
  latitude: number;
  longitude: number;
  estimatedEtaSeconds: number;
}

export class ProximityDispatchEngine {
  constructor(
    private redisClient: RedisClient,
    private routingEngine: RoutingServiceClient
  ) {}

  async findAndLockNearestDriver(
    riderLat: number,
    riderLon: number,
    tripId: string
  ): Promise<DriverCandidate | null> {
    // 1. Convert rider GPS to H3 Resolution 8 Cell (~460m edge length)
    const centerCell = latLngToCell(riderLat, riderLon, 8);

    // 2. Expand K-Rings: Ring 0 (origin) + Ring 1 (6 cells) + Ring 2 (12 cells) = 19 cells
    const searchCells = gridDisk(centerCell, 2);

    // 3. Multi-get all available driver IDs residing in these 19 H3 cells
    const pipeline = this.redisClient.pipeline();
    for (const cell of searchCells) {
      pipeline.smembers(`h3:cell:${cell}`);
    }
    const results = await pipeline.exec();
    const candidateDriverIds: string[] = [];
    for (const [, drivers] of results ?? []) {
      if (Array.isArray(drivers)) candidateDriverIds.push(...drivers);
    }

    if (candidateDriverIds.length === 0) return null;

    // 4. Batch query Routing Engine for true road-network driving ETAs
    const candidateDetails = await this.fetchDriverCoords(candidateDriverIds);
    const rankedDrivers = await this.routingEngine.calculateEtas(
      { lat: riderLat, lon: riderLon },
      candidateDetails
    );
    rankedDrivers.sort((a, b) => a.estimatedEtaSeconds - b.estimatedEtaSeconds);

    // 5. Atomic Lock Reservation: Attempt to acquire lock on top candidate
    for (const driver of rankedDrivers) {
      // Redis SET NX with 15-second TTL ensures driver is only offered one ride at a time
      const acquired = await this.redisClient.set(
        `driver:lock:${driver.driverId}`,
        tripId,
        'NX',
        'EX',
        15
      );
      if (acquired === 'OK') {
        return driver; // Successfully locked driver for dispatch offer!
      }
      // If lock failed, driver was already offered another trip; try next candidate
    }
    return null;
  }
}