Design Uber / Ride Sharing

Design a ride-sharing platform like Uber. Riders request rides, drivers accept, and the system matches them in real time. Track driver location, display ETA, and handle surge pricing.

Capacity Estimation

• Active drivers: 5M worldwide, 1M online at peak
• Location updates: 1M drivers × 1 update/5s = 200K location writes/sec
• Ride requests: 1M concurrent rides → ~200K new requests/hour
• Geospatial index size: 1M driver locations × 64 bytes = ~64 MB — fits in Redis

Architecture

[Driver App]
  → location update every 5s
  → [Location Service]
        → Redis Geo (GeoHash index)
        → Kafka (location events for analytics)

[Rider App]
  → ride request
  → [Matching Service]
        → queries Redis Geo for nearby drivers
        → sends offer to selected driver
        → [Driver App] accepts

[Trip Service]
  → manages active trip state
  → streams location to rider via WebSocket

[Pricing Service]
  → calculates surge multiplier from supply/demand ratio
  → feeds pricing to Matching Service

Geospatial indexing: geohashing vs quadtree

The architecture above uses Redis GEO (geohash-based) — worth naming the alternative explicitly. A quadtree recursively subdivides 2D space into four quadrants, going deeper only where point density is high, which adapts naturally to uneven driver distribution (dense in a city center, sparse in a suburb) without manual tuning. Geohashing (fixed-precision string encoding of lat/lng into a sorted key) is simpler to implement on top of an existing key-value store (exactly why Redis GEO works the way it does) and enables straightforward proximity queries via key-prefix matching, but its FIXED grid size doesn't adapt to density the way a quadtree does — a geohash cell sized well for a dense city center is often far too coarse or too fine elsewhere. Redis GEO's real-world convenience (a production-ready primitive requiring no custom index to build/maintain) usually outweighs a quadtree's better density-adaptivity for most ride-sharing scale.

Real-time location updates: WebSocket vs polling

The Trip Service above streams location via WebSocket specifically because ride tracking is latency-sensitive and genuinely bidirectional-feeling (the rider expects near-instant position updates without requesting them). Polling (the rider's app periodically requesting the driver's current position) would work but adds latency (bounded by the poll interval) and wasted requests when nothing has changed — the same WebSocket-vs-polling tradeoff covered generally in Design WhatsApp's real-time delivery discussion applies directly here.

API Design

// Driver
PUT /drivers/{driverId}/location
Body: { lat, lng, heading, speed }

PATCH /drivers/{driverId}/status  { status: AVAILABLE | ON_TRIP | OFFLINE }

// Rider
POST /rides/request
Body: { riderId, pickup: {lat,lng}, destination: {lat,lng} }
Response: { rideId, driverEta, estimatedFare }

GET /rides/{rideId}/driver-location  → real-time via WebSocket

// Matching
GET /drivers/nearby?lat=X&lng=Y&radius=2km&limit=10

Database Design

Driver locations (Redis GEO — O(log N) geospatial queries)

GEOADD drivers:available <lng> <lat> "driver:42"
GEOSEARCH drivers:available FROMMEMBER <point> BYRADIUS 2 km ASC COUNT 10

Trips (PostgreSQL — ACID, payment reconciliation)

rides
  id          UUID    PK
  rider_id    UUID
  driver_id   UUID
  pickup      POINT   (PostGIS geometry)
  destination POINT
  status      ENUM    (REQUESTED, ACCEPTED, ONGOING, COMPLETED, CANCELLED)
  started_at  TIMESTAMP
  ended_at    TIMESTAMP
  fare        DECIMAL

Trip tracking (Cassandra — time-series location history)

trip_location
  trip_id     UUID    PK
  recorded_at TIMEUUID
  lat, lng    DOUBLE

Scaling

Geospatial matching at scale

Redis GEO uses GeoHash under the hood — O(log N) radius search. With 1M active drivers:

• GEOSEARCH radius 2km returns results in <1ms
• Partition drivers by city (each city has its own Redis key)

Driver matching algorithm

1. Query Redis GEO for nearest 10 available drivers
2. Filter by vehicle type, rating
3. Offer ride to nearest driver (5-second acceptance window)
4. If rejected, offer to next driver

Surge pricing

surge_multiplier = demand / supply
where demand = ride_requests_last_10min in zone
      supply = available_drivers_last_10min in zone

if surge > 1.5: show surge warning to rider

Matching algorithm trade-offs: nearest driver vs utilization balancing

The scaling section above describes nearest-available-driver matching — simple, minimizes rider wait time for that specific request. The alternative worth naming: balancing driver utilization across a zone, deliberately NOT always picking the geometrically nearest driver, instead factoring in each nearby driver's recent idle time or earnings — this improves fairness and overall driver retention/satisfaction across the whole platform, at the cost of occasionally giving an individual rider a slightly longer wait than pure nearest-driver would. Production ride-sharing systems generally blend both: nearest-driver as the primary signal, with utilization as a secondary tie-breaker among close candidates, rather than purely optimizing one metric.

Handling driver/rider disconnects and ride-state consistency

Mobile network instability means the Trip Service can't assume a continuous connection — a driver's app losing connectivity mid-trip shouldn't corrupt ride state or leave the rider unable to see any updates. The standard approach: the Trip Service treats itself as the single source of truth for ride state (not the client apps), with each app reconnecting and re-syncing full current state on reconnect rather than relying on a continuous stream of incremental updates it might have partially missed. A brief location staleness during a disconnect is an acceptable, expected condition (shown as 'reconnecting' in the rider UI) rather than a failure requiring special-case handling — the system is explicitly designed to tolerate transient disconnects as normal operation, not an edge case.

• Redis GEO vs PostGIS: Redis GEO is faster (in-memory, O(log N)); PostGIS supports complex polygon queries and is durable. Use Redis for real-time matching, PostGIS for analytics.
• Push vs poll for driver location: Drivers push every 5s regardless. Riders poll every 3s for ongoing trips (or WebSocket for real-time map updates).
• Matching algorithm: greedy nearest-driver is fast but sub-optimal. ML-based matching (considering traffic, driver idle time) improves ETA accuracy but adds latency.

• Location write storm: 200K writes/sec to Redis. Use pipeline batching and Redis Cluster.
• Matching hotspots: airport, stadium events create thousands of simultaneous requests. Queue requests; serve in order.
• ETA accuracy: poor ETA erodes trust. Integrate with Google Maps / Here Maps API for real-time traffic.

• Redis GEO down: fall back to PostgreSQL PostGIS. Matching degrades from <1ms to ~10ms — still acceptable.
• Matching Service down: riders see 'no drivers available'. Trip requests queue; retry when service recovers.
• Driver app crash: trip status maintained server-side. Driver reconnects and resumes trip.