Design Uber-Style Ride Hailing

3 collapsed lines
1
// Headers
2
Authorization: Bearer {access_token}
3
Content-Type: application/json
4

5
// Request body
6
{
7
  "pickup": {
8
    "latitude": 37.7749,
9
    "longitude": -122.4194,
10
    "address": "123 Market St, San Francisco, CA"
11
  },
12
  "destination": {
13
    "latitude": 37.7899,
14
    "longitude": -122.4014,
15
    "address": "456 Mission St, San Francisco, CA"
16
  },
17
  "vehicleType": "UBER_X",
18
  "paymentMethodId": "pm_abc123",
19
  "riderCount": 1,
20
  "scheduledTime": null
21
}

5 collapsed lines
1
{
2
  "rideId": "ride_abc123xyz",
3
  "status": "REQUESTED",
4
  "pickup": {
5
    "latitude": 37.7749,
6
    "longitude": -122.4194,
7
    "address": "123 Market St, San Francisco, CA"
8
  },
9
  "destination": {
10
    "latitude": 37.7899,
11
    "longitude": -122.4014,
12
    "address": "456 Mission St, San Francisco, CA"
13
  },
14
  "estimate": {
15
    "fareAmount": 1850,
16
    "fareCurrency": "USD",
17
    "surgeMultiplier": 1.2,
18
    "distanceMeters": 2100,
19
    "durationSeconds": 480
20
  },
21
  "etaToPickup": null,
22
  "driver": null,
23
  "vehicle": null,
24
  "createdAt": "2024-01-15T14:30:00Z"
25
}

1
// Client → Server (every 4-5 seconds)
2
{
3
  "type": "LOCATION_UPDATE",
4
  "payload": {
5
    "latitude": 37.7751,
6
    "longitude": -122.4183,
7
    "heading": 45,
8
    "speed": 12.5,
9
    "accuracy": 5.0,
10
    "timestamp": 1705329000000
11
  }
12
}
13

14
// Server → Client (acknowledgment)
15
{
16
  "type": "LOCATION_ACK",
17
  "payload": {
18
    "received": 1705329000123
19
  }
20
}

3 collapsed lines
1
{
2
  "drivers": [
3
    {
4
      "driverId": "driver_xyz",
5
      "latitude": 37.7755,
6
      "longitude": -122.418,
7
      "heading": 90,
8
      "vehicleType": "UBER_X",
9
      "etaSeconds": 180
10
    },
11
    {
12
      "driverId": "driver_abc",
13
      "latitude": 37.774,
14
      "longitude": -122.42,
15
      "heading": 270,
16
      "vehicleType": "UBER_X",
17
      "etaSeconds": 240
18
    }
19
  ],
3 collapsed lines
20
  "surgeMultiplier": 1.2,
21
  "surgeExpiresAt": "2024-01-15T14:35:00Z"
22
}

1
{
2
  "multiplier": 1.5,
3
  "reason": "HIGH_DEMAND",
4
  "h3Cell": "892a100d2c3ffff",
5
  "expiresAt": "2024-01-15T14:40:00Z",
6
  "demandLevel": "VERY_HIGH",
7
  "supplyLevel": "LOW"
8
}

5 collapsed lines
1
-- Schemaless stores data as (row_key, column_name, ref_key) tuples
2
-- row_key: trip_id (UUID)
3
-- column_name: "base", "driver", "route", "payment", etc.
4
-- ref_key: version number
5
-- body: BLOB (protobuf-serialized data)
6

7
CREATE TABLE trips (
8
    added_id BIGINT AUTO_INCREMENT PRIMARY KEY,  -- Total ordering
9
    row_key BINARY(16) NOT NULL,                  -- trip_id as UUID
10
    column_name VARCHAR(64) NOT NULL,
11
    ref_key BIGINT NOT NULL,                      -- Version/timestamp
12
    body MEDIUMBLOB NOT NULL,
13
    created_at DATETIME NOT NULL,
14

15
    INDEX idx_row_column (row_key, column_name, ref_key DESC)
16
);

