Design Uber

This case study simulates a realistic FAANG system design interview for architecting a real-time dispatch and location-based system like Uber, Lyft, or Grab. It explores high-volume GPS data ingestion, geospatial partitioning, and race conditions during driver allocation.

1. Present the Interview Question

2. Clarifying Questions

The candidate scopes the requirements:

• ‍Candidate: What is our user scale? How many active drivers and riders do we support?
  Interviewer: We have 100 million active riders and 5 million active drivers globally.
• ‍Candidate: How frequently do drivers update their location?
  Interviewer: Active driver apps send a GPS coordinate ping every 4 seconds.
• ‍Candidate: What are the criteria for matching a rider to a driver?
  Interviewer: Proximity (finding drivers within a 3-mile/5-minute radius) is the primary factor. We also calculate ETA and check driver ratings.
• ‍Candidate: How does dynamic pricing (surge pricing) work?
  Interviewer: Pricing increases in real-time when the demand (riders calling trips) outweighs supply (active idle drivers) in a specific neighborhood.

3. Functional Requirements

• Real-time Location Ingestion: Ingest continuous GPS coordinates from active drivers every 4 seconds.
• Find Nearby Drivers: Show riders live locations of nearby idle drivers on their app map.
• Ride Request & Match: Match a rider with the nearest available driver, preventing double booking.
• Trip Tracking: Stream live coordinate updates to the rider's phone during the active ride.
• Surge Pricing: Apply price multipliers dynamically in high-demand, low-supply cells.

4. Non-Functional Requirements

• Low Latency Location Streaming: Location updates must process in under 1 second.
• Consistency: The matching engine must be strictly consistent to avoid matching one driver to two rides.
• High Write Availability: Ingesting millions of driver location pings must not degrade system read performance.

5. Capacity Estimation

1. Location Ingestion QPS (Writes)

• Active drivers: 5 Million.
• Update frequency: Every 4 seconds.
• Ingestion QPS: 5,000,000 / 4 = 1.25 Million writes/sec (QPS).
  Implication: We need a highly optimized in-memory or append-only write layer to handle 1.25M QPS.

2. In-Memory Active Location Cache (RAM)

We only need to track the *latest* coordinate of each active driver in memory.
Driver active record: driver_id (16B), latitude (8B), longitude (8B), status (1B), timestamp (8B) = ~41 bytes.
Total location memory capacity: 5,000,000 * 41 bytes = ~205 Megabytes. (Extremely small; easily fits in memory on a single Redis node).

3. Map Search QPS (Reads)

Assume 10 million active riders open the app. The client app requests nearby drivers every 10 seconds.
Read QPS: 10,000,000 / 10 = 1 Million reads/sec (QPS).

6. Identify Core Components

• Location Ingestion Gateway: Terminates connections and ingests pings.
• Location Service (Redis Geospatial): In-memory store holding driver coordinates.
• Geospatial Index Service (H3 Hexagons): Partitions coordinate space.
• Demand Service: Receives ride requests.
• Matching Engine: Evaluates matches and secures driver allocations.
• Surge Pricing Engine: Aggregates supply/demand density.

7. High-Level Architecture

The High-Level design separates the location ingestion write path from the rider match/dispatch loop:

8. API Design

1. Driver Location Stream Frame (WebSocket)

2. Ride Request API

POST /api/v1/trips/request

Request Payload:

Response Payload (202 Accepted):

9. Data Model

We track active trip states using SQL to ensure ACID transaction consistency during driver matching transitions:

10. Database Selection

‍Candidate:
- Real-Time Location Cache: I choose a Redis cluster. Redis provides native geospatial commands (like GEOADD and GEORADIUS), which use geohash strings behind the scenes. This enables low-latency coordinate lookups.
- Trip Management Database: I choose a relational database (PostgreSQL).
Justification: Matching drivers requires strict transaction safety. We must ensure that when an allocation completes, the trip status and driver state are committed atomically. PostgreSQL's row locking features prevent duplicate driver booking collisions.

11. Deep Dive: Geospatial Indexing (H3 Hex hexagons)

To perform fast queries like *"find drivers within 3 miles"*, scanning all 5 million drivers is impossible. We must partition the map.

• Why Hexagons (Uber H3) over Squares?
  If we use a square grid (e.g. Google S2), the distance from the center of a square to its corners is different than the distance to its sides. Hexagons have a unique mathematical benefit: the distance from the center of a hexagon to all its 6 neighbors is exactly the same. This simplifies radius search calculations.
• Implementation Details:
  We partition the earth using H3 resolution 8 cells (radius ~0.7 km).
  When a driver streams their GPS coordinate, the Location Service calculates the H3 index value in memory (e.g. 8828308281fffff) and writes the driver ID to a Redis set mapped to that cell key.
  When searching for nearby drivers, the matching service checks the rider's cell key and its 6 neighboring hexagons, restricting the search space to a few dozen keys.

12. Complete Request Lifecycle

Driver Ingestion Path

1. Driver app streams current coordinates over WebSockets every 4 seconds.
2. The Ingestion Gateway parses the coordinates and publishes an event to a Kafka location queue.
3. Location Workers consume the event, calculate the H3 hex ID, and execute a Redis pipeline:
   - GEOADD drivers_set longitude latitude driver_id
   - SET driver:driver_id:cell hex_id

