system-design

Design a Ride-Hailing Service (Uber / Careem / Grab)

Difficulty: Tier 3 Asked at: Uber, Careem, Grab, Amazon; the flagship question for MENA/SEA scale-ups Time budget: 45–60 min

This is the marquee question for Careem, Grab, and Uber — and it’s genuinely different from the feed/chat family because the data is geospatial and moving in real time. The core challenges are “find nearby drivers” over a constantly-updating map (geospatial indexing) and matching a rider to a driver. Nail geospatial indexing and the matching flow and you’ve got the spine of it.

Prerequisites: Geospatial Indexing, WebSockets, Message Queues

1. Requirements

Functional:

Riders request a ride from A to B; system matches a nearby available driver.
Track driver & rider locations in real time; show the car moving on the map.
Fare estimation; trip lifecycle (request → matched → en route → in trip → complete → pay).
Driver goes online/offline, accepts/rejects requests.

Non-functional:

Real-time & low latency — matching in seconds; live location updates.
Geospatially scalable — millions of drivers/riders, dense cities.
High availability — a broken app means lost rides/revenue.
Reliable trip state; correct payments.

Out of scope: payments internals (separate), surge-pricing ML, maps/routing internals (separate).

2. Estimation

Careem/Uber city scale: millions of active drivers globally, hundreds of thousands concurrent in peak cities.
Location updates: each active driver pings location every ~4 s → 1M drivers = ~250K location writes/sec. 🚨 This high-frequency location ingestion is a defining load.
Ride requests: far fewer (thousands/sec) but latency-critical.
The geospatial index must answer “drivers near (lat, lng)” thousands of times/sec over data that’s changing 250K times/sec.

3. The core problem: find nearby drivers

🚨 You cannot scan all drivers and compute distance — millions of them, thousands of queries/sec. You need a geospatial index that buckets drivers by location so “nearby” is a cheap lookup. (Geospatial Indexing)

Two standard approaches:

Geohash: encode (lat, lng) into a short string where a shared prefix = spatial proximity. Nearby drivers share a geohash prefix → look up the rider’s cell + neighbors. Easy to shard/store in Redis.
Quadtree / S2 cells: recursively subdivide space; dense areas subdivide more. Google S2 (used by Uber’s H3 is a hex variant) handles density well.

Store drivers in the index keyed by cell; a query fetches candidates from the rider’s cell and adjacent cells, then ranks by actual distance/ETA.

4. High-level design

flowchart TB
    Driver -->|location every ~4s| LocSvc[Location Service]
    LocSvc --> GeoIdx[(Geospatial index<br/>Redis: geohash/cells)]
    Rider -->|request ride| MatchSvc[Matching Service]
    MatchSvc --> GeoIdx
    MatchSvc -->|nearby drivers| Dispatch[Dispatch]
    Dispatch -->|offer| Driver
    Driver -->|accept| TripSvc[Trip Service]
    TripSvc --> TripDB[(Trip state store)]
    Driver <-->|live location| WS[WebSocket / streaming] <--> Rider

Location service ingests high-frequency driver pings and updates the geospatial index (in-memory, Redis) — the current position of every online driver.
Matching service takes a ride request, queries the index for nearby available drivers, ranks them (ETA, rating), and dispatches an offer.
Trip service manages the trip state machine and streams live locations between driver and rider over a persistent connection.

5. Deep dives

5a. Ingesting 250K location updates/sec

Don’t write each ping to a durable DB — too much write load, and you only need the latest position. Update an in-memory geospatial store (Redis with geo commands, or a sharded in-memory service) keyed by driver, partitioned by region so a city’s load spreads across shards. Old positions are simply overwritten. Optionally sample/aggregate pings; you don’t need every one persisted. 🚨 Latest-location-wins + in-memory = this becomes tractable.

5b. The matching flow

Rider requests → matching service computes the rider’s cell.
Query the index for available drivers in that cell + neighbors.
Rank candidates by ETA (needs the road network, not straight-line distance — reference maps), rating, driver preferences.
Offer to the best driver; if they decline/time out, offer the next. 🚨 This is a sequential/ short-list dispatch, not first-come chaos — avoid offering one ride to 50 drivers at once (double-booking) or racing.
On accept, atomically mark driver busy and rider matched (a transactional state change to prevent double-assignment).

5c. Preventing double-booking

A driver must not be offered two rides simultaneously, and a ride must go to one driver. Use an atomic claim: when a driver accepts, compare-and-set their state busy; if already busy, the accept fails and the rider is re-matched. The matching service serializes offers per driver. (Distributed Locking)

5d. Live tracking

