Design: Uber / Ride-Hailing¶

Difficulty: Senior → Staff | Time: 60–75 minutes

1. Problem Statement¶

Design a ride-hailing platform: a rider requests a trip from point A to point B, the system finds and assigns a nearby available driver, both parties see each other's live location on a map until pickup and again until drop-off, and the trip is priced and closed out at the end.

Every other exercise on this site reduces to caching, fan-out, or a shared counter — a hot key, a viral read, a shared integer. This is the first exercise where the core hard problem is genuinely geospatial: hundreds of thousands of drivers are continuously moving points, and the central query is "who are the K nearest available points to this moving point, right now?" That query has no cache-friendly answer — the answer set changes every few seconds as drivers move, and a naive relational index (WHERE lat BETWEEN ... AND lng BETWEEN ...) degrades badly at city scale. Say this distinction out loud early: you are not looking for a hot key to shard away, you are looking for a spatial data structure.

2. Clarifying Questions¶

3. Functional Requirements¶

• Rider requests a trip (pickup, destination); system returns a matched driver or a wait state
• Driver app reports live location continuously; rider app reports pickup/drop-off location
• Rider and driver each see the other's live position on a map during an active trip
• Driver can accept or reject/timeout a match offer
• Trip progresses through a defined lifecycle (requested → matched → en route → in progress → completed/cancelled)
• Fare is computed at trip completion (base + distance/time + surge multiplier)

4. Non-Functional Requirements¶

5. Capacity Estimation¶

Drivers (one major city, peak):
  100K online drivers
  Ping every 4s → 100K / 4 = 25,000 location writes/second, this city alone
  20 major-city deployments → 500K writes/second location-ingest, globally

Geospatial index size:
  100K drivers x (driver_id 8B + lat/lng 16B + geohash 8B + status 1B + ts 8B) ≈ 41B/driver
  100K x 41B ≈ 4 MB per city in the hot geo-index — trivially memory-resident
  Even 20 cities: ~80 MB total live driver state. This is NOT a storage problem, it's a query-shape problem.

Matching:
  Normal: ~500 ride requests/sec citywide
  Rush-hour surge (concert letting out): burst to ~3,000 requests/sec citywide
    (this is the NFR peak — 25K/s is location *ingest* for this city, not matches)
  Each match: 1 nearby-driver query + 1 conditional assignment write

Live-tracking fan-out:
  Each active trip has 2 observers (rider + driver) polling/subscribing to the other's position
  500K concurrent trips globally x 2 = 1M live location subscriptions
  At a 4s cadence that's 250K location pushes/sec to end-user devices — a WebSocket/pub-sub problem, not a DB problem

Trip records:
  15M trips/day x ~2KB (route, fare, timestamps) ≈ 30 GB/day, cheap relational/append storage

6. API Design¶

# Rider
POST /v1/rides
  { "pickup": {"lat":37.77,"lng":-122.41}, "destination": {...}, "ride_type": "standard" }
  → 202 { "request_id": "r_abc", "status": "searching" }

GET  /v1/rides/{request_id}
  → { "status": "matched", "driver": {...}, "eta_seconds": 180, "trip_id": "t_123" }

WS   /v1/rides/{trip_id}/stream        # live driver location + status pushes to rider

# Driver
POST /v1/driver/location
  { "driver_id": "d_1", "lat":37.78, "lng":-122.40, "heading": 90, "ts": 1755400000 }
  → 200 (fire-and-forget cadence: every 4s while online)

POST /v1/driver/offers/{offer_id}/respond
  { "response": "accept" | "reject" }
  → 200, or 409 if the offer already expired/was taken by matching another driver's accept

POST /v1/driver/trips/{trip_id}/status
  { "status": "arrived" | "picked_up" | "completed" }

# Internal (matching → driver app), pushed not polled
Offer pushed over WS: { "offer_id": "o_1", "trip_request_id": "r_abc", "pickup": {...}, "expires_in_ms": 8000 }

7. Data Model¶

Driver location store — the one decision that defines this exercise.

The naive option is a relational table: drivers(id, lat, lng, updated_at) with WHERE lat BETWEEN ? AND ? AND lng BETWEEN ? AND ?. This works at small scale but has two problems that get worse with driver count: (1) a lat/lng range scan on a B-tree index over two independent columns can't prune efficiently — a bounding box query still has to intersect two range scans and filter, and (2) every one of 100K drivers rewrites their row every 4 seconds, meaning the index is being rebalanced continuously under a query workload that also hits it constantly.

