This lesson opens Chapter 9 (Part II, Production System Blueprints) and covers sections 1 to 3. It continues in Ride Dispatch: Spatial Indexing, Batch Matching, and Deep Dives.

Chapter 9: Real-Time Ride Dispatch & Geospatial Matching

Production System Blueprint 6: High-Frequency GPS Telemetry, Uber H3 Hexagonal Spatial Indexing, and Global Bipartite Batch Matching

At a glance

1. The Scenario & Problem Framing

PROMPT:

"Design a real-time ride-sharing and on-demand delivery dispatch engine (like Uber, Lyft, or DoorDash) operating at major metropolitan scale.

The platform must track 100,000 concurrently active drivers transmitting GPS telemetry every 3 to 4 seconds (33,000 writes/second) with sub-50ms ingestion latency.

The system must match incoming ride requests and food delivery orders to drivers within a 2-second global optimization window, minimize average customer waiting time (p90 < 4 minutes), calculate dynamic surge pricing per micro-neighborhood, and prevent concurrent double-dispatch without freezing during peak rush-hour demand bursts."

In standard e-commerce platforms, resources are static: a product sits on a warehouse shelf with a fixed barcode, and inventory is decremented in a relational database row.

In on-demand transportation and logistics platforms, every resource is in constant, unpredictable physical motion:

• Supply (drivers, couriers) moves through physical space along a constrained topological road network at variable speeds dictated by traffic, weather, and traffic lights.
• Demand (riders, restaurant orders) appears unpredictably in time and space, with tight temporal tolerance: if a ride is not confirmed within 15 seconds, the customer closes the app and opens a competing ride-share service.
• Physical space is non-Euclidean: two vehicles separated by 100 meters across a river may require a 25-minute drive across the nearest bridge.

Designing a system to solve this real-time matching problem at metropolitan scale exposes four severe architectural traps:

1. The Greedy Nearest-Driver Trap: Junior engineers instinctively implement dispatch as: "When a rider requests a ride, query the database for the closest available driver and assign them immediately." As proven mathematically in operations research, greedy nearest-neighbor assignment produces globally terrible outcomes. Assigning Driver A to Rider 1 may leave Rider 2 (who requested a ride 500 milliseconds later 50 meters away) with an 18-minute wait because the only remaining driver is miles away.
2. The Square Grid & Geohash Distortion: Using square spatial grids (Geohash or Google S2) creates severe distance distortion. The distance from the center of a square cell to its edge neighbor is 1.0, but the distance to its diagonal corner neighbor is sqrt(2) ≈ 1.414—a 41.4% error in circular proximity queries! Furthermore, two drivers separated by 10 meters across a Geohash meridian boundary have completely different string prefixes, requiring complex 8-neighbor bounding-box queries.
3. The Relational Spatial Database Lockup: Attempting to store 33,000 GPS updates per second in PostgreSQL with PostGIS or MongoDB geospatial indexes (2dsphere) saturates disk write channels within minutes. Updating spatial B-trees or R-trees at 33k writes/sec triggers continuous index rebalancing, table-level lock contention, and connection pool exhaustion.
4. The Unbounded ETA Blind Spot: Candidates frequently assume: "We will call Google Maps API to calculate the driving ETA for every candidate driver." If 1,000 riders open the app simultaneously, evaluating 50 candidate drivers per rider requires 50,000 external Google Maps API calls every 2 seconds, costing millions of dollars per month and breaching external rate limits within seconds.

flowchart TB
  P["THE CORE PARADOX<br/>Dispatch optimization requires calculating optimal routes and travel times across thousands of moving drivers and riders simultaneously, yet decisions must be locked and committed within 2 seconds before vehicles move out of range"]
  G["Staff Goal: Ingest 33k GPS writes/sec directly into in-memory Uber H3 hexagonal sets in Redis, solve optimal bipartite matching across 2-second batch windows using the Hungarian algorithm, and enforce atomic 15-second driver reservation leases using distributed locks."]
  P --> G