1
-- Driver profile and state (high availability)
2
CREATE TABLE driver_state (
3
    driver_id UUID,
4
    city_id INT,
5
    status TEXT,           -- OFFLINE, AVAILABLE, DISPATCHED, ON_TRIP
6
    vehicle_id UUID,
7
    current_trip_id UUID,
8
    last_location_update TIMESTAMP,
9
    rating DECIMAL,
10
    total_trips INT,
11
    acceptance_rate DECIMAL,
12
    PRIMARY KEY ((city_id), driver_id)
13
) WITH CLUSTERING ORDER BY (driver_id ASC);
14

15
-- Per-driver time series (write-heavy)
16
CREATE TABLE driver_locations (
17
    driver_id UUID,
18
    day DATE,
19
    timestamp TIMESTAMP,
20
    latitude DOUBLE,
21
    longitude DOUBLE,
22
    h3_cell TEXT,
23
    speed DOUBLE,
24
    heading INT,
25
    PRIMARY KEY ((driver_id, day), timestamp)
26
) WITH CLUSTERING ORDER BY (timestamp DESC);

1
Square grid (geohash):           Hexagonal grid (H3):
2

3
+---+---+---+                    / \ / \ / \
4
| A | B | C |                   |   |   |   |
5
+---+---+---+    →              | A | B | C |
6
| D | X | E |                   |   |   |   |
7
+---+---+---+                    \ / \ / \ /
8
| F | G | H |                     |   |   |
9
+---+---+---+                     | D | E |
10

11
Distances from X:                 Distances from X:
12
  - A,C,F,H: √2 (diagonal)          - All 6 neighbors: 1 (uniform!)
13
  - B,D,E,G: 1 (cardinal)

8 collapsed lines
1
import h3 from "h3-js"
2

3
// Convert lat/lng to H3 cell at resolution 9
4
function locationToH3(lat: number, lng: number): string {
5
  return h3.latLngToCell(lat, lng, 9)
6
  // Returns: "89283082837ffff" (64-bit as hex string)
7
}
8

9
// Get all H3 cells within radius (k-ring)
10
function getCellsInRadius(centerH3: string, radiusKm: number): string[] {
11
  // k=1 ≈ 300m, k=3 ≈ 1km, k=10 ≈ 3km at resolution 9
12
  const k = Math.ceil(radiusKm / 0.17) // 170m per cell at res 9
13
  return h3.gridDisk(centerH3, k)
14
  // Returns all cells within k "rings" of center
15
}
16

17
// Example: Find drivers within 2km of pickup
18
function findNearbyDrivers(pickupLat: number, pickupLng: number, radiusKm: number = 2): Promise<Driver[]> {
19
  const centerCell = locationToH3(pickupLat, pickupLng)
20
  const searchCells = getCellsInRadius(centerCell, radiusKm)
21

22
  // Query Redis for drivers in each cell
23
  // Using pipelining for efficiency
24
  const pipeline = redis.pipeline()
25
  for (const cell of searchCells) {
26
    pipeline.zrange(`drivers:h3:${cell}`, 0, -1)
27
  }
28

29
  const results = await pipeline.exec()
30
  const driverIds = new Set(results.flat().filter(Boolean))
31
  return fetchDriverDetails([...driverIds])
32
}

10 collapsed lines
1
interface RideRequest {
2
  rideId: string
3
  pickupH3: string
4
  pickupLat: number
5
  pickupLng: number
6
  requestTime: number
7
}
8

9
interface DriverCandidate {
10
  driverId: string
11
  h3Cell: string
12
  lat: number
13
  lng: number
14
  etaSeconds: number // To pickup
15
}
16

