Design a Ride-Hailing System: Location, Matching and Real-Time Updates

A rider in Bengaluru opens the app and taps "Book". Within a few seconds, the app must find drivers who are close by right now, pick a good one, ask that driver, wait for an answer, try someone else if the driver declines, and then show the rider a car moving towards them on a map, updated every few seconds. Meanwhile half a million other drivers across the country are reporting their positions every four seconds, and a concert has just ended near the stadium, so two thousand people are booking from the same few streets.

Ride-hailing is a favourite SDE-2 question because it combines a very high-rate write stream (locations), a specialised index (geospatial), a correctness problem under contention (assigning drivers), and real-time updates. The design here is generic: it does not describe how any particular company builds its systems.

• How to estimate location ingestion, matching and live-tracking load.
• Why the latest location belongs in memory and the history in a stream.
• Geospatial indexing with grids, geohash, H3 and S2, with a runnable example.
• Matching with offers, timeouts and fallbacks.
• How to prevent assigning one driver to two riders.
• Trip state machines, live tracking, payments and partitioning by city.
• Failures, privacy and fraud.

Riders request a ride from a pickup point to a drop point. The system finds nearby available drivers, offers the ride to a driver, and on acceptance creates a trip. The rider sees the driver's position live until pickup and during the trip. At the end, the fare is charged.

Functional requirements: drivers go online, report location and receive offers; riders get fare estimates, request rides, see the assigned driver live; trips move through states to completion; fares are charged.

Non-functional requirements

Drivers online at peak: 500,000; one location update every 4 s  -> 125,000 location writes/s at peakRides: 10 million/day -> about 116 requests/s average, about 350/s at peak (factor 3)Fare estimates: about 10 per request -> about 3,500/s at peakActive trips (average 20 minutes, including pickup): 10M x 20 / 1,440 = about 139,000 on average,  about 420,000 at peakLive tracking: each active trip's rider gets an update every 4 s -> about 105,000 pushes/s at peakLocation history: 125,000/s x 100 bytes = 12.5 MB/s -> about 1 TB/day (if kept for every ping)Hot index memory: 500,000 drivers x ~200 bytes (id, position, status, timestamp, cell) = about 100 MB

Conclusions:

• Location writes (125,000 per second) are the dominant load, but each is tiny and only the latest value matters for matching. The hot index is small enough to keep entirely in memory (about 100 MB nationwide).
• Ride requests are modest in number but latency-critical and contended in hotspots.
• History is large and append-only: a stream into time-series or object storage.

Drivers and riders keep persistent connections (WebSockets, article 05; RFC 6455) through connection gateways like those in the chat design (article 34).

Driver app -> server (over the connection):  LOCATION  { lat, lng, heading, speed, accuracy_m, client_ts }      every 4 s while online  STATUS    { status: "online" | "offline" }Server -> driver app:  OFFER     { offer_id, pickup, drop, fare_estimate, expires_in_s: 15 }Driver app -> server (HTTP, idempotent):  POST /v1/offers/{offerId}/accept      -> 200 { trip_id } | 409 offer expired or taken  POST /v1/offers/{offerId}/decline  POST /v1/trips/{tripId}/arrived | /start | /complete      (state transitions)Rider app (HTTP):  POST /v1/fare-estimates  { pickup, drop, ride_type }      -> { estimate, estimate_id, valid_for_s }  POST /v1/ride-requests   Idempotency-Key: ...  { pickup, drop, ride_type, estimate_id }       -> 201 { request_id, status: "searching" }  POST /v1/ride-requests/{id}/cancelServer -> rider app (over the connection):  MATCHED { trip_id, driver, vehicle, eta }   DRIVER_LOCATION { lat, lng, eta }   TRIP_STATUS { ... }