The L5 vs L6 Contrast — What the Evaluator Actually Hears

The Senior Candidate (L5): Immediately draws a PostgreSQL database with PostGIS, a Redis cache, and a Dispatch Service. When asked how matching works, they say: "We run a PostGIS ST_DWithin query to find drivers within 5 km and send a push notification to the closest one." When asked how surge pricing works, they suggest counting riders in the city and multiplying the base fare by 2.0. They treat spatial distance as straight-line Euclidean geometry and treat dispatch as an isolated, instantaneous greedy query.

The Staff Candidate (L6): Reframes the problem around real-time spatial resource allocation under temporal uncertainty within the first 90 seconds: "Dispatch is not a nearest-neighbor query; it is a global bipartite matching problem solved across discrete 2-second batch windows. We ingest 33,000 GPS telemetry beacons per second into in-memory Uber H3 hexagonal spatial cells (Resolution 8 for pricing zones, Resolution 9 for dispatch) in Redis. Rather than greedy assignment, we construct a cost matrix combining road-network routing ETAs, driver acceptance ratings, and localized surge multipliers, solving the global minimum wait time using the Kuhn-Munkres (Hungarian) algorithm. Drivers receive 15-second atomic reservation leases enforced via Redis Redlock to eliminate race conditions."

2. Step 1: Commit to Intent & Scale Math

Before choosing spatial indexes or drawing routing architectures, an L6 Staff engineer establishes the core operational intent. Transportation and logistics encompass three conflicting models:

The Three Incompatible Intents

1. Ride-Sharing (Uber / Lyft):
   • The Constraint: Extreme rider sensitivity to pickup latency. Riders tolerate at most 3 to 5 minutes of driver arrival time before cancelling.
   • The Architectural Commit: 2-second batch windows, zero multi-rider bundling (for private rides), strict bipartite matching, and rapid driver pre-positioning.
2. On-Demand Food & Grocery Delivery (DoorDash / Instacart):
   • The Constraint: The dominant variance is not driving time, but restaurant kitchen preparation time (which accounts for 60% of late deliveries).
   • The Architectural Commit: Multi-order batching (assigning 2 orders from clustered restaurants to one courier), dispatch delayed until food prep is 70% complete, and multi-stop Vehicle Routing Problem (VRP) heuristics.
3. Scheduled Last-Mile Package Delivery (Amazon Flex / DHL):
   • The Constraint: Fixed delivery routes determined hours in advance across 80+ stops per van.
   • The Architectural Commit: Static genetic algorithms and simulated annealing running in offline batch pipelines overnight.

STAFF MOVE

Senior: "We will calculate candidate driver distances using Euclidean straight-line distance ( sqrt(dx² + dy²) )."

Staff: "Euclidean straight-line distance is completely invalid for real-world dispatch. In urban environments, one-way streets, divided highways, rivers, and railroad tracks mean that a driver 200 meters away straight-line may require a 4-mile, 15-minute detour. We must use an in-memory routing engine (like OSRM or Valhalla) loaded with OpenStreetMap road networks using Contraction Hierarchies to compute actual driving network distance and time in sub-millisecond queries."

Why: Differentiating topological road-network distance from straight-line geometry is the immediate divider between junior and Staff candidates.

Capacity Planning & Scale Math

At metropolitan scale (e.g., Greater New York, London, or Tokyo):

1. GPS TELEMETRY INGESTION VOLUME & WRITE THROUGHPUT

• Active Concurrent Drivers on Shift: 100,000 drivers.
• Telemetry Ping Interval: 1 update every 3 seconds (balance between road-snapping accuracy and battery/cellular drain).

Ingestion Write Throughput:

GPS Ingestion Rate = 100,000 drivers / 3 seconds ≈ 33,333 writes/second

Telemetry Payload Size:

Driver ID (UUIDv7: 16 bytes), Latitude (float64: 8 bytes), Longitude (float64: 8 bytes), Bearing (uint16: 2 bytes), Speed (uint16: 2 bytes), Status (uint8: 1 byte), Timestamp (uint64: 8 bytes) ≈ ~64 bytes binary (or ~200 bytes JSON over wire).

Ingestion Bandwidth:

Raw Ingestion Bandwidth = 33,333 writes/sec * 200 bytes ≈ 6.67 Megabytes/second (53.3 Mbps)

Network bandwidth is small, but the write concurrency (33.3k IOPS) crushes traditional relational database disk write paths!

2. SPATIAL INDEX MEMORY FOOTPRINT (REDIS + UBER H3)

Instead of storing coordinates in tables, we map coordinates to Uber H3 Hexagonal Cell IDs (Resolution 9 ≈ 100-meter radius, ~0.10 km² area).

An H3 Cell ID is a single 64-bit unsigned integer ( uint64 ) (8 bytes).

Redis Key-Value Layout:

• Active drivers per cell: geo:h3:<cell_id> -> Redis SET of driver_ids.
• Driver state hash: driver:<driver_id> -> Hash { lat, lon, cell_id, status, updated_at }.

RAM Calculations for 100,000 Drivers:

• 100,000 Driver Hashes * 256 bytes per hash ≈ 25.6 Megabytes.
• Active H3 Resolution 9 Cells across metro area (~10,000 cells): 10,000 Sets containing 100,000 total member elements ≈ 15 Megabytes.
• Total Active In-Memory Location Working Set ≈ under 200 Megabytes of RAM!

The Staff Revelation: Sizing proves that the entire real-time geospatial location state of a 100,000-driver metropolitan fleet fits entirely in RAM on a single Redis master (or a 3-node Redis Sentinel cluster for high availability)! Relational disk storage is completely unnecessary for live spatial queries.

3. RIDE REQUEST VOLUME & MATCHING ENGINE THROUGHPUT

• Completed Trips per Day: 1,000,000 rides/day.
• Peak Hour Demand: 20% of daily volume occurs during the 2 evening rush hours (5:00 PM to 7:00 PM):

Peak Ride Volume = 200,000 rides / 7,200 seconds ≈ 28 ride requests/second
Peak Search Queries (Riders opening app to check fares/ETAs) = 28 * 20 ≈ 560 searches/second

2-Second Dispatch Batch Size:

Pending Requests per 2-Second Window = 28 requests/sec * 2 sec ≈ 56 pending riders per city
Candidate Drivers Evaluated per Batch ≈ 50 available drivers within 3 km per rider
Bipartite Matrix Size per City Cluster ≈ 50 riders * 100 drivers = 5,000 edges

A 5,000-edge bipartite matching problem is solved by the Hungarian algorithm in less than 15 milliseconds in Go or C++!

4. THE HUNGARIAN COMPLEXITY & SPATIAL GRAPH PARTITIONING

The classical Kuhn-Munkres (Hungarian) algorithm has a time complexity of O(V² * E) ≈ O(N³), where N is the number of vertices.

If evaluated naively across an entire metropolitan area with 2,000 riders and 3,000 drivers in a single matrix:

Operations = (5,000)³ = 125,000,000,000 ops -> Requires 8 to 12 seconds to solve!

The Solution: Disjoint Spatial Graph Partitioning:

By partitioning the city into Disjoint H3 Resolution 7 clusters (~5.16 km² each, approximately the size of Downtown, Midtown, Uptown):

• Each independent cluster contains at most 40 riders and 60 drivers (100 total vertices).
• (100)³ = 1,000,000 operations, solving in under 4.5 milliseconds!
• 30 independent city clusters solve in parallel across 16 CPU cores, completing the entire metropolitan dispatch in less than 25 milliseconds total, comfortably within the 2.0-second window budget.

Key System Sizing Numbers Worth Memorizing

