Design a ride-sharing app (Uber / Lyft)

1. Clarify the requirements

Ask: Riders and drivers only, or also delivery? Do we need ride types (pool, premium)? Pricing and payments in scope? Global or one city to start?

Functional requirements

• Drivers go online and stream their location.
• A rider requests a ride from A to B and sees an estimated fare and ETA.
• The system matches the rider with a nearby available driver, who can accept or decline.
• Both see each other's live location until pickup, then the trip progresses to completion.

Non-functional requirements

• Low latency: match within a few seconds; location updates visible within about a second.
• Consistency for dispatch: a driver must never be assigned two trips at once.
• High availability, especially for in-progress trips; and resilience to mobile networks dropping.

2. Estimates

The ride request rate is small; the location stream is the heavy write path, and it must never sit behind slower trip logic. That calls for separate services and a memory-resident index.

3. High-level architecture

Location path. Driver apps send a small update (driver ID, lat/lng, heading, timestamp) every few seconds over a persistent connection. The location service writes it to the geo index, keyed by grid cell, with a TTL so drivers who vanish drop out automatically. It also appends updates to a log for trip history and analytics.

Request path. The trip service creates a trip in REQUESTED state and asks matching for a driver. Matching queries the rider's cell and its neighbours for available drivers, ranks candidates by ETA (road distance, not straight-line), and offers the trip to the best one. If the driver declines or doesn't answer within about 10 seconds, it moves to the next candidate.

4. Geospatial indexing

Divide the map into cells (geohash prefixes, quadtree leaves, or a hexagonal grid such as H3). Each cell holds the set of available drivers currently inside it. To find drivers near a rider: compute the rider's cell, read it plus its ring of neighbours, filter by availability and vehicle type, then rank. Choose a cell size where a typical cell holds tens of drivers in a dense city; widen the search ring if too few are found.

Partition the index by region (city or a coarse cell), so each partition is small and all queries for a city hit one place. Very dense cities can be split further.

5. Data model

driver_live (memory)  driver_id → { cell, lat, lng, status, vehicle_type, updated_at }   TTL 30 s
cell_index  (memory)  cell_id → set(driver_id)        -- available drivers only
trips                 trip_id, rider_id, driver_id, status, pickup, dropoff,
                      fare_estimate, fare_final, created_at, updated_at, version
trip_events           trip_id, seq, type, payload, at  -- append-only audit log
location_log          driver_id, ts, lat, lng           -- time-series / object store

Trip state is a strict state machine: REQUESTED → MATCHING → DRIVER_ASSIGNED → ARRIVED → IN_PROGRESS → COMPLETED (or CANCELLED). Every transition is a conditional update on version, so duplicate or out-of-order messages from phones can't corrupt state.

6. Dispatch consistency, ETA and scaling

• No double dispatch. Claim a driver with an atomic compare-and-set on status (available → offered) with an expiry. Only one matching request can win; the loser moves to the next candidate.
• Batch matching. Instead of greedy first-come matching, collect requests for a second or two per area and solve the assignment jointly to reduce total pickup time. Mention it as an optimisation.
• ETA uses a road graph with live traffic (a routing service with precomputed shortcuts), not straight-line distance. Cache ETAs between cells for ranking, and compute exact ETAs only for the top candidates.
• Surge pricing compares demand (requests) to supply (available drivers) per cell over a sliding window, computed by a stream processor and read by the pricing service.
• Live tracking pushes the assigned driver's updates to the rider over the rider's open connection, the same pattern as a chat app.
• Regional isolation. Run each region independently so an outage in one city's partition doesn't affect others.

7. Trade-offs to call out

• Update frequency vs cost: more frequent GPS updates give better matching and tracking, but cost battery, bandwidth, and write capacity.
• Greedy vs batched matching: lower latency vs better global efficiency.
• Consistency: the location index can be eventually consistent (seconds-old positions are fine); trip state and driver claims must be strongly consistent.
• Cell size: small cells mean more neighbour lookups; large cells mean more candidates to filter.

8. Common follow-up questions

1. The driver's phone loses signal mid-trip. What happens? The trip continues server-side; the app buffers GPS points and uploads them on reconnect, and fare calculation uses the reconciled route.
2. How do you handle a driver at a city boundary? Index by cell, not by city; partition boundaries are just cell ranges, and a query can read from two partitions.
3. How would you add pooled rides? Matching now considers drivers already on a trip whose route can absorb a detour within limits; the assignment problem becomes harder and benefits more from batching.
4. How do you handle airport queues? Model the airport as a special zone with a FIFO queue of waiting drivers instead of nearest-driver matching.
5. How do payments fit in? Authorise an estimate at request time and capture the final fare on completion; see design a payment system.