Design a Ride-Sharing Service

Requirements

A rider opens the app, sees nearby cars, requests a ride, gets matched with a driver within seconds, watches the car approach on a map, rides, and pays automatically at the end.

Functional

• Drivers go online/offline and stream their location every few seconds.
• Riders see nearby available drivers and an ETA / fare estimate.
• Riders request a ride; the system matches and dispatches a driver who can accept or decline.
• Both parties see live location during pickup and the trip.
• Trip lifecycle: requested → matched → arriving → in progress → completed / cancelled; fare computed and charged.
• Ratings and trip history.

Non-functional

• Low latency matching: a driver offer within a few seconds of the request.
• Huge write volume from location updates; each update must be cheap.
• High availability: if dispatch is down, the business is down.
• Consistency where it matters: a driver must never be assigned to two trips at once; trip and payment state must be durable.
• Location freshness is eventually consistent: a few seconds old is fine.

Capacity Estimates

Assume 100 M monthly riders, 20 M rides per day, 5 M drivers of whom 1 M are online at peak, location update every 4 seconds.

The workload is lopsided: a firehose of tiny, short-lived location writes, plus a much smaller stream of business-critical trip writes. Treat them as two different systems.

API Design

// Driver app (persistent WebSocket or frequent HTTP)
POST /v1/drivers/{id}/status          { "status": "ONLINE" | "OFFLINE" }
WS   location push:                   { "lat": 37.77, "lng": -122.41, "heading": 90, "ts": 1761830000 }
WS   server -> driver:                { "type": "OFFER", "tripId": "t_55", "pickup": {...}, "expiresIn": 15 }
POST /v1/trips/{tripId}/accept | /decline | /arrived | /start | /complete

// Rider app
GET  /v1/drivers/nearby?lat=..&lng=..          -> car icons for the map
POST /v1/estimates  { "pickup": {...}, "dropoff": {...}, "product": "standard" }
POST /v1/trips
  Headers: Idempotency-Key: ...
  Body: { "pickup": {...}, "dropoff": {...}, "product": "standard", "quoteId": "q_9" }
  201:  { "tripId": "t_55", "status": "REQUESTED" }
GET  /v1/trips/{tripId}                         -> status, driver, live location
POST /v1/trips/{tripId}/cancel

• Persistent WebSocket connections make server-to-driver offers and live updates cheap; the HTTP endpoints are fallbacks.
• Trip-mutating endpoints are idempotent (keyed by trip ID + action) because mobile networks retry a lot.

Data Model

CREATE TABLE trips (
  trip_id       VARCHAR(32) PRIMARY KEY,
  rider_id      BIGINT NOT NULL,
  driver_id     BIGINT,
  status        VARCHAR(16) NOT NULL,  -- REQUESTED, MATCHED, ARRIVING, IN_PROGRESS, COMPLETED, CANCELLED
  pickup_lat    DOUBLE, pickup_lng DOUBLE,
  dropoff_lat   DOUBLE, dropoff_lng DOUBLE,
  city_id       INT NOT NULL,
  fare_minor    BIGINT,
  version       INT NOT NULL,
  requested_at  TIMESTAMP, completed_at TIMESTAMP
);

CREATE TABLE drivers (
  driver_id     BIGINT PRIMARY KEY,
  vehicle_type  VARCHAR(16),
  rating        DECIMAL(3,2),
  city_id       INT
);

High-Level Design

flowchart LR
  DApp[Driver App] <-->|WebSocket| GWD[Connection Gateway]
  RApp[Rider App] <-->|WebSocket / HTTP| GWR[API Gateway]
  GWD --> LOC[Location Service]
  LOC --> GEO[(Geo Index in memory)]
  LOC --> K[[Kafka location stream]]
  K --> HIST[(Location History)]
  GWR --> TRIP[Trip Service]
  TRIP --> TDB[(Trips DB)]
  TRIP --> DISP[Dispatch / Matching Service]
  DISP --> GEO
  DISP --> ETA[ETA / Routing Service]
  DISP --> DS[(Driver State KV)]
  DISP -->|offer| GWD
  TRIP --> PRICE[Pricing Service]
  TRIP --> PAY[Payment Service]

1. Drivers stream locations to the Location Service, which updates the in-memory geo index and publishes to Kafka.
2. A rider requests a trip; the Trip Service persists it as REQUESTED and asks Dispatch for a driver.
3. Dispatch queries the geo index for nearby available drivers, ranks them by road ETA, atomically reserves the best one, and sends an offer through the driver's WebSocket gateway.
4. On accept, the trip moves to MATCHED; the rider subscribes to that driver's location updates.
5. On completion, Pricing computes the fare from the recorded route and Payment charges the rider.

Deep Dives

Location ingestion

At ~250 K updates/s, writing every ping to a durable database is wasteful: only the latest position matters for matching.