In memory (location service, per city partition):  driver_state: driver_id -> { lat, lng, cell, status (available, offered, on_trip, offline),                               vehicle_type, updated_at }  cell_index:   cell -> set of available driver_ids (by vehicle type)Durable (per city or region shard):  ride_requests (request_id PK, rider_id, pickup, drop, ride_type, status, created_at, idem_key)                UNIQUE (rider_id, idem_key)  offers        (offer_id PK, request_id, driver_id, status (sent, accepted, declined, expired),                 expires_at)  driver_assignment (driver_id PK, current_trip_id, current_offer_id, version)   -- the reservation record  trips         (trip_id PK, request_id UNIQUE, rider_id, driver_id, status, timestamps, fare)Stream and time series:  location events -> stream -> trip tracks (by trip_id) and analytics; retention limited

The UNIQUE (request_id) on trips guarantees one trip per request; the driver_assignment row is where the "one driver, one trip" rule is enforced.

Driver apps --POST location--> API --> UPDATE drivers SET lat, lng (database)Rider request --> API --> SELECT drivers ORDER BY distance(lat, lng, pickup) LIMIT 10 --> assign the first

At 125,000 location updates per second, the database is overwhelmed with writes whose values are stale four seconds later. Distance queries without a spatial index scan every driver. And "assign the first" races: two riders near each other both pick the same nearest driver.

1. Location write volume on a database, for data with a four-second lifetime.
2. Nearest-driver queries without a spatial index.
3. Double assignment: concurrent requests choosing the same driver.
4. Offers: the chosen driver may not respond; the system must move on quickly.
5. Hotspots: an airport or stadium concentrates demand (and drivers) in a few cells.
6. Live tracking at about 100,000 pushes per second.

Location updates arrive at gateways and go to the location service, partitioned by city (and, in very large cities, by area). Each partition keeps driver_state and cell_index in memory and updates them on every ping: if the driver moved to a new cell, remove them from the old cell's set and add them to the new one. Nothing is written to a database on this path.

In parallel, location events are published to a stream (partitioned by driver or by city; streams preserve order per partition (Introduction to Kafka)), from which consumers build trip tracks for active trips (for fare calculation and disputes), and analytics. If a location-service node restarts, its state rebuilds within one reporting interval as drivers keep sending updates, or faster from the stream.

To find "drivers near this point" quickly, bucket the map into cells and index drivers by cell. Searching then means looking in the pickup cell and its neighbours, not at every driver.

This Java program shows the idea with a simple square grid of about 1 km cells: drivers are bucketed by cell, and a search looks at the pickup cell and its eight neighbours, keeps available drivers and sorts them by great-circle distance. The coordinates are illustrative points in central Bengaluru.

// File: NearbyDrivers.javaimport java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Locale;import java.util.Map;public class NearbyDrivers {    record Driver(String id, double lat, double lng, boolean available) {}    static final double CELL_DEGREES = 0.01;   // about 1.1 km of latitude; a simple square grid    static String cellOf(double lat, double lng) {        return (long) Math.floor(lat / CELL_DEGREES) + ":" + (long) Math.floor(lng / CELL_DEGREES);    }    // Great-circle distance in kilometres (haversine formula).    static double km(double lat1, double lng1, double lat2, double lng2) {        double r = 6371.0;        double dLat = Math.toRadians(lat2 - lat1);        double dLng = Math.toRadians(lng2 - lng1);        double a = Math.sin(dLat / 2) * Math.sin(dLat / 2)                + Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2))                * Math.sin(dLng / 2) * Math.sin(dLng / 2);        return 2 * r * Math.asin(Math.sqrt(a));    }    public static void main(String[] args) {        List<Driver> drivers = List.of(                new Driver("d1", 12.9719, 77.5940, true),                new Driver("d2", 12.9790, 77.5910, true),                new Driver("d3", 12.9650, 77.6050, false),   // on a trip                new Driver("d4", 12.9601, 77.5880, true),                new Driver("d5", 13.0350, 77.5970, true));   // far away        // The index: cell -> drivers currently in it (updated on every location ping).        Map<String, List<Driver>> index = new HashMap<>();        for (Driver d : drivers) {            index.computeIfAbsent(cellOf(d.lat(), d.lng()), c -> new ArrayList<>()).add(d);        }        double pickupLat = 12.9716;        double pickupLng = 77.5946;        long row = (long) Math.floor(pickupLat / CELL_DEGREES);        long col = (long) Math.floor(pickupLng / CELL_DEGREES);        // Look in the pickup cell and its 8 neighbours, keep available drivers, sort by distance.        List<Driver> candidates = new ArrayList<>();        for (long r = row - 1; r <= row + 1; r++) {            for (long c = col - 1; c <= col + 1; c++) {                for (Driver d : index.getOrDefault(r + ":" + c, List.of())) {                    if (d.available()) {                        candidates.add(d);                    }                }            }        }        candidates.sort((a, b) -> Double.compare(km(pickupLat, pickupLng, a.lat(), a.lng()),                                                 km(pickupLat, pickupLng, b.lat(), b.lng())));        System.out.println("cells in index: " + index.size() + ", pickup cell " + cellOf(pickupLat, pickupLng));        for (Driver d : candidates) {            System.out.printf(Locale.US, "%s  %.2f km away%n", d.id(), km(pickupLat, pickupLng, d.lat(), d.lng()));        }    }}

