Bird
Raised Fist0

Uber - Driver Matching, Surge Pricing, Real-Time Location Tracking

HLDhardInterview freq: high
Choose your preparation mode4 modes available
🏗️
Uber - Driver Matching, Surge Pricing, Real-Time Location Tracking
Design a scalable, low-latency system for real-time driver-passenger matching with dynamic surge pricing and live location updates
hardLocation and Mapping SystemsFreq: high
Prerequisites:GeohashWebSocketsLocation Indexing
⚙️
Functional Requirements
  • Real-time driver location ingestion and tracking with sub-second latency
  • Efficient matching of riders to nearby available drivers using geospatial queries
  • Dynamic surge pricing calculation based on supply-demand imbalance in regions
  • Push notifications to drivers and riders about matches and price changes
  • Support for driver status updates (available, busy, offline) in real-time
  • Accurate fare estimation incorporating surge multipliers before ride confirmation
📊
Non-Functional Requirements
  • Support 2 billion daily active users globally
  • Handle peak write throughput of ~925K location updates per second
  • End-to-end latency for matching and notifications under 100ms P99
  • System availability of 99.99% with graceful degradation under load
  • Data consistency: eventual consistency acceptable for location, strong consistency for surge pricing
❓
Clarifying Questions to Ask
  • What is the expected average and peak number of concurrent drivers and riders per city?
  • How frequently do drivers send location updates and what is the payload size?
  • What is the acceptable staleness for driver location data in matching?
  • How is surge pricing calculated and how often does it update?
  • Are there SLAs for notification delivery to drivers and riders?
  • Should the system support multi-region failover and disaster recovery?
Out of Scope
✗ Route optimization and turn-by-turn navigation
✗ Payment processing and billing systems
✗ Driver background checks and onboarding
✗ Long-term historical analytics and reporting
📌
Assumptions
  • 2 billion DAU globally
  • Each user generates 40 location or status messages per day
  • Average message size is 100 bytes
  • Peak traffic is 5x average during rush hours
⚡
QPS Calculation
write qps925926
peak write qps4629630
read qps13888890
💾
Storage Estimate
daily storage gb7450
retention days7
total storage with replication gb156000
🖥️
Server Estimate
location ingestionKafka cluster with 100 brokers to handle 4.6M writes/sec partitioned by geohash
matching service200 stateless microservice instances behind load balancer to handle 14M reads/sec with caching
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |  Mobile Apps   |
          | (Drivers/Riders)|
          +--------+-------+
                   | WebSocket / REST API
                   v
          +----------------+
          |  API Gateway   |
          +--------+-------+
                   |
                   v
          +----------------+       +----------------+
          | Location Ingest|       | Surge Pricing  |
          |  Service       |       | Service        |
          | (Kafka + Cass) |       | (Redis + Cass) |
          +--------+-------+       +--------+-------+
                   |                        |
                   v                        v
          +----------------+       +----------------+
          | Location Store |       | Surge Store    |
          | (Cass + Redis) |       | (Cassandra)    |
          +--------+-------+       +----------------+
                   |
                   v
          +----------------+
          | Matching Svc   |
          | (Geo index +   |
          |  Redis)        |
          +--------+-------+
                   |
                   v
          +----------------+
          | Notification   |
          | Service (Kafka |
          |  + WebSocket)  |
          +----------------+
🧩
Components
API Gateway
Entry point for all client requests, handles authentication, rate limiting, and routing
Why thisNginx + Envoy proxy provide high throughput, low latency, and support WebSocket upgrades
Why notDirect client-to-service communication lacks centralized control and complicates scaling
Location Ingest Service
Consumes driver location updates from Kafka, validates and writes to Cassandra and Redis
Why thisKafka supports high-throughput, partitioned ingestion with durability; Cassandra scales linearly for writes
Why notRabbitMQ lacks partitioning at this scale; PostgreSQL cannot handle 4.6M writes/sec without sharding
Location Store
Stores recent driver locations in Cassandra for persistence and Redis for low-latency lookups
Why thisCassandra offers high write throughput and geo-partitioning; Redis TTL keys enable fast presence expiry
Why notMongoDB's single primary node limits write scalability; Memcached lacks persistence and TTL management
Matching Service
Performs geospatial queries using geohash indexes and Redis sorted sets to find nearby available drivers
Why thisRedis sorted sets provide sub-ms range queries; geohash indexing reduces search space efficiently
Why notElasticsearch has higher query latency and complexity; PostGIS does not scale well for real-time queries
Surge Pricing Service
Calculates dynamic surge multipliers based on supply-demand ratios per geohash region, stores in Redis and Cassandra
Why thisRedis supports fast atomic increments and TTL for surge data; Cassandra persists historical surge data for analytics
Why notMySQL's row locking limits concurrent surge updates; DynamoDB's eventual consistency delays pricing updates
Notification Service
Pushes real-time match and surge notifications to drivers and riders via Kafka and WebSocket connections
Why thisKafka decouples event generation and delivery; WebSocket enables low-latency bidirectional communication
Why notPolling HTTP APIs increase latency and server load; MQTT lacks widespread mobile client support
🔄
Data Flow
1
Driver Mobile App → API Gateway
Send location update via WebSocket
Low-latency, persistent connection reduces overhead
2
API Gateway → Location Ingest Service (Kafka)
Publish location update to Kafka topic partitioned by geohash
Partitioning ensures load distribution

