Requirements and Scale
Functional: drivers broadcast their location in real time. Riders request rides and are matched with the nearest available driver. Track active rides in real time. Handle driver acceptance/rejection and rider cancellation. Surge pricing based on supply/demand. Non-functional: low latency for matching (< 5s), highly available, accurate location data.
Scale: 1M active drivers, 3M active riders at peak. Drivers send location updates every 3 seconds → 333K location updates/sec. 1M ride requests per day → ~12/sec.
Driver Location — DriverLocationHT
Storing driver locations in a relational DB and updating every 3 seconds is impractical (too many writes, queries are too slow for sub-second matching). Solution: DriverLocationHT — a distributed in-memory hash table mapping driver_id → {lat, lng, last_updated, status}. Partitioned across multiple servers (consistent hashing by driver_id). Updates (location changes) are written to this hash table in memory and also asynchronously persisted to a time-series DB for history and analytics.
QuadTree for spatial lookup: updated every 15 seconds (not every 3 sec — reduces QuadTree write load). The DriverLocationHT is the source of truth for exact location; the QuadTree is used to find driver_ids near a rider's location, then the exact lat/lng is looked up from the HT.
graph LR Driver["Driver App"] -->|Every 3s| LocationServer["Location Update Server"] LocationServer --> DriverHT["DriverLocationHT (Distributed in-memory)"] DriverHT -->|Every 15s| QuadTree["QuadTree (Spatial Index)"] RiderApp["Rider App"] --> MatchService["Match Service"] MatchService --> QuadTree MatchService --> DriverHT MatchService --> Driver
Ride Matching Algorithm
When a rider requests a ride at location L: (1) Query QuadTree for all available drivers within radius R (e.g., 5 km). (2) For each candidate driver, fetch exact location from DriverLocationHT and compute actual distance. (3) Filter by driver rating and vehicle type. (4) Sort by ETA (estimated time of arrival). (5) Offer ride to the closest driver (lowest ETA). (6) If driver rejects within 15 sec, offer to next driver. (7) If no driver accepts in N rounds, expand radius and retry.
For ETA calculation: use a road distance API (Google Maps, HERE Maps) or a precomputed graph of the road network. Road distance is computed in near-real-time using a graph shortest-path algorithm.
Real-Time Tracking During Ride
Once a ride starts, both rider and driver share location in real time. The driver's app sends GPS coordinates every 3 seconds to a Trip Location Service. The Trip Location Service fans these updates out to the rider's WebSocket connection. The rider's app renders the driver's position on a map. WebSockets are used for this bidirectional real-time channel — the connection stays open for the duration of the trip.
Simultaneously, the ETA is continuously recomputed based on the driver's current position, traffic, and remaining route. The route is recalculated if the driver deviates.
Surge Pricing
Surge multiplier is calculated as a function of supply/demand ratio in each geo-zone. Supply = number of available drivers in the zone. Demand = number of pending ride requests in the zone. If demand/supply > threshold, apply surge multiplier (1.5×, 2×, etc.). Geo-zones are defined by the same QuadTree leaf nodes. A Surge Pricing Service runs every 30 seconds, reads driver and request counts per zone from the DriverLocationHT and request queue, and updates the surge price for each zone in Redis.
Payment and Trip History
Payment is handled by a separate Payment Service integrating with Stripe or Braintree. Fare is calculated at trip completion: base fare + time × rate + distance × rate × surge multiplier. Trip history is stored in a time-series DB (Cassandra) with records: trip_id, rider_id, driver_id, start_lat/lng, end_lat/lng, start_time, end_time, fare, route (polyline). Receipts and invoices are generated from this data.