3. End-to-End System Architecture

The architecture decouples the continuous high-frequency GPS ingestion stream from the 2-second global dispatch optimization loop:

Figure 9.1: End-to-End Real-Time Ride Dispatch & Geospatial Architecture

The Architecture Components in Depth

flowchart TB
  subgraph RT["END-TO-END REAL-TIME RIDE DISPATCH RUNTIME ARCHITECTURE"]
    DR["100,000 Active Driver Smartphones"]
    RC["Rider Mobile Clients"]
    C1["COMPONENT 1: Driver Ingestion Gateway<br/>• Extended Kalman Filter (EKF) De-Jitter<br/>• Velocity & Speed Thresholding (#lt;1 km/h)<br/>• Kafka #96;driver-telemetry#96; (H3 Keyed)"]
    C3["COMPONENT 3: 2-Second Window Matcher<br/>• Pending Trip Buffer (H3 Res 7 Cells)<br/>• Bipartite Cost Matrix Formulation<br/>• Kuhn-Munkres (Hungarian) Solver"]
    C2["COMPONENT 2: In-Memory Geospatial Engine<br/>• Redis Cluster Sharded by Metro Cluster<br/>• H3 Resolution 9 Cell Sets (#96;geo:h3:id#96;)<br/>• Driver State Hashes & 10s TTL Heartbeat"]
    C5["COMPONENT 5: Routing & ETA Engine<br/>• Self-Hosted OSRM Bare-Metal NVMe<br/>• Contraction Hierarchies (#lt;1ms Queries)<br/>• GBDT / LightGBM Traffic & Friction"]
    C4["COMPONENT 4: Atomic Dispatch Coordinator<br/>• Redis Distributed Lock (#96;PX 15000 NX#96;)<br/>• PostgreSQL Trip State (#96;OFFERED#96;)<br/>• Driver 15s Countdown Push WebSocket"]
    C6["COMPONENT 6: Dynamic Surge Engine<br/>• H3 Resolution 8 Demand/Supply Ratio<br/>• Spatial Laplacian Smoothing Operator<br/>• 5-Minute Cryptographic Quote Locks"]
    C7["COMPONENT 7: Rider Live Tracking & Map-Matching WebSocket Gateway<br/>• Hidden Markov Model (HMM) Map Road Snapping (OpenStreetMap Geometry)<br/>• Dead Reckoning Velocity Vector Interpolation (60 FPS Smooth Vehicle Animation)<br/>• Netty / Go WebSocket Edge Fleet Supporting 2,000,000 Concurrent Rider Sockets"]
    DR -->|"GPS Telemetry every 3s"| C1
    RC -->|"Ride Booking API"| C3
    C1 --> C2
    C2 --> C5
    C5 -->|"Candidate Drivers & Costs"| C3
    C3 -->|"Optimal Match Computed"| C4
    C5 -->|"Live Multipliers"| C6
    C4 -->|"En Route & Ongoing Trips"| C7
  end

Component 1: Driver Telemetry Ingestion Gateway & Edge Kalman Pre-Processor

• Responsibilities & Wire Protocol: Maintains persistent, multiplexed gRPC and WebSocket connections to 100,000+ active driver smartphones through an edge Envoy/Netty proxy fleet. Ingests raw GPS telemetry frames emitted every 3 to 4 seconds: (driver_id, lat, lon, heading, speed, altitude, accuracy, timestamp).
• Signal De-Noising & Filtering: Executes an in-memory Extended Kalman Filter (EKF) to eliminate multipath GPS reflections and sensor drift caused by high-rise urban canyons. If the calculated speed is below 1 km/h (vehicle stationary at a traffic light), updates are suppressed to conserve cell bandwidth and downstream IOPS.
• Kafka Partitioning Strategy: Writes sanitized telemetry records directly to the internal Kafka topic driver-telemetry. To guarantee strict temporal and spatial ordering without global lock contention, the topic is partitioned by H3 Resolution 7 Cell ID (~5.16 km² urban zones). Ingestion scales to 33,333 writes/second at sub-5ms producer latency.

