Design Uber

"Design Uber" (and its sibling "design Lyft") is the canonical geospatial system design question. The crux is matching each rider with a nearby driver in real time, which means ingesting a flood of location pings and answering "who's near this point?" thousands of times a second — without scanning every driver on the map.

Here's the full Uber system design walkthrough with a diagram, covering rider-driver matching, geospatial indexing (geohash, quadtree, S2), the trip lifecycle, surge, and scaling.

  Rider App                                 Driver App
     |  request ride                            |  location ping (every ~4s)
     v                                          v
+------------------+                   +------------------+
|   API Gateway    |                   | Location Service |
+--------+---------+                   +---------+--------+
         |                                       |
         v                                       v
+------------------+   nearby drivers   +-------------------+
| Matching Service | <----------------- | Geospatial Index  |
+--------+---------+   (geohash query)  | Redis: cell -> ids|
         |                              +-------------------+
         v
+------------------+      +----------------+     +----------------+
|  Trip Service    |----> | Trips DB       |     | Notification / |
| (lifecycle/state)|      | (durable)      |     | Push Service   |
+--------+---------+      +----------------+     +----------------+
         |
         v
+------------------+
| Pricing / Surge  |  supply vs demand per cell
+------------------+

1. Clarify the requirements

Functional requirements

• Riders request a ride from a pickup location
• Drivers continuously share their location
• Match a rider to a nearby available driver
• Track the trip through its lifecycle and show live ETAs
• Compute fare, including surge pricing

Non-functional requirements

• Low-latency matching (a rider shouldn't wait)
• High write throughput for location updates
• High availability — trips must not be lost mid-ride
• Geographic scale across many cities, sharded by region

Back-of-the-envelope scale: Assume ~5M active drivers each sending a location ping every 4 seconds — that's well over 1M location writes/sec, the dominant load in the system. Ride requests are far rarer (tens of thousands/sec at peak), but each one triggers a proximity search. So the design is shaped by a write-heavy location stream and a read-heavy nearest-neighbor query.

2. API design

# Driver streams location
POST /v1/drivers/{id}/location   { lat, lng }       (every ~4s)

# Rider requests and tracks a ride
POST /v1/rides                   { pickup, dropoff } -> { rideId }
GET  /v1/rides/{id}              -> { status, driverLoc, eta }

# Driver accepts and progresses the trip
POST /v1/rides/{id}:accept
POST /v1/rides/{id}:status       { state: "arrived" | "started" | "completed" }

3. The geospatial index: geohash, quadtree, S2

The whole question hinges on one operation: "find available drivers within N km of this point." Computing the distance to every driver is O(drivers) and hopeless at scale. The fix is a geospatial index that buckets the world into cells so proximity becomes a cheap lookup.

• Geohash encodes a lat/lng into a short string where nearby points share a common prefix. Store drivers keyed by geohash and a neighborhood query becomes a prefix match (plus the 8 neighboring cells to handle edge cases).
• Quadtree recursively subdivides space into four quadrants, going deeper where driver density is high — useful when density is very uneven across a city.
• S2 cells (Google's library) map the globe onto a space-filling curve, giving uniform, hierarchical cells that many production systems favor.

All three turn nearest-neighbor search into a bounded cell lookup. Drivers' current positions live in an in-memory store (Redis) keyed by cell, overwritten on each ping — this data is high-write and ephemeral, so it doesn't belong in the durable trips database.

4. Matching and the trip lifecycle

When a rider requests a ride, the matching service computes the pickup's cell, queries the geospatial index for nearby available drivers, ranks them (by ETA, rating, direction of travel), and offers the trip to the best candidate. If the driver declines or times out, it falls through to the next. A subtle but important detail: to avoid offering the same driver to two riders at once, the matcher must lock or reserve a driver for the duration of the offer — otherwise concurrent requests in a busy cell can double-book. A short-lived reservation key in Redis handles this cleanly.

Once accepted, the trip service owns a small state machine and persists it in the durable trips DB:

requested -> matched -> driver_en_route -> arrived
          -> in_progress -> completed (-> rated, paid)

Each transition emits events used for live ETAs, push notifications to both parties, and the final fare. The same kind of push delivery as a real-time chat app carries "driver is arriving" alerts. During the ride, the rider app keeps showing the driver's live position; that stream comes from the same location pings, relayed to the rider over a WebSocket or repeated polling so the map updates smoothly.

Because a trip is the system of record — it ties to payment and ratings — the trip service must survive a server crash mid-ride. The state machine is persisted on every transition, and an idempotency key on each request prevents a retried "complete" or "accept" from corrupting the trip's state.

5. Surge pricing

A pricing service watches supply (available drivers) versus demand (open requests) per geographic cell, using the very same location and request streams the matcher consumes. When demand outstrips supply in a cell, it raises a multiplier for that area; the multiplier is recomputed continuously and applied at request time. Because it's evaluated per cell, surge is local: one busy neighborhood doesn't raise prices across the whole city.

6. Data model, storage & scaling

• Driver location (Redis, in-memory) — keyed by geospatial cell, overwritten each ping; ephemeral and high-write.
• Trips, payments, ratings (durable DB) — sharded relational or wide-column store; this is the system of record.
• Shard by region/city so each city's location stream and matching run independently — geography is a natural partition key.
• Message queue decouples location ingestion, notifications, and billing from the request path.

Key trade-offs the interviewer probes

• Geohash vs quadtree vs S2. Geohash is simple and prefix-friendly; quadtree adapts to uneven density; S2 gives uniform global cells. Any is defensible — what matters is explaining why a flat distance scan won't scale.
• Location store durability. Keep live positions in memory and accept that they're disposable; never burden the durable trips DB with 1M+ writes/sec of throwaway pings.
• Cell size. Too coarse and a query returns too many drivers; too fine and you must scan many neighboring cells. The cell size is a tunable trade-off between query precision and lookup cost.

FAQ

How does Uber find nearby drivers efficiently?

It uses a geospatial index. Encoding each driver's latitude/longitude into a geohash, S2 cell, or quadtree bucket turns a nearest-neighbor search into a cheap prefix or cell lookup, so finding drivers within a few kilometers does not require scanning every driver on the map.

What is geohash and why use it for a ride-sharing system?

Geohash encodes a latitude/longitude pair into a short string where nearby locations share a common prefix. Storing drivers keyed by geohash lets you query a neighborhood with a prefix match, which is far faster than computing distances to every driver. Quadtree and Google's S2 cells solve the same proximity-search problem with different trade-offs.

How are driver locations updated in real time?

Drivers send a location ping every few seconds. Those updates flow through a location service into an in-memory geospatial store (such as Redis), which is high-write and ephemeral by design. Trip and billing data is persisted separately in a durable database.

How does surge pricing work in a system design answer?

A pricing service watches supply (available drivers) and demand (open ride requests) per geographic cell. When demand outstrips supply in a cell, it raises a multiplier for that area. It is computed per region and updated continuously from the same location and request data the matching service uses.

How do you store driver location versus trip data?

Driver location is high-volume, short-lived data best kept in a fast in-memory store keyed by geospatial cell and overwritten on each ping. Trips, payments, and ratings are durable records stored in a sharded relational or wide-column database. Splitting the two keeps the hot location path fast without risking the system of record.