Pick geohashing for this design (over quadtree/S2), and say why: a geohash is a single string computed directly from (lat, lng) — no tree structure to maintain, so a driver's location update is an O(1) upsert keyed by geohash prefix, and "nearby drivers" becomes a set lookup on the current cell plus its 8 neighbors, not a tree traversal. The trade-off you're accepting: geohash cells are not uniform area (they distort near the poles and are rectangular, not circular, so a naive single-cell query can miss a nearby driver just across a cell boundary — hence always querying the 3x3 neighbor grid, not just the exact cell) and cell edges don't align with actual "distance," so a driver 50m away in an adjacent cell and one 50m away in the same cell are indistinguishable by cell alone — you still rank candidates by real haversine distance after the cell lookup narrows the candidate set. Quadtrees adapt cell size to driver density (better in sparse suburbs) and S2 cells handle Earth's curvature more precisely (better at global scale spanning many latitudes) — either is defensible; geohash wins here because updates are O(1) with no rebalancing, which matters when the write rate (25K/s) dwarfs the query rate.

Hot store (Redis) — geohash SETs, not GEOADD. One model:
  geo:{city}:{geohash6}  → SET of driver_ids currently in that ~1.2km x 0.6km cell
  driver:{driver_id}     → HASH {lat, lng, geohash6, status, heading, updated_at}

Location write:
  SADD geo:{city}:{new_hash} driver_id
  SREM geo:{city}:{old_hash} driver_id   # if the cell changed
  HSET driver:{id} lat lng geohash6 ...

Nearby:
  SUNION of the rider's cell + 8 neighbors, then rank by haversine on HASH coords

-- Cold, durable trip record — small write volume, standard relational store
CREATE TABLE trips (
    id              VARCHAR(20) PRIMARY KEY,
    rider_id        VARCHAR(20) NOT NULL,
    driver_id       VARCHAR(20),
    pickup_lat      DOUBLE, pickup_lng DOUBLE,
    dest_lat        DOUBLE, dest_lng DOUBLE,
    status          VARCHAR(20) NOT NULL,   -- see state machine below
    requested_at    TIMESTAMPTZ NOT NULL,
    matched_at      TIMESTAMPTZ,
    picked_up_at    TIMESTAMPTZ,
    completed_at    TIMESTAMPTZ,
    fare_cents      INT,
    surge_multiplier DECIMAL(3,2) DEFAULT 1.0,
    INDEX idx_driver_status (driver_id, status),
    INDEX idx_rider_ts (rider_id, requested_at)
);

Trip state machine:

8. Version 1 — simplest thing that works¶

Single region, driver locations in a relational table, matching does a naive bounding-box scan.

graph LR
    DriverApp -->|POST location every 4s| API[API process]
    API -->|UPDATE drivers SET lat,lng| PG[(Postgres: drivers, trips)]
    RiderApp -->|POST /rides| API
    API -->|SELECT WHERE lat/lng BETWEEN ...| PG
    API -->|assign nearest| RiderApp

def find_nearby_drivers(pickup_lat, pickup_lng, radius_km=3):
    lat_delta = radius_km / 111.0                       # rough km-per-degree latitude
    lng_delta = radius_km / (111.0 * cos(radians(pickup_lat)))
    rows = db.query("""
        SELECT driver_id, lat, lng FROM drivers
        WHERE status = 'available'
          AND lat BETWEEN %s AND %s
          AND lng BETWEEN %s AND %s
    """, pickup_lat - lat_delta, pickup_lat + lat_delta,
         pickup_lng - lng_delta, pickup_lng + lng_delta)
    return sorted(rows, key=lambda r: haversine(pickup_lat, pickup_lng, r.lat, r.lng))[:20]

def match_ride(request):
    candidates = find_nearby_drivers(request.pickup_lat, request.pickup_lng)
    for driver in candidates:
        if try_assign(driver.driver_id, request.id):    # simple UPDATE ... WHERE status='available'
            return driver
    return None  # no_drivers_found

This works for a pilot city with a few thousand drivers. Do not add infrastructure yet — find the actual bottleneck first.

9. Identify the bottleneck¶

10. Version 2 — geospatial indexing¶

Move driver locations out of Postgres entirely into an in-memory, geo-indexed store keyed by geohash. Matching becomes a bounded lookup: compute the rider's cell, check that cell plus its 8 neighbors, rank the (small) candidate set by real distance.

graph LR
    DriverApp -->|POST location every 4s| API[API process]
    API -->|SADD/SREM geohash SET| Geo[(Redis geohash grid)]
    RiderApp -->|POST /rides| API
    API -->|SUNION cell+8 neighbors| Geo
    API -->|rank + assign| RiderApp
    API -.->|async, batched| PG[(Postgres: trip records only)]

