Low-Level Design: Taxi/Ride-Hailing Dispatch System — Driver Matching, Surge Pricing, and Trip Lifecycle

Core Entities

Driver: driver_id, user_id, vehicle_id, license_number, status (OFFLINE, AVAILABLE, ON_TRIP), current_lat, current_lng, last_location_update, rating, total_trips, acceptance_rate. Vehicle: vehicle_id, driver_id, make, model, year, plate, type (ECONOMY, COMFORT, XL, BLACK), capacity. Rider: rider_id, user_id, rating, payment_method_id, default_vehicle_type. Trip: trip_id, rider_id, driver_id, pickup_lat, pickup_lng, pickup_address, dropoff_lat, dropoff_lng, dropoff_address, vehicle_type, status (REQUESTED, ACCEPTED, DRIVER_ARRIVING, IN_PROGRESS, COMPLETED, CANCELLED), estimated_fare, final_fare, surge_multiplier, requested_at, accepted_at, pickup_at, dropoff_at, distance_km, duration_minutes. DriverLocation: (driver_id, lat, lng, timestamp) — high-write append-only log for trip history. Current location stored on Driver row.

Driver Location Tracking

Drivers send GPS updates every 4 seconds (mobile SDK). At scale: 500K active drivers * 1 update / 4s = 125K location writes per second. Architecture: driver app sends UDP heartbeats (not TCP — lower overhead, acceptable to lose occasional updates). Location update service writes to Redis geospatial index (GEOADD key lng lat driver_id) and asynchronously logs to the DriverLocation table for trip history. Redis GEOSEARCH: find all AVAILABLE drivers within 5km of a pickup point in O(N+log M) where N = results, M = total entries. This is the core of the dispatch query. Driver status must be AVAILABLE (not ON_TRIP, not OFFLINE). Redis geospatial uses Haversine distance — accurate enough for city-level dispatch.

Matching Algorithm

class DispatchService:
    def find_best_driver(self, pickup: LatLng, vehicle_type: str) -> Optional[Driver]:
        # Step 1: spatial query — drivers within 5km radius
        candidates = self.redis.georadius(
            f'available_drivers:{vehicle_type}',
            pickup.lng, pickup.lat,
            radius=5, unit='km',
            withdist=True, count=20, sort='ASC'
        )
        if not candidates:
            return None

        # Step 2: rank by ETA (estimated time of arrival), not raw distance
        # ETA accounts for traffic, road network (not straight-line)
        # Use routing API for top 5 candidates (limit API calls)
        top5 = candidates[:5]
        etas = self.routing_api.batch_eta(
            [(c.driver_id, c.location, pickup) for c in top5]
        )

        # Step 3: apply driver score (acceptance rate, rating)
        def score(driver, eta):
            return eta * 0.7 + (1 - driver.acceptance_rate) * 120 + (5 - driver.rating) * 30

        ranked = sorted(zip(top5, etas), key=lambda x: score(x[0], x[1]))
        return ranked[0][0]

    def dispatch_trip(self, trip_id: int, driver_id: int):
        # Offer trip to driver; wait 15 seconds for accept/decline
        self.redis.setex(f'trip_offer:{driver_id}', 15, trip_id)
        self.events.publish('trip.offered', {'driver_id': driver_id, 'trip_id': trip_id})

Offer-and-fallback: if the top driver does not accept within 15 seconds, offer to the next candidate. Track attempts in Redis. After 3 failed offers: widen radius to 10km and repeat. After 5 minutes without a match: notify the rider (no cars available).

Surge Pricing

Surge multiplier is applied when demand exceeds supply in a geographic cell. Geohash grid: divide the city into geohash cells (precision 6 = ~1.2km x 0.6km cells). For each cell: compute supply = count of AVAILABLE drivers in the cell; demand = count of open trip requests in the last 2 minutes in the cell. Surge = f(demand / supply). Tiers: ratio 3.0 → 2.5x (capped). Updated every 30 seconds. Stored in Redis: HSET surge:geohash multiplier. Rider sees the surge multiplier before confirming the trip. Legal requirement: must disclose surge before charging. The multiplier is locked in at trip request time — not updated after the rider confirms. Anti-gaming: if a driver cluster moves to a surge area intentionally, detect and adjust (supply-side gaming filter).

Trip State Machine and Billing

States: REQUESTED → ACCEPTED (driver accepts) → DRIVER_ARRIVING (driver en route to pickup) → IN_PROGRESS (trip started, rider in car) → COMPLETED or CANCELLED. Cancellation policy: rider cancels after driver is en route for > 5 min: small cancellation fee. Driver cancels after accepting: penalty to driver acceptance rate. Fare calculation at trip completion: base_fare + (per_km_rate * distance) + (per_min_rate * duration). Apply surge_multiplier. Apply promo codes (stored in PromoCode table, mark as used after application). Minimum fare enforced. Round to nearest cent. Payment: charge the rider’s card on file via Stripe. On failure: retry 3x, then move to collections queue. Driver payout: 80% of fare (platform keeps 20%). Paid weekly via bank transfer. Receipt: email + in-app with route map, fare breakdown, and driver name.

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you efficiently find nearby available drivers in a ride-hailing system?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Store driver locations in a Redis geospatial index using GEOADD. Query with GEORADIUS or GEOSEARCH to find AVAILABLE drivers within a given radius (e.g., 5km) of the pickup point. Redis geospatial uses Haversine distance and returns results in O(N + log M) where N is the result count and M is the total driver count.”}},{“@type”:”Question”,”name”:”Why rank drivers by ETA rather than raw distance?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Raw (straight-line) distance does not account for road network topology, traffic conditions, or one-way streets. A driver 1km away across a river may have a longer ETA than one 1.5km away on the same road. ETA from a routing API more accurately predicts when the driver will arrive, improving rider experience and reducing cancellations.”}},{“@type”:”Question”,”name”:”How does surge pricing work at a technical level?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”The city is divided into geohash cells. Every 30 seconds, for each cell: supply = count of AVAILABLE drivers, demand = count of open trip requests in the last 2 minutes. A surge multiplier is computed from the demand/supply ratio and stored in Redis. The multiplier is shown to the rider before confirming and locked in at request time — later changes do not affect a confirmed trip.”}},{“@type”:”Question”,”name”:”How do you handle the case where a dispatched driver does not accept the trip?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Set a 15-second offer timeout in Redis (setex). If the driver does not accept within 15 seconds, the dispatch service moves to the next ranked candidate. After 3 failed offers, the search radius is widened (e.g., from 5km to 10km) and the process repeats. After 5 minutes without a match, the rider is notified that no cars are available.”}},{“@type”:”Question”,”name”:”How do you handle driver location updates at scale (500K active drivers)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Drivers send GPS updates every 4 seconds via UDP (lower overhead than TCP, occasional packet loss is acceptable). A location update service writes to Redis geospatial index for dispatch queries and asynchronously logs to a DriverLocation table for trip history auditing. The current location is stored on the Driver row for fast single-driver lookups.”}}]}