Katkat
Back

Design a Real-Time Nearby-Driver Service

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

Tests the ability to architect a high-throughput, low-latency geospatial ingestion and query service that tracks millions of moving entities, handles state transitions, and avoids boundary/hot-spot bottlenecks.

Scenario

Design the core real-time nearby-driver tracking service for a ride-hailing platform. When a passenger opens the mobile app, they need to see available drivers within their immediate vicinity. As hundreds of thousands of drivers move simultaneously, their mobile clients transmit location updates every few seconds. Your service must ingest these telemetry streams, maintain driver state, and serve low-latency geospatial queries.

Requirements

Functional Requirements

  • Location Ingestion: Ingest periodic location pings (latitude, longitude, timestamp, driver ID) from active drivers every 3 to 5 seconds.
  • Nearby Driver Discovery: Given a rider's coordinates and an optional radius (e.g., 3 km), return the top K (e.g., 10) closest available drivers.
  • State Management: Drivers can be in states such as OFFLINE, AVAILABLE, EN_ROUTE_TO_PICKUP, or ON_TRIP. Only AVAILABLE drivers should be discoverable.
  • Stale Driver Eviction: Automatically prune drivers who fail to send a heartbeat or ping within a configurable window (e.g., 15–30 seconds).

Non-Functional Requirements

  • Low Latency: p99 query latency under 50 ms for nearby-driver searches; ingestion pipeline processing latency under 100 ms.
  • Scalability: Scale to support 5 million total active drivers globally, with up to 1 million drivers concurrently online during peak hours.
  • Availability: 99.99% availability. Temporary eventual consistency of vehicle locations is acceptable, but stale or unavailable drivers should not be matched.

Scale Assumptions

  • Peak concurrent online drivers: 1,000,000
  • Ingestion rate: 1 update per 4 seconds per driver = 250,000 updates/second
  • Rider search requests: Peak read throughput of 50,000 queries/second

What Your Design Should Cover

  1. Data Ingestion & In-Memory Spatial Index: Evaluate spatial indexing techniques (e.g., H3 hexagonal indexing vs. Geohash vs. QuadTrees) and explain your sharding strategy across memory tiers.
  2. Boundary & Filtering Pipeline: Address cell-edge boundary problems (e.g., querying neighbor cells / k-rings) and separating coarse cell retrieval from fine-grained Haversine distance ranking.
  3. Hot Spot Handling & State Transitions: Mitigate severe traffic concentrations (airports, concerts) and describe how status changes (accepting a trip) immediately invalidate availability.
  4. Failure Recovery & Edge Smoothing: How client-side interpolation masks network jitter and how the system recovers state if an indexing node fails.

Hints

Hint 1

Choose a discrete global grid system such as Uber's H3 or Geohash so driver updates map deterministically to discrete cell IDs that serve as partition keys.

Hint 2

Solve the cell-edge boundary problem by querying the target cell alongside its immediate neighboring cells (e.g., an H3 k-ring of 1), followed by exact distance filtering.

Hint 3

Handle stale drivers by recording an epoch timestamp in an in-memory sorted set or setting an expiring TTL on the driver's location key.

Follow-up questions

  • How would you prevent a sudden burst of rider queries in a single spatial cell (like a stadium event) from overloading the node hosting that cell?
  • How can the rider's mobile client render smooth car animations if location updates only arrive every 4 seconds?
  • If an entire in-memory spatial index partition crashes, what is your strategy to rebuild state without waiting for millions of drivers to re-ping?