def find_nearby_drivers(pickup_lat, pickup_lng, radius_km=3):
    cells = geohash_and_neighbors(pickup_lat, pickup_lng)  # 3×3 at geohash6
    ids = redis.sunion(*[f"geo:sf:{c}" for c in cells])
    drivers = [redis.hgetall(f"driver:{i}") for i in ids]
    ranked = sorted(drivers, key=lambda d: haversine(pickup_lat, pickup_lng, d))
    return ranked[:20]

Location writes now hit an in-memory structure sized for exactly this (~4 MB of hot state per city, see capacity estimate) instead of a durable relational table. Postgres only ever sees trip records — a few writes per trip, not per ping.

11. Identify the next bottleneck¶

12. Version 3 — production architecture¶

graph TD
    DriverApp -->|WS: location ping 4s| Ingest[Location Ingestion Service<br/>write-optimized, buffered]
    RiderApp -->|WS: subscribe to trip| Gateway[Realtime Gateway]
    Ingest -->|batched writes| GeoSvc[Geo-Index Service<br/>sharded geohash grid]
    Ingest -->|stream| Stream[Kafka: location events]
    Stream -->|fan-out| Gateway
    RiderApp -->|POST /rides| API[Trip API]
    API -->|nearby query| GeoSvc
    API -->|score + rank| Matcher[Matching Service]
    Matcher -->|offer, exclusive claim| GeoSvc
    Matcher -->|surge multiplier| Surge[Surge Pricing Service]
    API -->|trip state| TripSvc[Trip Service]
    TripSvc --> PG[(Postgres: trips, sharded by city)]
    GeoSvc --> Redis1[(Redis shard: city zone A)]
    GeoSvc --> Redis2[(Redis shard: city zone B)]

Key production decisions:

• Location ingestion is a dedicated write-optimized service, not a direct DB write per ping. Pings land in a short-lived buffer/ring and are flushed to the geo-index in small batches (e.g. every 500ms), and simultaneously published to a stream (Kafka) so the realtime gateway can fan them out to subscribed rider/driver apps without ever touching the geo-index for reads. This decouples "update where I think this driver is" from "tell everyone watching this driver where they are."
• Geo-index is sharded by city/region, each shard a Redis (or equivalent) instance owning one geographic partition. A hot cell during a surge gets extra read replicas or a temporary finer-grained cell split for that zone specifically — you don't need to over-provision every city for one stadium's surge.
• Matching service claims a driver exclusively, not just reads their position — this is the mechanism that prevents double-booking (see Consistency section below).
• Surge pricing reads live supply/demand ratio per zone (candidates found vs requests in the last N seconds) and multiplies the base fare; it does not gate matching, it only affects price shown before confirm.
• Trip service and Postgres are sharded by city — a trip in Austin never needs a trip in Tokyo's shard, which is the geographic shardability called out in Staff Extensions below.

13. Failure analysis¶

14. Consistency considerations — the double-booking race¶

This is the correctness problem the whole exercise turns on, so make the mechanism explicit rather than hand-waving "use a lock."

The race: Rider A and Rider B both request rides at nearly the same instant. Both match queries return Driver D as the nearest available candidate — this is expected and fine, the geo-index is a read-mostly view that can be slightly stale by design. The bug appears if both matching attempts proceed to assign Driver D to a trip.

The fix — assignment must be a single atomic conditional write against one source of truth for driver status, not a read-then-write:

UPDATE drivers
SET status = 'matched', current_trip_id = %s
WHERE id = %s AND status = 'available'
RETURNING id;

If this returns zero rows, the driver was already claimed — the losing matcher immediately retries against the next-nearest candidate from its already-fetched candidate list (no need to re-query the geo-index for a small miss). This is the same compare-and-swap pattern as the rate limiter's token bucket and pastebin's burn-after-read delete — "check and mutate" must be one atomic operation against a single authoritative row, never two round trips with a gap an interleaved request can land in.

sequenceDiagram
    participant A as Rider A's matcher
    participant B as Rider B's matcher
    participant Geo as Geo-index (eventually consistent)
    participant D as drivers table (source of truth)
    participant DrvD as Driver D

    A->>Geo: nearest_available(rider A location)
    Geo-->>A: [Driver D, Driver E, ...]
    B->>Geo: nearest_available(rider B location)
    Geo-->>B: [Driver D, Driver F, ...]
    note over A,B: both see Driver D as nearest — expected,\nthe index is read-mostly and slightly stale by design

    par racing CAS claim on the same driver row
        A->>D: UPDATE drivers SET status='matched', current_trip_id=trip_A\nWHERE id=D AND status='available'
    and
        B->>D: UPDATE drivers SET status='matched', current_trip_id=trip_B\nWHERE id=D AND status='available'
    end

    D-->>A: 1 row updated (won the CAS)
    D-->>B: 0 rows updated (status was no longer 'available')

    A->>DrvD: send offer(trip_A)
    B->>B: claim failed — retry against next candidate\n(Driver F) from already-fetched list, no re-query of Geo
    note over B: no dirty read-then-write gap — B never\nbelieved it had Driver D in the first place