17
// Batch window: accumulate requests for 100-200ms
18
class MatchingBatcher {
19
  private pendingRequests: RideRequest[] = []
20
  private batchInterval = 150 // ms
21

22
  constructor() {
23
    setInterval(() => this.processBatch(), this.batchInterval)
24
  }
25

26
  addRequest(request: RideRequest) {
27
    this.pendingRequests.push(request)
28
  }
29

30
  private async processBatch() {
31
    if (this.pendingRequests.length === 0) return
32

33
    const requests = this.pendingRequests
34
    this.pendingRequests = []
35

36
    // 1. Find candidate drivers for all requests
37
    const candidatesMap = await this.findCandidatesForAll(requests)
38

39
    // 2. Build bipartite graph
40
    const graph = this.buildBipartiteGraph(requests, candidatesMap)
41

42
    // 3. Solve assignment (minimize total ETA)
43
    const assignments = this.solveAssignment(graph)
44

6 collapsed lines
45
    // 4. Dispatch drivers
46
    for (const { rideId, driverId, eta } of assignments) {
47
      await this.dispatchDriver(rideId, driverId, eta)
48
    }
49
  }
50
}

5 collapsed lines
1
// Cost matrix: riders × drivers
2
// cost[i][j] = ETA for driver j to reach rider i's pickup
3
// Use Infinity for infeasible pairs (driver too far)
4

5
function solveAssignment(requests: RideRequest[], candidates: Map<string, DriverCandidate[]>): Assignment[] {
6
  const n = requests.length
7
  const allDrivers = new Set<string>()
8
  candidates.forEach((c) => c.forEach((d) => allDrivers.add(d.driverId)))
9
  const m = allDrivers.size
10
  const driverList = [...allDrivers]
11

12
  // Build cost matrix
13
  const cost: number[][] = Array(n)
14
    .fill(null)
15
    .map(() => Array(m).fill(Infinity))
16

17
  for (let i = 0; i < n; i++) {
18
    const rideCandidates = candidates.get(requests[i].rideId) ?? []
19
    for (const candidate of rideCandidates) {
20
      const j = driverList.indexOf(candidate.driverId)
21
      cost[i][j] = candidate.etaSeconds
22
    }
23
  }
24

25
  // Hungarian algorithm: O(n³)
26
  // For large scale, use auction algorithm or relaxation-based approximations
27
  const assignments = hungarianAlgorithm(cost)
28

29
  return assignments.map(([i, j]) => ({
30
    rideId: requests[i].rideId,
31
    driverId: driverList[j],
32
    eta: cost[i][j],
33
  }))
34
}

1
                    ┌─────────────────┐
2
                    │  Road Network   │
3
                    │  Graph (OSM)    │
4
                    └────────┬────────┘
5
                             │
6
    Pickup/Destination ──────┼──────────────┐
7
                             │              │
8
                             ▼              ▼
9
                    ┌─────────────────┐ ┌─────────────────┐
10
                    │ Routing Engine  │ │  DeepETA Model  │
11
                    │ (Dijkstra/A*)   │ │ (Linear Transf) │
12
                    └────────┬────────┘ └────────┬────────┘
13
                             │                   │
14
                             ▼                   ▼
15
                    Physics-based ETA    ML Residual (R)
16
                          (Y)
17
                             │                   │
18
                             └───────┬───────────┘
19
                                     │
20
                                     ▼
21
                            Final ETA = Y + R

5 collapsed lines
1
interface ETAFeatures {
2
  // Spatial features
3
  originH3: string
4
  destH3: string
5
  routeH3Cells: string[] // H3 cells along route
6

7
  // Temporal features
8
  hourOfDay: number // 0-23
9
  dayOfWeek: number // 0-6
10
  isHoliday: boolean
11
  minutesSinceMidnight: number
12

13
  // Traffic features
14
  currentTrafficIndex: number // 0-1 (free flow to gridlock)
15
  historicalTrafficIndex: number // Same time last week
16
  trafficTrend: number // Improving/worsening
17

18
  // Route features
19
  distanceMeters: number
20
  numIntersections: number
21
  numHighwaySegments: number
22
  routingEngineETA: number // Physics-based baseline
23

24
  // Weather (optional)
25
  precipitation: number
26
  visibility: number
27
}
28