Component 2: In-Memory Geospatial Spatial Engine (Redis + Uber H3)

• Storage Topology & Sharding Model: A horizontally sharded Redis cluster partitioned by metro_id and parent H3 cell index. Maintains the real-time spatial index of all on-duty drivers in memory using two synchronized data structures:
  1. geo:h3:<res9_cell> (Redis SET): Stores active available driver_ids within each ~0.10 km² hexagonal cell.
  2. driver:state:<driver_id> (Redis HASH): Stores (current_cell, lat, lon, heading, status, last_ping_epoch).
• Atomic Cell Transitions & Heartbeat TTLs: As telemetry streams off Kafka, an atomic Lua script removes the driver from their previous H3 cell and registers them in their new cell (SREM old_cell, SADD new_cell). A 10-second TTL is attached to the driver's heartbeat; if GPS pings cease for 10 seconds (e.g., phone battery dies or enters a tunnel), the driver is automatically evicted from the dispatchable pool to prevent ghost dispatching.

Component 3: 2-Second Window Batch Matching Engine & Bipartite Hungarian Solver

• Batch Aggregation Pipeline: Eliminates the myopic inefficiencies of greedy FIFO matching by buffering incoming ride requests into discrete 2.0-second time windows. For each geographic metropolitan partition (H3 Resolution 7), the engine pools all unassigned riders and available candidate drivers in the cell and its concentric \(k=1\) and \(k=2\) hexagonal rings.
• Bipartite Cost Matrix Formulation: Formulates an \(N \times M\) bipartite matching graph. The edge cost \(C_{ij}\) between Rider \(i\) and Driver \(j\) is dynamically computed:

\[ C_{ij} = w_1 \cdot \text{ETA}_{ij} + w_2 \cdot (100 - \text{AR}_j) + w_3 \cdot \Delta \theta_{ij} + w_4 \cdot \text{CancelRisk}_{ij} \]

where \(\text{AR}_j\) is the driver's historical acceptance rate, \(\Delta \theta_{ij}\) is the angular heading alignment (penalizing drivers traveling in the opposite direction on divided boulevards), and \(\text{ETA}_{ij}\) is the real road travel time.

• Kuhn-Munkres (Hungarian) Execution: Solves the assignment problem to minimize total system wait time. Evaluated across disjoint spatial partitions in Go/C++ SIMD routines, solving in < 4.5ms per cluster and under 25ms metropolitan total, cutting aggregate passenger wait times by up to 32% compared to greedy nearest-neighbor dispatch.

Component 4: Atomic Dispatch Lock & Distributed Trip State Coordinator

• Lease Acquisition & Anti-Collision: When the batch engine computes an optimal \((Rider_i, Driver_j)\) assignment, the coordinator must reserve Driver \(j\) without race conditions. It acquires a 15-second distributed lock in Redis:

SET lock:driver:<driver_id> <trip_id> NX PX 15000

• State Machine & Fencing Tokens: Transitions the trip entity in PostgreSQL from REQUESTED to OFFERED with a monotonically incrementing fencing token. Atomically updates the driver's Redis state to OFFERED and removes them from geo:h3:<cell>.
• Resolution Handlers & Cascading Timeouts: Pushes the dispatch offer to the driver's mobile device over WebSocket with an active 15-second countdown timer. If the driver taps "Accept", the trip transitions to ACCEPTED. If the driver rejects or the 15-second timer expires, the coordinator deletes the Redis lock, applies a temporary 30-second dispatch penalty to that driver, and re-injects the rider into the next 2-second batch window.

Component 5: Routing, Contraction Hierarchies & ETA Prediction Engine (OSRM + GBDT)