• The geo-index is allowed to be eventually consistent (a driver shown as "available" 200ms after they were actually claimed is fine — the CAS above is what actually enforces correctness, not index freshness).
• Driver status is the one place strong consistency is non-negotiable. Everything else in this system (location display, ETA estimates, surge pricing snapshots) can tolerate seconds of staleness; driver assignment cannot tolerate even a few milliseconds of a dirty read-then-write gap.
• Idempotency on offer response: a driver's "accept" arriving twice (retry after a flaky network) must not double-assign — key the accept on offer_id, and a second accept on an already-resolved offer is a no-op 409, not a re-run of the assignment.

15. Observability¶

Metrics:
  match_latency_ms p50/p99 (SLO: p99 < 10s)
  location_ingestion_lag_ms per shard
  geo_index_query_latency_ms
  driver_claim_conflict_rate (CAS losses / total claim attempts — should be low outside surge)
  drivers_online, drivers_available, drivers_on_trip (gauge, per city)
  offer_accept_rate, offer_timeout_rate
  hot_cell_qps (top-K geohash cells by query+write volume)

Alerts:
  match_latency_p99 > 10s for 5 min
  location_ingestion_lag > 15s
  driver_claim_conflict_rate > 5% (surge is expected to spike this, but a sustained high rate outside surge means matching is broken, e.g. two matcher instances racing without the CAS)
  any single geohash cell > 20% of citywide QPS

16. Cost analysis¶

Location ingestion (25K writes/sec x 20 cities = 500K/s globally):
  Kafka/streaming cluster:                          ~$3,000/mo
  Buffered flush to Redis (reduces effective write rate 5-10x): keeps Redis cluster small

Geo-index (Redis, sharded per city, ~4-8 shards/major city):
  20 cities x 4 shards x $150/mo (small memory footprint, this is a QPS-sized cluster not a storage-sized one): ~$12,000/mo

Trip storage (Postgres, sharded by city, 15M trips/day, ~30GB/day):
  ~$4,000/mo across shards + replicas

Realtime gateway (WebSocket fan-out, 1M concurrent connections):
  ~$5,000/mo (connection-count-driven, not bandwidth-driven at this payload size)

Total: ~$24,000/mo at 20-city global scale

Cost lever: location ping cadence. Dropping from 4s to 6s during low-demand hours
  cuts ingestion + geo-index write volume by ~35% with negligible UX impact when few riders are watching maps.

17. Alternative architectures¶

18. Staff Engineer Extensions¶

19. Interview follow-ups¶

1. How would you estimate ETA? Not raw straight-line distance — needs a routing graph (road network) and historical/live traffic data. Briefly: precomputed road-segment travel-time estimates, updated from aggregate driver GPS trails, queried per candidate during ranking (not just nearest-by-distance — nearest-by-distance can pick a driver on the wrong side of a highway).
2. How does surge pricing actually get computed? Briefly: per-zone ratio of open ride requests to available drivers over a short rolling window, mapped to a multiplier; must update fast enough to reflect a sudden supply shock (concert ending) but not oscillate wildly request-to-request — usually smoothed/bucketed rather than continuous.
3. How do you rank multiple nearby candidates, not just pick the closest? Distance is one input; also consider driver's current heading (moving away vs toward pickup), acceptance-rate history (a driver who reliably rejects offers wastes the 8s timeout), and fairness (rotate among idle drivers rather than always picking the single closest to avoid starving drivers at the edge of a cell).
4. What happens to a request during the exact moment a driver's app is mid-reconnect? The geo-index may show them "available" from stale state even though their connection just dropped — this is why the CAS assignment step re-validates against the authoritative driver-status row, not the geo-index snapshot, at the moment of claim.

Self-Assessment¶

• [ ] I can explain why this exercise's hard problem is geospatial, not caching or fan-out
• [ ] I can justify geohash over quadtree/S2 with a concrete trade-off, not just a name-drop
• [ ] I can walk through the double-booking race and why it needs an atomic CAS, not a lock or a queue
• [ ] I can separate the "matching latency" SLA from the "location staleness" SLA and explain why they need different mechanisms
• [ ] I can explain why this system shards naturally by geography where other exercises on this site cannot