Practice

(1/5)
1. In the request flow, at Step 4 the Delivery Worker checks the message queue's visibility timeout before processing. What happens if the visibility timeout expires before the message is acknowledged?
easy
A. The message is moved to a dead-letter queue without retry
B. The message is deleted immediately to prevent duplicates
C. The message is archived permanently without redelivery
D. The message becomes visible again and can be redelivered to another worker

Solution

  1. Step 1: Understand visibility timeout semantics

    Visibility timeout hides the message during processing; if not acknowledged, it reappears for redelivery.
  2. Step 2: Analyze options

    Immediate deletion (A) risks data loss; archiving without retry (C) prevents recovery; dead-letter queue (D) is for failed retries, not timeout expiry.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Visibility timeout expiry -> message reappears for retry [check]
Hint: Visibility timeout expiry -> message requeued for retry [check]
Common Mistakes:
2. You need to handle 1 million product updates per minute in the catalog without blocking user searches. Which component best handles this high write throughput while ensuring eventual consistency?
easy
A. Use a distributed log system like Kafka to buffer and asynchronously process updates
B. Use an in-memory cache like Redis as the primary data store for product updates
C. Use a NoSQL key-value store with synchronous writes for every update
D. Use a relational database with immediate consistency for all writes

Solution

  1. Step 1: Identify write throughput handling

    Relational DBs (A) and synchronous NoSQL writes (C) block on writes, limiting throughput. Redis (D) lacks durability guarantees for primary storage.
  2. Step 2: Recognize Kafka's role

    Kafka buffers high write volume asynchronously, decoupling writes from reads and enabling eventual consistency.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Kafka buffers writes asynchronously -> high throughput, eventual consistency [check]
Hint: Buffer writes asynchronously with Kafka for high throughput [check]
Common Mistakes:
3. A messaging system must handle 1 million writes per second and fan-out delivery to thousands of consumers without blocking producers. Which component is primarily responsible for decoupling producers from consumers to achieve this?
easy
A. Use a relational database with write-ahead logging to buffer messages
B. Use direct synchronous HTTP calls from producers to consumers
C. Use a centralized in-memory cache like Redis to store messages temporarily
D. Use a distributed message broker with partitioned logs and asynchronous consumers

Solution

  1. Step 1: Identify the decoupling mechanism

    Relational DBs with WAL (Use a relational database with write-ahead logging to buffer messages) are durable but cannot handle 1M writes/sec with fan-out efficiently; Redis (Use a centralized in-memory cache like Redis to store messages temporarily) is fast but lacks durability and persistence guarantees at this scale; direct HTTP calls (Use direct synchronous HTTP calls from producers to consumers) block producers and do not decouple.
  2. Step 2: Recognize distributed brokers' role

    Distributed message brokers with partitioned logs (Use a distributed message broker with partitioned logs and asynchronous consumers) allow asynchronous writes and reads, decoupling producers and consumers, enabling high throughput and scalable fan-out.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Partitioned broker logs decouple producers and consumers for high throughput [check]
Hint: Partitioned brokers decouple producers and consumers [check]
Common Mistakes:
4. If the Feature Store's update stream (e.g., Kafka) fails, what exactly breaks in the search ranking system?
medium
A. Model Serving continues scoring with stale features, causing degraded ranking quality
B. Feature Store blocks all read requests until the update stream recovers, causing high latency
C. A/B testing traffic routing fails, causing all users to see the control model only
D. The system loses all feature data permanently, causing model serving to crash

Solution

  1. Step 1: Trace failure impact of update stream loss

    The update stream failure stops feature updates but does not block reads or cause permanent data loss.
  2. Step 2: Identify component relying on update stream

    A/B testing routing depends on fresh feature updates to decide traffic splits; without updates, routing falls back to control model only.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Update stream failure -> A/B routing fallback to control model [check]
Hint: Update stream failure -> A/B routing falls back, not feature reads [check]
Common Mistakes:
5. At 10x scale, which component in the webhook delivery system is most likely to fail first and why?
hard
A. The database, due to increased write contention on event status updates
B. The load balancer, as it cannot efficiently route millions of concurrent webhook requests
C. The Delivery Workers, because they maintain stateful connections per subscriber limiting horizontal scaling
D. The retry queue, since it cannot handle the exponential growth of failed events

Solution

  1. Step 1: Identify stateful bottleneck at scale

    Delivery Workers hold stateful connections (e.g., HTTP keep-alive) per subscriber, limiting resharding and horizontal scaling.
  2. Step 2: Compare other components

    Databases can be sharded; load balancers scale horizontally; retry queues are usually distributed and scalable.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Stateful Delivery Workers -> scaling bottleneck [check]
Hint: Stateful workers block scaling first [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard