Design Uber / Ride Sharing

Design Uber / Ride Sharing — the 45-minute interview walkthrough

This lesson is the interview version: how to structure the answer and which deep dives to expect. The full reference design is the case study Design Uber / Ride Sharing in this chapter.

A ride-sharing platform connects two moving populations, riders and drivers, in real time. Its hardest parts aren't the usual CRUD. They are tracking millions of moving points, finding the nearest available drivers in milliseconds, and making sure one driver is never assigned to two riders.

Minutes 0–5: clarify requirements

• Core flow: rider requests → system matches a nearby driver → driver accepts → live tracking → trip ends → payment.
• Scale: e.g. 5 million active drivers sending a GPS update every ~4 seconds, which is over 1 million location writes per second at peak. Tens of millions of trips per day.
• Latency: a match within a few seconds. Location on the rider's map refreshed every few seconds.
• Scope decisions: is pricing in scope (surge)? ETAs? Scheduled rides? Pooling? Say which ones you'll cover.

The key observation to state: location data is huge, hot, and short-lived. You only care where a driver is now, so it doesn't belong in the durable trips database.

Minutes 5–15: the high-level design

 Driver app ─ location every ~4s ─▶ Location service ─▶ In-memory geo index (by cell)
                                          │                     ▲
                                          └─▶ stream (Kafka) ─▶ trip tracking, analytics, ETA models
 Rider app ─ request ride ─▶ Trip service ─▶ Matching service ─ query nearby ─┘
                                 │                 │
                                 │                 └─▶ offer to driver (push / persistent connection)
                                 ▼
                        Trips DB (durable: trips, fares, states)

• Location service: accepts the flood of GPS updates and keeps only each driver's latest position, plus availability, in a geo index held in memory.
• Matching service: for a request, finds candidate drivers near the pickup, ranks them (distance/ETA, rating), and offers the trip.
• Trip service: owns the durable trip record and its state machine (REQUESTED → MATCHED → DRIVER_ARRIVING → IN_PROGRESS → COMPLETED / CANCELLED).

Minutes 15–35: the deep dives

1. "Find drivers near this point": geospatial indexing

Scanning every driver per request is impossible. You need to partition the map into cells:

• Geohash: encodes latitude/longitude into a string where a shared prefix means nearby. A 6-character geohash is roughly a 1.2 km × 0.6 km cell. To search, look up the rider's cell plus its 8 neighbours (a point near a cell's edge has close drivers just across the boundary).
• Uber's H3 (hexagons) and Google's S2 (squares on a sphere) are refinements. Hexagons have uniform neighbour distances, which makes "rings" of nearby cells cleaner.
• Implementation: a map from cellId → set of available driverIds, sharded by cell across location servers. Redis's GEOADD/GEOSEARCH is a reasonable single-cluster answer at moderate scale.

When a driver moves across a boundary, remove them from the old cell and add them to the new one. Since only the latest position matters, updates overwrite rather than append.

2. The write load

A million updates per second is fine because they're small, overwrite-only and in memory. Shard location servers by region/cell. Apps can send updates less often when the driver is idle or stationary. The raw stream also goes to Kafka for trip replay, analytics and ETA models, off the hot path.

3. Never double-book a driver

Two matching requests may pick the same nearest driver at the same moment. Each match must atomically claim the driver:

• A conditional write, "set driver state to OFFERED(trip 123) only if it's AVAILABLE", on the store that owns driver state (a compare-and-set, or SET ... NX with a TTL in Redis).
• The TTL matters: if the driver doesn't accept within ~10–15 seconds, the claim expires automatically and the driver is available again, with no cleanup job needed.
• If the claim fails, move to the next candidate.

4. Offering and accepting

Offer to the best candidate. If there's no response or a decline, move to the next. For busy areas you could offer to a few at once, where the first to accept wins via the same atomic claim. Drivers hold a persistent connection, so offers arrive instantly. Push notifications are the fallback.

5. Surge pricing (if in scope)

Per cell, compare demand (open requests) with supply (available drivers) over a short window, and set a multiplier from that ratio, smoothed so it doesn't flicker. The multiplier is quoted and locked when the rider confirms, so the price doesn't change mid-request.

Minutes 35–45: trade-offs and wrap-up

• In-memory geo index vs database: fast and cheap to update, but volatile. If a location server dies, drivers repopulate it within one update interval (~4 s), so that's acceptable.
• Cell size: smaller cells mean fewer candidates per lookup but more boundary crossings. Tune per city density.
• Consistency where it matters: the driver claim and the trip state machine need strong consistency. Location and ETA can be approximate.
• With more time: ETA using road networks and traffic (not straight-line distance), pooled rides, fraud detection, multi-region.

Common mistakes in interviews

• Storing every GPS ping in the main relational database and querying it for matches.
• A radius search that ignores neighbouring cells.
• No story for double-booking, or a check-then-set that races.
• Using straight-line distance as if it were travel time, without at least mentioning ETA.

Follow-up questions this topic invites — and their answers

Q: Why not use PostGIS for nearby-driver queries? A: A spatial index (PostGIS with GiST) handles proximity queries well at moderate scale, and is a fine answer for a smaller service. At a million position updates per second, the problem is the write rate: constantly updating indexed rows is expensive and hurts the database used for durable data. An in-memory, overwrite-only cell index is built for exactly this pattern.

Q: How do you compute ETA? A: Straight-line distance is only a rough filter. Real ETA needs routing on the road graph with current traffic. That's done by a routing service (graph algorithms with precomputed shortcuts, like contraction hierarchies), plus models trained on historical trip times. Matching typically shortlists candidates by distance, then ranks the shortlist by ETA.

Q: What happens if the rider's phone loses connection after the match? A: The trip lives on the server, not in the app, so the match stands. The driver still gets the pickup location, and when the rider reconnects the app fetches the current trip state. Timeouts in the state machine (for example the driver waiting at pickup for N minutes) resolve abandoned trips.

Q: How would you shard the trips database? A: By trip ID for writes and by rider/driver ID for history queries, often with a separate read store for each access pattern. Active trips are a small, hot set and can be held in a fast store. Completed trips move to cheaper storage for history and analytics.