Rider Match Path

1. Rider sends a trip request. The Demand Service validates pick-up coordinates.
2. Demand Service queries the Surge Engine to get the price multiplier.
3. Demand Service creates a pending record in PostgreSQL and pushes a matching job to Kafka.
4. The Matching Engine consumes the job, reads the rider's H3 cell, and queries Redis for available drivers inside that cell and neighboring cells (using GEORADIUS).
5. The engine sorts candidate drivers by ETA. It selects the top driver, locks their state in Redis, and sends a WebSocket request to the driver's phone.
6. If the driver accepts, PostgreSQL commits the matched trip status. If the driver declines (or times out in 10s), the engine releases the lock and retries with the next candidate.

13. Scaling Strategy: Geo-Sharding

Since riders in San Francisco only match with drivers in San Francisco, we can partition our systems by geographic regions:

• Geo-Routing at Gateway: Route API traffic to regional data center clusters (e.g. Europe East, US West) based on client coordinates.
• Regional Redis Shards: Partition Redis clusters by city boundaries. London coordinates are cached only in European Redis nodes, ensuring single-digit millisecond latency.

14. Bottleneck Analysis: Double Matching

‍Candidate: We enforce lock boundaries using Redis distributed locks:
1. When the Matching Engine selects driver X, it attempts to acquire a Redis lock: SET lock:driver_X locked NX PX 12000.
2. If the lock fails, it means another thread is matching driver X. The engine immediately skips driver X and tries the next candidate.
3. If the lock succeeds, it sends the offer to the driver. If the driver accepts, we commit the state transition in PostgreSQL, keeping the lock until the trip starts.

15. Trade-off Discussion: Location Storage Frequency

Interviewer: Why use WebSockets over simple UDP packets for driver location updates?
‍Candidate:
- *UDP:* Lowest overhead and fastest ingestion. However, UDP offers no delivery guarantees. In dense city centers with poor cellular signal, lost location updates can cause drivers to drop off the map.
- *WebSockets (TCP):* Guarantees delivery and keeps a persistent connection active. This allows us to push trip offers to drivers in real-time over the same socket, eliminating connection overhead for dispatches.
Decision: The reliability and bi-directional nature of WebSockets outweigh UDP's speed benefits for our core dispatch flow.

16. Failure Scenarios

Outage mitigations:

• Redis Cluster Node Crash: Since driver coordinates are updated every 4 seconds, location data is transient. If a Redis node fails and failover replica promotion takes 5 seconds, the new master will quickly repopulate with fresh coordinates naturally.
• Geospatial Lock Failures: If a driver loses connection mid-trip, we keep the trip active. The client app uses cached coordinates to estimate the route.

17. Security Design

• Location Privacy: Obfuscate passenger coordinates in historical database logs. Add a randomized offset (e.g. 50 meters) to protect user home details from data leaks.
• SSL Pinning: Enforce SSL pinning on driver apps to prevent request manipulation and fake GPS spoofing.

18. Monitoring & Observability

• Unmatched Trip Percentage: Alert if the percentage of requests that fail to match a driver within 5 minutes spikes.
• Ingestion Queue Lag: Monitor Kafka consumer lag for location queues to ensure coordinates are fresh.

19. Cost Optimization

To save on connection bandwidth: if a driver status changes from "idle" to "on_trip", we decrease their update frequency from every 4 seconds to every 10 seconds. The client app uses dead reckoning algorithms to estimate intermediate locations, reducing server QPS by 60%.

20. Production Improvements: Dynamic Surge Pricing

The surge pricing engine calculates dynamic pricing multipliers using a real-time stream aggregation model:
1. Location updates and trip requests are published to Kafka.
2. Apache Flink aggregates supply (idle drivers) and demand (pending trip requests) in each H3 hexagon every 10 seconds.
3. If the ratio of requests to idle drivers exceeds 1.5, a surge multiplier is computed (e.g. multiplier = requests / idle_drivers) and written to Redis.
4. When a user requests a ride, the Demand Service reads the surge multiplier from Redis to calculate the dynamic fare.

21. Interviewer Follow-up Questions

‍Candidate: We route location updates via WebSockets:
1. When a trip starts, the rider establishes a WebSocket connection to a Gateway.
2. The rider's gateway subscribes to a Redis Pub/Sub channel for that active trip: trip_channel:trip_123.
3. As the driver streams coordinates, their gateway publishes them to the trip channel.
4. The rider's gateway intercepts the coordinates and pushes them to the rider's phone in real-time, updating the map cursor.

22. Final Architecture

The complete optimized architecture showing driver location ingestion, geo-sharded caching, and the matching engine matching paths:

23. Summary

We designed Uber using a geospatial-sharded architecture. Drivers stream GPS coordinates every 4 seconds to a Location Ingestion Service, which updates an in-memory Redis cluster. The map is partitioned into H3 hexagons to enable fast proximity searches. Race conditions during matching are avoided using Redis distributed locks and PostgreSQL database transactions.

24. Cheat Sheet

25. Candidate Interview Evaluation