29
// Model inference
7 collapsed lines
30
async function predictETA(features: ETAFeatures): Promise<number> {
31
  // Call ML serving layer (Michelangelo)
32
  const residual = await mlClient.predict("deepeta", features)
33

34
  // Final ETA = routing engine + ML residual
35
  return features.routingEngineETA + residual
36
}

8 collapsed lines
1
interface SurgeCell {
2
  h3Cell: string // Resolution 7 (larger area)
3
  demandCount: number // Ride requests in last 5 minutes
4
  supplyCount: number // Available drivers
5
  multiplier: number // Calculated surge
6
  updatedAt: number
7
}
8

9
// Calculate surge for each H3 cell
10
async function calculateSurge(cityId: string): Promise<Map<string, SurgeCell>> {
11
  const cells = new Map<string, SurgeCell>()
12

13
  // Get H3 cells for the city (resolution 7, ~5km² each)
14
  const cityCells = getCityH3Cells(cityId, 7)
15

16
  for (const h3Cell of cityCells) {
17
    // Count requests in this cell (last 5 minutes)
18
    const demandCount = (await redis.get(`demand:${h3Cell}:5min`)) || 0
19

20
    // Count available drivers in this cell
21
    const childCells = h3.cellToChildren(h3Cell, 9) // Expand to res 9
22
    let supplyCount = 0
23
    for (const child of childCells) {
24
      supplyCount += await redis.scard(`drivers:h3:${child}:available`)
25
    }
26

27
    // Calculate multiplier
28
    const ratio = supplyCount > 0 ? demandCount / supplyCount : 10
29
    const multiplier = calculateMultiplier(ratio)
30

31
    cells.set(h3Cell, {
32
      h3Cell,
33
      demandCount,
34
      supplyCount,
35
      multiplier,
36
      updatedAt: Date.now(),
37
    })
38
  }
39

11 collapsed lines
40
  return cells
41
}
42

43
function calculateMultiplier(demandSupplyRatio: number): number {
44
  // Piecewise linear function
45
  // ratio < 0.5: no surge (1.0x)
46
  // ratio 0.5-1.0: linear 1.0x-1.5x
47
  // ratio 1.0-2.0: linear 1.5x-2.5x
48
  // ratio > 2.0: cap at 3.0x (regulatory/PR limits)
49

50
  if (demandSupplyRatio < 0.5) return 1.0
51
  if (demandSupplyRatio < 1.0) return 1.0 + (demandSupplyRatio - 0.5)
52
  if (demandSupplyRatio < 2.0) return 1.5 + (demandSupplyRatio - 1.0)
53
  return Math.min(3.0, 1.5 + demandSupplyRatio - 1.0)
54
}

5 collapsed lines
1
// Exponential moving average to prevent jarring jumps
2
function smoothSurge(
3
  currentMultiplier: number,
4
  previousMultiplier: number,
5
  alpha: number = 0.3, // Smoothing factor
6
): number {
7
  // New surge = α × current + (1-α) × previous
8
  const smoothed = alpha * currentMultiplier + (1 - alpha) * previousMultiplier
9

10
  // Also limit change rate (max ±0.3 per update)
11
  const maxDelta = 0.3
12
  const delta = smoothed - previousMultiplier
13
  if (Math.abs(delta) > maxDelta) {
14
    return previousMultiplier + Math.sign(delta) * maxDelta
15
  }
16

17
  return smoothed
18
}

10 collapsed lines
1
// Instead of updating each marker individually,
2
// batch updates and render to canvas overlay
3