During a trip, driver and rider exchange live locations over a persistent connection (WebSocket) so the rider sees the car move and ETA updates. This is the chat connection pattern applied to location streams.

5e. Regional sharding & the density problem

Partition everything by geography (city/region) — a driver in Karachi never matches a rider in Dubai, so shards are naturally independent and scale per-city. Dense areas (airport, downtown) are hotspots — quadtree/ S2 adaptively subdivides dense cells so a single cell doesn’t hold too many drivers. (Hot Keys)

5f. Trip state machine & reliability

A trip moves through states (requested → accepted → arrived → started → completed). Persist state transitions durably (they drive payment and support). Handle failures: driver app crashes mid-trip, network drops — the state machine must recover to a consistent state, not lose the trip.

6. Bottlenecks & scaling further

Location write load → in-memory geo index, latest-wins, regional sharding.
Nearby queries → geohash/S2 index makes them O(cell), not O(all drivers).
Dense-city hotspots → adaptive cells (quadtree/S2), regional shards.
Matching races → atomic driver-claim, serialized offers.
Live tracking connections → WebSocket connection servers (chat pattern).

7. Trade-off summary

Decision	Chosen	Alternative	Why
Nearby search	Geospatial index (geohash/S2)	Scan all drivers	O(cell) vs O(millions) per query
Location storage	In-memory, latest-wins	Durable per-ping	250K writes/sec; only latest matters
Partitioning	By geography	By user hash	Rides are inherently local; independent shards
Matching	Sequential offer + atomic claim	Broadcast to all	Prevents double-booking
Live tracking	WebSocket streaming	Polling	Real-time car movement

8. Follow-up questions

How do you find nearby drivers without scanning them all?

Use a geospatial index that buckets drivers by location so proximity becomes a lookup instead of a scan. With geohashing, you encode each driver's latitude/longitude into a string whose shared prefix length corresponds to spatial closeness, so all drivers in a small area share a prefix; a query hashes the rider's location and reads the matching cell plus its neighboring cells to get candidate drivers, then ranks those few by actual ETA. Quadtrees or Google's S2/H3 cells do the same with adaptive subdivision that handles dense areas better. Either way, "drivers near here" touches only the handful of cells around the rider — a cheap operation — rather than computing distance to every driver in the system, which would be impossible at millions of drivers and thousands of queries per second.

250,000 location updates per second — how do you not melt the database?

Don't treat location like durable transactional data. You only ever need each driver's *latest* position, so you keep positions in an in-memory store (Redis geo, or a sharded in-memory location service) where a new ping simply overwrites the old one — no history, no disk write per ping. Partition the store by geography so each city/region's updates land on different shards, spreading the 250K/sec across many nodes. You can also sample or slightly batch pings, since sub-second precision on a car's position isn't required. The combination — latest-wins semantics, in-memory storage, and regional sharding — turns a crushing write load into something each shard handles comfortably, while durable stores are reserved for trip state that actually matters.

How do you prevent two riders from being matched to the same driver?

Serialize offers per driver and make the acceptance an atomic claim. The matching service doesn't broadcast one ride to many drivers hoping one accepts; it offers to the best candidate, and only if they decline or time out does it move to the next — so a driver isn't juggling simultaneous offers. When a driver accepts, the system does an atomic compare-and-set on that driver's state from "available" to "busy" (a conditional update or distributed lock); if the driver is already busy, the accept fails and that rider is re-matched to someone else. This guarantees each driver is assigned to exactly one trip and each ride to exactly one driver, even under concurrent requests in a dense area.

Why partition by geography rather than by user or driver ID?

Because rides are inherently local: a rider is only ever matched with drivers physically near them, so all the data and computation for a request is confined to one geographic area. Partitioning by region means a matching query only ever touches the shard(s) for that area, shards are independent (Karachi's load never touches Dubai's), and you can scale hot cities independently by giving them more capacity. Partitioning by user or driver hash would scatter geographically-adjacent drivers across all shards, so every "nearby" query would have to fan out to every shard — the opposite of what you want. Geographic partitioning aligns the data layout with the access pattern, which is the whole art of sharding.

9. What junior / mid / senior answers look like

Junior: stores driver locations in a table and does a distance query to find nearby ones. Works for a few drivers; collapses at millions and 250K writes/sec.
Mid: uses a geospatial index (geohash), in-memory latest-location store, a matching service that queries nearby cells and offers to a driver, WebSocket live tracking.
Senior: all that plus regional sharding as the scaling axis, adaptive cells for dense-area hotspots, atomic driver-claim to prevent double-booking, a durable trip state machine with failure recovery, and ETA ranking that needs road-network routing — clearly separating the high-frequency in-memory location plane from the durable trip plane.