• Drivers hold a WebSocket to a connection gateway fleet; the gateway forwards pings to the Location Service partitioned by driverId (or by city).
• The Location Service overwrites the driver's entry in the geo index with a TTL (e.g. 30 s). A driver whose app dies simply ages out.
• Every ping is also appended to Kafka for downstream consumers (trip route recording, ETA model training, fraud detection), decoupling the hot path from storage.
• Clients adapt the update rate: more often during a trip, less often when idle or stationary, to save battery and bandwidth.

Geospatial indexing with geohash

"Find available drivers within 2 km" cannot scan a million rows. Space is divided into cells so a lookup checks only a few buckets.

• Geohash encodes (lat, lng) into a base32 string by recursively halving longitude and latitude ranges. Each extra character narrows the cell; nearby points usually share a prefix. Precision 6 gives cells of roughly 1.2 km × 0.6 km.
• Index drivers as cell → set of driverIds. To query, compute the rider's cell plus its 8 neighbours (points near a border share no prefix with their neighbour across it), gather candidates, then filter by true distance.
• If too few drivers are found, widen to a coarser precision or a larger ring.
• Redis GEOADD/GEOSEARCH implements this pattern (a geohash stored as a sorted-set score), which is a practical choice at moderate scale.

Matching and dispatch

1. Fetch nearby available candidates from the geo index (say the 10 closest by distance).
2. Ask the ETA service for road ETAs in batch and rank (ETA, driver rating, acceptance rate, vehicle type).
3. Atomically reserve the top driver in the driver state store: compare-and-set status AVAILABLE → OFFERED(tripId) with a short TTL. If it fails, someone else grabbed them; try the next.
4. Send the offer; the driver has ~15 s to accept. On decline or timeout, release the driver back to AVAILABLE and offer the next candidate.
5. On accept, set driver ON_TRIP and trip MATCHED in the trips DB with a versioned conditional update.

At high demand, greedy one-at-a-time matching is suboptimal. Batching requests over a 1–2 second window and solving an assignment problem across all riders and drivers in an area reduces total pickup time.

Trip state machine

REQUESTED -> MATCHED -> DRIVER_ARRIVING -> IN_PROGRESS -> COMPLETED
     \           \              \
      -> CANCELLED (rider/driver/no driver found, with fee rules)

• Each transition is a conditional update on (trip_id, status, version), so duplicate or late events cannot move a trip backwards.
• Every transition emits an event (outbox → Kafka) consumed by notifications, pricing, payments and analytics.
• Timeouts drive progress: no driver after N attempts → CANCELLED (no supply); driver not moving toward pickup → reassign.
• Fare is computed at COMPLETED from the recorded route (distance and time from the location stream) plus surge multiplier locked at request time, then handed to the payment system with the trip ID as the idempotency key.

Live tracking

Once matched, the rider needs the driver's position every few seconds. The Location Service publishes each update for on-trip drivers to a pub/sub channel keyed by trip ID; the rider's gateway subscribes and pushes over WebSocket. Clients interpolate smoothly between points so the car does not jump.

Scaling & Reliability

• Shard by geography: each city (or region of cells) is owned by a set of location and dispatch nodes; most interactions are local, so shards rarely talk to each other. Consistent hashing over cell IDs (Uber's Ringpop is an example of this idea) rebalances when nodes fail.
• In-memory state is rebuildable: if a geo index node dies, drivers' next pings (within seconds) repopulate it. Replicate for faster recovery, but durability is not required.
• Trips DB is durable and replicated; partition by trip_id with a secondary index on rider and driver for history.
• Gateway fleet holds millions of WebSocket connections; use a connection registry (driverId → gateway node) to route offers.
• Surge pricing runs as a stream job over the request and supply events per hex cell, publishing multipliers every minute.
• Degradation: if ETA service is slow, fall back to straight-line estimates; if payments are down, complete trips and charge later.
• Multi-region: keep each city in its home region; fail over the city to a standby region, with drivers reconnecting and repopulating state.

Trade-offs

Interview Tips

• Do the location-update math first; 250 K writes/s justifies an in-memory index.
• Explain geohash precision and the neighbour-cell lookup; know at least one alternative (quadtree or H3).
• Separate the "find candidates" step (geo index) from "rank" (ETA) and "reserve" (atomic CAS).
• Draw the trip state machine and say how idempotent transitions handle retries.
• Mention driver offer timeouts, declines and reassignment.
• Close with geographic sharding and how in-memory state is rebuilt after failures.

References

• System Design Primer: real-world architectures (How Uber scales) and consistency patterns
• High Scalability: How Uber scales their real-time market platform
• Wikipedia: Geohash
• Redis docs: Geospatial indexes
• H3: Hexagonal hierarchical geospatial indexing system