Deep dive · Hard

Design a ride sharing

A real-time state problem. Millions of moving objects, a matching decision that must be exclusive, and a geospatial query that a naive database cannot serve. It also tests whether you can keep a long-running stateful trip consistent.

What it trains: Geospatial indexing, matching, real-time state

1. Requirements

Functional

Drivers publish location continuously; riders request a ride from A to B
Match a rider with a nearby available driver and let the driver accept or decline
Track the trip in real time until completion, then price and charge it

Non-functional

Matching within a few seconds — riders abandon fast
Location updates from millions of drivers, every 3–5 seconds
A driver must never be assigned two trips: matching requires strong consistency
Regional availability; a failure in one city should not affect another

2. Back-of-envelope numbers

1M active drivers pinging every 4 seconds ≈ 250K location writes/sec — the dominant write load
Each ping is ~100 bytes; keeping only current location means ~100 MB of hot state, not terabytes
500K rides/day ≈ 6 matches/sec average, ~50/sec at peak — matching is rare compared to pings
Trip history at ~2 KB per ride is small; the raw location trail is what gets big, so downsample it

3. Architecture

  ┌────────┐  location ping (4s)   ┌──────────────────┐
  │ Driver │──────────────────────▶│ Location service │
  └────▲───┘                       └────────┬─────────┘
       │ offer                              │ write current position
       │                            ┌───────▼─────────────┐
  ┌────┴─────────┐                  │ Redis geospatial /  │
  │   Matching   │◀─── query ───────│ QuadTree index      │
  │   service    │   "drivers within│ (sharded by region) │
  └────┬─────────┘    2km of pickup"└─────────────────────┘
       │ lock driver (atomic)
  ┌────▼─────────┐   ┌──────────────┐   ┌────────────────┐
  │  Trip store  │──▶│    Kafka     │──▶│ Pricing, ETA,  │
  │  (Postgres)  │   │ (trip events)│   │ analytics, S3  │
  └────┬─────────┘   └──────────────┘   └────────────────┘
       │ trip updates (WebSocket)
  ┌────▼───┐
  │ Rider  │
  └────────┘

Fast-moving location state lives in memory; the trip — which must be correct — lives in a transactional store.

Split the state by how much correctness it needs

Driver locations are high-volume, low-value, and disposable: keep only the current position in an in-memory geospatial index, and stream the trail to Kafka for analytics. Trips are low-volume and must be exactly right: put them in a relational database with transactions. Making this split explicit is most of the answer.

The matching flow

Rider requests → query the geo index for available drivers within a radius → rank them by ETA (not straight-line distance) → offer to the best candidate with a 15-second timeout → on accept, atomically transition the driver to 'on trip'; on decline or timeout, offer the next. Sequential offers avoid double-assignment; parallel offers to several drivers are faster but require a race-safe claim.

Trip lifecycle

requested → matched → driver en route → in progress → completed → paid. Model it as an explicit state machine with allowed transitions, persisted on every step. This is what makes crash recovery and support tooling possible.

4. Deep dives

This is where levels are decided. Go deep on one or two of these rather than shallow on all of them.

Geospatial indexing

A SQL query over latitude and longitude cannot use a single index efficiently for a 2D radius search. You need a structure that maps 2D space to something indexable.

Geohash: encodes a lat/long into a string prefix; nearby points share prefixes, so a radius search becomes a prefix scan over 9 neighbouring cells. Simple, and what Redis GEO uses.
QuadTree: recursively subdivides dense areas, so downtown has fine cells and the suburbs have coarse ones. Better under uneven density, more work to maintain.
S2 cells: Google's spherical variant, avoids the distortion geohash suffers near the poles and at cell boundaries.

Handling 250K location writes per second

Do not write every ping to a database. Update an in-memory index keyed by driver ID — an overwrite, not an append — so throughput is bounded by memory bandwidth, not disk. Shard the index by geographic region so each city is its own set of nodes; this also gives you regional fault isolation and lets you scale hot cities independently. Drivers whose heartbeat lapses drop out of the index by TTL.

Preventing double-assignment

This is the one place in the design that needs strong consistency. Use a conditional update — UPDATE drivers SET status='on_trip' WHERE id=? AND status='available' — and treat zero rows affected as 'someone else got them'. A distributed lock with a lease works too, but a conditional write in the transactional store is simpler and has no lease-expiry failure mode.

ETA and pricing

Straight-line distance is a bad proxy — a driver across a river is far away in time. Call a routing service for ETA on the shortlisted candidates only, so the expensive computation is bounded. Surge pricing derives from a rolling ratio of open requests to available drivers per geo cell, recomputed every minute from the Kafka stream.

Failure modes

A driver's phone loses signal mid-trip — buffer locations on the device and replay on reconnect; never cancel the trip on missing pings. The matching service crashes after offering but before the accept lands — the offer's TTL expires and the rider is re-matched, which is why offers must be idempotent and time-bounded.

5. Tradeoffs to argue

In-memory geo index vs geospatial database

Upside: In-memory handles 250K writes/sec and sub-millisecond radius queries

Cost: Volatile state and a rebuild story you must be able to explain

Sequential vs parallel driver offers

Upside: Parallel offers cut match time significantly

Cost: Requires race-safe claiming and annoys drivers who lose the race

Distance vs routed ETA ranking

Upside: Distance is instant and free

Cost: Bad matches across rivers and highways; ETA needs a routing call per candidate

6. Questions the interviewer will ask

Two riders request a ride and the same driver is the closest to both. What happens?
How does your geo index behave during a stadium exit when 20,000 people request at once?
A city's region shard goes down mid-trip. What do riders and drivers see?
How would you support scheduled rides an hour in advance?

7. Mistakes that sink this answer

Writing every location ping to a relational database
Using a lat/long BETWEEN query and calling it a geospatial index
No mechanism preventing one driver from being matched twice
Ranking purely by straight-line distance

Practice this live

Run a mock system design interview and get scored against your target level.

Start mock interview