cells in index: 4, pickup cell 1297:7759d1  0.07 km awayd2  0.91 km awayd4  1.47 km away

Driver d3 is close but on a trip, so it is filtered out; d5 is several kilometres away and is never even looked at, because its cell is not a neighbour. Real systems use hierarchical cells (H3 or S2) so they can search in expanding rings (first the immediate neighbourhood, then wider) until they have enough candidates, and use smaller cells in dense city centres.

Ride request (idempotent) -> ride_requests: status searchingMatching service (partition for this city):  1. candidates = available drivers in rings around the pickup, of the right vehicle type (top 20)  2. estimate time to pickup for the closest few with a routing service (road ETA, not straight line)  3. pick the best candidate; RESERVE the driver (below); send OFFER with a 15 s expiry  4. accepted -> create trip; rider gets MATCHED; driver status on_trip     declined or expired -> release the reservation; next candidate (widen the search if needed)  5. after N attempts or T seconds without success -> tell the rider "no drivers available"

Two refinements are common at scale:

• Batched matching: collect requests for a second or two and solve an assignment across all of them (minimising total pickup time), rather than greedily taking the nearest driver for each request in arrival order. Better overall outcomes in dense areas, at the cost of a small delay.
• Dispatch to drivers finishing a trip nearby, not only idle drivers.

Two matching workers may choose the same driver for two riders at the same moment. The reservation is a conditional update on the driver's assignment record, the same check-and-act idea as article 14:

UPDATE driver_assignmentSET current_offer_id = :offer_id, version = version + 1WHERE driver_id = :driver_id AND current_offer_id IS NULL AND current_trip_id IS NULL;-- 1 row: this offer owns the driver. 0 rows: someone else has them; pick another candidate.

The in-memory index marks the driver offered so other searches skip them, but the durable conditional update is the referee: the memory state may be briefly stale on another partition replica; the database row is not.

On accept, a second conditional update turns the offer into a trip, in one transaction: the offer must still be sent and unexpired, the driver's current_offer_id must match, and inserting the trip (with request_id unique) guarantees one trip per request. A late accept after the offer expired gets 409. On decline or expiry, the reservation is cleared (conditionally, only if it still refers to this offer). Offers expire through a timer in the matching service, backed by the scheduler pattern of article 37 so that a crashed matcher cannot leave a driver reserved forever.

The trip is a state machine (driver_assigned -> driver_arrived -> on_trip -> completed, or cancelled from early states), with each transition a conditional update, so duplicate or out-of-order requests from flaky apps cannot corrupt it.

During the trip, the driver's location updates also go to the rider: the location service publishes them on the trip's channel, and the rider's gateway forwards them over the open connection (article 34's routing). If the rider's connection drops, the app reconnects and fetches the latest position; nothing is lost because only the latest matters.