• In-Memory Contraction Hierarchies: Evaluates point-to-point road network travel times using a cluster of self-hosted Open Source Routing Machine (OSRM) instances running on bare-metal NVMe memory nodes. Utilizes pre-computed Contraction Hierarchies over OpenStreetMap road networks to evaluate shortest-path driving times in under 1.0 millisecond per query.
• Machine Learning Feature Calibration: Raw topological routing times are dynamically calibrated using a Gradient Boosted Decision Tree (GBDT / LightGBM) model. The model incorporates real-time road speeds derived from recent driver telemetry, localized precipitation sensor feeds, urban pickup friction (e.g., high-rise office towers vs. single-family residential curbs), and driver-specific historical navigation speeds.

Component 6: Real-Time Dynamic Surge Pricing Engine & Spatial Smoothing

• Dynamic Supply/Demand Aggregation: Evaluates economic balance across H3 Resolution 8 hexagonal cells (~0.74 km²). Demand aggregates real-time app opens, fare quote requests, and active trip bookings. Supply aggregates available idle drivers plus forward-projected supply (drivers completing trips within 3 minutes in that cell).
• Spatial Laplacian Diffusion: To prevent abrupt price cliffs where adjacent city blocks differ wildly in price (causing riders to walk across intersections to avoid 3.0x multipliers), the engine applies a Discrete Laplacian Smoothing Operator across all 6 hexagonal neighbors (\(\lambda = 0.4\)), producing smooth continuous price contours.
• Cryptographic Quote Locking: When a rider views an estimated fare, the engine generates an HMAC-SHA256 signed quote token freezing the rate for 5 minutes, protecting checkout conversion while preventing riders from gaming the pricing engine.

Component 7: Rider Live Tracking & Road-Snapped Interpolation WebSocket Gateway

• Edge Multiplexing Fleet: A stateless, horizontally scalable Netty / Go WebSocket gateway fleet serving over 2,000,000 concurrent rider mobile sessions.
• Map Road Snapping via Hidden Markov Model (HMM): Ingests asynchronous GPS coordinates emitted by assigned drivers. Because raw GPS drifts off roads, an asynchronous worker matches coordinates to physical road centerlines using an HMM based on vehicle heading and network topology.
• Dead Reckoning Animation: Between 3-second GPS updates, the client SDK uses dead reckoning (projecting current position along the road vector using reported vehicle velocity). This delivers fluid 60 FPS car movement across the rider's map screen while slashing backend telemetry egress bandwidth by 80%.

Step-by-Step Driver Ingest & Geospatial Matching Flow

The following sequence details the complete lifecycle of driver telemetry ingestion, 2-second batch matching, atomic dispatch reservation, and live rider map synchronization:

sequenceDiagram
  participant DA as Driver App
  participant EG as Edge Gateway
  participant KI as Kafka Ingress
  participant RE as Redis Engine
  participant BM as Batch Matcher
  participant OR as OSRM Routing
  participant RC as Rider Client
  DA->>EG: (1) GPS Ping (3s) (lat, lon, spd)
  EG->>KI: (2) Kalman Filter & Ingest
  KI->>RE: (3) Update H3 Res 9 Cell
  RC->>BM: (4) Book Trip (2s Window)
  BM->>OR: (5) Candidate ETAs Query
  OR-->>BM: Matrix Costs
  BM->>RE: (6) Solve Hungarian & Acquire Lock
  RE-->>DA: (7) Push Offer (15s Countdown)
  DA->>RE: (8) Accept Trip
  RE->>RC: Confirm Driver Match (Transition DB: ACCEPTED)

STEP 1: HIGH-FREQUENCY GPS EMISSION

Every 3 to 4 seconds, the driver's smartphone transmits a compact binary Protocol Buffer payload over an existing persistent gRPC / HTTP/2 stream to the edge ingestion cluster: (driver_id: "drv_4901", lat: 40.7589, lon: -73.9851, heading: 42.0, speed: 8.5 m/s, accuracy: 4.2m).