4
class DriverMapLayer {
5
  private canvas: HTMLCanvasElement
6
  private drivers: Map<string, DriverPosition> = new Map()
7
  private pendingUpdates: DriverPosition[] = []
8
  private rafId: number | null = null
9

10
  // Buffer updates, render on next animation frame
11
  updateDriver(position: DriverPosition) {
12
    this.pendingUpdates.push(position)
13

14
    if (!this.rafId) {
15
      this.rafId = requestAnimationFrame(() => this.render())
16
    }
17
  }
18

19
  private render() {
20
    // Apply all pending updates
21
    for (const update of this.pendingUpdates) {
22
      this.drivers.set(update.driverId, update)
23
    }
24
    this.pendingUpdates = []
25
    this.rafId = null
26

27
    // Clear and redraw all drivers
28
    const ctx = this.canvas.getContext("2d")!
29
    ctx.clearRect(0, 0, this.canvas.width, this.canvas.height)
30

31
    for (const driver of this.drivers.values()) {
32
      this.drawDriver(ctx, driver)
33
    }
34
  }
11 collapsed lines
35

36
  private drawDriver(ctx: CanvasRenderingContext2D, driver: DriverPosition) {
37
    const [x, y] = this.latLngToPixel(driver.lat, driver.lng)
38
    // Draw car icon rotated to heading
39
    ctx.save()
40
    ctx.translate(x, y)
41
    ctx.rotate((driver.heading * Math.PI) / 180)
42
    ctx.drawImage(this.carIcon, -12, -12, 24, 24)
43
    ctx.restore()
44
  }
45
}

5 collapsed lines
1
// State machine for ride lifecycle
2
type RideStatus =
3
  | "IDLE"
4
  | "REQUESTING"
5
  | "MATCHING"
6
  | "DRIVER_ASSIGNED"
7
  | "DRIVER_ARRIVING"
8
  | "DRIVER_ARRIVED"
9
  | "IN_PROGRESS"
10
  | "COMPLETED"
11
  | "CANCELLED"
12

13
interface RideState {
14
  status: RideStatus
15
  ride: Ride | null
16
  driver: Driver | null
17
  driverLocation: LatLng | null
18
  etaSeconds: number | null
19
  route: LatLng[] | null
20
}
21

22
// WebSocket message handler
23
function handleRideUpdate(state: RideState, message: WSMessage): RideState {
24
  switch (message.type) {
25
    case "DRIVER_ASSIGNED":
26
      return {
27
        ...state,
28
        status: "DRIVER_ASSIGNED",
29
        driver: message.driver,
30
        etaSeconds: message.eta,
31
      }
32

33
    case "DRIVER_LOCATION":
34
      return {
11 collapsed lines
35
        ...state,
36
        driverLocation: message.location,
37
        etaSeconds: message.eta,
38
        status: message.eta < 60 ? "DRIVER_ARRIVED" : state.status,
39
      }
40

41
    case "TRIP_STARTED":
42
      return {
43
        ...state,
44
        status: "IN_PROGRESS",
45
        route: message.route,
46
      }
47

48
    case "TRIP_COMPLETED":
49
      return {
50
        ...state,
51
        status: "COMPLETED",
52
        ride: { ...state.ride!, fare: message.fare },
53
      }
54

55
    default:
56
      return state
57
  }
58
}

5 collapsed lines
1
// Queue ride request locally if offline
2
class RideRequestQueue {
3
  private queue: RideRequest[] = []
4

5
  async requestRide(request: RideRequest): Promise<void> {
6
    if (!navigator.onLine) {
7
      // Store locally
8
      this.queue.push(request)
9
      localStorage.setItem("pendingRides", JSON.stringify(this.queue))
10
      throw new OfflineError("Ride queued, will submit when online")
11
    }
12

13
    return this.submitRide(request)
14
  }
15

16
  // Called when connectivity restored
17
  async processQueue(): Promise<void> {
18
    const pending = [...this.queue]
19
    this.queue = []
20

21
    for (const request of pending) {
22
      try {
23
        await this.submitRide(request)
24
      } catch (e) {
25
        // Re-queue if still failing
26
        this.queue.push(request)
27
      }
28
    }
29

8 collapsed lines
30
    localStorage.setItem("pendingRides", JSON.stringify(this.queue))
31
  }
32
}
33

34
// Listen for online event
35
window.addEventListener("online", () => {
36
  rideQueue.processQueue()
37
})