At completed, the fare is computed by the pricing service from the trip's recorded track (distance and time) and the fare rules, then charged through the payment platform (article 39) as the next steps of a small saga: charge the rider, record driver earnings, send receipts (article 27's event design). A failed charge does not undo the trip; it creates an outstanding balance and retry, which is the compensation appropriate to a ride that already happened (Microsoft's Saga guidance describes compensations and pivot steps (Saga pattern)).

A stream processor computes demand (requests) and supply (available drivers) per cell per minute; where demand far exceeds supply, the pricing service applies a multiplier to estimates in those cells. Estimates carry an estimate_id and a validity period, so the rider is charged the price they saw.

Matching is local: a rider in Chennai never needs a driver in Pune. So location partitions, matching workers, offers and trips are partitioned by city (or by region within very large cities). Each city's partition is a unit of capacity and failure: a problem in one city's partition affects only that city. Very busy cities are split further by geography, with care at boundaries (a pickup near a border searches neighbouring partitions).

Driver apps --WebSocket--> Gateways --> Location service (per city, in memory: driver_state, cell_index)                                         `--> location stream --> trip tracks, analytics, surgeRider apps  --HTTP--> API --> Ride requests (per-city DB) --> Matching service (per city)                                  |-- candidate search (location service)                                  |-- ETA (routing service)                                  |-- reservation + offers (per-city DB, conditional updates)                                  `-- offer timers (scheduler)Offer/trip events --> Gateways --> driver and rider apps (OFFER, MATCHED, DRIVER_LOCATION)Trip completed --> Pricing --> Payment platform --> Earnings, Receipts (events)

• Locations: eventually consistent and approximate; a few seconds stale is fine; nothing durable depends on any single ping.
• Driver assignment: strongly consistent per driver, enforced by conditional updates on one record; at most one active offer and one active trip.
• Ride request to trip: at most one trip per request (unique constraint), even with retries.
• Trip state: strongly consistent transitions; apps converge to it.
• Fares and payments: eventually consistent via the post-trip saga.

• Location privacy: a driver's precise location is shown to a rider only after matching and only during the trip; a rider's pickup location is shared only with the assigned driver. Retain fine-grained location history only as long as needed for trips, safety and disputes, then aggregate or delete. Access by staff is audited.
• Phone number masking: riders and drivers communicate through proxied numbers or in-app calls, not personal numbers.
• Fraud: GPS spoofing, fake trips between colluding accounts to earn incentives, promotion abuse. Use device integrity checks, plausibility checks on tracks, and anomaly detection.
• Authentication and authorisation: drivers authenticate per device; only the assigned driver can transition a trip; only the rider can cancel their request.
• Safety features (sharing a live trip with contacts, emergency assistance) are product requirements that rely on the same live-tracking channel.

"At peak we have 500,000 online drivers sending locations every four seconds, about 125,000 updates a second, and around 350 ride requests a second, with matching expected in under ten seconds.

Locations go over persistent connections to a location service partitioned by city that keeps only the latest position in memory, indexed by hierarchical cells such as H3; a copy streams to Kafka for trip tracks, analytics and surge pricing. A ride request is idempotent; the city's matching service searches rings of cells around the pickup for available drivers of the right type, ranks a few by road ETA, reserves the best one with a conditional update on its assignment record, and sends an offer that expires in 15 seconds. Accepting turns the offer into a trip in one transaction, with a unique request id, so a driver can never get two trips and a request never creates two. Declines and expiries release the reservation and move to the next candidate; dense areas use batched matching.

The trip is a state machine with conditional transitions; the rider sees the driver's location pushed over their connection. At completion, pricing computes the fare from the track and a saga charges through the payment platform. Everything is partitioned by city, so failures stay local, and precise locations are shared only between matched parties and retained only as long as needed."

Updates: 60,000 / 3 s = 20,000 per secondIngress: 20,000 x 150 bytes = 3 MB/s, about 24 MbpsIndex memory: 60,000 x 250 bytes = 15 MB

• Next: Design a Food Delivery Platform: Orders, Restaurants and Delivery Partners, which reuses this matching machinery inside a three-party order workflow.
• Related: article 22 for leases and article 34 for persistent connections.