STEP 2: EDGE KALMAN FILTERING & SHARDED INGESTION

The ingestion node evaluates the ping through an Extended Kalman Filter (EKF) to suppress multipath noise. It validates that the telemetry point does not represent an impossible physical teleportation (> 150 km/h). The sanitized record is published to Kafka topic driver-telemetry, keyed by the driver's parent H3 Resolution 7 cell (872a100d8ffffff), guaranteeing all telemetry within that ~5 km² metropolitan zone routes to the same Kafka partition.

STEP 3: IN-MEMORY SPATIAL GRID UPDATING (REDIS H3 INDEX)

A consumer fleet processes the telemetry batch from Kafka. It converts the (lat, lon) coordinates into an H3 Resolution 9 index (892a100d843ffff). An atomic Redis Lua script checks if the driver's cell has changed:

1. If changed: removes the driver from the previous cell set (SREM geo:h3:<old_cell> drv_4901) and adds them to the new cell set (SADD geo:h3:<new_cell> drv_4901).
2. Refreshes the driver's state hash: HSET driver:drv_4901 lat 40.7589 lon -73.9851 status AVAILABLE.
3. Resets the 10-second heartbeat expiration key: SET driver:hb:drv_4901 1 EX 10.

STEP 4: RIDER TRIP REQUEST & 2-SECOND BATCH BUFFERING

A passenger taps "Request Ride" on their mobile device. The booking service checks the active 5-minute cryptographic quote lock for price validity. Rather than instantly assigning the nearest car, the request is appended to the active 2.0-second batch matching buffer for that urban cluster (buffer:trips:metro_nyc:872a100d8ffffff).

STEP 5: ROAD-NETWORK ROUTING & BIPARTITE MATRIX ASSEMBLY

When the 2.0-second window timer ticks, the batch matching worker activates. It queries Redis for all available drivers within the rider's H3 cell and adjacent concentric hexagonal rings (\(k=1, 2\)). It dispatches a batch matrix query to the in-memory OSRM routing engine, which executes Contraction Hierarchy queries in sub-millisecond C++ routines to return precise road travel times (\(\text{ETA}_{ij}\)), penalizing drivers that require illegal U-turns or bridge detours.

STEP 6: KUHN-MUNKRES OPTIMIZATION & ATOMIC RESERVATION LOCK

The batch matcher constructs the weighted bipartite cost matrix and executes the Kuhn-Munkres (Hungarian) algorithm in Go/C++ SIMD memory. It identifies the globally optimal set of assignments that minimizes total passenger wait time. For the winning assignment (Rider 101 -> Driver 42), the matcher executes an atomic reservation lock in Redis:

SET lock:driver:drv_42 "trip_901" NX PX 15000

Upon lock acquisition, Driver 42's status in Redis transitions to OFFERED, and they are temporarily removed from the active availability set to prevent concurrent matching.

STEP 7: PUSH OFFER DISPATCH & MOBILE COUNTDOWN

The dispatch coordinator emits a push notification over the driver's active WebSocket connection. The driver's mobile interface flashes with pickup details, destination zone, estimated fare, and a 15-second radial countdown timer. Simultaneously, the rider's mobile UI displays "Connecting with your driver...".

STEP 8: DRIVER ACCEPTANCE & TRIP STATE COMMITMENT

The driver taps "Accept" at second 4. The mobile client transmits an AcceptTrip RPC with the active fencing token. The coordinator executes an atomic update in PostgreSQL:

UPDATE trips SET status = 'ACCEPTED', driver_id = 'drv_42', accepted_at = NOW()
WHERE trip_id = 'trip_901' AND status = 'OFFERED';

The Redis lock is converted into an active trip session. The routing engine generates the turn-by-turn navigation path to the pickup point, streaming the driver's road-snapped vehicle coordinates to the rider's device at 60 FPS via the tracking WebSocket gateway.